比赛前提前一个小时去了机房,为什么呢?因为 Switch 就应该在寝室以外的地方玩
玩了会【星之卡比探索发现】,接着玩了会【动物森友会】
比赛时 比赛链接
先看了一圈题,最后又从 开始做
A 简单的逆序对问题 + 离散化
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 #include <bits/stdc++.h> struct node { int l,r,id; }; bool cmp (node x,node y) { return x.l < y.l; } int f[300000 ];int lowbit (int x) { return x & -x; } void add (int x,int val) { for (int i = x; i <= 200000 ; i += lowbit (i)) f[i] += val; } int query (int x) { int sum = 0 ; for (int i = x; i ; i -= lowbit (i)) sum += f[i]; return sum; } int main () { int n; std::cin >> n; std::vector<node> a (n) ; std::vector<int > ans (n) ; std::vector<int > hash (n) ; int cnt = 0 ; for (int i = 0 ; i < n; i++) { std::cin >> a[i].l >> a[i].r; hash[i] = a[i].r; a[i].id = i; } std::sort (a.begin (), a.end (), cmp); std::sort (hash.begin (), hash.end ()); for (int i = n - 1 ; i >= 0 ; i--) { int l = 0 , r = n - 1 ; int pos = 0 ; while (l <= r) { int mid = (l + r) >> 1 ; if (hash[mid] < a[i].r) l = mid + 1 ; else if (hash[mid] > a[i].r) r = mid - 1 ; else if (hash[mid] == a[i].r) { pos = mid; break ; } } pos++; ans[a[i].id] = query (pos); add (pos, 1 ); } for (int i = 0 ; i < n; i++) std::cout << ans[i] << '\n' ; }
C 小学数学题,思想出问题了,错了两次
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include <bits/stdc++.h> #define LL long long int main () { LL n,a,b; std::cin >> n >> a >> b; for (LL i = 2 ; i * i <= b; i++) { while (a % i == 0 && b % i == 0 ) { a /= i; b /= i; } } std::vector<LL> x (n) ; for (LL i = 0 ; i < n; i++) std::cin >> x[i]; for (LL i = 0 ; i < n; i++) { LL pos = x[i] * a / b; LL p = pos * b; LL ans = x[i] - (p / a) - (p % a != 0 ); std::cout << ans << ' ' ; } }
G 找找规律,不难发现数字只能在副对角线上移动
简单统计判断一下就行
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #include <bits/stdc++.h> int n,m;int a[2000 ][2000 ],b[2000 ][2000 ];int main () { std::cin >> n >> m; for (int i = 1 ; i <= n; i++) for (int j = 1 ; j <= m; j++) std::cin >> a[i][j]; for (int i = 1 ; i <= n; i++) for (int j = 1 ; j <= m; j++) std::cin >> b[i][j]; bool flag = true ; for (int j = 1 ; j <= 1000 ; j++) { std::priority_queue<int > A,B; for (int i = 1 ; j - i + 1 > 0 ; i++) { A.push (a[i][j - i + 1 ]); B.push (b[i][j - i + 1 ]); } while (!A.empty ()) { if (A.top () != B.top ()) flag = false ; A.pop ();B.pop (); } } if (flag) std::cout << "YES" ; else std::cout << "NO" ; return 0 ; }
E 简单模拟
多进行个 1e6
次就差不多行了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 #include <bits/stdc++.h> #define LL long long int main () { int a,b,c,d; std::cin >> a >> b >> c >> d; long double x,y,z,ans = 0 ; x = (long double ) a / b; y = (long double ) c / d; z = 1 ; for (int i = 1 ; i <= 1e6 ; i++) { ans += z * x; z = z * (1 - x) * (1 - y); } printf ("%.12Lf\n" ,ans); }
F 简单模拟
找到度数最大的点,需要的颜色数量为度数 + 1
然后 一次就行
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 #include <bits/stdc++.h> int n,root = 1 ,ans;std::vector<std::vector<int >> To; std::vector<int > color; void dfs (int u,int fa) { std::vector<bool > book (ans + 1 ) ; book[color[fa]] = true ; book[color[u]] = true ; int cnt = 1 ; for (int v : To[u]) { if (v == fa) continue ; while (book[cnt]) cnt++; color[v] = cnt; dfs (v,u); book[cnt] = true ; } } int main () { std::cin >> n; To.resize (n + 1 ); color.resize (n + 1 ); for (int i = 1 ; i < n; i++) { int x,y; std::cin >> x >> y; To[x].push_back (y); To[y].push_back (x); } for (int i = 1 ; i <= n; i++) { if (To[i].size () > To[root].size ()) root = i; } ans = To[root].size () + 1 ; color[root] = 1 ; dfs (root, 0 ); std::cout << ans << '\n' ; for (int i = 1 ; i <= n; i++) std::cout << color[i] << ' ' ; }
B 简单
前缀和记录一下
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include <bits/stdc++.h> const int mod = 1e9 +7 ;int f[100010 ],ans[100010 ];int main () { int t,k; std::cin >> t >> k; f[0 ] = 1 ; for (int i = 1 ; i <= 100000 ; i++) { f[i] = (f[i] + f[i - 1 ]) % mod; f[i] = (f[i] + f[i - k]) % mod; } ans[0 ] = 0 ; for (int i = 1 ; i <= 100000 ; i++) ans[i] = (ans[i - 1 ] + f[i]) % mod; for (int i = 1 ; i <= t; i++) { int a,b; std::cin >> a >> b; int ANS = (ans[b] - ans[a - 1 ] + mod) % mod; std::cout << ANS << '\n' ; } }
D 简单模拟
似乎不能开 2e5
个 queue
,会莫名死机,返回信息却是 WA
,挺恶心的。。。
合法的序列需要满足的条件有
深度单调不下降
当前的点对应的父亲节点应该是满足一定序列的
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 #include <bits/stdc++.h> int n;std::vector<std::vector<int >> To; std::vector<int > deep,Fa,a; void dfs (int u,int fa) { deep[u] = deep[fa] + 1 ; for (int v : To[u]) { if (v == fa) continue ; Fa[v] = u; dfs (v,u); } } int main () { std::cin >> n; To.resize (n + 1 ); deep.resize (n + 1 ); Fa.resize (n + 1 ); a.resize (n + 1 ); for (int i = 1 ; i < n; i++) { int u,v; std::cin >> u >> v; To[u].push_back (v); To[v].push_back (u); } for (int i = 1 ; i <= n; i++) std::cin >> a[i]; dfs (1 , 0 ); bool flag = true ; int Dp = 0 ; for (int i = 1 ; i <= n; i++) { int u = a[i]; if (deep[u] < Dp) flag = false ; if (deep[u] > Dp) Dp = deep[u]; } if (flag) { std::queue<int > q[2 ]; int cnt = 0 ; int now = 0 ,DP = 1 ; for (int i = 1 ; i <= n; i++) { int u = a[i], Deep = deep[u]; if (Deep == 1 ) { q[now].push (u); continue ; } if (Deep != DP) { DP = Deep; now ^= 1 ; } if (To[u].size () != 1 ) q[now].push (u); int ls = q[now ^ 1 ].front (); if (Fa[u] != ls) { flag = false ; break ; } cnt++; if (deep[ls] == 1 && cnt == To[ls].size ()) { q[now ^ 1 ].pop (); cnt = 0 ; } if (deep[ls] != 1 && cnt + 1 == To[ls].size ()) { q[now ^ 1 ].pop (); cnt = 0 ; } } } if (flag) std::cout << "Yes" ; else std::cout << "No" ; return 0 ; }
H 状压
预处理可能的情况,最多也不过是 1e2
的数量级,实测应该在 60
左右
然后四重循环
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 #include <bits/stdc++.h> int N,M,ans;std::string a[110 ]; int s[110 ];int use[100 ],sum[100 ],cnt;int f[110 ][70 ][70 ];void DFS (int x,int step) { if (step >= M) { use[++cnt] = x; int S = 0 ; for (int i = 0 ; i < M; i++) if (x & (1 << i)) S++; sum[cnt] = S; return ; } bool flag = true ; if (step >= 1 && (x & (1 << (step - 1 )) ) ) flag = false ; if (step >= 2 && (x & (1 << (step - 2 )) ) ) flag = false ; DFS (x,step + 1 ); if (flag) DFS (x | (1 << step),step + 1 ); } int main () { std::cin >> N >> M; for (int i = 1 ; i <= N; i++) { std::cin >> a[i]; for (int j = 0 ; j < M; j++) if (a[i][j] == 'H' ) s[i] |= 1 << j; } DFS (0 ,0 ); for (int i = 1 ; i <= N; i++) { for (int j = 1 ; j <= cnt; j++) { if (s[i] & use[j]) continue ; for (int k = 1 ; k <= cnt; k++) { if (use[j] & use[k]) continue ; for (int p = 1 ; p <= cnt; p++) { if (use[j] & use[p]) continue ; f[i][j][k] = std::max (f[i][j][k], f[i - 1 ][k][p] + sum[j]); } } } } int ans = 0 ; for (int i = 1 ; i <= cnt; i++) for (int j = 1 ; j <= cnt; j++) ans = std::max (ans,f[N][i][j]); std::cout << ans << '\n' ; return 0 ; }
比赛后 为了看 提前一个小时 然后溜了
顺便取了个快递:喷射战士2!!!