整个比赛都做的特别不顺，开始写第一题看到大数问题就用了java，最后提交内存超限，然后又在纠结是不是自己申请多了变量的原因。纠结了很久最后想去网站看一下用java写的ac的代码的内存，结果发现没有人用java ac了，然后开始用c++的大数模板去解，今天看了题解，发现有更简单的解法。
【1001】
【题意】 两个星球从宇宙大爆炸开始就产生了
Xixi星球一年有73天,Haha星球一年有137天
问宇宙大爆炸开始第N天是否是两个星球一年当中的第一天
【类型】 同余定理 【分析】 认真读题,我们可以发现如果第N天是两个星球一年当中的第一天
那么N必定能被73整除,同时能被137整除
就这样,题目发生了转变,然而此题还没有就此解决
因为N这个数长度可达10000000,显然这是个极大的数
那我们就需要采取同余定理求解
首先,我们知道模运算是不影响乘法和加法的
所以一个数,比如23,对5取模,23≡2*10+3(mod 5)
故,这个巨大的数N可以拆解成一位一位取模,这样,此题就可以得到圆满解决
【时间复杂度&&优化】 O(strlen(n))
题目链接→HDU 5832 A water probl
/*Sherlock and Watson and Adler*/ #pragma comment(linker, "/STACK:1024000000,1024000000") #include<stdio.h> #include<string.h> #include<stdlib.h> #include<queue> #include<stack> #include<math.h> #include<vector> #include<map> #include<set> #include<cmath> #include<complex> #include<string> #include<algorithm> #include<iostream> #define eps 1e-9 #define LL long long #define bitnum(a) __builtin_popcount(a) using namespace std; const int N = 10000005; const int M = 10005; const int inf = 1000000007; const int mod = 1000000007; char s[N]; int main() { int ans1,ans2,p=1,i,k; while(~scanf("%s",s)) { ans1=ans2=0; k=strlen(s); for(i=0;i<k;i++) { ans1=(ans1*10+s[i]-'0')%73; ans2=(ans2*10+s[i]-'0')%137; } if(!ans1&&!ans2) printf("Case #%d: YES\n",p++); else printf("Case #%d: NO\n",p++); } return 0; }【1002】
数学一直很差，看到题目真的不知道应该用什么数学知识，看了题解说用高斯消元，我只能说好像学过，但是一直也没怎么用，高数也学的不怎样，看了题解还是一脸懵逼，我只想说马上就要省赛啦，希望能够多学习几个知识点。
解题思路:
【题意】 有n个数,每个数的质因数不会超过2000 问从n个数中至少选取1个数,它们的乘积是完全平方数的情况有多少种,结果对1000000007取模
【类型】 高斯消元 【分析】 首先,我们知道的是,完全平方数的各种质因子必定出现偶数次
不然不可能被开方
例如36=2*2*3*3
质因子2,3均出现两次
所以呢,此题已经可以转化为类似开关问题的高斯消元了
这里,,表示第i个数取或不取
,表示质因子出现偶数次
,表示(第j个数分解质因数后,2000以内第i个质数出现多少次,奇数次值为1,偶数次值为2)
剩下的就是套一下高斯消元的模板,求解出自由变元的个数ans,那此题的结果就是,这个快速幂求解一下就可以了
如果还是不明白的话,我们来举例说明
就比如样例3,3,4
方程变元x前的系数k为我们打素数表2,3,5,……,1999中第k个质数出现奇数次还是偶数次
那该样例可得方程组为
第一条方程是质数2的贡献,因为3是不包含质因子2的,故贡献为0,而4虽包含质因子2,但出现了偶数次,故贡献同样为0
第二条方程,两个3都贡献了1,而4不包含质因子3,所以无贡献
显然,方程组只有一条方程,但有3个未知数,所以自由变元有2个,而自由变元的取值为{0,1}
故方程组的解有2^2=4种,除去全为0的一种(因为题目指明至少取一个数),剩3种(1,1,0),(0,0,1),(1,1,1)
【时间复杂度&&优化】 O(n^3)
题目链接→HDU 5833 Zhu and 772002
/*Sherlock and Watson and Adler*/ #pragma comment(linker, "/STACK:1024000000,1024000000") #include<stdio.h> #include<string.h> #include<stdlib.h> #include<queue> #include<stack> #include<math.h> #include<vector> #include<map> #include<set> #include<cmath> #include<complex> #include<string> #include<algorithm> #include<iostream> #define eps 1e-9 #define LL long long #define bitnum(a) __builtin_popcount(a) using namespace std; const int N = 305; const int M = 2001; const int inf = 1000000007; const int mod = 1000000007; int prime[M],k; bool v[M]; //有equ个方程，var个变元。增广矩阵行数为equ,列数为var+1,分别为0到var int equ,var; int a[N][N]; //增广矩阵 int x[N]; //解集 int free_x[N];//用来存储自由变元（多解枚举自由变元可以使用） int free_num;//自由变元的个数 void get_prime() { k=0; for(int i=2;i<M;i++) if(!v[i]) { prime[k++]=i; for(int j=i;j<M;j+=i) v[j]=true; } } __int64 Quick_Mod(int a,int b)//快速幂 { __int64 res = 1,term = a % mod; while(b) { if(b & 1) res = (res * term) % mod; term = (term * term) % mod; b >>= 1; } return res; } //返回值为-1表示无解，为0是唯一解，否则返回自由变元个数 int Gauss() { int max_r,col,k; free_num = 0; for(k = 0, col = 0 ; k < equ && col < var ; k++, col++) { max_r = k; for(int i = k+1;i < equ;i++) { if(abs(a[i][col]) > abs(a[max_r][col])) max_r = i; } if(a[max_r][col] == 0) { k--; free_x[free_num++] = col;//这个是自由变元 continue; } if(max_r != k) { for(int j = col; j < var+1; j++) swap(a[k][j],a[max_r][j]); } for(int i = k+1;i < equ;i++) { if(a[i][col] != 0) { for(int j = col;j < var+1;j++) a[i][j] ^= a[k][j]; } } } for(int i = k;i < equ;i++) if(a[i][col] != 0) return -1;//无解 if(k < var) return var-k;//自由变元个数 //唯一解，回代 for(int i = var-1; i >= 0;i--) { x[i] = a[i][var]; for(int j = i+1;j < var;j++) x[i] ^= (a[i][j] && x[j]); } return 0; } int main() { get_prime(); int t,i,j,n,p=1,c; __int64 ans,s; scanf("%d",&t); while(t--) { ans=0; memset(a,0,sizeof(a)); scanf("%d",&n); equ=k;var=n; for(i=0;i<n;i++) { scanf("%I64d",&s); for(j=0;j<k;j++) { c=0; while(s%prime[j]==0) { s/=prime[j]; c++; } if(c&1) a[j][i]=1; } } int r,c; ans=Gauss(); printf("Case #%d:\n%I64d\n",p++,Quick_Mod(2,ans)-1); } return 0; } 【1003】 看到这道题，第一个想法就是深搜，然后默默去写了深搜代码，发现根本无法运行，二维数组太大，然后把二维数组变小去运行，发现没有出来结果，说明自己的搜索写的很有问题。最后也没能ac。 这题没出是我的锅。。有个地方偷个懒少维护个东西结果被卡T了 f[i][0/1]表示这个点为根的情况不返回/返回的最大收益 然后先以1为根做一遍 然后遍历这棵树。手动转换根。每次转换只影响自己和父节点两个 HDU5834 #pragma comment(linker, "/STACK:1024000000,1024000000") #include<map> #include<cmath> #include<queue> #include<vector> #include<cstdio> #include<string> #include<cstring> #include<iostream> #include<algorithm> using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } struct line { int s,t,x; int next; }a[400001]; int head[200001]; int edge; inline void add(int s,int t,int x) { a[edge].next=head[s]; head[s]=edge; a[edge].s=s; a[edge].t=t; a[edge].x=x; } int fa[200001],val[200001]; int sx[200001],ans[200001]; int f[200001][2];//0不返回1返回 int fx[200001][2]; inline void dfs(int d) { int i,sum=0; for(i=head[d];i!=0;i=a[i].next) { int t=a[i].t; if(fa[d]!=t) { fa[t]=d; dfs(t); if(2*a[i].x<f[t][1]) sum+=f[t][1]-2*a[i].x; } } sx[d]=sum; int maxx=sum,maxi=0,maxt=0; for(i=head[d];i!=0;i=a[i].next) { int t=a[i].t; if(fa[d]!=t) { if(2*a[i].x<f[t][1]) { if(sum-f[t][1]+f[t][0]+a[i].x>maxx) { maxt=maxx; maxx=sum-f[t][1]+f[t][0]+a[i].x; maxi=t; } else if(sum-f[t][1]+f[t][0]+a[i].x>maxt) maxt=sum-f[t][1]+f[t][0]+a[i].x; } else { if(sum+f[t][0]-a[i].x>maxx) { maxt=maxx; maxx=sum+f[t][0]-a[i].x; maxi=t; } else if(sum+f[t][0]-a[i].x>maxt) maxt=sum+f[t][0]-a[i].x; } } } f[d][0]=maxx+val[d]; f[d][1]=sum+val[d]; fx[d][0]=maxi; fx[d][1]=maxt+val[d]; } inline void trdp(int d,int x) { int t0=f[fa[d]][0],t1=f[fa[d]][1],ts=sx[fa[d]]; int tt0=f[d][0],tt1=f[d][1],tts=sx[d]; if(2*x<f[d][1]) sx[fa[d]]=sx[fa[d]]+x*2-f[d][1]; int i,sum=sx[fa[d]]; if(fx[fa[d]][0]==d) { f[fa[d]][0]=fx[fa[d]][1]; if(f[d][1]>x*2) f[fa[d]][0]=f[fa[d]][0]-f[d][1]+x*2; } else { if(f[d][1]>x*2) f[fa[d]][0]=f[fa[d]][0]-f[d][1]+x*2; } f[fa[d]][1]=sum+val[fa[d]]; if(2*x<f[fa[d]][1]) sx[d]=sx[d]-x*2+f[fa[d]][1]; sum=sx[d]; int maxx=sum,maxi=0,maxt=0; for(i=head[d];i!=0;i=a[i].next) { int t=a[i].t; if(2*a[i].x<f[t][1]) { int tt=sum-f[t][1]+f[t][0]+a[i].x; if(tt>maxx) { maxt=maxx; maxx=tt; maxi=t; } else if(tt>maxt) maxt=tt; } else { int tt=sum+f[t][0]-a[i].x; if(tt>maxx) { maxt=maxx; maxx=tt; maxi=t; } else if(tt>maxt) maxt=tt; } } f[d][0]=maxx+val[d]; f[d][1]=sum+val[d]; fx[d][0]=maxi; fx[d][1]=maxt+val[d]; ans[d]=f[d][0]; int dx=fa[d]; fa[dx]=d; fa[d]=0; for(i=head[d];i!=0;i=a[i].next) { int t=a[i].t; if(t!=dx) trdp(t,a[i].x); } f[d][0]=tt0; f[d][1]=tt1; f[dx][0]=t0; f[dx][1]=t1; fa[d]=dx; fa[dx]=0; sx[dx]=ts; sx[d]=tts; } int main() { // freopen("1003.in","r",stdin); // freopen("1003.out","w",stdout); int T,k=0; T=read(); while(T>0) { T--; k++; edge=0; int n,i,ss,tt,xx; n=read(); for(i=1;i<=n;i++) val[i]=read(); for(i=1;i<=n-1;i++) { ss=read();tt=read();xx=read(); edge++; add(ss,tt,xx); edge++; add(tt,ss,xx); } dfs(1); ans[1]=f[1][0]; // printf("%d\n",f[1][0]); for(i=head[1];i!=0;i=a[i].next) trdp(a[i].t,a[i].x); printf("Case #%d:\n",k); for(i=1;i<=n;i++) printf("%d\n",ans[i]); for(i=1;i<=n;i++) { fa[i]=0; head[i]=0; } } return 0; }
【1004】
HDU5835
看着题目中分发礼物的规则写的是连续分发，就理解错成不能空着座位做，一大推判断条件，现在看到大家的题解傻眼啦，竟然是可以随便坐的，真的是水的不能再水啦
不知道他们的解法是不是应为数据太水了的原因。
这是认为可以随便做的解法，虽然能够ac但是我觉得应该是不对的。
#include<bits/stdc++.h> using namespace std; #define N 12000 #define INF 0x3f3f3f3f int a[N]; int main() { int T,n,i,sum,k=1; scanf("%d", &T); while(T--) { sum=0; scanf("%d", &n); for(i=0;i<n;i++) { scanf("%d", &a[i]); sum+=a[i]; } printf("Case #%d: ",k++); if(sum==1) printf("1\n"); else printf("%d\n", sum/2); } return 0; }解题思路:
【题意】 n种礼物,每种有a[i]个,所有的礼物可以作为普通礼物,也可以作为神秘礼物发放给孩子
现在从第一个人开始,每人可以收到一个普通礼物和一个神秘礼物,相邻两个人不能收到相同的普通礼物,神秘礼物没限制,发完为止
问最多有多少个人可以拿到两件礼物
【类型】 贪心 【分析】 暂时先不考虑普通礼物的限制
那么最多有sum/2个人可以拿到两件礼物(sum为总的礼物件数,即a[1]+a[2]+……+a[n])
那么在考虑普通礼物限制的情况下,我们肯定先要发放普通礼物,直到不能发或超过sum/2为止,这时多出来的礼物就作为神秘礼物补齐发到过普通礼物的孩子
那么说明情况是不能发呢?因为相邻两人要获得不同的普通礼物
所以我们可以借助优先队列,每次将队首的两种礼物取出来发放
假设队首两种礼物的数量为a,b(a>b)
那么可以有2*b个孩子拿到普通礼物,没发完的第一种礼物还剩a-b件,丢进优先队列重新来过
最终得到答案ans,与sum/2取个小值就行了
【时间复杂度&&优化】 O(n)
题目链接→HDU 5835 Danganronpa
/*Sherlock and Watson and Adler*/ #pragma comment(linker, "/STACK:1024000000,1024000000") #include<stdio.h> #include<string.h> #include<stdlib.h> #include<queue> #include<stack> #include<math.h> #include<vector> #include<map> #include<set> #include<cmath> #include<complex> #include<string> #include<algorithm> #include<iostream> #define eps 1e-9 #define LL long long #define bitnum(a) __builtin_popcount(a) using namespace std; const int N = 15; const int M = 26; const int inf = 1000000007; const int mod = 1000000007; int s[N]; priority_queue<int> q; int main() { int t,i,n,p=1,sum,k,a,b,ans; scanf("%d",&t); while(t--) { ans=sum=k=0; while(!q.empty()) q.pop(); scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d",&s[i]); sum+=s[i]; q.push(s[i]); } sum/=2; while(!q.empty()) { if(k) { b=q.top(); q.pop(); ans+=2*b; q.push(a-b); } else { a=q.top(); q.pop(); } k^=1; } if(a!=0) ans++; printf("Case #%d: %d\n",p++,min(ans,sum)); } return 0; } <a target=_blank href="http://acm.hdu.edu.cn/showproblem.php?pid=5793" target="_blank"></a><a target=_blank href="http://acm.hdu.edu.cn/showproblem.php?pid=5781" target="_blank"></a><a target=_blank href="http://acm.hdu.edu.cn/showproblem.php?pid=5783" target="_blank"></a><a target=_blank href="http://acm.hdu.edu.cn/showproblem.php?pid=5763" target="_blank"></a><a target=_blank href="http://acm.hdu.edu.cn/showproblem.php?pid=5752" target="_blank"></a>
【1011】
这道题也真的是个坑，题目中一直在描述最长递增子序列，然后我一直以为要按照字母大小去递增，wa很多次，最后改成统计不同字母的个数总算ac啦。
HDU5842
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int main() { int t,num=1; char a[100005]; int len,i; scanf("%d",&t); while(t--) { int count=1; scanf("%s",a); len=strlen(a); sort(a,a+len); for(i=0;i<len-1;i++) { if(a[i]!=a[i+1]) count++; } printf("Case #%d: %d\n",num++,count); } return 0; } 