浙江大学acm答案完整版.docx
《浙江大学acm答案完整版.docx》由会员分享，可在线阅读，更多相关《浙江大学acm答案完整版.docx（99页珍藏版）》请在冰点文库上搜索。
浙江大学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到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
#include
intmain（）
{
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;
}
//////////////////
HDUACM1014UniformGenerator三月22nd,
这个题目是判断给定的步长和mod，判断所产生的随机数已经覆盖0~mod-1中所有的数，如果是，则说明所选的步长和mod是一个Goodchoice，否则为badchoice.
需要懂得的基本内容为线性同余产生随机数，链接：
http:
//zh.wikipedia.org/zh-cn/%E7%B7%9A%E6%80%A7%E5%90%8C%E9%A4%98%E6%96%B9%E6%B3%95
ProblemDescription
willbegeneratedeveryMODiterationsofthefunction.Notethatbythenatureofthefunctiontogeneratethesameseed（x+1）everytimeseed（x）occursmeansthatifafunctionwillgenerateallthenumbersbetween0andMOD-1,itwillgeneratepseudo-randomnumbersuniformlywitheveryMODiterations.
IfSTEP=15andMOD=20,thefunctiongeneratestheseries0,15,10,5（oranyotherrepeatingseriesiftheinitialseedisotherthan0）.ThisisapoorselectionofSTEPandMODbecausenoinitialseedwillgenerateallofthenumbersfrom0andMOD-1.
YourprogramwilldetermineifchoicesofSTEPandMODwillgenerateauniformdistributionofpseudo-randomnumbers.
Input
EachlineofinputwillcontainapairofintegersforSTEPandMODinthatorder（1<=STEP,MOD<=100000）.
Output
Foreachlineofinput,yourprogramshouldprinttheSTEPvalueright-justifiedincolumns1through10,theMODvalueright-justifiedincolumns11through20andeither"GoodChoice"or"BadChoice"left-justifiedstartingincolumn25.The"GoodChoice"messageshouldbeprintedwhentheselectionofSTEPandMODwillgenerateallthenumbersbetweenandincluding0andMOD-1whenMODnumbersaregenerated.Otherwise,yourprogramshouldprintthemessage"BadChoice".Aftereachoutputtestset,yourprogramshouldprintexactlyoneblankline.
SampleInput
35
1520
6392399999
SampleOutput
35GoodChoice
1520BadChoice
6392399999GoodChoice
线性同余方法（LCG）是个产生伪随机数的方法。
它是根据递归公式：
其中A,B,M是产生器设定的常数。
LCG的周期最大为M，但大部分情况都会少于M。
要令LCG达到最大周期，应符合以下条件：
B,M互质；
M的所有质因子的积能整除A?
1；
若M是4的倍数，A?
1也是；
A,B,N0都比M小；
A,B是正整数。
由以上可知，本题的求解方案。
代码如下：
#include
intmain（）
{
inta,b,max,min,tmp;
while（scanf（"%d%d",&a,&b）!
=EOF）
{
max=a>b?
a:
b;
min=aa:
b;
while（min）
{
tmp=max%min;
max=min;
min=tmp;
}
if（max==1）printf（"%10d%10dGoodChoice\n\n",a,b）;
elseprintf（"%10d%10dBadChoice\n\n",a,b）;
}
return0;
/
//////////////////
ProblemDescription
"OK,youarenottoobad,em...Butyoucanneverpassthenexttest."feng5166says.
"IwilltellyouanoddnumberN,andthenNintegers.Therewillbeaspecialintegeramongthem,youhavetotellmewhichintegeristhespecialoneafterItellyoualltheintegers."feng5166says.
"Butwhatisthecharacteristicofthespecialinteger?
"Ignatiusasks.
"Theintegerwillappearatleast（N+1）/2times.Ifyoucan'tfindtherightinteger,IwillkillthePrincess,andyouwillbemydinner,too.Hahahaha....."feng5166says.
CanyoufindthespecialintegerforIgnatius?
Input
Theinputcontainsseveraltestcases.Eachtestcasecontainstwolines.ThefirstlineconsistsofanoddintegerN（1<=N<=999999）whichindicatethenumberoftheintegersfeng5166willtellourhero.ThesecondlinecontainstheNintegers.Theinputisterminatedbytheendoffile.
Output
Foreachtestcase,youhavetooutputonlyonelinewhichcontainsthespecialnumberyouhavefound.
SampleInput
5
13233
11
11111555555
7
1111111
SampleOutput
3
5
1
#include
#include
#include
#include
usingnamespacestd;
intmain（）{
intn,i,x;
//freopen（"a.txt","r",stdin）;
while（scanf（"%d",&n）!
=EOF）{
vectorv;
mapm;
for（i=0;iscanf（"%d",&x）;
m[x]++;
}
n=（n+1）/2;
map:
:
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}
printf（"\n"）;
}
return0;
}
////////////////1048;
用100°的AC热情，挑战39°的高温——加油!
TheHardestProblemEver
TimeLimit:
2000/1000MS（Java/Others）MemoryLimit:
65536/32768K（Java/Others）
TotalSubmission（s）:
5571AcceptedSubmission（s）:
2540
ProblemDescription
JuliusCaesarlivedinatimeofdangerandintrigue.ThehardestsituationCaesareverfacedwaskeepinghimselfalive.Inorderforhimtosurvive,hedecidedtocreateoneofthefirstciphers.Thiscipherwassoincrediblysound,thatnoonecouldfigureitoutwithoutknowinghowitworked.
YouareasubcaptainofCaesar'sarmy.ItisyourjobtodecipherthemessagessentbyCaesarandprovidetoyourgeneral.Thecodeissimple.Foreachletterinaplaintextmessage,youshiftitfiveplacestotherighttocreatethesecuremessage（i.e.,iftheletteris'A',theciphertextwouldbe'F'）.SinceyouarecreatingplaintextoutofCaesar'smessages,youwilldotheopposite:
Ciphertext
ABCDEFGHIJKLMNOPQRSTUVWXYZ
Plaintext
VWXYZABCDEFGHIJKLMNOPQRSTU
Onlylettersareshiftedinthiscipher.Anynon-alphabeticalcharactershouldremainthesame,andallalphabeticalcharacterswillbeuppercase.
Input
Inputtothisproblemwillconsistofa（non-empty）seriesofupto100datasets.Eachdatasetwillbeformattedaccordingtothefollowingdescription,andtherewillbenoblanklinesseparatingdatasets.Allcharacterswillbeuppercase.
Asingledatasethas3components:
Startline-Asingleline,"START"
Ciphermessage-Asinglelinecontainingfromonetotwohundredcharacters,inclusive,comprisingasinglemessagefromCaesar
Endline-Asingleline,"END"
Followingthefinaldatasetwillbeasingleline,"ENDOFINPUT".
Output
Foreachdataset,therewillbeexactlyonelineofoutput.ThisistheoriginalmessagebyCaesar.
SampleInput
START
NSBFW,JAJSYXTKNRUTWYFSHJFWJYMJWJXZQYTKYWNANFQHFZXJX
END
START
NBTZQIWFYMJWGJKNWXYNSFQNYYQJNGJWNFSANQQFLJYMFSXJHTSINSWTRJ
END
START
IFSLJWPSTBXKZQQBJQQYMFYHFJXFWNXRTWJIFSLJWTZXYMFSMJ
END
ENDOFINPUT
SampleOutput
INWAR,EVENTSOFIMPORTANCEARETHERESULTOFTRIVIALCAUSES
IWOULDRATHERBEFIRSTINALITTLEIBERIANVILLAGETHANSECONDINROME
DANGERKNOWSFULLWELLTHATCAESARISMOREDANGEROUSTHANHE
#include
#include
intmain（）
{
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;
}
////////////
1018BigNumber
TimeLimit:
20000/10000MS（Java/Others）MemoryLimit:
65536/32768K（Java/Others）
TotalSubmission（s）:
8372AcceptedSubmission（s）:
3701
ProblemDescription
Inmanyapplicationsverylargeintegersnumbersarerequired.Someoftheseapplicationsareusingkeysforsecuretransmissionofdata,encryption,etc.Inthisproblemyouaregivenanumber,youhavetodeterminethenumberofdigitsinthefactorialofthenumber.
Input
Inputconsistsofseverallinesofintegernumbers.Thefirstlinecontainsanintegern,whichisthenumberofcasestobetested,followedbynlines,oneinteger1≤n≤107oneachline.
Output
Theoutputcontainsthenumberofdigitsinthefactorialoftheintegersappearingintheinput.
SampleInput
2
10
20
SampleOutput
7
19
#include
#include
#definepi3.14159265
intnum,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{
//求阶乘共用多少位，经典常用
scanf（"%d",&num）;
JC（）;
}
return0;
}
////////
1013
ProblemDescription
Thedigitalrootofapositiveintegerisfoundbysummingthedigitsoftheinteger.Iftheresultingvalueisasingledigitthenthatdigitisthedigitalroot.Iftheresultingvaluecontainstwoormoredigits,thosedigitsaresummedandtheprocessisrepeated.Thisiscontinuedaslongasnecessarytoobtainasingledigit.
Forexample,considerthepositiveinteger24.Addingthe2andthe4yieldsavalueof6.Since6isasingledigit,6isthedigitalrootof24.Nowconsiderthepositiveinteger39.Addingthe3andthe9yields12.Since12isnotasingledigit,theprocessmustberepeated.Addingthe1andthe2yeilds3,asingledigitandalsothedigitalrootof39.
Input
Theinputfilewillcontainalistofpositiveintegers,oneperline.Theendoftheinputwillbeindicatedbyanintegervalueof
升级会员 