Two planets named Haha and Xixi in the universe and they were created with the universe beginning.
There is 73 days in Xixi a year and 137 days in Haha a year.
Now you know the days N after Big Bang, you need to answer whether it is the first day in a year about the two planets.
There are several test cases(about 5 huge test cases).
For each test, we have a line with an only integer N(0≤N), the length of N is up to 10000000.
For the i-th test case, output Case #i: , then output “YES” or “NO” for the answer.
10001 0 333
Case #1: YES Case #2: YES Case #3: NO
UESTC
题意：判断n是不是同时整除73和137，由于n比较的大，所以字符串输入，同余一下。
#include <bits/stdc++.h> using namespace std; const int Max = 11000000; char s[Max]; int main() { int num1,num2; int z =1; while(~scanf("%s",s)) { int len = strlen(s); num1 = 0; num2 = 0; for(int i = 0;i<len;i++) { num1 = num1*10+s[i]-'0'; num2 = num2*10+s[i]-'0'; num1%=73; num2%=137; } if(num1 == num2 && num1 == 0) printf("Case #%d: YES\n",z++); else printf("Case #%d: NO\n",z++); } return 0; }Zhu and 772002 are both good at math. One day, Zhu wants to test the ability of 772002, so he asks 772002 to solve a math problem.
But 772002 has a appointment with his girl friend. So 772002 gives this problem to you.
There are n numbers a1,a2,…,an. The value of the prime factors of each number does not exceed 2000, you can choose at least one number and multiply them, then you can get a number b.
How many different ways of choices can make b is a perfect square number. The answer maybe too large, so you should output the answer modulo by 1000000007.
First line is a positive integer T , represents there are T test cases.
For each test case:
First line includes a number n(1≤n≤300)，next line there are n numbers a1,a2,…,an,(1≤ ai ≤ 1018 ).
For the i-th test case , first output Case #i: in a single line.
Then output the answer of i-th test case modulo by 1000000007.
2 3 3 3 4 3 2 2 2
Case #1: 3 Case #2: 3
UESTC
题意：给你n个数，求能组成平方数的方案数。一个数是平方数，说明在素数分解中每一个素因子的个数都是偶数。对于一个数来数
a1=pb111×pb122⋯×px1nn ,那么我们选择一些数进行组合，那么组合之后的数就可以表示为 s=px1b11+x2b21+⋯xmbm11×px1b12+x2b22+⋯xmbm22⋯×px1b1n+x2b2n+⋯xmbmn1 其中x只有0或者1，表示对应的数选或者不选。那么由于平方数的素因子的个数都是偶数，那么 x1b11+x2b21+x3b31+⋯xmbm1=0(mod2)x1b12+x2b22+x3b32+⋯xmbm2=0(mod2)x1b13+x2b23+x3b33+⋯xmbm3=0(mod2)⋮x1b1n+x2b2n+x3b3n+⋯xmbmn=0(mod2) 那么就转化为模2下的高斯消元，最后的答案就是 2自由遍元数−1 #include <bits/stdc++.h> using namespace std; typedef long long LL; const int Max = 2000; const int Mod = 1000000007; int vis[Max+100]; int pr[Max]; LL b[300]; int arr[400][400]; void Get() { pr[0] = 0; memset(vis,false,sizeof(vis)); for(int i = 2;i<=Max;i++) { if(!vis[i]) { pr[++pr[0]] = i; for(int j = i+i;j<=Max;j+=i) { vis[j] = true; } } } } void build(int n) { for(int i = 0;i<n;i++) { for(int j = 1;j<=pr[0];j++) { if(b[i]%pr[j] == 0) { int num = 0; while(b[i]%pr[j] ==0) { b[i]/=pr[j]; num++; } arr[j-1][i] = num%2; } } } } int Gauss(int n,int m) { int num = 0; int row = 0,col = 0; for(;row<=n&&col<m;row++,col++) { int r = row; for(int i = row+1;i<=n;i++) if(arr[i][col]) r= i; if(arr[r][col] ==0) { num++; row --; continue; } for(int i = col;i<=m;i++) swap(arr[row][i],arr[r][i]); for(int i = row+1;i<=n;i++) { if(arr[i][col] ==0 )continue; for(int j = col;j<=m;j++) { arr[i][j] ^=arr[row][j]; } } } for(int i = row;i<m;i++) if(arr[i][col]) return -1; return num; } LL Pow(LL n,LL m) { LL ans = 1; while(m) { if(m%2) { ans = (ans*n)%Mod; } n = (n*n)%Mod; m>>=1; } return ans; } int main() { int T,z =1; int n; Get(); scanf("%d",&T); while(T--) { scanf("%d",&n); memset(arr,0,sizeof(arr)); for(int i = 0;i<n;i++) scanf("%I64d",&b[i]); build(n); int ans = Gauss(pr[0],n); printf("Case #%d:\n",z++); if(ans == -1) { printf("0\n"); } else printf("%I64d\n",((Pow(2,ans)-1)%Mod+Mod)%Mod); } return 0; }Bi Luo is a magic boy, he also has a migic tree, the tree has N nodes , in each node , there is a treasure, it’s value is V[i], and for each edge, there is a cost C[i], which means every time you pass the edge i , you need to pay C[i].
You may attention that every V[i] can be taken only once, but for some C[i] , you may cost severial times.
Now, Bi Luo define ans[i] as the most value can Bi Luo gets if Bi Luo starts at node i.
Bi Luo is also an excited boy, now he wants to know every ans[i], can you help him?
First line is a positive integer T(T≤ 104 ) , represents there are T test cases.
Four each test：
The first line contain an integer N(N≤ 105 ).
The next line contains N integers V[i], which means the treasure’s value of node i(1≤V[i]≤ 104 ).
For the next N−1 lines, each contains three integers u,v,c , which means node u and node v are connected by an edge, it’s cost is c(1≤c≤ 104 ).
You can assume that the sum of N will not exceed 106.
For the i-th test case , first output Case #i: in a single line , then output N lines , for the i-th line , output ans[i] in a single line.
1 5 4 1 7 7 7 1 2 6 1 3 1 2 4 8 3 5 2
Case #1: 15 10 14 9 15
UESTC
树形dp，dp[u][0]表示回来的最大的价值，dp[u][1]表示不会来的最大的价值，首先第一遍dfs求出以某个点为根节点，向下回来和不回来的最大价值，第二遍dfs求出任意方向的最大的价值。更新和维护是比较难的部分
#include <bits/stdc++.h> using namespace std; const int Max = 1e5+100; struct node { int v,next,cost; }E[Max*2]; int h[Max],top; int w[Max]; int dp[Max][2],to[Max]; int ans[Max]; void add(int u,int v,int cost) { E[top].v = v; E[top].cost = cost; E[top].next = h[u]; h[u] = top++; } void dfs1(int u,int fa) { dp[u][0] = dp[u][1] = w[u]; to[u] = 0; for(int i = h[u];~i;i = E[i].next) { int v = E[i].v; if(v == fa)continue; dfs1(v,u); int ans1 =max(0,dp[v][0]-2*E[i].cost);//当经过这个节点回来的价值（小于0肯定不会走） int temp = max(0,dp[u][0]+dp[v][1]-E[i].cost);//在这个节点不回来的最大的价值 dp[u][1]+=ans1;//不以这个节点为终点的价值 if(dp[u][1]<temp) { dp[u][1] = temp; to[u] = v;//记录在哪个节点不回来 } dp[u][0]+=ans1; } } void dfs2(int u,int fa,int M0,int M1) { ans[u] = max(dp[u][0] + M1,dp[u][1] + M0);//更新答案 int W0= dp[u][0]; int W1 = dp[u][1]; int id = to[u]; W1 += M0; if(W1<W0+M1) { W1 = W0+M1; id = fa; } W0 += M0; for(int i = h[u]; ~i;i = E[i].next) { int v = E[i].v; if(v == fa)continue; if(v == id) { int ans0 = M0+w[u]; int ans1 = M1+w[u]; for(int j = h[u];~j; j = E[j].next) { int tv = E[j].v; if(tv == fa || tv == id) continue; int temp = max(0,dp[tv][0]-2*E[j].cost); ans1 = max(ans0+max(0,dp[tv][1]-E[j].cost),ans1+temp); ans0+=temp; } ans0 = max(0,ans0-2*E[i].cost); ans1 = max(0,ans1-E[i].cost); dfs2(v,u,ans0,ans1); } else { int temp = max(0,dp[v][0] - 2*E[i].cost); int ans0 = max(0,W0-temp-2*E[i].cost); int ans1 = max(0,W1-temp-E[i].cost); dfs2(v,u,ans0,ans1); } } } int main() { int T,n,u,v,W,z = 1; scanf("%d",&T); while(T--) { scanf("%d",&n); memset(h,-1,sizeof(h));top =0; for(int i = 1;i<=n;i++) { scanf("%d",&w[i]); } for(int i =1 ;i<=n-1;i++) { scanf("%d %d %d",&u,&v,&W); add(u,v,W); add(v,u,W); } dfs1(1,-1); dfs2(1,-1,0,0); printf("Case #%d:\n",z++); for(int i = 1;i<=n;i++) printf("%d\n",ans[i]); } return 0; }Chisa Yukizome works as a teacher in the school. She prepares many gifts, which consist of n kinds with a[i] quantities of each kind, for her students and wants to hold a class meeting. Because of the busy work, she gives her gifts to the monitor, Chiaki Nanami. Due to the strange design of the school, the students’ desks are in a row. Chiaki Nanami wants to arrange gifts like this:
Each table will be prepared for a mysterious gift and an ordinary gift.
In order to reflect the Chisa Yukizome’s generosity, the kinds of the ordinary gift on the adjacent table must be different.
There are no limits for the mysterious gift.
The gift must be placed continuously.
She wants to know how many students can get gifts in accordance with her idea at most (Suppose the number of students are infinite). As the most important people of her, you are easy to solve it, aren’t you?
The first line of input contains an integer T(T≤10) indicating the number of test cases.
Each case contains one integer n. The next line contains n (1≤n≤10) numbers: a1,a2,...,an,(1≤ai≤100000) .
For each test case, output one line containing “Case #x: y” (without quotes) , where x is the test case number (starting from 1) and y is the answer of Chiaki Nanami’s question.
1 2 3 2
Case #1: 2
UESTC
2016中国大学生程序设计竞赛 - 网络选拔赛
题意：礼物分为两种,普通礼物要求相邻的不能相同，神秘礼物任意摆放。每个桌子必须放一个神秘礼物和普通礼物，问最多摆放多少张桌子。那就先摆放普通礼物，每次选取礼物中数量最大的和次大的进行交叉摆放 ，依次进行选择摆放，然后让剩下的作为神秘礼物
#include <bits/stdc++.h> using namespace std; int main() { int T,n,z = 1; scanf("%d",&T); while(T--) { int sum = 0,data; scanf("%d",&n); priority_queue<int>Q; for(int i = 0; i<n; i++) { scanf("%d",&data); sum+=data; Q.push(data); } int ans = 0; while(Q.size()>1) { int a = Q.top(); Q.pop(); int b = Q.top(); Q.pop(); ans+=2*b; a-=b; if(a) Q.push(a); } int a ; if(Q.empty()) a= 0 ; else { a = Q.top(); Q.pop(); } if(a <=ans) ans+=a; else ans+=ans; printf("Case #%d: %d\n",z++,ans/2); } return 0; }后来队友说是水过去了orz。。。。。,正确的代码
#include<bits/stdc++.h> using namespace std; const int maxn = 15; int a[maxn],cas; int main(){ int t; scanf("%d",&t); while(t--){ int n,mx=0,sum=0; scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); mx=max(a[i],mx); sum+=a[i]; } int ans=min(sum/2,(sum-mx)*2+1); printf("Case #%d: %d\n",++cas,ans); } }Given n points which are in three-dimensional space(without repetition).
Please find out how many distinct Special Tetrahedron among them. A tetrahedron is called Special Tetrahedron if it has two following characters.
At least four edges have the same length.
If it has exactly four edges of the same length, the other two edges are not adjacent.
Intput contains multiple test cases.
The first line is an integer T,1≤T≤20, the number of test cases.
Each case begins with an integer n(n≤200), indicating the number of the points.
The next n lines contains three integers xi,yi,zi,(−2000≤xi,yi,zi≤2000) , representing the coordinates of the ith point.
For each test case,output a line which contains”Case #x: y”,x represents the xth test(starting from one),y is the number of Special Tetrahedron.
2 4 0 0 0 0 1 1 1 0 1 1 1 0 9 0 0 0 0 0 2 1 1 1 -1 -1 1 1 -1 1 -1 1 1 1 1 0 1 0 1 0 1 1
Case #1: 1 Case #2: 6
UESTC
题意：给你空间的中的n个点，问有多少个符合条件的四面体。 n4 的暴力加剪枝,其中的正四面体会被计算六次，其余的会被计算2次，分别统计
#include <bits/stdc++.h> using namespace std; const int Max = 250; struct node { int x,y,z; node(){} node(int _x,int _y,int _z):x(_x),y(_y),z(_z){} node operator + (const node &a)const { return node(x+a.x,y+a.y,x+a.z); } node operator - (const node &a)const { return node(x-a.x,y-a.y,z-a.z); } int operator * (const node &a)const { return x*a.x+y*a.y+z*a.z; } node operator * (const int &a)const { return node(x*a,y*a,z*a); } node operator /(const int &a)const { return node(x/a,y/a,z/a); } node operator ^ (const node &a)const { return node(y*a.z-a.y*z,z*a.x-x*a.z,x*a.y-y*a.x); } }p[Max],s[Max]; int dis(node a,node b) { return (a-b)*(a-b); } node pvec(node a,node b,node c) { return (a-b)^(b-c); } int dots_onplane(node a,node b,node c,node d) { return pvec(a,b,c)*(d-a); } int main() { int T,n,z = 1; scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i = 0;i<n;i++) { scanf("%d %d %d",&p[i].x,&p[i].y,&p[i].z); } int ans1 = 0,ans2 = 0; for(int i = 0;i<n;i++) { for(int j = i+1;j<n;j++) { int cnt = 0; for(int k = 0;k<n;k++) { if(k ==i || k == j)continue; if(dis(p[k],p[i]) == dis(p[k],p[j]))s[cnt++] = p[k]; } if(cnt<=1) continue; for(int k1 = 0;k1<cnt;k1++) { for(int k2 = k1+1;k2<cnt;k2++) { if(dis(s[k1],p[i])!=dis(s[k2],p[i])) continue; if(!dots_onplane(p[i],p[j],s[k1],s[k2])) continue; if(dis(p[i],p[j]) == dis(p[i],s[k1]) && dis(p[i],p[j]) == dis(s[k1],s[k2])) ans1++; else ans2++; } } } } printf("Case #%d: %d\n",z++,ans1/6+ans2/2); } return 0; }Lweb has a string S.
Oneday, he decided to transform this string to a new sequence.
You need help him determine this transformation to get a sequence which has the longest LIS(Strictly Increasing).
You need transform every letter in this string to a new number.
A is the set of letters of S, B is the set of natural numbers.
Every injection f:A→B can be treat as an legal transformation.
For example, a String “aabc”, A={a,b,c}, and you can transform it to “1 1 2 3”, and the LIS of the new sequence is 3.
Now help Lweb, find the longest LIS which you can obtain from S.
LIS: Longest Increasing Subsequence. (https://en.wikipedia.org/wiki/Longest_increasing_subsequence)
The first line of the input contains the only integer T,(1≤T≤20).
Then T lines follow, the i-th line contains a string S only containing the lowercase letters, the length of S will not exceed 105 .
For each test case, output a single line “Case #x: y”, where x is the case number, starting from 1. And y is the answer.
2 aabcc acdeaa
Case #1: 3 Case #2: 4
UESTC
题意：题目真正的意思是统计字符串中有多少不同的字符orz。
#include <bits/stdc++.h> using namespace std; const int Max = 1e5+100; bool vis[30]; char s[Max]; int main() { int T; scanf("%d",&T); for(int z = 1;z<=T;z++) { scanf("%s",s); int len = strlen(s); memset(vis,false,sizeof(vis)); int ans = 0; for(int i = 0 ;i<len;i++) { if(vis[s[i]-'a']) continue; else { ans++; vis[s[i]-'a'] = true; } } printf("Case #%d: %d\n",z,ans); } return 0; }