C
有n个节点和m边条，求一条最长的路径，该路径(c1,c2,c3...cn)满足 不出现重复的节点，ci 和ci+1是邻居节点，且 ci 的邻居节点数量小于ci+1的邻居节点数量。
记忆DFS遍历，每次递归计算的值都保存在数组里，这样复杂度相当于O(m)
1 #include <bits/stdc++.h> 2 #define INF 0x3f3f3f3f 3 #define ll long long 4 using namespace std; 5 const int N = 1e5+10; 6 vector<int> vs[N]; 7 int MAX, ans[N]; 8 int dfs(int v) { 9 if(ans[v]!=0) return ans[v]; 10 int cnt = 0; 11 for(auto u : vs[v]) { 12 if(vs[u].size() > vs[v].size()) { 13 cnt = max(cnt, dfs(u)); 14 } 15 } 16 ans[v] = cnt+1; 17 return cnt+1; 18 } 19 int main() { 20 int n, m, v, u; 21 cin >> n >> m; 22 for(int i = 1; i <= m; i ++) { 23 cin >> v >> u; 24 vs[v].push_back(u); 25 vs[u].push_back(v); 26 } 27 for(int i = 0; i < n; i ++) { 28 dfs(i); 29 MAX = max(MAX, ans[i]); 30 } 31 cout << MAX << endl; 32 return 0; 33 }
D
给定一个数字x，问一直使用x = f(x)这个函数是否可以将x变成1.
f(x) 的定义是对每一位数进行平方求和。签到题
1 #include <bits/stdc++.h> 2 #define INF 0x3f3f3f3f 3 #define ll long long 4 using namespace std; 5 map<int,int> mp; 6 int f(int x) { 7 int ans = 0; 8 while(x) { 9 int y = x%10; 10 ans += y*y; 11 x /= 10; 12 } 13 return ans; 14 } 15 int main() { 16 int n; 17 cin >> n; 18 while(true) { 19 n = f(n); 20 if(n == 1) return 0*printf("HAPPY\n"); 21 if(mp.count(n)) break; 22 mp[n] = 1; 23 } 24 printf("UNHAPPY\n"); 25 return 0; 26 }
F
已知边长和走的步数，求当前的位置。
分而治之。对于当前边长为n的图，可以分为四份。
如果在左下角，顺时针旋转了90°，相当于x和y值交换下。
如果在右下角，逆时针旋转了90°，相当于x和y值交换下，对称看。
如果在左上角，y值加n/2。
如果在右上角，x值和y值都加n/2。
1 #include <bits/stdc++.h> 2 #define INF 0x3f3f3f3f 3 #define ll long long 4 using namespace std; 5 const int N = 1e5+10; 6 struct Point{ 7 int x, y; 8 }; 9 Point dfs(int n, int m) { 10 Point a; 11 if(n == 2) { 12 if(m == 0) a.x = 1, a.y = 1; 13 else if(m == 1) a.x = 1, a.y = 2; 14 else if(m == 2) a.x = 2, a.y = 2; 15 else if(m == 3) a.x = 2, a.y = 1; 16 return a; 17 } 18 int ans = n*n/4; 19 int cnt = m%ans; 20 a = dfs(n/2, cnt); 21 if(m < ans) { 22 swap(a.x, a.y); 23 } else if(m < 2*ans) { 24 a.y += n/2; 25 } else if(m < 3*ans) { 26 a.x += n/2; 27 a.y += n/2; 28 } else { 29 int x = n+1-a.y; 30 int y = n/2+1 - a.x; 31 return (Point){x, y}; 32 } 33 return a; 34 } 35 36 int main() { 37 int n, m; 38 cin >> n >> m; 39 Point p = dfs(n, m-1); 40 printf("%d %d\n",p.x,p.y); 41 return 0; 42 }
H
有两个字符串，只有三个字符，R(石头)、S(剪刀)和P(布)，求第二个在第一个在哪里开始比赛赢的数数最多，求数量。
12 4
RSPPSSSRRPPR
RRRR
第二个字符串从第4或第5位置开始可以赢3把，所以答案是3。
题目可以转成成从哪里开始，位置一一对应是相同的数量。将第二个字符串反转，使用fft套模板就出答案了。
主要是想到为什么对第二个字符进行反转，假设有两个字符串
1 2 3 456
RRRSSS
SSPR
1 2 3 4
RPSS
从第一个位置开始，一一对应是1+4,2+3,3+2,4+1，都是5
从第二个位置开始，一一对于是2+4,3+3,4+2,5+1，都是6
这样就知道为什么反转了。只要对两个数组求卷积就行。
1 #include <iostream> 2 #include <algorithm> 3 #include <math.h> 4 #define INF 0x3f3f3f3f 5 #define ll long long 6 using namespace std; 7 const int N = 1e5+10; 8 char s1[N], s2[N]; 9 const double PI = acos(-1.0); 10 struct complex { 11 double r,i; 12 complex(double _r = 0,double _i = 0) { 13 r = _r; i = _i; 14 } 15 complex operator +(const complex &b) { 16 return complex(r+b.r,i+b.i); 17 } 18 complex operator -(const complex &b) { 19 return complex(r-b.r,i-b.i); 20 } 21 complex operator *(const complex &b) { 22 return complex(r*b.r-i*b.i,r*b.i+i*b.r); 23 } 24 }; 25 void change(complex y[],int len) { 26 int i,j,k; 27 for(i = 1, j = len/2;i < len-1;i++) { 28 if(i < j)swap(y[i],y[j]); 29 k = len/2; 30 while( j >= k) { 31 j -= k; 32 k /= 2; 33 } 34 if(j < k)j += k; 35 } 36 } 37 void fft(complex y[],int len,int on) { 38 change(y,len); 39 for(int h = 2;h <= len;h <<= 1) { 40 complex wn(cos(-on*2*PI/h),sin(-on*2*PI/h)); 41 for(int j = 0;j < len;j += h) { 42 complex w(1,0); 43 for(int k = j;k < j+h/2;k++) { 44 complex u = y[k]; 45 complex t = w*y[k+h/2]; 46 y[k] = u+t; 47 y[k+h/2] = u-t; 48 w = w*wn; 49 } 50 } 51 } 52 if(on == -1) 53 for(int i = 0;i < len;i++) 54 y[i].r /= len; 55 } 56 57 const int MAXN = 400040; 58 complex x1[MAXN], x2[MAXN]; 59 int a[MAXN/4], n, m; 60 ll num[MAXN], ans[MAXN]; 61 void slove(char ch) { 62 int len = 1; 63 while(len < 2*n || len < 2*m)len <<= 1; 64 for(int i = 0;i < n;i++) 65 x1[i] = complex(s1[i]==ch,0); 66 for(int i = n;i < len;i++) 67 x1[i] = complex(0,0); 68 for(int i = 0;i < m;i++) 69 x2[i] = complex(s2[i]==ch,0); 70 for(int i = m;i < len;i++) 71 x2[i] = complex(0,0); 72 fft(x1,len,1); 73 fft(x2,len,1); 74 for(int i = 0;i < len;i++) 75 x1[i] = x1[i]*x2[i]; 76 fft(x1,len,-1); 77 for(int i = 0;i < len;i++) 78 num[i] = (long long)(x1[i].r+0.5); 79 for(int i = 0; i < len; i ++) 80 ans[i] += num[i]; 81 } 82 int main() { 83 cin >> n >> m; 84 cin >> s1 >> s2; 85 for(int i = 0; i < n; i ++) { 86 if(s1[i] == ‘R‘) s1[i] = ‘P‘; 87 else if(s1[i] == ‘P‘) s1[i] = ‘S‘; 88 else if(s1[i] == ‘S‘) s1[i] = ‘R‘; 89 } 90 for(int i = 0; i < m/2; i ++) swap(s2[i], s2[m-i-1]); 91 slove(‘R‘); 92 slove(‘S‘); 93 slove(‘P‘); 94 ll MAX = 0; 95 for(int i = m-1; i < n+m-1; i ++) MAX = max(MAX, ans[i]); 96 cout << MAX << endl; 97 return 0; 98 }
2017-2018 ACM-ICPC, Asia Daejeon Regional Contest
原文：https://www.cnblogs.com/xingkongyihao/p/9932439.html
