A:Ambitious number
http://202.120.80.191/problem.php?problemid=1868
這道題想法其實(shí)不難，可是開始的方向就錯(cuò)了，做的時(shí)候有種投機(jī)取巧的感覺，雖然知道是錯(cuò)的，但是我也要去試，呵呵，一頭撞到底
首先打質(zhì)數(shù)表，然后找到小與N的每個(gè)質(zhì)數(shù)的最大系數(shù)，開始一頭就扎進(jìn)了用倆數(shù)的乘積去除公約數(shù)的方法做，這顯然不對(duì)啊，要去模的阿，哎
下面是垃圾代碼：
#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題等會(huì)兒再說(shuō)，他是我的痛
http://202.120.80.191/problem.php?problemid=1869
C題Cards
http://202.120.80.191/problem.php?problemid=1870
這道題開始用o(n2)的做的，并沒有想到該怎么做，后面超時(shí)，才是是這用o(n)的做，開始想的一直都不清楚
主要是在每次當(dāng)前移除情況下又出現(xiàn)了present_numR>present_numB的情況，就要更新切牌點(diǎn)，并且也要同時(shí)更新切牌而移除的紅牌或黑牌
一下是我的沒人品的代碼：（我這么說(shuō)一點(diǎn)都不過(guò)分）
#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
這是按照解題報(bào)告寫得，是一道動(dòng)態(tài)規(guī)劃題，動(dòng)態(tài)規(guī)劃還是要堅(jiān)持繼續(xù)做，每次都靠蒙著想到是不行的
要用眼睛直接發(fā)現(xiàn)它。
這道題首先用一compute函數(shù)把每次用size[]的篩子，擲numSize下的所得每種可能結(jié)果的概率保存在p中
void compute(double p[],int size[],int numSize)
在主函數(shù)中我們分別把A,B的結(jié)果的計(jì)算出來(lái)
而后對(duì)B進(jìn)行處理，這里同樣是利用動(dòng)態(tài)規(guī)劃的思想，將pB[i]中，點(diǎn)數(shù)〈i的概率保存在tmp[i]中
然后結(jié)合tmp[],pA[]，計(jì)算結(jié)果輸出。
容易出錯(cuò)點(diǎn)：
在compute函數(shù)中for(j=MaxS-1;j>=0;j--){
p[j]=0;//這里要先初始化為0，在下一格6個(gè)size中，每種size的概率都要加
for(t=0;t<6;t++)
if(j-size(t)>0)//這里也是容易出錯(cuò)的，runtime error的起源
p[j]+=p[j-size[t]]/6.0;//這里也是，6.0，而不是6，要養(yǎng)成習(xí)慣
#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;
}
未完待續(xù)..............
posted on 2008-04-07 21:47
zoyi 閱讀(208)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
acm 、
比賽總結(jié)