[套题记录]Codeforces Global Round 14

刷着刷着就要刷完了…… 有一些其他题混入其中。 # [DP] E Phoenix and Computers **题意** ： 给定 $n$ ，有 $n$ 个电脑排成一排。 初始时所有电脑都关机，你要**按某种顺序**手动开电脑，使得最终所有电脑都被开启位置。 若某电脑两侧的电脑都开机，这台电脑会立刻自动开机。不能开一个已经开了的电脑。 将手动开的电脑编号依次记下，求有多少种可能的编号序列。 答案对给定的质数 $mod$ 取模。 $n\leq 400$ ，时限$\texttt{3s}$。 ------------ - $O(n^2)$ 做法可见：[一类基于笛卡尔树的排列计数DP](https://www.luogu.com.cn/blog/command-block/yi-lei-ji-yu-duan-di-pai-lie-ji-shuo-dp) # [??] F Phoenix and Earthquake **题意** ： 在紧张又忙碌地准备联合省选时，发生了大地震，把原本要参赛的 $n$ 个城市之间的全部 $m$ 条道路震垮了。 现在，需要紧急恢复 $n-1$ 条原来的道路，使得任意两个城市可以互相到达。 好在每个城市分别存有 $w_i$ 吨沥青。修复一条道路需要 $x$ 吨沥青，如果两个城市 $i,j$ 之间有一条损坏的道路，且两个城市的沥青总量 $\geq x$ ，那么就可以消耗这两个城市的 $x$ 吨沥青来修路。 修好了路之后，装载沥青的卡车就可以在路上跑，在这一部分连通的城市中任意地来往运送沥青了。 判定能否让 $n$ 个城市连通，如果能，输出任意一种修路的方案。 $n,m\leq 3\times 10^5$ ，时间$\texttt{3s}$。 ------------ 首先，若沥青总和不足 $(n-1)x$ ，则显然无法完成。 猜想一旦沥青总数 $\geq (n-1)x$（称作性质A）就一定能完成，证明如下 ： 只需证明图为树的情况，一般图的条件显然比树更优越。 修路 $(u,v)$ 可以视作将两端的点 $u,v$ 缩合为一个点，且新点权值 $w_u+w_v-x$ 。 不难发现，在若干缩合操作后，性质A仍然保持，于是考虑归纳。只需证对于任意满足性质的树，都至少能修出一条路。 反证，若对于任意边 $(u,v)$ 都有 $w_u+w_v<x$ ，对于边 $(u,fa_u)$ ，将限制扩大为 $w_u<x$ 。特殊地，任选一条 $(u,rt)$ ，限制写为 $w_u+w_{rt}<x$。 这样，我们把 $n$ 个点的权值（不重不漏地）划分到 $n-1$ 个不等式里面去了，且不等式右侧总和为 $(n-1)x$ ，这就能得到点权和 $<(n-1)x$ ，矛盾。证毕。 ------------ 接下来考虑如何快速求出一种方案。 对于一般图的情况，我们可以任保留一棵生成树，忽略其他的边，这样可以简化问题。 根据如上证明，一种正确策略是：每次修任意一条能修的边。但这样不好维护。 我们考虑将策略特化以便维护。 - 策略一 （根据`P6775 [NOI2020] 制作菜品`）考虑权值最大的点 $u$ 和权值最小的点 $v$ ，有 $w_u+w_v\geq x$ 。 证明 ：若不满足，则说明 $w_u<x$ ，和最大的情况是除了最小值外都是 $x-1$ ，仅为 $(n-1)(x-1)$ ，不足 $(n-1)x$ ，矛盾。 也就是说，$u$ 点任意连边都是合法的。 实现时，用堆维护目前的权值最大点，并查集启发式合并维护边表即可。 - 策略二 考虑任意一个叶子 $u$ ，若 $w_u+w_{fa}\geq x$ ，直接连边 $(u,fa)$ 。 否则必有 $w_u<x$ ，则将点 $u$ 忽略，剩余的点形成（必然有解的）子问题。处理完剩余的点之后再连接 $(u,fa)$ （不难发现此时必然能连）。 实现时，在树上 dfs ，当点 $u$ 的子树访问完毕准备弹栈时： - 若 $w_u\geq x$ （要考虑子树内连边的影响），则连边 $(u,fa)$ ，令 $w_{fa}\leftarrow w_{fa}+w_{u}-x$ 。 - 若 $w_u<x$ ，则将边 $(u,fa)$ 加入一个栈中。 在 dfs 完毕后，弹出栈中的边，并依次连接。 注意到上述两种策略都能导出对应的归纳证明，而且证明是构造性的，而非上文中的反证法。启发：找策略时可以尝试从构造性证明入手。 代码是策略一的。 ```cpp #include<algorithm> #include<cstdio> #include<vector> #define ll long long #define pb push_back #define MaxN 300500 using namespace std; int f[MaxN]; int find(int u) {return f[u]==u ? u : f[u]=find(f[u]);} bool merge(int u,int v){ u=find(u);v=find(v); if (u==v)return 0; f[u]=v;return 1; } vector<int> g[MaxN],id[MaxN]; int x,ans[MaxN],ans2[MaxN],tn,tn2;ll w[MaxN]; void dfs(int u,int fa) { int sav=0; for (int i=0;i<g[u].size();i++) if (g[u][i]!=fa)dfs(g[u][i],u); else sav=id[u][i]; if (fa){ if (w[u]+w[fa]>=x){ ans[++tn]=sav; w[fa]+=w[u]-x; }else ans2[++tn2]=sav; } } int n,m; int main() { scanf("%d%d%d",&n,&m,&x); ll sum=0; for (int i=1;i<=n;i++){ scanf("%lld",&w[i]); sum+=w[i];f[i]=i; } if (sum<1ll*(n-1)*x){puts("NO");return 0;} for (int i=1,u,v;i<=m;i++){ scanf("%d%d",&u,&v); if (merge(u,v)){ g[u].pb(v);id[u].pb(i); g[v].pb(u);id[v].pb(i); } } dfs(1,0); puts("YES"); for (int i=1;i<=tn;i++)printf("%d\n",ans[i]); for (int i=tn2;i;i--)printf("%d\n",ans2[i]); return 0; } ``` # G Phoenix and Odometers **题意** ： 给定一张 $n$ 个点 $m$ 条边的有向图，有边权。 进行 $q$ 次询问，每次询问给定$v,s,t$，判定是否存在一条起点终点均为 $v$ 的路径，满足 $\text{路径长}+s\equiv 0\pmod t$。 $n,m,q\leq 2\times 10^5$，时限$\texttt{2s}$。 ------------ 不难发现经过 $v$ 的回路都在 $v$ 所在的强连通分量内部。 于是可以对每个强连通分量分别求解。 若存在某条回路满足条件，则找出一个经过所有点的回路，将其走 $t$ 次（没有贡献），然后接上去，可以将这个回路转移到任意点，也就是说答案和 $v$ 无关。 考虑求出所有回路的一组“基”，使得所有回路都可以表示成基的线性组合（系数为整数）。 若基的 $\gcd$ 为 $g$ ，显然所有回路的权值都是 $g$ 的倍数。 进一步根据斐蜀定理，$\gcd(t,g)|s$ 时有解，否则无解。我们只需要求出 $g$ 就可以回答询问。 ------------ 接下来是求基的方法。 令根为 $1$，对正图和反图分别求 dfs 树，令正图上 $1\to u$ 的路径为 $P(x)$，反图上为 $Q(x)$。 对于每个 $u$ 将回路 $P(x)+Q(x)$ 加进基中，称为 $u$ 元；对于每条边 $(u,v)$ 再将回路 $P(u)+(u,v)+Q(v)$ 加入基中，称为 $(u,v)$ 元。 如此一来，对于任意一个回路，我们先将环上所有边的 $(u,v)$ 元加起来，再减去所有环上点的 $u$ 元，就实现了用基表示这个回路的方案。 复杂度 $O(n+(m+q)\log v)$ 。 ```cpp ``` # H Phoenix and Bits **题意** ：维护大小为 $n$ 的集合 $S$，$q$ 次操作： - 将 $[x,y]$ 之中的数按位与 $z$。 - 将 $[x,y]$ 之中的数按位或 $z$。 - 将 $[x,y]$ 之中的数按位异或 $z$。 - 查询 $[x,y]$ 之中有多少个不同的数。 $n\leq 2\times 10^5,q\leq 10^5,c<2^{20}$ ，时限$\texttt{4s}$。 ------------ 看起来很均摊。 注意到与操作相当于 取反+或+取反，故只需考虑后三种操作。 用 Trie 维护（由于 $c$ 很小，不需要动态开点，但是需要交换儿子），对于 xor 操作，打懒标记即可。 对于或操作，我们维护当前子树的或 $s_1$ 与补集的或 $s_0$。 若 $s_1\cap s_0\cap z=\varnothing$ ，说明每个受影响的位都确定，影响（是否取反）也可以预测，那么用异或标记代替。 若有交，暴力 dfs。 对于某个 Trie 节点，我们记势能为 $|s_1\cap s_0|$ 。 对于一次异或操作，会使得 $O(\log c)$ 个节点的势能不可预期地变化，总变化量为 $O(\log^2c)$。 对于或操作，每次 dfs 会使得当前节点势能减少 $1$。 总复杂度为 $O(n\log c+q\log^2c)$ 。 ```cpp ``` ## CF702F T-Shirts **题意** ： 有 $n$ 种衬衫，第 $i$ 种价格为 $c_i$ ，品质为 $w_i$ ，数量无限。 有 $m$ 个人依次来买衬衫，第 $i$ 个人有 $v_i$ 元。购买策略：不断买能买的品质最好的衬衫（若品质相同则买便宜的），直到买不起任意一件衬衫为止。 求每个人最终各买了多少件衬衫。 $n,q\leq 2\times 10^5$ ，时限$\texttt{4s}$ 。 ------------ 我们发现，假如对每个人分别处理，可以将钱数的转移视为内向树。一个经典的做法是倍增，但本题中钱数非常大，难以处理。 考虑转置，转而维护每个人的钱数，逐个考虑衬衫。 假设当前衬衫的价格为 $c$ ，即对于钱数 $>c$ 的人将钱数减去 $c$ 并将答案加一。 同：[[DS记录]P7447 [Ynoi2007] rgxsxrs](https://www.luogu.com.cn/blog/command-block/ds-ji-lu-p7447-ynoi2007-rgxsxrs) 复杂度 $O((n+m)\log^2n/\log\log n)$。 # I Phoenix and Diamonds **题意** ： $n$ 种钻石，一颗第 $i$ 种钻石重量为 $w_i$，价值为 $v_i$，一开始第 $i$ 中钻石的库存为 $a_i$。 接下来进行 $m$ 次操作： - 修改某个 $a$ - 假设你有一个大小为 $c$ 的袋子，且按照第一关键字为价值（从大到小），第二关键字为重量（从小到大）的顺序取钻石（若取不下则跳过），求你最终可以取到钻石的价值为多少。（注意操作不会真正执行） $n\leq 2\times 10^5,m\leq 10^5$ ，时限$\texttt{5s}$。 ------------ 将钻石按照拿取顺序排序。 仍然考虑倍增分段，按**重量**分为 $[2^i,2^{i+1})$。 假设现在准备拿后缀 $[i,n]$ ，记 $c\in[2^i,2^{i+1})$ 。 若使得 $c$ 减半，最多拿一个 $[2^i,2^{i+1})$ 中的钻石。 我们对于 $[1,2^i)$ 中的钻石（跳过其他钻石）进行线段树上二分，看看最右取到那里。 如果最右能越过某个 $[2^i,2^{i+1})$ 中的钻石，则检查一下这个钻石能否被取。 经过一轮操作， $c$ 的值至少减半。 时间复杂度 $O(n\log n+m\log^2n)$ ，空间复杂度 $O(n\log n)$。 ```cpp ```