Section 1.1
Your Ride Is Here 貌似没啥可说
Greedy Gift Givers 上来就想stl map映射，有两个坑：如果送给别人的人数为0，那么需要特判一下，防止整数被0除；另外分给别人的钱可能会有剩余（不能整除），所以送礼者的钱数减少时不能直接减他想送出去的钱。
Friday The Thirteenth狗血模拟题，开始想要高级的一月一计算，看题解后还是用了一天一移动。
1 #include<cstdio> 2 #include<algorithm> 3 4 using namespace std; 5 6 int n; 7 int nowyear,nowday,nowmonth,week; 8 int tong[100]; 9 10 bool ren(int x) 11 { 12 if((x%4==0)&&(x%100!=0)||(x%400==0)) return 1; 13 return 0; 14 } 15 16 int month(int year,int tmpm) 17 { 18 if(ren(year)&&tmpm==2) return 29; 19 else if(!ren(year)&&tmpm==2) return 28; 20 if(tmpm==4||tmpm==6||tmpm==9||tmpm==11) return 30; 21 return 31; 22 } 23 24 int main() 25 { 26 scanf("%d",&n); 27 nowyear=1900,nowday=1,nowmonth=1,week=1; 28 while(1) 29 { 30 if(nowyear==1900+n&&nowday==1&&nowmonth==1) 31 break;//到达目标年12月31日的下一天，也就是1月1日 32 nowday++; 33 week=week+1; 34 if(week>7) week=1; 35 if(nowday>month(nowyear,nowmonth)) 36 nowmonth++,nowday=1; 37 if(nowmonth>12) 38 nowyear++,nowmonth=1; 39 if(nowday==13) tong[week]++; 40 } 41 printf("%d %d ",tong[6],tong[7]); 42 for(int i=1;i<=5;i++) 43 printf("%d ",tong[i]); 44 return 0; 45 }
Broken Necklace 又是一道狗血模拟题，直接枚举断点即可。然后需要断环为链。然后又几个坑：要开vis数组记录有没有采集过当前的珠子，并时刻检查；还有特判断点（origin）为w珠的情况。而且在奶牛站上交的时候还把文件名写错了==
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 5 using namespace std; 6 7 int n,ans; 8 bool vis[900]; 9 char nl[900]; 10 11 int main() 12 { 13 scanf("%d",&n); 14 scanf("%s",nl+1); 15 for(int i=1;i<=n;i++) nl[i+n]=nl[i]; 16 for(int x=1;x<=n;x++) 17 { 18 memset(vis,0,sizeof(vis)); 19 /* int r=i+1,l=i; 20 if(i==n) r=1; 21 bool flagl=1,flagr=1; 22 char source_r=nl[r],source_l=nl[l]; 23 int cntl=1,cntr=1; 24 while(l!=r) 25 { 26 r++;l--; 27 if(l<1) l=n; 28 if(r>n) r=1; 29 if(nl[l]!=source_l&&nl[l]!='w') flagl=0; 30 if(nl[r]!=source_r&&nl[r]!='w') flagr=0; 31 if(flagl&&!vis[l]) cntl++,vis[l]=1; 32 if(flagr&&!vis[r]) cntr++,vis[r]=1; 33 }*/ 34 int cnt=1; 35 char origin=nl[x]; 36 vis[x]=vis[x+n]=1; 37 for(int i=x-1;i>=1;i--) 38 { 39 if(vis[i]) break; 40 if(nl[i]==origin||nl[i]=='w') cnt++; 41 else if(origin=='w') cnt++,origin=nl[i]; 42 else break; 43 vis[i]=vis[i+n]=1; 44 } 45 ans=max(ans,cnt); 46 if(vis[x+1]) continue; 47 cnt++; 48 origin=nl[x+1]; 49 for(int i=x+2;i<=2*n;i++) 50 { 51 if(vis[i]) break; 52 if(nl[i]==origin||nl[i]=='w') cnt++; 53 else if(origin=='w') cnt++,origin=nl[i]; 54 else break; 55 vis[i]=vis[i+n]=1; 56 } 57 ans=max(ans,cnt); 58 } 59 printf("%d",ans); 60 return 0; 61 }
小结：lj模拟题目，注意细节。
Section 1.2
Milking Cows 还是很好想的区间问题，情况要想全。而且要在“最长至少有一人在挤奶的时间段”赋初值！（掉坑了）
Transformations 没有什么说的，想全情况，慢慢推导（考场1A，并没有什么可自豪）
Palindromic Squares 也是很简单。不过要注意！！进制数可能会超过10，有的要用字母表示！！！判断的时候不用，输出的时候需要预处理出一个char数组，如果模数大于10，就输出字母。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 5 using namespace std; 6 7 int B; 8 int a[10000]; 9 char g[20]={'A','B','C','D','E','F','G','H','I','J','K'}; 10 11 bool judge(int x) 12 { 13 int pos=0; 14 memset(a,0,sizeof(a)); 15 while(x) 16 { 17 a[++pos]=x%B; 18 x/=B; 19 } 20 int head=1,tail=pos; 21 while(head<tail) 22 { 23 if(a[head]!=a[tail]) return 0; 24 head++,tail--; 25 } 26 return 1; 27 } 28 29 void getf(int x) 30 { 31 int tmp[10000],cellur=0; 32 memset(tmp,0,sizeof(tmp)); 33 while(x) 34 { 35 tmp[++cellur]=x%B; 36 x/=B; 37 } 38 for(int i=cellur;i>=1;i--) 39 { 40 if(tmp[i]<10) printf("%d",tmp[i]); 41 else printf("%c",g[tmp[i]-10]); 42 } 43 printf(" "); 44 } 45 46 int main() 47 { 48 scanf("%d",&B); 49 for(int i=1;i<=300;i++) 50 { 51 if(judge(i*i)) 52 getf(i),getf(i*i),printf(" "); 53 } 54 return 0; 55 }
Dual Palindromes 直接模拟就行，然后注意审清题目：从大于这个数开始算起。而不是大于等于。
Name That Number 目测自己的做法最简单（盲目自信），只要用一个map存一下每个字母对应的数字就行，题意有点绕，字典它是会输进来的。每输入一个单词进行严苛判断即可。第一次交手残了，本来可以1A的，逻辑不清楚写错了一个地方。
1.2小结：都是简单的枚举题目，细心，细心，再细心！
Section 1.3
Combination Lock 由于数据范围的锅，可以n^3直接过掉，然后预处理的时候我写的有点麻烦。需要特判极端数据1的情况（直接输出1）
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 5 using namespace std; 6 7 int n,ans; 8 bool vis[900]; 9 char nl[900]; 10 11 int main() 12 { 13 scanf("%d",&n); 14 scanf("%s",nl+1); 15 for(int i=1;i<=n;i++) nl[i+n]=nl[i]; 16 for(int x=1;x<=n;x++) 17 { 18 memset(vis,0,sizeof(vis)); 19 /* int r=i+1,l=i; 20 if(i==n) r=1; 21 bool flagl=1,flagr=1; 22 char source_r=nl[r],source_l=nl[l]; 23 int cntl=1,cntr=1; 24 while(l!=r) 25 { 26 r++;l--; 27 if(l<1) l=n; 28 if(r>n) r=1; 29 if(nl[l]!=source_l&&nl[l]!='w') flagl=0; 30 if(nl[r]!=source_r&&nl[r]!='w') flagr=0; 31 if(flagl&&!vis[l]) cntl++,vis[l]=1; 32 if(flagr&&!vis[r]) cntr++,vis[r]=1; 33 }*/ 34 int cnt=1; 35 char origin=nl[x]; 36 vis[x]=vis[x+n]=1; 37 for(int i=x-1;i>=1;i--) 38 { 39 if(vis[i]) break; 40 if(nl[i]==origin||nl[i]=='w') cnt++; 41 else if(origin=='w') cnt++,origin=nl[i]; 42 else break; 43 vis[i]=vis[i+n]=1; 44 } 45 ans=max(ans,cnt); 46 if(vis[x+1]) continue; 47 cnt++; 48 origin=nl[x+1]; 49 for(int i=x+2;i<=2*n;i++) 50 { 51 if(vis[i]) break; 52 if(nl[i]==origin||nl[i]=='w') cnt++; 53 else if(origin=='w') cnt++,origin=nl[i]; 54 else break; 55 vis[i]=vis[i+n]=1; 56 } 57 ans=max(ans,cnt); 58 } 59 printf("%d",ans); 60 return 0; 61 }
Prime Cryptarithm 模拟乘法竖式的各个步骤，注意细节，一道橙题调了好久，我好弱呀。模拟的时候多膜了。
1 /* 2 ID:cellur_2 3 TASK:crypt1 4 LANG:C++ 5 */ 6 #include<cstdio> 7 #include<algorithm> 8 9 using namespace std; 10 typedef long long ll; 11 12 int n,cnt; 13 ll ans; 14 int seq[100]; 15 bool vis[100]; 16 17 bool check(int i,int j,int a,int b,int c) 18 { 19 if(!vis[(a*c)%10]) return 0; 20 int tmp=a*c/10; 21 if(!vis[(j*c+tmp)%10]) return 0; 22 int cellur=(j*c+tmp)%10; 23 tmp=(j*c+tmp)/10; 24 if(!vis[i*c+tmp]) return 0; 25 int Chemist=(i*c+tmp)%10; 26 27 if(!vis[(a*b)%10]) return 0; 28 int Shouzu=(a*b)%10; 29 if(!vis[(cellur+Shouzu)%10]) return 0; 30 int qwq=(cellur+Shouzu)/10; 31 tmp=a*b/10; 32 if(!vis[(j*b+tmp)%10]) return 0; 33 int phd=(j*b+tmp)%10; 34 tmp=(j*b+tmp)/10; 35 if(!vis[i*b+tmp]) return 0; 36 if(!vis[(Chemist+phd+qwq)%10]) return 0; 37 qwq=(phd+Chemist+qwq)/10; 38 if(!vis[i*b+tmp+qwq]) return 0; 39 40 return 1; 41 } 42 43 int main() 44 { 45 freopen("crypt1.in","r",stdin); 46 freopen("crypt1.out","w",stdout); 47 scanf("%d",&n); 48 for(int i=1;i<=n;i++) 49 scanf("%d",&seq[i]),vis[seq[i]]=1; 50 for(int i=1;i<=n;i++) 51 for(int j=1;j<=n;j++) 52 for(int a=1;a<=n;a++) 53 for(int b=1;b<=n;b++) 54 for(int c=1;c<=n;c++) 55 if(check(seq[i],seq[j],seq[a],seq[b],seq[c])) ans++; 56 printf("%lld ",ans); 57 return 0; 58 }
Ski Course Design 一道可以让人深刻理解枚举的题目。在答案可能的范围内进行枚举。是某次正睿周末普转提的题目。
Wormhole 是一道题意难以理解的搜索题目。“先枚举所有的匹配方式，然后匹配完之后dfs搜找环”--redbag的简明扼要题解
枚举所有的匹配方式：是一种难得的搜索，要求我们不重不漏地枚举两两相配的情况。
dfs搜找环：
Section 1.4
Arithmetic Progressions lwz dalao表示他不能理解题目，当时可能我太弱（？）没能帮到他。现在再来看竟然一下就明白题意了。一道数论题。我们可以先处理出在范围内的双平方数集合，将他们进行标记，去重排序，暴力枚举从数列的每一项出发能产生多少等差数列（看起来是n²的，其实好像还是n³的）。还有一种方法，每次枚举前两个数然后可得公差，不过感觉貌似快不了多少（？）最可笑的是无解情况没输出，忘特判输出“NONE”了，我真傻，真的。
Mother's milk 终于写出了正确的搜索框架（一次）！但是内容并没有填充hhh。有一个细节写炸了，洛谷交竟然还能拿70分，数据真是弱啊。
1 /* 2 ID:cellur_2 3 TASK:milk3 4 LANG:C++ 5 */ 6 #include<cstdio> 7 #include<algorithm> 8 9 using namespace std; 10 11 int a,b,c,m; 12 int ret[1000]; 13 bool vis[25][25][25]; // 记录A桶装了_,B桶装了_,C桶装了_是否可行 14 15 void dfs(int a1,int a2,int a3) 16 { 17 if(vis[a1][a2][a3]) return ; 18 if(!a1) ret[++m]=a3;//A桶空 记录C中所剩牛奶 19 vis[a1][a2][a3]=1; 20 //模拟倒奶过程 21 if(a1) 22 {//a1还有 23 if(a2<b)//向a2里面倒 24 dfs(a1-min(a1,b-a2),a2+min(a1,b-a2),a3); 25 if(a3<c) 26 dfs(a1-min(a1,c-a3),a2,a3+min(a1,c-a3)); 27 } 28 if(a2) 29 { 30 if(a1<a) 31 dfs(a1+min(a2,a-a1),a2-min(a2,a-a1),a3); 32 if(a3<c) 33 dfs(a1,a2-min(a2,c-a3),a3+min(a2,c-a3)); 34 } 35 if(a3) 36 { 37 if(a1<a) 38 dfs(a1+min(a3,a-a1),a2,a3-min(a3,a-a1)); 39 if(a2<b) 40 dfs(a1,a2+min(a3,b-a2),a3-min(a3,b-a2)); 41 } 42 return ; 43 } 44 45 int main() 46 { 47 freopen("milk3.in","r",stdin); 48 freopen("milk3.out","w",stdout); 49 scanf("%d%d%d",&a,&b,&c); 50 dfs(0,0,c); 51 int res=unique(ret+1,ret+1+m)-(ret+1); 52 sort(ret+1,ret+1+res);//q离散化去重 53 for(int i=1;i<=res;i++) 54 if(i!=res) printf("%d ",ret[i]); 55 else printf("%d",ret[i]); 56 printf(" "); 57 return 0; 58 }
Section 2.1
Healthy Holsteins大佬们都说是裸搜索，可是我还是太弱了，不会搜。搜索需要记录当前的个数及第几种，对于每次可以选当前饲料或不选。
但是因为我们的题目需要保证字典序最小，所以先搜选当前饲料的情况。
1 #include<cstdio> 2 #include<algorithm> 3 4 using namespace std; 5 6 int v,mini=99999999,G; 7 int sta[50],feed[20][30],noww[50],ans[50]; 8 9 bool check(int cnt) 10 { 11 for(int i=1;i<=v;i++) 12 { 13 int tmp=0; 14 for(int j=1;j<=cnt;j++) 15 tmp+=feed[noww[j]][i]; 16 if(tmp<sta[i]) return 0; 17 } 18 return 1; 19 } 20 21 void dfs(int type,int cnt) 22 { 23 if(type>G) 24 { 25 if(check(cnt)&&cnt<mini) 26 { 27 mini=cnt; 28 for(int i=1;i<=mini;i++) ans[i]=noww[i]; 29 } 30 return ; 31 } 32 noww[cnt+1]=type; 33 dfs(type+1,cnt+1); 34 noww[cnt+1]=0; 35 36 dfs(type+1,cnt); 37 } 38 39 int main() 40 { 41 scanf("%d",&v); 42 for(int i=1;i<=v;i++) scanf("%d",&sta[i]); 43 scanf("%d",&G); 44 for(int i=1;i<=G;i++) 45 for(int j=1;j<=v;j++) 46 scanf("%d",&feed[i][j]); 47 dfs(1,0); 48 printf("%d ",mini); 49 for(int i=1;i<=mini;i++) 50 printf("%d ",ans[i]); 51 return 0; 52 }
Section 2.2
Runaround Numbers 直接模拟即可，1A，需要细心。
Section 2.3
Controlling Companies 开始想不使用任何算法地水过，后来发现布星。用Vector存各个公司的儿子，但是会蜜汁RE+AC和零星的AC。话说最近用vector屡用屡WA，不用为妙。搜索真香。最朴素的搜索：存每个公司对其他公司的股份，然后分别对每个公司进行搜索。
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 5 using namespace std; 6 7 int n,x,y,opt; 8 int w[109][109],vis[109],f[109],sum[109]; 9 10 void dfs(int x) 11 { 12 if(vis[x]) return ; 13 vis[x]=1; 14 for(int i=1;i<=100;i++) 15 { 16 sum[i]+=w[x][i]; 17 if(sum[i]>50) 18 { 19 f[i]=1; 20 dfs(i); 21 } 22 } 23 } 24 25 int main() 26 { 27 scanf("%d",&n); 28 for(int i=1;i<=n;i++) 29 scanf("%d%d%d",&x,&y,&opt),w[x][y]=opt; 30 for(int i=1;i<=100;i++) 31 { 32 memset(vis,0,sizeof(vis)); 33 memset(f,0,sizeof(f)); 34 memset(sum,0,sizeof(sum)); 35 dfs(i); 36 for(int j=1;j<=100;j++) 37 if(f[j]&&i!=j) printf("%d %d ",i,j); 38 } 39 return 0; 40 }
Section 2.4
The Tamworth Two 一道模拟题，模拟农夫与两头牛走的地图，需要注意如何判断走的情况无解呢？可以给一定的循环次数限制来防止死循环。
Section 3.1
Stamps dp题目，也就是完全背包。f[i]表示面值为i的最小次数。然后上界要设的稍微大一些。边界条件f[0]=0，需要先把数组赋成正无穷才知道什么时候是上限解。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 5 using namespace std; 6 7 int n,k,ans; 8 int stamp[100],f[3000000]; 9 10 int main() 11 { 12 scanf("%d%d",&k,&n); 13 for(int i=1;i<=n;i++) scanf("%d",&stamp[i]); 14 memset(f,127,sizeof(f));int fAKe=f[1]; 15 f[0]=0; 16 for(int i=1;i<=n;i++) 17 for(int j=stamp[i];j<=3000000;j++) 18 if(f[j-stamp[i]]+1<=k) f[j]=min(f[j],f[j-stamp[i]]+1); 19 for(int i=1;i<=3000000;i++) 20 if(f[i]==fAKe) 21 { 22 printf("%d",i-1); 23 return 0; 24 } 25 return 0; 26 }
Section 3.3
Home on the Range神似最大正方形。二维前缀和搞一搞就好，然后写这道题的时候才发现写最大正方形的时候有些bug,边界是小于0.因为第一行也可能被选到。
A Game 区间dp，写了正经题解。
Camelot 搜索，写了正经题解。
Shopping Offers完全背包，写了正经题解。
Riding The Fence 欧拉路，写了正经题解。
Section 3.4
Raucous Rockers 真·搜索
American Heritage是一道不错的二叉树基础练习题。用到了string奇淫技巧，需要熟练掌握二叉树三种遍历序列。
Electric Fence 正经计算几何，写了正经题解。
