A.括号匹配

题意：问一个括号环，在某一点处剪开，是否能成为一个合法的括号序列。

题解：考虑左右括号数量是否相等即可。

证明：不会。

B. Oooooooo AAAAE

题解：二分图最小点权覆盖模板题，建议自行百度学习，一下子也很难讲清楚，但真的是模板题。

代码：

#include <bits/stdc++.h> #define mem(sx,sy) memset(sx,sy,sizeof(sx)) #define pa pair<int, int> typedef long long ll; typedef unsigned long long ull; const int MAXN = 1e5 + 100; const int MAXM = 2e6 + 5; const int INF = 0x3f3f3f3f; const int MOD = 1e9 + 7; const double PI = acos(-1); using namespace std; struct dinic { struct edge { int to, flow, nxt; } edges[MAXM]; int n, m, cnt, st, en; int head[MAXM], dis[MAXM], cur[MAXM]; void init(int _st, int _en, int _n) { st = _st, en = _en, n = _n; cnt = -1; mem(head, -1); } void addedge(int u, int v, int w) { // cout << " " << u << " " << v << " " << w << endl; edges[++cnt] = { v, w, head[u] }; head[u] = cnt; edges[++cnt] = { u, 0, head[v] }; head[v] = cnt; } int bfs() { queue<int> Q; mem(dis, 0); dis[st] = 1; Q.push(st); while (!Q.empty()) { int u = Q.front(); Q.pop(); if (u == en) return 1; for (int i = head[u]; i != -1; i = edges[i].nxt) { int v = edges[i].to, w = edges[i].flow; if (!dis[v] && w) { dis[v] = dis[u] + 1; Q.push(v); } } } return dis[en] != 0; } int dfs(int u, int flow) { int ret = flow, a; if (u == en || flow == 0) return flow; for (int &i = cur[u]; i != -1; i = edges[i].nxt) { int v = edges[i].to; if (dis[v] == dis[u] + 1 && (a = dfs(v, min(ret, edges[i].flow)))) { edges[i].flow -= a; edges[i ^ 1].flow += a; ret -= a; if (!ret) break; } } if (ret == flow) dis[u] = 0; return flow - ret; } int maxflow() { int ans = 0; while (bfs()) { for (int i = 1; i <= n; i++) cur[i] = head[i]; ans += dfs(st, INF); } return ans; } } G; int main() { int n, m; scanf("%d%d", &n, &m); int st = 2 * n + 1; int ed = st + 1; G.init(st, ed, ed); for (int i = 1, w; i <= n; i++) { scanf("%d", &w); G.addedge(n + i, ed, w); } for (int i = 1, w; i <= n; i++) { scanf("%d", &w); G.addedge(st, i, w); } while (m--) { int u, v; scanf("%d%d", &u, &v); G.addedge(u, v+n, INF); } printf("%d\n", G.maxflow()); }

C. 给你一个666

题意：给你一个数组，每次给你两个数字，经过一系列的操作后，问你一个区间内的最大和最小值。

题解：给你$a,b$,令$c$为$a$在二进制下的高3位乘$b$在二进制下的低3位，令$d$为$b$在二进制下的高三位乘$a$在二进制下的低3位， 即$c=(a/8)\ast (b\%8),d=(a\%8)\ast (b/8)$，区间左端点$l=min(a,b)\ast min(c,d)$,右端点$r=max(a,b)\ast max(c,d),$然后区间最值询问可以用ST表或者线段树。

巨坑：阅读理解，左端点越界时按1处理，右端点越界时按n处理，也就是假如 $l=r=n+1$，则也要使得$l=1,r=n$。

代码：

#include <bits/stdc++.h> #pragma warning(disable:4996); #define mem(sx,sy) memset(sx,sy,sizeof(sx)) #define pa pair<int, int> typedef long long ll; typedef unsigned long long ull; const int MAXN = 1e5 + 100; const int MAXM = 2e6 + 5; const int INF = 0x3f3f3f3f; const int MOD = 1e9 + 7; const double PI = acos(-1); using namespace std; int a[MAXN]; int dpmin[MAXN][20]; int dpmax[MAXN][20]; void RMQinit(int n) { for (int i = 1; i <= n; i++) { dpmin[i][0] = a[i]; dpmax[i][0] = a[i]; } int m = int(log((double)n) / log(2.0)); for (int i = 1; i <= m; i++) { for (int j = 1; j + (1 << i) - 1 <= n; j++) { dpmin[j][i] = min(dpmin[j][i - 1], dpmin[j + (1 << (i - 1))][i - 1]); dpmax[j][i] = max(dpmax[j][i - 1], dpmax[j + (1 << (i - 1))][i - 1]); } } } int Querymin(int l, int r) { int k = int(log(double(r - l + 1)) / log(2.0)); return min(dpmin[l][k], dpmin[r - (1 << k) + 1][k]); } int Querymax(int l, int r) { int k = int(log(double(r - l + 1)) / log(2.0)); return max(dpmax[l][k], dpmax[r - (1 << k) + 1][k]); } int main() { int n, k; scanf("%d%d", &n, &k); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } RMQinit(n); while (k--) { int a, b; scanf("%d%d", &a, &b); int ah = a / 8, al = a % 8; int bh = b / 8, bl = b % 8; int c = ah * bl, d = al * bh; int l = min(c, d) * min(a, b); int r = max(c, d) * max(a, b); l = max(1, l); r = min(n, r); printf("%d %d\n", Querymax(l, r), Querymin(l, r)); } }

D. LiMn2O4的数学之路

题意：该公式为斐波那契额数列的通项公式，然后问你斐波那契额数列的第$n(n<10^9)$项。

题解：矩阵快速幂裸题，建议自己百度学习。

E. Spinach和发牌姬

题意：大模拟。

题解：按照题意模拟即可，（我就剩这一道还没过了qaq

F. 猜球球

题意：有n个盒子，有个小球小球出现在每个盒子的概率为p[i]，你现在可以问类似（小球是否在盒子{1,4,……,n}中？）（1-n的一个子集）的问题，问策略最优情况下，猜出小球所在盒子的猜测次数的数学期望。

官方题解：因为任意一次询问和回答，都可以确定其中一半的球球集合包含目标球，另一半则不包含目标球。然后再对包含目标球的球球集合进一步划分，直到包含目标球的集合里只包含一个球，就可以百分百确定了。这样就得到了一个决策树（二叉形状），二叉决策树根节点到每个叶子的路到都是期中一种情况的解决方案，显然深度就是询问次数。 则有：期望=∑(询问次数每种情况出现的概率)=∑(叶子对应的深度它出现在盒子里的概率)。 而我们知道：这个公式 ∑（深度*元素出现的概率 ） 与某种编码方案的编码长度期望公式 相同。询问次数的期望最小也就是编码长度的期望最小。而解决这个问题的经典方法就是——哈夫曼树。（https://blog.csdn.net/GreyBtfly/article/details/89456514）

一句话总结：构造一棵哈夫曼树，然后有$ans=\sum _{i=1}^{n}p[i]\ast deep[i]$

但我这里有段更加简短优美的代码：

#include <bits/stdc++.h> #pragma warning(disable:4996); #define mem(sx,sy) memset(sx,sy,sizeof(sx)) typedef long long ll; typedef unsigned long long ull; const double eps = 1e-8; const int MAXN = 5000 + 5; const int MAXM = 2e6 + 5; const int MOD = 1e9 + 7; const int INF = 0x3f3f3f3f; const double PI = acos(-1); using namespace std; #define pa pair<double, int> vector<int> G[MAXN]; double a[MAXN]; double ans = 0; void dfs(int cur, int d) { if (G[cur].size() == 0) ans += a[cur] * d; for (auto it : G[cur]) { dfs(it, d + 1); } } int main() { int n; scanf("%d", &n); priority_queue<pa, vector<pa>, greater<pa> >Q; for (int i = 1; i <= n; i++) { scanf("%lf", &a[i]); if (a[i] == 0) { n--; i--; continue; } Q.push(pa(a[i], i)); } int cnt = n; while (Q.size() >= 2) { pa t1 = Q.top(); Q.pop(); pa t2 = Q.top(); Q.pop(); pa np(t1.first + t2.first, ++cnt); Q.push(np); G[cnt].push_back(t1.second); G[cnt].push_back(t2.second); } int root = Q.top().second; dfs(root, 0); printf("%.7lf\n", ans); } /* 3 0.5 0.25 0.25 4 0.3 0.3 0.2 0.2 */

G. 似魔鬼的步伐

题意：你有$n$块钱，初始能力$ans=0$，你可以花一块钱使得$ans=ans+1$，或者花两块钱使得$ans=2\ast ans+2$，问$ans$最大值。

题解：贪心，花一个两块 比 花两个一块要赚，n为偶数的话一直花两块即可，n为奇数的话先花一个一块，然后一直花两块，数据范围较小，矩阵快速幂都不用。

H. 挑剔程度

题意：n个值，你可以最多去掉k个值，问剩下的最大值。

题解：温暖的签到题，排个序就可以了，注意k是可以大于n的。

I. 热狗树

题意：有一棵点权为0或1的树，问所有0的点到所有1的距离和以及所有1的点到所有0的距离和。

题解：树形dp，设$num[0]$和$num[1]$分别为点权为0或者1的点的个数，由dp可以得到$u$号节点的$siz[0][u]$和$siz[1][u]$分别为$u$节点子树点权为0和子树点权为1的点的个数，则对于某一个点u，其连着他爸爸的那条边的边权为w，则这条边对于答案的贡献为

$ans+=w\ast (siz[0]\ast (num[1]-siz[1])+siz[1]\ast (num[0]-siz[0]))$

至于为什么你们自己稍微想一想应该就能理解了！（考虑一条边将一棵树分成了两个部分）记得取模。

代码：

#include <bits/stdc++.h> #pragma warning(disable:4996); #define mem(sx,sy) memset(sx,sy,sizeof(sx)) #define pa pair<int, int> typedef long long ll; typedef unsigned long long ull; const int MAXN = 2e5 + 5; const int MAXM = 2e6 + 5; const int INF = 0x3f3f3f3f; const double PI = acos(-1); const int MOD = 998244353; using namespace std; vector<pa> G[MAXN]; int a[MAXN]; int siz01[MAXN]; int siz[2][MAXN]; ll ans = 0; int n, sz[2] = { 0,0 }; void dfs1(int cur, int fa) { siz[a[cur]][cur] = 1; for (auto it : G[cur]) { int v = it.first; if (v == fa) continue; dfs1(v, cur); siz[0][cur] += siz[0][v]; siz[1][cur] += siz[1][v]; } } void dfs2(int cur, int fa) { for (auto it : G[cur]) { int v = it.first; int w = it.second; if (v == fa) continue; ans += 1ll * siz[1][v] * (sz[0] - siz[0][v]) % MOD * w; ans %= MOD; ans += 1ll * siz[0][v] * (sz[1] - siz[1][v]) % MOD * w; ans %= MOD; dfs2(v, cur); } } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); sz[a[i]]++; } for (int i = 1, u, v, w; i < n; i++) { scanf("%d%d%d", &u, &v, &w); G[u].emplace_back(v, w); G[v].emplace_back(u, w); } dfs1(1, 0); dfs2(1, 0); printf("%lld\n", ans * 2 % MOD); }

J. 流浪西邮之寻找火石碎片

题意：n件物品，每件有两个不同的货币的价格c1，c2，你可以使用任意一种货币购买它，和其价值v，你现在有两种货币a，b（对应c1，c2）你现在还能免费拿k件物品，问最大价值是多少。

考虑二维01背包，再加一维霸王餐，令$dp[i][x][y][j]$为第i件物品，花费x单位的第一种货币，y单位的第二种货币，用了j次霸王餐的最大值，则有暴力转移：

$dp[i][x][y][j]=max(dp[i-1][x][y][j],dp[i-1][x-c1[i]][y][j]+v[i],dp[i-1][x][y-c2[i]][j]+v[i],dp[i-1][x][y][j-1]+v[i])$

转移考虑清楚后就像01背包那样写就行了，数据范围不大，空间够用，不用优化，注意史诗级wa点：多组输入。

代码：

#include <bits/stdc++.h> #pragma warning(disable:4996); #define mem(sx,sy) memset(sx,sy,sizeof(sx)) #define pa pair<int, int> typedef long long ll; typedef unsigned long long ull; const int MAXN = 1e5 + 100; const int MAXM = 2e6 + 5; const int INF = 0x3f3f3f3f; const int MOD = 1e9 + 7; const double PI = acos(-1); using namespace std; int dp[105][105][105][10]; int c1[105], c2[105], v[105]; int main() { int n, m1, m2, k; while (~scanf("%d%d%d%d", &n, &m1, &m2, &k)) { for (int i = 1; i <= n; i++) { scanf("%d%d%d", &c1[i], &c2[i], &v[i]); } int ans = 0; mem(dp, 0); for (int i = 1; i <= n; i++) { for (int x = 0; x <= m1; x++) { for (int y = 0; y <= m2; y++) { for (int j = 0; j <= k; j++) { dp[i][x][y][j] = dp[i - 1][x][y][j]; if (x >= c1[i]) { dp[i][x][y][j] = max(dp[i][x][y][j], dp[i - 1][x - c1[i]][y][j] + v[i]); } if (y >= c2[i]) { dp[i][x][y][j] = max(dp[i][x][y][j], dp[i - 1][x][y - c2[i]][j] + v[i]); } if (j > 0) { dp[i][x][y][j] = max(dp[i][x][y][j], dp[i - 1][x][y][j - 1] + v[i]); } ans = max(dp[i][x][y][j], ans); } } } } printf("%d\n", ans); } }

K. 到底有多少个小和尚?

题意：给你a,b，计算$ans=\sum _{i=a}^{b}i\ast (i+1)$。

题解：温暖的签到题，前缀和搞搞就行了。

。

。

总结，比赛较为温暖，几乎没有什么难题，但坑点很多导致比赛体验极差，比如一半题不要多组输入，另一半题要多组输入，比如1e5的cin能T成傻逼，比如语文阅读理解，再比如B的样例出锅……让我前后在这种地方wa了30几发，网络赛还好，要是现场赛估计已经被队友打死了。