A:Ambitious number
http://202.120.80.191/problem.php?problemid=1868
这道题想法其实不难，可是开始的方向就错了，做的时候有种投机取巧的感觉，虽然知道是错的，但是我也要去试，呵呵，一头撞到底
首先打质数表，然后找到小与N的每个质数的最大系数，开始一头就扎进了用俩数的乘积去除公约数的方法做，这显然不对啊，要去模的阿，哎
下面是垃圾代码：
#include<iostream>
#include<math.h>
#define MaxN 500005
#define M 987654321
int notP[MaxN];
using namespace std;
void init()
{
int i,j;
memset(notP,0,sizeof(notP));
notP[1]=1;
for(i=2;i<sqrt((double)MaxN);i++)
if(notP[i]==0){
for(j=2;j*i<MaxN;j++)
notP[j*i]=1;
}
}
int solve(int n)
{
int i,ans=1,t;
for(i=2;i<=n;i++){
if(notP[i])continue;
t=n;
while(t>=i){
ans=(((__int64)ans)*i)%M;
t/=i;
}
}
return ans;
}
int main()
{
int N,ans;
init();
while(scanf("%d",&N)!=EOF){
ans=solve(N);
printf("%d\n",ans);
}
return 0;
}
B题等会儿再说，他是我的痛
http://202.120.80.191/problem.php?problemid=1869
C题Cards
http://202.120.80.191/problem.php?problemid=1870
这道题开始用o(n2)的做的，并没有想到该怎么做，后面超时，才是是这用o(n)的做，开始想的一直都不清楚
主要是在每次当前移除情况下又出现了present_numR>present_numB的情况，就要更新切牌点，并且也要同时更新切牌而移除的红牌或黑牌
一下是我的没人品的代码：（我这么说一点都不过分）
#include<iostream>
#include<cstring>
#define MaxN 100005
char deck[MaxN];
int main()
{
int numR,numS,i,k,remR,remS,len;
while(scanf("%s",deck)!=EOF){
remR=remS=numR=numS=k=0;
len=(int)strlen(deck);
for(i=0;i<len;i++){
if(deck[i]=='R')numR++;
else numS++;
if(numR-remR>numS-remS){
remR=numR;
remS=numS;
k=i+1;}
}
printf("%d\n",k);
}
return 0;
}
D题 DICE
这是按照解题报告写得，是一道动态规划题，动态规划还是要坚持继续做，每次都靠蒙着想到是不行的
要用眼睛直接发现它。
这道题首先用一compute函数把每次用size[]的筛子，掷numSize下的所得每种可能结果的概率保存在p中
void compute(double p[],int size[],int numSize)
在主函数中我们分别把A,B的结果的计算出来
而后对B进行处理，这里同样是利用动态规划的思想，将pB[i]中，点数〈i的概率保存在tmp[i]中
然后结合tmp[],pA[]，计算结果输出。
容易出错点：
在compute函数中for(j=MaxS-1;j>=0;j--){
p[j]=0;//这里要先初始化为0，在下一格6个size中，每种size的概率都要加
for(t=0;t<6;t++)
if(j-size(t)>0)//这里也是容易出错的，runtime error的起源
p[j]+=p[j-size[t]]/6.0;//这里也是，6.0，而不是6，要养成习惯
#include<iostream>
#define MaxS 23*100//每次最多丢到100
int sizeA[6],sizeB[6];
double pA[MaxS],pB[MaxS];
int numDiceA,numDiceB;
void compute(double p[],int size[],int numSize)
{
int i,j,t;
for(i=1;i<numSize;i++)
for(j=MaxS-1;j>=0;j--){
p[j]=0;//important
for(t=0;t<6;t++)
if(j-size[t]>0)
p[j]+=p[j-size[t]]/6.0;
}
}
int main()
{
int i;
double ans,tmp[MaxS];
while(scanf("%d%d",&numDiceA,&numDiceB)!=EOF){
ans=0.0;
memset(tmp,0,sizeof(tmp));
memset(pA,0,sizeof(pA));
memset(pB,0,sizeof(pB));
for(i=0;i<6;i++){
scanf("%d",&sizeA[i]);
pA[sizeA[i]]+=1/6.0;}
for(i=0;i<6;i++){
scanf("%d",&sizeB[i]);
pB[sizeB[i]]+=1/6.0;}
compute(pA,sizeA,numDiceA);
compute(pB,sizeB,numDiceB);
for(i=1;i<MaxS;i++)
tmp[i]=tmp[i-1]+pB[i-1];
for(i=1;i<MaxS;i++)
ans+=pA[i]*tmp[i];
printf("%.9lf\n",ans);
}
return 0;
}
未完待续..............
posted on 2008-04-07 21:47
zoyi 阅读(174)
评论(0) 编辑 收藏 引用 所属分类:
acm 、
比赛总结