巧妙的方法.doc

1281 凸多边形对角线对角线问题；统计问题Description给出一个带n个顶点的凸多边形，我们保证它不存在3条对角线相交于同一个点。请统计每两条对角线的交点数的和。n=6时，图中的15个圆点即为所求交点Input输入只含一个整数n（3n100）。 Output输出交点数。Sample Input6Sample Output15Hint一个多边形是凸多边形当且仅当每个内角都小于180。 代码：#include int main() int n; while(scanf(%d,&n)!=EOF) int allb; allb=n*(n-1)*(n-2)*(n-3)/24; printf(%dn,allb); return 0; 1341 巧用异或 Who will be punishedDescriptionThis time,suddenly,teacher Li wants to find out who have missed interesting DP lesson to have fun.The students who are found out will get strictly punishment.Because,teacher Li wants all the students master the DP algorithm.However,Li doesnt want to waste the class time to call over the names of students.So he let the students to write down their names in one paper.To his satisfaction,this time, only one student has not come.He can get the name who has not come to class,but,it is troublesome,and,teacher always have many things to think about,so,teacher Li wants you, who is in the ACM team, to pick out the name.InputThere are several test cases.The first line of each case have one positive integer N.N is the number of the students,and N will not greater than 500,000.Then,following N lines,each line contains one name of students who have attended class.The N-1 lines are presented after N lines.These N-1 lines indicates the names of students who have come to class this time,one name in one line.The length of students name is not greater than 30.Process to the end of file.OutputFor each test case, first print a line saying Scenario #k, where k is the number of the test case.Then output the name of the student who have not come to class.One case per line.Print a blank line after each test case, even after the last one.Sample Input3ABCBCSample OutputScenario #1A代码A：#include #include #include using namespace std;int main() int t; int k=1; while(cint) string str,sum; cinsum; for(int j = 1;j str; for(int i = 0;i str.size();i+) sumi = sumistri; printf(Scenario #%dn,k); coutsumendlendl; k+; return 0; 代码B：#include #include #include using namespace std;int main() int t; int k=1; int sum32; while(cint) string str; for(int i = 0;i 32;i +) sumi = 0; for(int j = 1;j str; for(int i = 0;i str.size();i+) sumi = sumi+stri; for(int j = 1;j str; for(int i = 0;i str.size();i+) sumi = sumi-stri; printf(Scenario #%dn,k); for(int i = 0; sumi!=0;i+) printf(%c,sumi); printf(nn); k+; return 0; 1353 素因数问题 LCM与数对Description请你求出以n为最小公倍数的不同正整数对(u, v)的个数。注：对于u v，数对(u, v)与(v, u)被视为不同的。Input本题有多组测试数据，输入的第一行是一个整数T代表着测试数据的数量，接下来是T组测试数据。对于每组测试数据：第1行 包含一个整数n (1 n 1012)。Output对于每组测试数据：第1行 输出以n为最小公倍数的不同正整数对(u, v)的个数。Sample Input3234Sample Output335代码：#include #include #include using namespace std;long long Prime6000000;int N = 12000000; void fliter() bool isPrimeN; for(int i = 2;i N;i+ ) isPrimei = true; for(int i = 2;i N;i+) if(isPrimei) for(int j = 2;i*j N;j+ ) isPrimei*j = false; int k = 0; for(int i = 2;i N & k1 & Primek1) ans = ans*3; return ans; int main() fliter(); int T; cinT; while(T-) long long n; scanf(%lld,&n); printf(%lldn,solve(n); return 0;Ps：思想： N 为U,V的最小公倍数；设N的素因子是P1,P2，P3，P4.,.Ps；即N = P1a1*P2a2*P3a3.Psas;则V，U,一定包含这些素因子 即V = P1ai1*P2ai2*P3ai3.Psais (ai1属于0,a1，ai2属于0,a2.)U = P1aj1*P2aj2*P3aj3.Psajs (aj1属于0,a1，aj2属于0,a2.)则 的情况取决于 ai1，ai2，。aj1,aj2.的取值情况对于ai1，aj1一定有一个要等于a1，如果都不等于a1，则最小公倍数一定不会有P1a1这一项因子。假设ai1 =a1，则aj1 可取 0，1,2,3,4，。a1-1，即有a1种取法。如果aj1=a1，同理ai1有a1种取法。还有两者都是a1的情况，所以是（1+2*a1）种情况；则总共情况是（1+2*a1）*（1 + 2*a2）。（1+2*as）1362 组合的递推公式XianGe画方方DescriptionXianGe受到委屈时，总要念叨着“画个圈圈诅咒你”。这回，他要“画个方方祝福你”。XianGe得到了一张包含r行c列的表格，他要按照如下规矩画出k个矩形：1.他每次都沿着表格线在刚刚画出的矩形内部画一个新矩形（画第一个矩形时，他将整个表格的边框视为刚刚画出的矩形）。2.每次画出的新矩形是严格在刚刚画出的矩形内部的（即不含公共点或者公共边）。现在给出表格的大小，他要画出k个矩形，他想知道有多少种不同的画法。Input本题有多组测试数据，输入的第一行是一个整数T代表着测试数据的数量，接下来是T组测试数据。对于每组测试数据：第1行 包含三个以空格分隔的整数r，c和k(1 r, c, k1000)。Output对于每组测试数据：第1行 输出XianGe有多少种不同的画法。由于这个数字可能非常大，所以请将答案对1000000007取模后输出。Sample Input23 3 14 4 1Sample Output19因为宪哥每次都严格在上次的矩形里画新矩形 所以可以再r-1行里选出2*k个行，在c-1列里选出2*k个列，用来作为各个矩形的边。这样选出来的边只能确定一种方案。因为矩形不会有交叉嘛 所以最靠上和最靠下的两行为最外层矩形的长，最靠左和最靠右的两列为最外层矩形的宽。剩下由外向内递推 你举个栗子画一下就知道了这个不知道的应该是组合公式的递推因为数据很大，相乘会出现超界而WA 所以用这种递推方式进行计算这样两个数之和保证在INT型内 不会超界代码：#include #include #define INF 1000000007using namespace std;long long n10011001;void initiate() for(int i = 0;i = 1000;i +) ni0 = 1; nii = 1; for(int i = 1;i = 1000;i +) for(int j = 1;j T; while(T-) int r,c,k; scanf(%d%d%d,&r,&c,&k); if(2*k r-1|2*kc-1) printf(0n); else printf(%lldn,(nr-12*k*nc-12*k)%INF); 1365 巧妙的规律Unlucky Number IIIDescriptionSome positive integers representations only consist of the unlucky digits 4 and 7. We call them Unlucky Numbers. For example, numbers 74, 774, 7 are unlucky while 2, 12, 352 are not.Letf (x)be the minimum unlucky number which is not less thanx.What is the value off (a)+f (a+1)+ f (a+2) + . + f (b-2)+f (b-1)+f (b)?InputThere are multiple test cases. The first line of input is an integerTindicating the number of test cases. ThenTtest cases follow.For each test case:Line 1. This line contains two integersaandb(1ab109).OutputFor each test case:Line 1. Output the value off (a)+f (a+1)+ f (a+2) + . + f (b-2)+f (b-1)+f (b).Sample Input23 64 4Sample Output224HintIn the first sample:f (3)+f (4)+f (5)+f (6)=4+4+7+7=22In the second sample:f (4)=4代码：#include #include #include using namespace std;long long a1050 = 0, 0, 4, 7;int main() for (int i = 2; i = 512; i+) ai * 2 = ai * 10 + 4;ai * 2 + 1 = ai * 10 + 7;int f;scanf(%d, &f);while (f-) long long l, r;scanf(%lld%lld, &l, &r);long long ans = 0;for (int i = 2; i r) break;if (ai = l) ans += (min(ai, r) - l + 1) * ai;l = ai + 1;printf(%lldn, ans);1364 构造法Unlucky Number IIDescriptionSome positive integers representations only consist of the unlucky digits 4 and 7. We call them Unlucky Numbers. For example, numbers 74, 774, 7 are unlucky while 2, 12, 352 are not.Letf (x)be the sum of the digits ofx.What is the minimum unlucky numberxwhich makesf (x)equal ton?InputThere are multiple test cases. The first line of input is an integerTindicating the number of test cases. ThenTtest cases follow.For each test case:Line 1. This line contains an integern(1n106) indicating the sum.OutputFor each test case:Line 1. Output the minimum unlucky numberxrequired, or output -1 if suchxdoes not exist.Sample Input21213Sample Output444-1代码：#include #include #include using namespace std;int main() int f;scanf(%d, &f);while (f-) int n;scanf(%d, &n);int k = 0;while (n = 0) if (n % 7 = 0) break;k+;n -= 4;if (n = 0) for (int i = 0; i k; i+) putchar(4);for (int i = 0; i A=SS=B=SS=C=S代码：#include #include #define INF 1000000007using namespace std;long long a44;long long b44;long long temp44;void initiate() for(int i = 0;i 4;i+) for(int j = 0;j 4;j +) if(i = j) aij = 0;bij = 1;else aij = 1;bij = 0; void matipule(int n) while(n) if(n&1=1) for(int i = 0;i 4;i +) for(int j = 0;j 4;j +) long long ans = 0; for(int s = 0;s 4;s +) ans = (bis *asj%INF+ans)%INF; tempij = ans; for(int i = 0;i 4;i +) for(int j = 0;j 4;j +) bij = tempij; for(int i = 0;i 4;i +) for(int j = 0;j 4;j +)long long ans = 0;for(int s = 0;s 4;s +) ans = (ais * asj%INF+ans)%INF;tempij = ans; for(int