2017-2018 ACM-ICPC, Asia Daejeon Regional Contest
分类:
IT文章
•
2023-11-02 13:43:43
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 }
View Code
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
");
21 if(mp.count(n)) break;
22 mp[n] = 1;
23 }
24 printf("UNHAPPY
");
25 return 0;
26 }
View Code
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
",p.x,p.y);
41 return 0;
42 }
View Code
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 }
View Code
