题目链接 第十六届北京师范大学程序设计竞赛决赛
一句话总结：迟到选手抢到FB之后进入梦游模式最后因为忘加反向边绝杀失败……
好吧其实还是自己太弱
下面进入正题
Problem A
签到题（读题是一件非常有趣事情）
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i) #define dec(i, a, b) for (int i(a); i >= (b); --i) #define MP make_pair #define fi first #define se second typedef long long LL; int main(){ int T; string s; scanf("%d", &T); while (T--){ int n; scanf("%d", &n); int fg = 1; rep(i, 1, n){ cin >> s; if (s != "PERFECT") fg = 0; } puts(fg ? "MILLION Master" : "NAIVE Noob"); } return 0; }
Problem B
设读进来的那个序列为$b_{i}$
要还原出的那个序列答案为$a_{i}$
我们求出$a_{i}$对$b_{i}$每一项的贡献就可以了。
这个过程实现起来不难。
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i) #define dec(i, a, b) for (int i(a); i >= (b); --i) typedef long long LL; const LL mod = 1e9 + 7; const int N = 1e3 + 10; int T; int n; LL a[N], b[N], c[N]; LL k; inline LL Pow(LL a, LL b, LL mod){ LL ret(1); for (; b; b >>= 1, (a *= a) %= mod) if (b & 1) (ret *= a) %= mod; return ret; } void pre(){ int cnt = 0; c[++cnt] = 1; LL now = 1; rep(i, 1, n - 1){ now = now * (k + i - 1) % mod; now = now * Pow((LL)i, mod - 2, mod) % mod; c[++cnt] = now; } } int main(){ scanf("%d", &T); while (T--){ scanf("%d%lld", &n, &k); memset(c, 0, sizeof c); pre(); rep(i, 1, n) scanf("%lld", b + i); a[1] = b[1]; rep(i, 1, n){ int cnt = 0; rep(j, i, n){ ++cnt; b[j] -= (c[cnt] * a[i] % mod); b[j] += mod; b[j] %= mod; } a[i + 1] = b[i + 1]; } rep(i, 1, n - 1) printf("%lld ", a[i]); printf("%lld\n", a[n]); } return 0; }
Problem C
打表之后找规律
#include<bits/stdc++.h> using namespace std; int T; int n; int main(){ cin >> T; while (T--){ cin >> n; cout << fixed << setprecision(10) << (n * n - 1) / 3.0 << endl; } return 0; }
Problem D
这个DP转移
每个点有两种转移的方向，每个方向取最近的那个点就好了。
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i) #define dec(i, a, b) for (int i(a); i >= (b); --i) #define MP make_pair #define fi first #define se second typedef long long LL; const int N = 1e5 + 10; int T; int n, m, k; LL a[N], b[N], c[N], f[N], g[N], h[N]; map <LL, LL> mp; set <LL> s; int main(){ scanf("%d", &T); while (T--){ scanf("%d%d%d", &n, &m, &k); rep(i, 1, n) scanf("%lld", a + i); rep(i, 1, m) scanf("%lld", b + i); rep(i, 1, k) scanf("%lld", c + i); rep(i, 1, n) f[i] = 1; rep(i, 1, m) g[i] = 1e15; mp.clear(); rep(i, 1, n) mp[a[i]] = f[i]; mp[1e18] = 1e18, mp[-1e18] = 1e18; s.clear(); rep(i, 1, n) s.insert(a[i]); s.insert(1e18); s.insert(-1e18); rep(i, 1, m){ LL xx = b[i]; auto it = s.lower_bound(xx); g[i] = min(g[i], mp[*it] + abs((*it) - xx) + 1); --it; g[i] = min(g[i], mp[*it] + abs((*it) - xx) + 1); } rep(i, 1, k) h[i] = 1e15; mp.clear(); rep(i, 1, m) mp[b[i]] = g[i]; mp[1e18] = 1e18, mp[-1e18] = 1e18; s.clear(); rep(i, 1, m) s.insert(b[i]); s.insert(1e18); s.insert(-1e18); rep(i, 1, k){ LL xx = c[i]; auto it = s.lower_bound(xx); h[i] = min(h[i], mp[*it] + abs((*it) - xx) + 1); --it; h[i] = min(h[i], mp[*it] + abs((*it) - xx) + 1); } LL ans = 1e18; rep(i, 1, k) ans = min(ans, h[i]); printf("%lld\n", ans); } return 0; }
Problem E
考虑到长度为$k$的子序列个数不超过$10^{5}$，那么直接暴力，搜索深度不超过$9$。
注意：$k$比较大的时候考虑反面即可。
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i) #define dec(i, a, b) for (int i(a); i >= (b); --i) #define MP make_pair #define fi first #define se second typedef long long LL; const int N = 1e5 + 10; int T; int n, k; int z; int c[N]; LL a[N]; LL ans; void check(LL x){ LL vv = x * x; ans ^= vv; } void dfs(int x, LL now){ if (x > k){ check(now); return; } else{ rep(i, z, n){ int la = z; z = i + 1; dfs(x + 1, now + a[i]); z = la; } } } void dfs2(int x, LL now){ if (x > k){ check(now); return; } else{ rep(i, z, n){ int la = z; z = i + 1; dfs2(x + 1, now - a[i]); z = la; } } } int main(){ scanf("%d", &T); while (T--){ scanf("%d%d", &n, &k); LL sum = 0; rep(i, 1, n) scanf("%lld", a + i), sum += a[i]; z = 1; ans = 0; if (k > n - k){ k = n - k; dfs2(1, sum); } else{ dfs(1, 0); } printf("%lld\n", ans); } return 0; }
Problem F
显然答案是单调的。
二分答案，把那些符合条件的汤圆一个个加入队列，然后BFS，到最后如果所有汤圆都被删除了，那么该答案可行。
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i) #define dec(i, a, b) for (int i(a); i >= (b); --i) #define MP make_pair #define fi first #define se second typedef long long LL; typedef pair <int, LL> PII; const int N = 1e5 + 10; int T; int n, m; int vis[N], inq[N]; LL a[N], bb[N]; LL l, r; vector <PII> v[N]; bool check(LL now){ queue <int> q; memset(vis, 0, sizeof vis); memset(inq, 0, sizeof inq); rep(i, 1, n) bb[i] = a[i]; rep(i, 1, n) if (bb[i] <= now) q.push(i), inq[i] = 1; while (!q.empty()){ int x = q.front(); vis[x] = 1; q.pop(); inq[x] = 0; for (auto edge : v[x]){ int u = edge.fi; LL w = edge.se; if (vis[u]) continue; bb[u] -= w; if (bb[u] <= now){ if (!inq[u]) q.push(u), inq[u] = 1; } } } rep(i, 1, n) if (!vis[i]) return false; return true; } int main(){ scanf("%d", &T); while (T--){ scanf("%d%d", &n, &m); rep(i, 0, n + 1) v[i].clear(); rep(i, 0, n + 1) a[i] = 0; rep(i, 1, m){ int x, y; LL z; scanf("%d%d%lld", &x, &y, &z); v[x].push_back({y, (LL)z}); v[y].push_back({x, (LL)z}); a[x] += z; a[y] += z; } l = 0, r = 1e14; while (l + 1 < r){ LL mid = (l + r) / 2ll; if (check(mid)) r = mid; else l = mid + 1; } if (check(l)) printf("%lld\n", l); else printf("%lld\n", r); } return 0; }
Problem G
模拟题，没什么好说的。（我还是WA了好几发）
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i) #define dec(i, a, b) for (int i(a); i >= (b); --i) #define MP make_pair #define fi first #define se second typedef long long LL; char s[24]; bool ff[24]; int T; bool upper(char c){ return c >= 'A' && c <= 'Z'; } bool check(int n){ bool re = 1; bool flag = 0; int cnt = 0; if (!upper(s[0])) s[0] += 'A' - 'a', flag = 1; rep(i, 1, n - 1){ if (upper(s[i]) && upper(s[i - 1])) re = 0; if (upper(s[i])) cnt++, ff[i] = 1; } if (flag) s[0] += 'a' - 'A'; return re && (cnt) && !upper(s[n - 1]); } int main(){ cin >> T; while (T--){ scanf("%s", &s); memset(ff, 0, sizeof ff); int n = strlen(s); if (check(n)){ rep(i, 0, n - 1){ if (ff[i]) putchar('_'); if (upper(s[i])) s[i] += 'a' - 'A'; putchar(s[i]); } putchar(10); } else puts(s); } return 0; }
Problem H
数据结构题，留坑。
Problem I
每次交换相邻的两个不一样的元素会使整个序列的逆序对数改变$1$
那么计算一下逆序对个数就好了。
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i) #define dec(i, a, b) for (int i(a); i >= (b); --i) #define MP make_pair #define fi first #define se second typedef long long LL; const int N = 1e6 + 10; int T; int n; int a[N]; char s[N]; LL k; int main(){ scanf("%d", &T); while (T--){ scanf("%d%lld", &n, &k); scanf("%s", s + 1); rep(i, 1, n) a[i] = (s[i] == 'D'); LL cc = 0; rep(i, 1, n) cc += a[i]; LL ju = 1ll * cc * (LL)(n - cc); if (ju < k) { puts("-1"); continue; } LL cnt = 0, ss = 0; rep(i, 1, n){ if (a[i] == 0) cnt += ss; ss += a[i]; } printf("%lld\n", abs(cnt - k)); } return 0; }
Problem J
计算几何，留坑。
Problem K
留坑。
转载于:https://www.cnblogs.com/cxhscst2/p/8722580.html
相关资源：各显卡算力对照表！