~

https://atcoder.jp/contests/arc183/tasks A分类讨论奇偶，看样例基本上能猜出来。 B 注意 $K=1$ 是容易判断的。 第二种情况是 $b_i$ 出现了 $a_i$ 没出现的数字。 否则 $K \geq 2$，以及 $a_i$ 里面有所有 $b_i$ 出现的值。 考虑最后一步如果能弄出来 $b$，那么 $b$ 肯定有两个相同数字的距离小于等于 $K$，并且有相同的数字。 验证这是充要条件：考虑除了最后一步全都使用 $k=2$ 的操作，这样就可以类似插入排序来做，假设相同的数字是 $(i, j)$ 拿其中某一个相同的数字，比如说 $i$，可以当做一个中间值，也就是 temp 的作用，也就是除了最后一个位置都能达成。 只需要满足最后一步的条件即可。 C考虑 $bad_{l,r,i}$ 表示 $[l,r]$ 中的最大值不能是 $i$ 这个位置。 然后类似笛卡尔树分治下去求方案即可。 记忆化搜索。 D考虑这个其实最开始是给了一个合法的方案。 然后找到一个重心。 重心有如下性质： 可以一一配对，并且配对的答案更大。 一棵树最多 ...

E$dp_i$ 表示 $[1, i]$ 的答案。 然后记录一个 $sum_{S}$ 表示 $\sum_{sum_i = S} dp_i$。 F二分之后判定，一定是能断开就直接断开。 然后数一下最多能多少段，最后看看是否 $\geq k$ 即可。 Ghttps://atcoder.jp/contests/abc370/tasks/abc370_g 不会做。

Efloyd 之后 $2^k \times k!$ 枚举方向和排列。 F直接类似扫描线，并且输出方案即可。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768const int N=1<<18;using info = array<int,2>;info c[N];void upd(int x, info v){ while (x < N) { cmax(c[x], v); x += x & -x; }}info query(int x) { info res{}; while (x) { res = max(res, c[x]); x -= x & -x; } return res;}pii a[N];v ...

E考虑 $S_i$ 时间进去的时候更新一个地方的 $X$ 值。 然后 $T_i$ 时间用 $X$ 值去更新标记。 准确说，是一个类似 lazytag 的东西。 F其实可以把唯一分解之后的指数相加。 然后就是简单的博弈题了。 G考虑 $B \ge 2$ 的不会超过 $\log$ 个，所以其实是个诈骗了。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071void solve() { int n; cin>>n; vi a(n),b(n); rep(n)cin>>a[i]; rep(n)cin>>b[i]; int q;cin>>q; vl aa(n*2); rep(n)aa[i+n]=a[i]; for(int i=n-1;i>=0;i--)aa[i]=aa[i*2]+aa[i*2+1]; a ...

E倍增即可。 12345678910111213141516171819202122232425void solve() { int N; ll K; cin>>N>>K; vi X(N); rep(N) cin>>X[i],--X[i]; vi A(N); rep(N) cin>>A[i]; vi Y(N); rep(N) Y[i]=i; while(K){ if(K%2==1){ vi YY(N); rep(N) YY[i]=Y[X[i]]; Y.swap(YY); } vi XX(N); rep(N) XX[i]=X[X[i]]; X.swap(XX); K/=2; } rep(N) cout<<A[Y[i]]<<" \n"[i+1==N];} F哈希 12345678910111213141516171819202122232425262728 ...

E随便计算一下就可以。 枚举其中一维的差值，然后另一维做前缀和即可。 F考虑交换相邻即可。 G首先可以考虑随机赋值，大概率线性无关。 然后将邻居的 $g_i$ 丢进线性基，其实表示的是一个方程 $=0$。 线性基中的每个组合的异或结果都是 0。 从 $x=1$ 开始到 $x=n$ 考虑对阶梯头依次解出每个的值即可。 123456789101112131415161718192021222324252627282930313233343536373839404142434445ll p[66];void ins(ll x){ for(int i=59;i>=0;i--){ if(x>>i&1){ if(!p[i]){ p[i]=x; } x^=p[i]; } }}void solve() { int n,m; cin>>n>>m; vl g(n); re ...

E按位考虑，模板题。 F边界考虑倍增跳跃。 G其实是根号分治某题的改版。 但是疑似我代码是错的，但是过题了。

https://codeforces.com/gym/105182 A观察性质，然后疑似是用 BIT 什么维护一下就好了。 B队友写的。 C$\sum i^2 = \frac{n(n+1)(2n+1)}{6}$ D一段 0 再一段 1。 123456789101112131415161718192021222324252627282930313233343536373839404142#include <bits/stdc++.h>using namespace std;const long long INF = 1e9;void solve() { int n; cin >> n; vector<int> x(n), y(n); // 0-white // 1-black int max_white = 0; int max_black = 0; for (int i = 0; i < n; i++) { cin >> x[i] >> y[i]; int whi ...

CF1976https://codeforces.com/contest/1976/problems A直接 sort 即可。 B前 $n$ 个直接做差即可，加上最后一个的答案。 C考虑前缀和，二分出来分界点。 D考虑合法条件是什么。 首先让 ‘(‘ 为 1，’)’ 为 -1，括号序列合法仅当所有前缀和大于等于0。 注意到翻转的这个区间一定是一个区间和为0的区间。 然后根据上面的条件判断即可，只需要做一个二分rmq即可。 E忘了。 F注意到要让桥边最少，肯定每次拉出来的都是最长链，删除一条最长链等这条路径的边权都设成0。 第一次操作只能删除 $(1,x)$ 之后的操作都可以删除 $(x,y)$，等价删两次从 1 开始的最长链。 CF1980https://codeforces.com/contest/1980/problems G分奇环和偶环考虑。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616 ...

五边形数定理证明 $$ \varphi(x) = \sum_k (-1)^k x^{\frac{k(3k+1)}{2}}$$ 欧拉函数的倒数是划分数的生成函数: $\frac{1}{\varphi(x)} = \sum p(i)x^i = \prod \frac{1}{1-x^i}$。 定义可以知道 $\varphi(x) \times \frac{1}{\varphi(x)} = 1$ 代入: $(\sum (-1)^k x^{\frac{k(3k+1)}{2}})(\sum p(i) x^i) = 1$ 即为 $(1-x-x^2+x^5+x^7…)(1+p(1)x+p(2)x^2…)=1$ 可知 $p(k) = p(k-1)+p(k-2)-p(k-5)…$。 通过这个我们可以得到 $\sum p(i)x^i$，前者的项数是 $\sqrt n$ 的，所以总体复杂度是 $O(n \sqrt n)$。 如果限定拆分出来最大的数 $<k$，那么可以用类似的做法（等比数列求和然后转成欧拉函数相关） $F(x) &#x ...