首页 浙江大学acm答案完整版

浙江大学acm答案完整版

浙江大学acm答案完整版求余运算给出S和M，求0*S%M，1*S%M，2*S%M......(M-1)*S%M能否组成一个集合包含0.1.。。。M-1；（这个是原题意改造而来）；算法：判断两个数是否互质；or暴力解决其实暴力完全可以解决这个问题（⊙﹏⊙b），只是其中用数学方法更加高效，巧妙；证明如果S和M互质则满足题意：另G=gcd(S,M);则S=A*G，M=B*G；另X=K*S%M=K*S-T*M（T为整数，满足X属于0到M-1）；X=K*A*G-T*B*G;因此取余后的整数一定是G的倍数，G只能取1才能满足条件；充分性的证明：（即当...

求余运算给出S和M，求0*S%M，1*S%M，2*S%M......(M-1)*S%M能否组成一个集合包含0.1.。。。M-1；（这个是原题意改造而来）；算法：判断两个数是否互质；or暴力解决其实暴力完全可以解决这个问题（⊙﹏⊙b），只是其中用数学方法更加高效，巧妙；证明如果S和M互质则满足题意：另G=gcd(S,M);则S=A*G，M=B*G；另X=K*S%M=K*S-T*M（T为整数，满足X属于0到M-1）；X=K*A*G-T*B*G;因此取余后的整数一定是G的倍数，G只能取1才能满足条件；充分性的证明：（即当S与M互质，则0到M-1的S倍对M取余一定能遍历0到M-1）只需证明的是，该余数中两两之间互不相等；假设k*S和b*S对M取余相等（k和b∈[0,M)，并且k和b不等);则k*S=q1*M+r=q2*M+r=b*S<==>（k-b)*S=M*(q1-q2);S与M互质，由上式子可得M|（k-b），与k和b∈[0,M)，并且k和b不等矛盾；因此得证；另外，偶然看到一个很牛叉的辗转相除法；intgcd(inta,intb){while(b)b^=a^=b^=a%=b;returna;}此代码，很好很强大；把涉及位运算的交换的程序加入，便到得这段简洁高效的代码；注：A和B；经过A^=B^=A^=B，结果就得到A和B的交换////////////////////////////1000#includeintmain(){inta,b,i,;scanf("%d",&a);for(i=1;i<=a;i++){intsum=0;sum=sum+i;printf("%d\n",sum);}return0;};1001;#include"stdio.h"intmain(){unsigned_int64n;unsigned_int64temp;while(scanf("%I64u",&n)!=EOF)//是i非L{temp=(1+n)*n/2;printf("%I64u\n\n",temp);}return0;}//////////////////这个题目是判断给定的步长和mod，判断所产生的随机数已经覆盖0~mod-1中所有的数，如果是，则说明所选的步长和mod是一个Goodchoice，否则为badchoice.ProblemDescriptionComputersimulationsoftenrequirerandomnumbers.Onewaytogeneratepseudo-randomnumbersisviaafunctionoftheformseed(x+1)=[seed(x)+STEP]%MODwhere'%'isthemodulusoperator.Suchafunctionwillgeneratepseudo-randomnumbers(seed)between0andMOD-1.Oneproblemwithfunctionsofthisformisthattheywillalwaysgeneratethesamepatternoverandover.Inordertominimizethiseffect,selectingtheSTEPandMODvaluescarefullycanresultinauniformdistributionofallvaluesbetween(andincluding)0andMOD-1.Forexample,ifSTEP=3andMOD=5,thefunctionwillgeneratetheseriesofpseudo-randomnumbers0,3,1,4,2inarepeatingcycle.Inthisexample,allofthenumbersbetweenandincluding0andMOD-1willbegeneratedeveryMODiterationsofthefunction.Notethatbythenatureofthefunctiontogeneratethesameseed(x+1)everytimeseed(x)occursmeansthatifafunctionwillgenerateallthenumbersbetween0andMOD-1,itwillgeneratepseudo-randomnumbersuniformlywitheveryMODiterations.IfSTEP=15andMOD=20,thefunctiongeneratestheseries0,15,10,5(oranyotherrepeatingseriesiftheinitialseedisotherthan0).ThisisapoorselectionofSTEPandMODbecausenoinitialseedwillgenerateallofthenumbersfrom0andMOD-1.YourprogramwilldetermineifchoicesofSTEPandMODwillgenerateauniformdistributionofpseudo-randomnumbers.InputEachlineofinputwillcontainapairofintegersforSTEPandMODinthatorder(1<=STEP,MOD<=100000).OutputForeachlineofinput,yourprogramshouldprinttheSTEPvalueright-justifiedincolumns1through10,theMODvalueright-justifiedincolumns11through20andeither"GoodChoice"or"BadChoice"left-justifiedstartingincolumn25.The"GoodChoice"messageshouldbeprintedwhentheselectionofSTEPandMODwillgenerateallthenumbersbetweenandincluding0andMOD-1whenMODnumbersaregenerated.Otherwise,yourprogramshouldprintthemessage"BadChoice".Aftereachoutputtestset,yourprogramshouldprintexactlyoneblankline.SampleInput3515206392399999SampleOutput35GoodChoice1520BadChoice6392399999GoodChoice线性同余方法（LCG）是个产生伪随机数的方法。它是根据递归公式：其中A,B,M是产生器设定的常数。LCG的周期最大为M，但大部分情况都会少于M。要令LCG达到最大周期，应符合以下条件：B,M互质；M的所有质因子的积能整除A?1；若M是4的倍数，A?1也是；A,B,N0都比M小；A,B是正整数。由以上可知，本题的求解方案。代码如下：#includeintmain(){inta,b,max,min,tmp;while(scanf("%d%d",&a,&b)!=EOF){max=a>b?a:b;min=a#include#include#includeusingnamespacestd;intmain(){intn,i,x;//freopen("a.txt","r",stdin);while(scanf("%d",&n)!=EOF){vectorv;mapm;for(i=0;i::iteratorit;for(it=m.begin();it!=m.end();it++){if(it->second>=n)v.push_back(it->first);}sort(v.begin(),v.end());if(v.size()>=1){printf("%d",v[0]);for(i=1;i#includeintmain(){chara[15];charb[100];charc[15];intj;for(;;){gets(a);if(!strcmp(a,"START")){gets(b);gets(c);if(!(strcmp(c,"END"))){for(j=0;b[j]!='\0';j++){if(b[j]>='F'&&b[j]<='Z')b[j]=b[j]-5;elseif(b[j]>='A'&&b[j]<='E')b[j]=b[j]+21;}}printf("%s\n",b);}elseif(!strcmp(a,"ENDOFINPUT"))break;}return0;}////////////1018BigNumberTimeLimit:20000/10000MS(Java/Others)MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):8372AcceptedSubmission(s):3701ProblemDescriptionInmanyapplicationsverylargeintegersnumbersarerequired.Someoftheseapplicationsareusingkeysforsecuretransmissionofdata,encryption,etc.Inthisproblemyouaregivenanumber,youhavetodeterminethenumberofdigitsinthefactorialofthenumber.InputInputconsistsofseverallinesofintegernumbers.Thefirstlinecontainsanintegern,whichisthenumberofcasestobetested,followedbynlines,oneinteger1≤n≤107oneachline.OutputTheoutputcontainsthenumberofdigitsinthefactorialoftheintegersappearingintheinput.SampleInput21020SampleOutput719#include#include#definepi3.14159265intnum,result;voidJC(){doublet;t=(num*log(num)-num+0.5*log(2*num*pi))/log(10);//经典的转换技巧result=(int)t+1;printf("%d\n",result);}intmain(){inti,n;scanf("%d",&n);for(i=0;i#includeusingnamespacestd;intDigit(intn){intdigit=0;while(true){digit=0;while(n){digit+=n%10;//这步很经典，常用数字的判断及各位数的存取。如123，可以得出，//百位为1，十位为2；等等！n/=10;}if(digit<10)returndigit;n=digit;}}intmain(){intdigit,sum,i;strings;while(cin>>s){sum=0;for(i=0;i>s){for(i=0;iusingnamespacestd;intmain(){intm,n,lenm,lenn;while(cin>>m>>n){intstart=m,end=n,i,max=0;if(start>end){inttemp=start;start=end;end=temp;}//iffor(i=start;i<=end;i++){intcount=1,temp=i;while(temp!=1){if(temp%2!=0)temp=3*temp+1;elsetemp/=2;count++;}//whileif(maxvoidmain(){intn,i,m,j,k,t,l,a[10000];scanf("%d",&n);for(i=0;ia[t+1]){l=a[t];a[t]=a[t+1];a[t+1]=l;}}for(j=0;j#includeintmain(){intn,k,t,p,sum,j,i;ints[40000];while(scanf("%d",&n)!=EOF){k=0;t=0;p=0;sum=0;s[0]=1;for(j=1;j<=n;j++){for(i=0;i<=t;i++){sum=s[i]*j+p;p=0;if(sum>9){s[i]=sum%10;p=sum/10;if(t==i){t++;s[t]=0;}//看不明白}elses[i]=sum;}}for(i=t;i>=0;i--)printf("%d",s[i]);printf("\n");}return0;}、、、、、、、、、、、、、、、、、GridlandTimeLimit:2000/1000MS(Java/Others)MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):981AcceptedSubmission(s):474ProblemDescriptionForyears,computerscientistshavebeentryingtofindefficientsolutionstodifferentcomputingproblems.Forsomeofthemefficientalgorithmsarealreadyavailable,thesearethe“easy”problemslikesorting,evaluatingapolynomialorfindingtheshortestpathinagraph.Forthe“hard”onesonlyexponential-timealgorithmsareknown.Thetraveling-salesmanproblembelongstothislattergroup.GivenasetofNtownsandroadsbetweenthesetowns,theproblemistocomputetheshortestpathallowingasalesmantovisiteachofthetownsonceandonlyonceandreturntothestartingpoint.ThepresidentofGridlandhashiredyoutodesignaprogramthatcalculatesthelengthoftheshortesttraveling-salesmantourforthetownsinthecountry.InGridland,thereisonetownateachofthepointsofarectangulargrid.RoadsrunfromeverytowninthedirectionsNorth,Northwest,West,Southwest,South,Southeast,East,andNortheast,providedthatthereisaneighbouringtowninthatdirection.ThedistancebetweenneighbouringtownsindirectionsNorth–SouthorEast–Westis1unit.ThelengthoftheroadsismeasuredbytheEuclideandistance.Forexample,Figure7shows2×3-Gridland,i.e.,arectangulargridofdimensions2by3.In2×3-Gridland,theshortesttourhaslength6.InputThefirstlinecontainsthenumberofscenarios.Foreachscenario,thegriddimensionsmandnwillbegivenastwointegernumbersinasingleline,separatedbyasingleblank,satisfying1#includeusingnamespacestd;intmain(){inti,j,cas,mid,k;doubleres,root=sqrt(2.0);cin>>cas;for(k=1;k<=cas;k++){cin>>i>>j;mid=i*j;if(mid%2==0)res=double(mid);elseres=double(mid)-1+root;printf("Scenario#%d:\n%.2lf\n\n",k,res);}return0;}/////////////////1095A+BforInput-OutputPractice(VII)TimeLimit:2000/1000MS(Java/Others)MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):11057AcceptedSubmission(s):7506ProblemDescriptionYourtaskistoCalculatea+b.InputTheinputwillconsistofaseriesofpairsofintegersaandb,separatedbyaspace,onepairofintegersperline.OutputForeachpairofinputintegersaandbyoushouldoutputthesumofaandb,andfollowedbyablankline.SampleInput151020SampleOutput630includeusingnamespacestd;intmain(){inta,b;while(cin>>a>>b){cout<>n;while(n--){sum=0;cin>>m;for(i=0;i>a[i];for(i=0;i#includeusingnamespacestd;intmain(){inta,b;ints[10][10]={{1,0},{1,1},{4,2,4,8,6},{4,3,9,7,1},{2,4,6},//经典这步{1,5},{1,6},{4,7,9,3,1},{4,8,4,2,6},{2,9,1}};while(2==scanf("%d%d",&a,&b)){a%=10;b%=s[a][0];if(!b)b=s[a][0];printf("%d\n",s[a][b]);}return0;}、、、、、、、、、1097#includeusingnamespacestd;intmain(){inta,b;while(cin>>a>>b){longtemp,s,count=0;intibuf[10]={0};intflag[10]={0};temp=a%10;ibuf[++count]=temp;flag[temp]=1;s=temp;while(1){s*=temp;s%=10;if(flag[s]==0){flag[s]=1;ibuf[++count]=s;}elsebreak;}ibuf[0]=ibuf[count];temp=b%count;cout<#includeusingnamespacestd;intmain(){charch[1006];inta[1006],ind;while(scanf("%s",ch+1)!=EOF){ind=1;inti=1,len=strlen(ch+1);while(i<=len){while(i<=len&&ch[i]=='5')i++;inttemp=0;while(i<=len&&ch[i]!='5'){temp=10*temp+ch[i]-'0';i++;}if(ch[i-1]!='5')a[ind++]=temp;}sort(a+1,a+ind);printf("%d",a[1]);for(inti=2;i#includeusingnamespacestd;longfactor(inta){longi,s=1;for(i=1;i<=a;i++){s*=i;}returns;}intmain(){longdoublee=1;intn,i;cout<<"n"<<""<<"e"<#include#defineINF0x7FFFFFFF#defineMAX101doublec[MAX][MAX];doubledis[MAX],visit[MAX];typedefstruct{doublex;doubley;}Point;doubledistance(Pointa,Pointb){doublelen;len=sqrt(1.0*(a.x-b.x)*(a.x-b.x)+1.0*(a.y-b.y)*(a.y-b.y));returnlen;}intmain(){Pointp[105];inti,j,k,n;doublesum,l;while(scanf("%d",&n)!=EOF){for(i=1;i<=n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);for(i=0;i<=n;i++)for(j=0;j<=n;j++){if(i==j)c[i][j]=0;//对a[][]进行

                    本文档为【浙江大学acm答案完整版】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

浙江大学acm答案完整版

你可能还喜欢