本文共 11181 字，大约阅读时间需要 37 分钟。
转载请将本段放在文章开头显眼处，如有二次创作请标明。
原文链接：放假后的第一场比赛，深夜场。
Div3开小号打了，开始状态奇差，后来还可以，A-E都一发过了，没罚多少时，但开局不利，Rank没进500.整体有一定的思维难度，质量不错的题目。这次的 A 题做出人数比 B 题还少，卡了我20min……
给出\(x = \max(a,b)\)，\(y = \max(a,c)\)，\(z = \max(b,c)\) 要求找到任意一组符合条件的 \(a,b,c\)一开始想分类讨论没想清楚，后来官方发了个 Announcement 说输出顺序任意，就想到怎么打了。
首先可以确定最大的数，确定最大的数后，最大的数一定出现两次。
那么剩下那个数就是第二大的数，最小的数取 \(1\) 即可。
#include#include #include const int bufSize = 1e6;inline char nc(){ #ifdef DEBUG return getchar(); #endif static char buf[bufSize], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;}inline void read(char *s){ static char c; for (; !isalpha(c); c = nc()); for (; isalpha(c); c = nc()) *s++ = c; *s = '\0';}template inline T read(T &r){ static char c; static int flag; flag = 1, r = 0; for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1; for (; isdigit(c); c = nc()) r = r * 10 + c - 48; return r *= flag;}int T;int a[4];int main(){ read(T); while(T--) { for(int i = 1;i<=3;++i) read(a[i]); std::sort(a + 1,a + 4); int maxx = a[3]; if(a[2] != a[3]) { puts("NO"); goto end; } puts("YES"); printf("%d %d %d\n",maxx,a[1],1); end:; } return 0;}
B 题的数据范围看上去似乎想让人用暴力，但其实是个 \(O(n)\) 的结论题。
观察样例发现，只取序列中首次出现的数，就能还原数组。现在我们证明这个结论：
第一个数一定是原数组的第一个数。
将数组中所有出现的第一个数删除后，原先偏序不变。
随后问题即缩小成子问题，依次求解。
删除过程等价于打个值标记，每次取第一个数其实就是顺序遍历。
#include#include #include const int bufSize = 1e6;inline char nc(){ #ifdef DEBUG return getchar(); #endif static char buf[bufSize], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;}inline void read(char *s){ static char c; for (; !isalpha(c); c = nc()); for (; isalpha(c); c = nc()) *s++ = c; *s = '\0';}template inline T read(T &r){ static char c; static int flag; flag = 1, r = 0; for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1; for (; isdigit(c); c = nc()) r = r * 10 + c - 48; return r *= flag;}int T,n;const int maxn = 120;int a[maxn],vis[maxn];int main(){ read(T); while(T--) { read(n); for(int i = 1;i<=n;++i) vis[i] = 0; for (int i = 1; i <= n * 2; ++i) { int x; read(x); if(!vis[x]) vis[x] = 1,printf("%d ",x); } putchar('\n'); } return 0;}
首先考虑 \(b\) 数组的性质，要求每次取头尾元素，所取元素单调不减。
那么一定存在一个峰点，峰点左边元素单调不减，峰点右边元素单调不增。
否则，如果存在双峰点，那么某个峰点内侧的元素就会比其小，从而不满足要求。
那么解法就简单了，从后往前找到第一个峰点，从峰点向前找到第二个峰点，删除第二个峰点即其左边的元素即可。
#include#include #include const int bufSize = 1e6;inline char nc(){ #ifdef DEBUG return getchar(); #endif static char buf[bufSize], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;}inline void read(char *s){ static char c; for (; !isalpha(c); c = nc()); for (; isalpha(c); c = nc()) *s++ = c; *s = '\0';}template inline T read(T &r){ static char c; static int flag; flag = 1, r = 0; for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1; for (; isdigit(c); c = nc()) r = r * 10 + c - 48; return r *= flag;}const int maxn = 2e5 + 100;int T,n;int a[maxn],f[maxn];int front[maxn],back[maxn];int main(){ read(T); while(T--) { read(n); for (int i = 1; i <= n; ++i) read(a[i]); int top = n; while(top > 1 && a[top - 1] >= a[top]) --top; int head = top; while(head > 1&& a[head - 1] <= a[head]) --head; printf("%d\n",head - 1); } return 0;}
阅读题面，发现好串的定义就是在提示使用分治做法。
每次可以假设左边全是 \(c\) 或右边全是 \(c\)，计算相应的代价，取最小值即可。
这样处理过程就像遍历一棵线段树一样，复杂度 \(O(2n)\)。
计算代价可以用前缀和快速处理。
#include#include #include #define int long longconst int bufSize = 1e6;inline char nc(){ #ifdef DEBUG return getchar(); #endif static char buf[bufSize], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;}inline void read(char *s){ static char c; for (; !isalpha(c); c = nc()); for (; isalpha(c); c = nc()) *s++ = c; *s = '\0';}template inline T read(T &r){ static char c; static int flag; flag = 1, r = 0; for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1; for (; isdigit(c); c = nc()) r = r * 10 + c - 48; return r *= flag;}const int maxn = 2e5 + 100;char s[maxn];int sum[maxn][26];int T,n;inline int solve(int l,int r,int c){ if(l == r) return c != s[l]; int mid = l + r >> 1; int left = solve(l,mid,c + 1),right = solve(mid + 1,r,c + 1); int lval = left + r - mid - (sum[r][c] - sum[mid][c]); int rval = right + (mid - l + 1) - (sum[mid][c] - sum[l - 1][c]); return std::min(lval,rval);}signed main(){ read(T); while(T--) { read(n); read(s + 1); for(int i = 1;i<=n;++i) s[i] -= 'a'; for (int i = 1; i <= n; ++i) { for (int j = 0; j < 26; ++j) sum[i][j] = sum[i - 1][j]; sum[i][s[i]]++; } printf("%lld\n",solve(1,n,0)); } return 0;}
给定一个有向图，给一些无向边，要为无向边决定方向，使最终图是个有向无环图。
一开始想在原图上乱搜一通，然后试错法乱选方向，样例都没过去……
但可以发现，无论如何，都是从给定的有向图的性质入手。
如果原图含有环，一定是 NO，否则一定是 YES。
有向无环图才有拓扑排序，而如果最终图有拓扑排序，它就是有向无环图。
对原图进行拓扑排序，顺便判环。
对于每条无向边，按照拓扑排序的顺序决定方向即可。
代码写得乱了点。
#include#include #include const int bufSize = 1e6;inline char nc(){#ifdef DEBUG return getchar();#endif static char buf[bufSize], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;}inline void read(char *s){ static char c; for (; !isalpha(c); c = nc()); for (; isalpha(c); c = nc()) *s++ = c; *s = '\0';}template inline T read(T &r){ static char c; static int flag; flag = 1, r = 0; for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1; for (; isdigit(c); c = nc()) r = r * 10 + c - 48; return r *= flag;}const int maxn = 2e5 + 100, maxm = maxn << 1;struct node{ int from, to, next, directed;} E[maxm];int head[maxn], tot;inline void add(const int &x, const int &y, const int &t){ E[++tot].next = head[x], E[tot].from = x, E[tot].to = y, E[tot].directed = t, head[x] = tot;}int T, n, m;int in[maxn];int q[maxn], qh, qt, id[maxn], vis[maxn], cnt, ans;inline void topo(){ qh = 1, qt = 0; for (int i = 1; i <= n; ++i) if (!in[i]) q[++qt] = i; while (qt >= qh) { if(ans) return; int u = q[qh++]; id[u] = ++cnt, vis[u]++; // printf("inq:%d\n",u); for (int p = head[u]; p; p = E[p].next) { if (!E[p].directed) continue; int v = E[p].to; if (--in[v] == 0) q[++qt] = v; if (in[v] < 0) ans = 1; // printf("in:%d %d\n",v,in[v]); } } // for(int i = 1;i<=n;++i) printf("%d %d %d\n",i,id[i],vis[i]);}int main(){ read(T); while (T--) { ans = tot = cnt = 0; read(n), read(m); for (int i = 1; i <= n; ++i) vis[i] = head[i] = 0, in[i] = 0; for (int i = 1; i <= m; ++i) { int t, a, b; read(t), read(a), read(b); add(a, b, t); if (t) in[b]++; } topo(); if(ans) {puts("NO"); goto end;} for (int i = 1; i <= n; ++i) if (!id[i] || vis[i] != 1){puts("NO");goto end;} puts("YES"); for (int i = 1; i <= m; ++i) { if (E[i].directed) printf("%d %d\n", E[i].from, E[i].to); else if (id[E[i].from] < id[E[i].to]) printf("%d %d\n", E[i].from, E[i].to); else printf("%d %d\n", E[i].to, E[i].from); } continue; end:; } return 0;}
这题赛中没做出来，现在也没来得及补正解，随便口胡两句。
该解法是错误的，第二个pretest就WA了QAQ
主要原因是看错题了。要求删除的叶子都在同一点上，我以为是任选……
以下解法看看就好，愚蠢的代码也贴上来吧。
每次删除恰好 \(k\) 个叶子，很容易让人想到贪心。
如果一个节点恰好与 \(x\) 个叶子相连，那么删除这 \(x\) 个叶子后它将成为叶子。将这种即为一类点。
将所有一类点放入堆中，按 \(x\) 升序排序。
也将所有与叶子相连的、不全与叶子相连的点放入堆中，优先级最低，即放在尾部。将这类点记为二类点。
选取 \(k\) 个叶子时，从堆顶取出：
如果 \(x \leq k\)，那么该节点会成为叶子，检查它的父亲是否能成为一类点，如果可以放入堆中，否则作为二类点放入堆中。
如果 \(x > k\)，那么该节点会取部分，且当前次取叶子成功。更新在堆中的状态。
用配对堆来维护即可。