《杭电acm题解》由会员分享，可在线阅读，更多相关《杭电acm题解（339页珍藏版）》请在金锄头文库上搜索。
1、杭电 ACM 题解1000 求余运算给出 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
2、互质，则 0 到 M-1 的 S倍对 M 取余一定能遍历 0 到 M-1）只需证明的是，该余数中两两之间互不相等；假设 k*S 和 b*S 对 M 取余相等（k 和 b0,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 和 b0,M)，并且 k 和 b 不等矛盾；因此得证；另外，偶然看到一个很牛叉的辗转相除法；int gcd(int a,int b)while(b) b=a=b=a%=b;return a;此代码，很好很强大；把涉及位运算的交换的程序加入，便到得这段简洁高
3、效的代码；注：A 和 B；经过 A=B=A=B，结果就得到 A 和 B 的交换/ 1000#include int main()int a,b,i,;scanf(“%d“, for(i=1;iint main()int a, b, max, min, tmp;while (scanf(“%d%d“,min = a#include#include#includeusing namespace std;int main()int n,i,x;/freopen(“a.txt“,“r“,stdin);while(scanf(“%d“,mapm;for(i=0;i:iterator it;for(it=
4、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“,v0);for(i=1;i #include int main() char a15;char b100;char c15;int j;for(;)gets(a);if(!strcmp(a,“START“)gets(b);gets(c);if(!(strcmp(c,“END“)for(j=0;bj!=0;j+)if(bj=F void JC() double t;t=(nu
5、m*log(num) - num + 0.5*log(2*num*pi)/log(10); /经典的转换技巧result = (int)t+1;printf(“%dn“,result);int main() int i,n;scanf(“%d“,for( i=0 ; i#include using namespace std;int Digit(int n)int digit=0;while(true)digit=0;while(n)digit+=n%10; /这步很经典，常用数字的判断及各位数的存取。如 123 ，可以得出， /百位为 1，十位为 2；等等！n/=10;if(digits)s
6、um=0; for(i=0; is)for(i=0; iusing namespace std;int main()int m,n,lenm,lenn;while(cinmn)int start=m,end=n,i,max=0;if(startend)int temp=start;start=end;end=temp; / /iffor(i=start;ivoid main()int n,i,m,j,k,t,l,a10000;scanf(“%d“,for(i=0;iat+1)l=at;at=at+1;at+1=l;for(j=0;j#includeint main()int n,k,t,p,s
7、um,j,i;int s40000;while(scanf(“%d“,t=0;p=0;sum=0;s0=1;for(j=1;j9)si=sum%10;p=sum/10;if(t=i)t+;st=0; /看不明白elsesi=sum;for(i=t;i=0;i-)printf(“%d“,si);printf(“n“);return 0;、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、GridlandTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submi
8、ssion(s): 981 Accepted Submission(s): 474Problem DescriptionFor years, computer scientists have been trying to find efficient solutions to different computing problems. For some of them efficient algorithms are already available, these are the “easy” problems like sorting, evaluating a polynomial or
9、 finding the shortest path in a graph. For the “hard” ones only exponential-time algorithms are known. The traveling-salesman problem belongs to this latter group. Given a set of N towns and roads between these towns, the problem is to compute the shortest path allowing a salesman to visit each of t
10、he towns once and only once and return to the starting point.The president of Gridland has hired you to design a program that calculates the length of the shortest traveling-salesman tour for the towns in the country. In Gridland, there is one town at each of the points of a rectangular grid. Roads
11、run from every town in the directions North, Northwest, West, Southwest, South, Southeast, East, and Northeast, provided that there is a neighbouring town in that direction. The distance between neighbouring towns in directions NorthSouth or EastWest is 1 unit. The length of the roads is measured by
12、 the Euclidean distance. For example, Figure 7 shows 2 3-Gridland, i.e., a rectangular grid of dimensions 2 by 3. In 2 3-Gridland, the shortest tour has length 6. InputThe first line contains the number of scenarios.For each scenario, the grid dimensions m and n will be given as two integer numbers
13、in a single line, separated by a single blank, satisfying 1 #includeusing namespace std;int main()int i,j,cas,mid,k;double res,root=sqrt(2.0);cincas;for(k=1; kij;mid = i*j;if(mid%2=0) res = double(mid);else res = double(mid) - 1 + root; printf(“Scenario #%d:n%.2lfnn“,k,res);return 0;/1 095A+B for In
14、put-Output Practice (VII)Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 11057 Accepted Submission(s): 7506Problem DescriptionYour task is to Calculate a + b.InputThe input will consist of a series of pairs of integers a and b, separated by a spac
15、e, one pair of integers per line.OutputFor each pair of input integers a and b you should output the sum of a and b, and followed by a blank line.Sample Input1 510 20Sample Output630 includeusing namespace std;int main() int a,b; while(cinab) coutn; while(n-) sum=0; cinm; for(i=0;iai; for(i=0;i#includeusing namespace std;int main()int a, b;int s1010 = 1, 0,1, 1,4, 2, 4,
