A，Kaixinxiaoxiaole，给一个至多1000*1000的图问这个图上有多少种合法操作。水题。直接暴力。
我居然连写带调花了四十分钟。。弱的一比。对得起我暑假在机房玩的那么多关消消乐么！（雾。
1 #include <cstdio> 2 #include <iostream> 3 #include <math.h> 4 #include <string.h> 5 using namespace std; 6 const int N = 1005; 7 int n,m,ans; 8 char a[N][N]; 9 void solve() 10 { 11 for (int i=0; i<n-1; i++) 12 for (int j=0; j<m; j++) 13 if ((j>1&&a[i+1][j-1]==a[i+1][j-2]&&a[i+1][j-1]==a[i][j]) || (j<m-2&&a[i+1][j+1]==a[i+1][j+2]&&a[i+1][j+2]==a[i][j]) || (i<n-3&&a[i+2][j]==a[i+3][j]&&a[i][j]==a[i+2][j]) || (j>0&&j<m-1&&a[i+1][j-1]==a[i+1][j+1]&&a[i][j]==a[i+1][j-1])) ans++; 14 for (int i=1; i<n; i++) 15 for (int j=0; j<m; j++) 16 if ((j>1&&a[i-1][j-1]==a[i-1][j-2]&&a[i-1][j-1]==a[i][j]) || (j<m-2&&a[i-1][j+1]==a[i-1][j+2]&&a[i-1][j+2]==a[i][j]) || (i>2&&a[i-2][j]==a[i-3][j]&&a[i][j]==a[i-2][j]) || (j>0&&j<m-1&&a[i-1][j-1]==a[i-1][j+1]&&a[i][j]==a[i-1][j-1])) ans++; 17 for (int j=0; j<m-1; j++) 18 for (int i=0; i<n; i++) 19 if ((i>1&&a[i-1][j+1]==a[i-2][j+1]&&a[i-2][j+1]==a[i][j]) || (i<n-2&&a[i+1][j+1]==a[i+2][j+1]&&a[i+2][j+1]==a[i][j]) || (j<m-3&&a[i][j+2]==a[i][j+3]&&a[i][j]==a[i][j+2]) || (i>0&&i<n-1&&a[i+1][j+1]==a[i-1][j+1]&&a[i][j]==a[i+1][j+1])) ans++; 20 for (int j=1; j<m; j++) 21 for (int i=0; i<n; i++) 22 if ((i>1&&a[i-1][j-1]==a[i-2][j-1]&&a[i-2][j-1]==a[i][j]) || (i<n-2&&a[i+1][j-1]==a[i+2][j-1]&&a[i+2][j-1]==a[i][j]) || (j>2&&a[i][j-2]==a[i][j-3]&&a[i][j]==a[i][j-2]) || (i>0&&i<n-1&&a[i-1][j-1]==a[i+1][j-1]&&a[i][j]==a[i-1][j-1])) ans++; 23 } 24 int main() 25 { 26 //freopen("in.txt","r",stdin); 27 while (~scanf("%d%d",&n,&m)) 28 { 29 ans = 0; 30 for (int i=0; i<n; i++) 31 scanf("%s",a[i]); 32 solve(); 33 printf("%d\n",ans); 34 } 35 return 0; 36 }
B，Prefix Substring，给两个串a,b，问多少个a的子串是b的前缀。
去长春那天刚好讲了KMP。用next数组的性质水过。然而我还是没写出来……不过没有关系！大神队友zig_zag写粗来了！
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 using namespace std; 5 typedef long long LL; 6 const int maxn = 1e5 + 5; 7 char a[maxn], b[maxn]; 8 int next[maxn], f[maxn]; 9 void prekmp(char *b, int *next) 10 { 11 memset(next,-1,sizeof next); 12 memset(f,0,sizeof f); 13 int j = -1; 14 for (int i=1; b[i]; i++) 15 { 16 while (j!=-1 && b[i]!=b[j+1]) 17 j = next[j]; 18 if (b[i] == b[j+1]) j++; 19 next[i] = j; 20 } 21 for (int i=0; b[i]; i++) 22 { 23 int tmp = i; 24 while (tmp != -1) 25 { 26 f[i]++; 27 tmp = next[tmp]; 28 } 29 } 30 } 31 LL kmp(char *a, char *b, int *next) 32 { 33 int j = -1; 34 LL ret = 0; 35 for (int i=0; a[i]; i++) 36 { 37 while (j!=-1 && a[i]!=b[j+1]) 38 j = next[j]; 39 if (a[i] == b[j+1]) ret += f[++j]; 40 } 41 return ret; 42 } 43 int main() 44 { 45 scanf("%s%s",a,b); 46 prekmp(b, next); 47 printf("%lld\n",kmp(a,b,next)); 48 return 0; 49 }
C，Game，博弈，给出两个整数a,b，每次可以给a+1或者加到它之上最小的素数，第一个加过b的输。看起来像sg函数的找规律。。真是坑死喵了。。
考虑到除了2之外所有的质数都是奇数，所以从奇偶性入手判断结果。特殊情况很多，容易错漏。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <vector> 6 #include <algorithm> 7 using namespace std; 8 typedef long long LL; 9 const int N = 1000000; 10 int a,b; 11 vector<int> prime; 12 bool is_prime[N]; 13 void prime_table() 14 { 15 for (int i=0; i<N; i++) is_prime[i] = true; 16 for (int i=2; i<N; i++) 17 { 18 if (is_prime[i]) prime.push_back(i); 19 for (int j=0; j<prime.size() && i*prime[j]<N; j++) 20 { 21 is_prime[i*prime[j]] = false; 22 if (i % prime[j] == 0) break; 23 } 24 } 25 } 26 int main() 27 { 28 prime_table(); 29 int t; 30 scanf("%d",&t); 31 while (t--) 32 { 33 scanf("%d%d",&a,&b); 34 if (a == b) 35 { 36 puts("No"); 37 continue; 38 } 39 else if (b == 2) 40 { 41 puts("Yes"); 42 continue; 43 } 44 else if (b == 3) 45 { 46 if (a == 1) puts("No"); 47 if (a == 2) puts("Yes"); 48 continue; 49 } 50 if (is_prime[b]) 51 { 52 int t1 = lower_bound(prime.begin(), prime.end(), b) - prime.begin(); 53 t1 = prime[--t1]; 54 if (a >= t1) puts("Yes"); 55 else if (a & 1) puts("Yes"); 56 else puts("No"); 57 } 58 else 59 { 60 if (b & 1) 61 { 62 int t1 = lower_bound(prime.begin(), prime.end(), b) - prime.begin(); 63 t1 = prime[--t1]; 64 int t2 = lower_bound(prime.begin(), prime.end(), t1) - prime.begin(); 65 t2 = prime[--t2]; 66 if (a >= t1) 67 { 68 if (a & 1) puts("No"); 69 else puts("Yes"); 70 } 71 else if (a >= t2) puts("Yes"); 72 else if (a & 1) puts("Yes"); 73 else puts("No"); 74 } 75 else if (a & 1) puts("Yes"); 76 else puts("No"); 77 } 78 } 79 return 0; 80 }
D，Snake Filled，从(0,0)开始蛇形填数，问(0,x)的值。典型的一眼秒找规律。
1 #include <iostream> 2 #include <cstdio> 3 typedef long long LL; 4 int main() 5 { 6 int t,n; 7 scanf("%d",&t); 8 while (t--) 9 { 10 scanf("%d",&n); 11 printf("%d\n",4*n*n+n); 12 } 13 return 0; 14 }
E，Ants，n*n的矩阵，问总共有多少种用不重复的哈密顿路覆盖矩阵的方法。
插头DP，据说暴力打表能打三天三夜？反正我不会。先挂个名字。万一我以后会了再来补呢。
F，LIS，给你一个树，输出有LIS的那条线。用dfs序做。注意nlogn求dfs序的同时记录路径会WA。
树学得特别糟糕...先放这里以后再补吧。
G，Max Sub-matrix，找出最大子矩阵边值和。因为正数的个数不超过100，把它们找出来暴力就好了。
H，Qingming Travel，给出一堆花的坐标，分成两部分，每人从各自选择的花中横座标最小的花开始，按照横座标递增的顺序依次采集。当一个人每采集完一朵花之后，他（她）会沿最短距离走向下一朵花的位置。求两个人路径交点最多的个数。
第一眼容易跳进“怎么划分两个集合”里面出不来……其实并不需要知道哪朵花在谁的集合里，dp就可以了。
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <math.h> 5 #include <algorithm> 6 using namespace std; 7 typedef long long LL; 8 const double EPS = 1e-8; 9 const int maxn = 233; 10 struct Point 11 { 12 double x,y; 13 Point(double x=0, double y=0):x(x),y(y) {} 14 } p[maxn]; 15 int dp[maxn][maxn]; 16 typedef Point Vec; 17 Vec operator -(Point A,Point B) 18 { 19 return Vec(A.x-B.x,A.y-B.y); 20 } 21 bool operator <(const Point& a,const Point& b) 22 { 23 return a.x<b.x || (a.x == b.x && a.y<b.y); 24 } 25 int dcmp(double x) 26 { 27 if (fabs(x) < EPS) return 0; 28 else return x < 0 ? -1 : 1; 29 } 30 bool operator == (const Point& a,const Point &b) 31 { 32 return dcmp(a.x-b.x)==0 && dcmp(a.y-b.y) == 0; 33 } 34 double Cross(Vec A,Vec B) 35 { 36 return A.x*B.y - A.y*B.x; 37 } 38 bool SegmentProperIntersection(Point a1,Point a2,Point b1,Point b2) 39 { 40 double c1 = Cross(a2-a1,b1-a1),c2 = Cross(a2-a1,b2-a1); 41 double c3 = Cross(b2-b1,a1-b1),c4 = Cross(b2-b1,a2-b1); 42 return dcmp(c1)*dcmp(c2)<0 && dcmp(c3)*dcmp(c4)<0; 43 } 44 int main() 45 { 46 int n; 47 while (~scanf("%d",&n)) 48 { 49 for (int i=1; i<=n; i++) 50 scanf("%lf%lf",&p[i].x,&p[i].y); 51 sort(p+1, p+n+1); 52 memset(dp,0,sizeof dp); 53 for (int i=1; i<=n; i++) 54 for (int j=1; j<i-1; j++) 55 { 56 int cnt = 0; 57 for (int k=j+1; k<i-1; k++) 58 { 59 cnt += SegmentProperIntersection(p[i],p[j],p[k],p[k+1]); 60 } 61 for (int k=1; k<j; k++) 62 { 63 int ok = SegmentProperIntersection(p[i],p[j],p[k],p[j+1]); 64 dp[i][j] = max(dp[i][j], dp[j+1][k]+cnt+ok); 65 } 66 dp[i][j] = max(dp[i][j], cnt); 67 } 68 int ans = 0; 69 for (int i=1; i<=n; i++) 70 ans = max(ans, dp[n][i]); 71 printf("%d\n",ans); 72 } 73 return 0; 74 }
I，Math Question,找出指定区间内是素数&两个平方数和的数的个数。水题，暴力。
1 #include <stdio.h> 2 #include <iostream> 3 #include <cmath> 4 #include <algorithm> 5 #include <cstring> 6 #include <vector> 7 using namespace std; 8 const int N = 1e8 + 5; 9 vector<int> prime; 10 bool is_prime[N]; 11 int ans[N]; 12 void prime_table() 13 { 14 ans[0] = ans[1] = 0; 15 for (int i=0; i<N; i++) is_prime[i] = true; 16 for (int i=2; i<N; i++) 17 { 18 ans[i] = ans[i-1]; 19 if (is_prime[i]) 20 { 21 prime.push_back(i); 22 if (i == 2 || i % 4 == 1) ans[i]++; 23 } 24 for (int j=0; j<prime.size() && i*prime[j]<N; j++) 25 { 26 is_prime[i*prime[j]] = false; 27 if (i % prime[j] == 0) break; 28 } 29 } 30 } 31 int main() 32 { 33 prime_table(); 34 int t,l,r; 35 scanf("%d",&t); 36 while (t--) 37 { 38 scanf("%d%d",&l,&r); 39 printf("%d\n",ans[r]-ans[l-1]); 40 } 41 return 0; 42 }
J，Pin Pin Pin，给一个构造函数F(n)=F(n-1)+n（字符串加法），问F(n)%(1e9+7)的值。
正解是分段矩阵快速幂。现场赛的时候用分段打表过了…打出来十万的数组…出题的学长从此就恨上了我orz。
固定mod天地灭。
1 #include <stdio.h> 2 #include <iostream> 3 #include <cmath> 4 #include <algorithm> 5 #include <cstring> 6 #include <vector> 7 using namespace std; 8 typedef long long LL; 9 const int N = 5; 10 const int MOD = 1e9 + 7; 11 struct Mat 12 { 13 LL mat[N][N]; 14 int len; 15 Mat() {} 16 Mat(int _len,int num) 17 { 18 memset(mat,0,sizeof(mat)); 19 if(num) 20 { 21 mat[0][0] = num; 22 mat[1][0] = mat[1][1] = 1; 23 mat[2][1] = mat[2][2] = 1; 24 } 25 len = _len; 26 } 27 Mat operator * (Mat b) 28 { 29 Mat c = Mat(len,0); 30 for(int i=0; i<len; i++) 31 { 32 for(int k = 0; k<len; k++) 33 { 34 if(!mat[i][k]) continue; 35 for(int j=0; j<len; j++) 36 { 37 c.mat[i][j] += mat[i][k] * b.mat[k][j]; 38 } 39 } 40 } 41 for(int i=0; i<len; i++) 42 { 43 for (int j = 0; j < len; j++) 44 { 45 c.mat[i][j] %= MOD; 46 } 47 } 48 return c; 49 } 50 friend Mat operator ^ (Mat a,int k) 51 { 52 Mat c = Mat(a.len,0); 53 for(int i = 0; i<a.len; i++) 54 for(int j=0; j<a.len; j++) 55 c.mat[i][j] = (i == j); 56 for(; k; k>>=1) 57 { 58 if(k&1) c = c*a; 59 a = a*a; 60 } 61 return c; 62 } 63 }; 64 struct Vector 65 { 66 LL num[N]; 67 int len; 68 Vector() 69 { 70 len = 3; 71 memset(num,0,sizeof(num)); 72 } 73 Vector(int _len,LL *_num) 74 { 75 len = _len; 76 for(int i=0; i<len; i++) 77 num[i] = _num[i]; 78 } 79 Vector operator * (Mat b) 80 { 81 Vector c; 82 for(int k=0; k<len; k++) 83 { 84 if(!num[k])continue; 85 for(int j=0; j<len; j++) 86 { 87 c.num[j] += num[k] * b.mat[k][j]; 88 } 89 } 90 for(int i=0; i<len; i++) 91 c.num[i]%=MOD; 92 return c; 93 } 94 }; 95 96 int main() 97 { 98 int T; 99 cin>>T; 100 LL _10[10]; 101 _10[0] = 1; 102 for(int i=1; i<10; i++) 103 _10[i] = _10[i-1]*10; 104 while(T--) 105 { 106 int n; 107 scanf("%d",&n); 108 LL temp[] = {0,1,1}; 109 Vector st = Vector(3,temp); 110 int len = (int)floor(log10((double)n))+1; 111 for(int i=1; i<len; i++) 112 { 113 Mat use = Mat(3,_10[i]); 114 st = st * (use ^ (_10[i]-_10[i-1])); 115 } 116 Mat use = Mat(3,_10[len]); 117 st = st * (use ^ (n - _10[len-1]+1)); 118 cout<<st.num[0]<<endl; 119 } 120 return 0; 121 }
K，Calculate Niega，给出密码和译文的一一对应关系，求有多少个nie和niega。
题很难读懂，但是很水。唯一坑点是知道25个字母的对应关系之后要推第26个字母的对应。
1 #include <stdio.h> 2 #include <iostream> 3 #include <cmath> 4 #include <algorithm> 5 #include <cstring> 6 #include <vector> 7 using namespace std; 8 typedef long long LL; 9 const int maxn = 1000005; 10 char map1[30],map2[30],vis[30]; 11 char s[33],s1[33],s2[maxn]; 12 int main() 13 { 14 int n; 15 while(~scanf("%d",&n)) 16 { 17 memset(map1,-1,sizeof(map1)); 18 memset(map2,-1,sizeof(map2)); 19 memset(vis,false,sizeof(vis)); 20 int flag = true; 21 for(int i = 1; i <= n; i++) 22 { 23 scanf("%s%s",s1,s2); 24 int len = strlen(s1); 25 if(!flag) continue; 26 for(int j = 0; j < len; j++) 27 { 28 if(map1[s1[j]-‘a‘] != -1) 29 { 30 if(map1[s1[j]-‘a‘] != s2[j]-‘a‘) 31 { 32 flag = false; 33 break; 34 } 35 } 36 else 37 { 38 if(map2[s2[j]-‘a‘] == -1) 39 { 40 map1[s1[j]-‘a‘] = s2[j] - ‘a‘; 41 map2[s2[j]-‘a‘] = s1[j] - ‘a‘; 42 vis[s2[j]-‘a‘] = true; 43 } 44 else 45 { 46 flag = false; 47 break; 48 } 49 } 50 } 51 } 52 scanf("%s",s); 53 if(!flag) 54 { 55 printf("Please nie in proportion!\n"); 56 continue; 57 } 58 int trick = -1; 59 for(int i=0; i<=25; i++) 60 if(!vis[i]) trick = i; 61 int count1 = 0; 62 int tricki = -1; 63 for(int i=0; i<=25; i++) 64 if(map1[i] == -1) 65 tricki = i,count1++; 66 if(count1 == 1) map1[tricki] = trick; 67 int lens = strlen(s); 68 for(int i=0; i<lens; i++) 69 { 70 if(map1[s[i]-‘a‘] != -1) 71 s[i] = map1[s[i]-‘a‘] + ‘a‘; 72 } 73 int ansnie = 0,ansniega = 0; 74 for(int i = 0; i < lens;) 75 { 76 if(s[i] == ‘n‘) 77 { 78 if(i + 4 < lens) 79 { 80 if(s[i+1] == ‘i‘ && s[i+2] == ‘e‘ && (s[i+3] != ‘g‘ || s[i+4] != ‘a‘)) ansnie++,i += 3; 81 else if(s[i+1] == ‘i‘ && s[i+2] == ‘e‘ && s[i+3] == ‘g‘ && s[i+4] == ‘a‘) ansniega++,i += 5; 82 else i++; 83 } 84 else if(i + 2 < lens) 85 { 86 if(s[i+1] == ‘i‘ && s[i+2] == ‘e‘) ansnie++,i += 3; 87 else i++; 88 } 89 } 90 else i++; 91 } 92 printf("%d %d\n",ansnie+ansniega,ansniega); 93 } 94 return 0; 95 }
开始的时候分开读题，读完一道一抬头发现满世界的D气球。zig_zag大腿一看，哎呀，水！啪啪啪一顿敲过了。然后看B题很短，很开心，看起了B。我提出用kmp的next性质做，大腿觉得麻烦要暴力试一发，毫无悬念的T掉，老实改kmp，改了一段时间，中间顺便把I题AC了，由于题太水，A完我都不知道题意…。然后发现好多人过A，一看题，这不就一暴力嘛。于是pzh很开心的去敲A。我看上的C死活过不去，看另一个队把J过了，看看题觉得是一个分段打表。我就上去打。先隔100W，再10W，再1W，中间废了很多时间去说服队友让我再试一次说不定就不T了呢！（泪眼。于是这个题过的时候已经三个多小时了。裁判给出了K的中文题意和坑点，按学长的话说，“就差跪着求你们做K了”。然而我和pzh都觉得C差一点点就能过，zig_zag感觉字符串好麻烦不想写，就去怼F了，然后就两边交错着WA到比赛结束。
总体来说这个比赛成绩不错，进了金牌线，虽然并不能拿奖TUT。最后那段时间一起看K和G的话说不定两道都能过！这种临场决策问题只能慢慢攒经验吧。
原文：http://www.cnblogs.com/honeycat/p/4858611.html
