CF1707 题解
A
考场上 1h 才出思路...弱智了。
我们将参加大于当前智商的行为叫做 “摆烂”。我们考虑如果现在摆一次，将来某一次不摆，那么现在不摆，将来那次开摆，中间过程的智商会加1。更优。所以一定一摆就摆到底。而且一定会摆到最后一个。
所以我们二分从什么时候开摆，看是否能摆到最后，中间 \(\Theta(n)\) 模拟过程。
其实可以直接从后往前递推到 \(q\) ，线性解决。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N],ans = 0,n,q,cs[N],as[N];
inline int run(int x)
{
fill(cs + 1,cs + n + 1,0);
int res = 0;
for(int i = 1;i < x;i++) if(a[i] <= q) ++res,cs[i] = 1;
int tmp = q;
for(int i = x;i <= n && tmp;i++)
{
++res;
cs[i] = 1;
tmp -= (a[i] > tmp);
if(!tmp)
{
if(res > ans)
{
for(int j = 1;j <= n;j++) as[j] = cs[j];
ans = res;
}
return i;
}
}
if(res > ans)
{
for(int j = 1;j <= n;j++) as[j] = cs[j];
ans = res;
}
return n;
}
int main()
{
int T;
cin>>T;
while(T--)
{
ans = 0;
cin>>n>>q; fill(as + 1,as + n + 1,0);
for(int i = 1;i <= n;i++) cin>>a[i];
int l = 1,r = n;
if(n == 1) {if(q > 0) as[1] = 1,ans = 1;}
while(l < r)
{
int mid = (l + r) >> 1;
if(run(mid) < n) l = mid + 1;
else r = mid;
}
for(int i = 1;i <= n;i++) cout<<as[i];
cout<< '\n';
}
return 0;
}
B
考虑暴力模拟过程，是 \(\Theta(n^2 \log n)\) 的。
差分只会让值变的越来越小，手模发现会出现一些 \(0\) ，然而 \(0\) 的差分不需要算，只需要记录 \(0\) 的个数，每次减少 \(1\) 即可，有前导 \(0\) 的时候要保留第一个差分值。
将 \(0\) 除掉过后暴力做，发现可以 AC。
考虑记 \(S\) 为所有数的和，第一次 \(S = a_n - a_1\) 。后面进行一次操作之前 \(S \geq n - 1 + a_n\) ，操作之后 \(S = a_n - a_1\) 。所以至少减去了 \(n - 1\) 。所以操作是 \(\Theta(\frac Sn)\) 次，每次 \(\Theta(n \log n)\) ，复杂度就是 \(\Theta(S\log n)\) 。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N],n,b[N];
inline int solve()
{
int tmp,l = 1,r = n,rem0 = 0;
for(tmp = 1;tmp <= n - 1;tmp++)
{
a[l - 1] = 0;
for(int i = l;i <= r;i++) b[i] = a[i] - a[i - 1];
if(!rem0)
{
sort(b + l + 1,b + r + 1);
for(int i = l + 1;i <= r;i++) a[i] = b[i];
l++;
while(a[l] == 0 && l <= r) ++l,++rem0;
}
else
{
sort(b + l,b + r + 1);
for(int i = l;i <= r;i++) a[i] = b[i];
while(a[l] == 0 && l <= r) ++l,++rem0;
rem0--;
}
if(l > r) return 0;
}
return a[l];
}
int main()
{
ios::sync_with_stdio(0);
int T;
cin>>T;
while(T--)
{
cin>>n;
for(int i = 1;i <= n;i++) cin>>a[i];
cout<<solve()<< '\n';
}
return 0;
}
C
考虑一个点可以的条件是以它为根的搜索树就是最小生成树，由于搜索树只有树边和返祖边，考虑不在最小生成树上的边，只有两个端点的子树出发才能将这条边作为返祖边，这些点才合法。
如图，红色即为可以取的点。
所以直接将这些集合求交即可，具体方法是树上差分后子树加，最后看点值是否等于 \(m - n + 1\) 即可。复杂度 \(\Theta(m \log m + n)\) 。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct Edge{
int u,v,w,us;
}e[N * 4];
int head[N],n,m,dfn[N],siz[N],a[N],fa[19][N],dep[N];
vector <Edge> G[N];
struct UFS{
int fa[N];
inline void init() {for(int i = 1;i <= n;i++) fa[i] = i;}
inline int find(int x) {return (x == fa[x]) ? x : fa[x] = find(fa[x]);}
inline void unionn(int x,int y) {x = find(x); y = find(y); fa[y] = x;}
}t;
inline void Kruskal()
{
sort(e + 1,e + m + 1,[&](Edge x,Edge y) {return x.w < y.w;});
t.init();
for(int i = 1;i <= m;i++)
{
if(t.find(e[i].u) == t.find(e[i].v)) continue;
G[e[i].u].push_back(e[i]); G[e[i].v].push_back(e[i]);
e[i].us = 1;
t.unionn(e[i].u,e[i].v);
}
}
inline void dfs(int x,int last)
{
siz[x] = 1;
dep[x] = dep[last] + 1;
fa[0][x] = last;
for(auto in : G[x])
{
int to = in.u ^ x ^ in.v;
if(to == last) continue;
dfs(to,x);
siz[x] += siz[to];
}
}
inline int jump(int x,int d)
{
for(int i = 18;i >= 0;i--) if(dep[fa[i][x]] >= d) x = fa[i][x];
return x;
}
inline void dfs2(int x,int last)
{
for(auto in : G[x])
{
int to = in.u ^ x ^ in.v;
if(to == last) continue;
a[to] += a[x];
dfs2(to,x);
}
}
int main()
{
cin>>n>>m;
for(int i = 1,x,y;i <= m;i++)
{
cin>>e[i].u>>e[i].v;
e[i].w = i;
}
Kruskal();
dfs(1,0);
for(int i = 1;i <= 18;i++)
for(int j = 1;j <= n;j++)
fa[i][j] = fa[i - 1][fa[i - 1][j]];
for(int i = 1;i <= m;i++)
{
if(e[i].us) continue;
int x = e[i].u,y = e[i].v;
if(dep[x] < dep[y]) swap(x,y);
if(jump(x,dep[y]) == y)
{
a[x]++; a[1]++;
a[jump(x,dep[y] + 1)]--;
}
else
{
a[x]++;
a[y]++;
}
}
dfs2(1,0);
for(int i = 1;i <= n;i++) if(a[i] == m - n + 1) putchar('1'); else putchar('0');
return 0;
}
D
考虑不好处理真子集，我们将其变成子集。
这可以看作一个过程：从整棵树开始，每一个单位时间你可以删掉某些点，求每个 \(k \in [1,n - 1]\) ， \(k\) 个单位时间后将树删为 \(1\) 的方案数。
考虑恰好不好说，二项式反演，假设 \(f_{u,k}\) 为 \(u\) 的子树，\(k\) 时间后删完了的方案数。那么对于 \(k\) ，有：
\[f_{1,k} = \sum_{i = 1}^{k} \binom{k}{i}ans_i
\]
表示选择 \(i\) 步做出实质性的改变，其余的都不变。
反演得到：
\[ans_k = \sum_{i = 1}^k (-1)^{k - i}\binom{k}{i} f_{1,i}
\]
考虑 dp 求出 \(f_{i,k}\) ，一个子树只可能有两种顺序：
-
先删完所有儿子，再删自己
-
先删到只有一个儿子，再删自己，再删儿子。
对于第一种情况，有：
\[f_{i,k} = \prod_{v} \sum_{j = 1}^k f_{v,j}
\]
因为儿子合法，那么相应地自己就合法，所以是乘起来。
考虑前缀和优化，设 \(s_{i,k} = \sum_{j = 1}^k f_{i,j}\)
对于第二种情况，有：
\[f_{i,k} = f_{i,k} + \sum_{v \in son(i)}f_{v,k}\sum_{p = 0}^{k - 1}\prod_{w \neq v}s_{w,p}
\]
尝试优化第二种情况，我们可以在外层枚举 \(p\) ，算出对于所有儿子 ，\(s_{w,p}\) 的前后缀积。 这样对于每一个儿子，复杂度就是 \(\Theta(n)\) 级别的，总体做到了 \(\Theta(n^2)\) 。
#include<bits/stdc++.h>
using namespace std;
const int N = 2005;
typedef long long ll;
int n,p;
vector <int> G[N];
ll f[N][N],g[N][N],pre[N][N],suf[N][N],s[N][N],frac[N],inv[N];
inline ll ksm(ll base,int pts)
{
ll ret = 1;
for(;pts > 0;pts >>= 1,base = base * base % p)
if(pts & 1)
ret = ret * base % p;
return ret;
}
inline void dfs(int x,int last)
{
vector <int> son;
for(auto to : G[x]) if(to != last) dfs(to,x),son.push_back(to);
if(!son.size())
{
for(int i = 1;i <= n - 1;i++) f[x][i] = 1,s[x][i] = i;
return;
}
int cnt = son.size();
for(int j = 1;j <= n - 1;j++)
for(int i = 0;i < cnt;i++)
pre[i][j] = suf[i][j] = s[son[i]][j];
for(int j = 1;j <= n - 1;j++)
for(int i = 1;i < cnt;i++)
pre[i][j] = pre[i - 1][j] * pre[i][j] % p;
for(int j = 1;j <= n - 1;j++)
for(int i = cnt - 2;i >= 0;i--)
suf[i][j] = suf[i + 1][j] * suf[i][j] % p;
for(int j = 1;j <= n - 1;j++) f[x][j] = pre[cnt - 1][j];
if(x == 1) return;
for(int j = 1;j <= n - 1;j++)
{
for(int i = 0;i < cnt;i++)
{
f[x][j] = (f[x][j] + f[son[i]][j] * g[son[i]][j - 1] % p) % p;
g[son[i]][j] = (g[son[i]][j - 1] + ((i == 0) ? 1 : pre[i - 1][j]) * ((i == cnt - 1) ? 1 : suf[i + 1][j]) % p) % p;
}
s[x][j] = (((j == 0) ? 0 : s[x][j - 1]) + f[x][j]) % p;
}
}
inline ll C(int y,int x)
{
if(y < 0 || x < 0 || y < x) return 0;
return frac[y] * inv[x] % p * inv[y - x] % p;
}
int main()
{
memset(f,0,sizeof(f)); memset(g,0,sizeof(g)); memset(pre,0,sizeof(pre)); memset(suf,0,sizeof(suf)); memset(s,0,sizeof(s));
cin>>n>>p;
for(int i = 1,x,y;i <= n - 1;i++)
{
cin>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
frac[0] = inv[0] = 1;
for(int i = 1;i < N;i++) frac[i] = frac[i - 1] * i % p;
inv[N - 1] = ksm(frac[N - 1],p - 2);
for(int i = N - 2;i >= 0;i--) inv[i] = inv[i + 1] * (i + 1) % p;
dfs(1,0);
for(int i = 1;i <= n - 1;i++)
{
ll now = 0;
for(int j = 1;j <= i;j++)
now = (now + (((i - j) & 1) ? p - 1 : 1) * C(i,j) % p * f[1][j] % p) % p;
cout<<now<< ' ';
}
return 0;
}
E
性质题，做完对倍增有更深的了解。
考虑每一次操作是在上一次的基础上再对区间拓宽，考虑倍增。假设 \(f_{t,i,j}\) 为 \([i,j]\) 做 \(2^t\) 次操作的区间是什么，每次由于处理好了 \(t - 1\) 的信息，直接将 \(2^{t - 1}\) 的结果区间拿去做即可。
但是这样是 \(\Theta(n^2\log n)\) 的，考虑优化，如果这个区间信息像 \(max\) 一样可以合并，我们就能够对于区间长度同样地倍增。但是貌似不能合并？
事实上发现可以，即：
\[f([l,r]) = \cup_{i = l}^{r - 1}f([i,i + 1])
\]
证明可以归纳，即新加入的一个值会刷新原来区间的左右端点，一个一个加入相当于用区间内的所有值将左右端点更新了一遍，和原来效果相同。
所以我们设 \(f_{i,j,k}\) 为 \([k,k + 2^j - 1]\) 做 \(2^i\) 次可以得到的区间，\(\Theta(n\log^2n)\) 预处理后 \(\Theta(\log n)\) 倍增回答询问即可。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct Segment{
int l,r;
}f[20][20][N];
Segment operator +(Segment a,Segment b) {return Segment{min(a.l,b.l),max(a.r,b.r)};}
int a[N],n,q,lg[N];
inline Segment getval(int k,int l,int r)
{
int now = lg[r - l + 1];
return f[k][now][l] + f[k][now][r - (1 << now) + 1];
}
int main()
{
cin>>n>>q;
lg[0] = -1;
for(int i = 1;i <= n;i++) lg[i] = lg[i >> 1] + 1;
for(int i = 1;i <= n;i++) cin>>a[i];
for(int i = 1;i <= n;i++) f[0][0][i].l = f[0][0][i].r = a[i];
for(int i = 1;i <= 18;i++)
for(int j = 1;j + (1 << i) - 1 <= n;j++)
f[0][i][j] = f[0][i - 1][j] + f[0][i - 1][j + (1 << (i - 1))];
for(int i = 1;i <= 18;i++)
for(int j = 1;j <= 18;j++)
for(int k = 1;k + (1 << j) - 1 <= n;k++)
f[i][j][k] = getval(i - 1,f[i - 1][j][k].l,f[i - 1][j][k].r);
for(int i = 1,l,r;i <= q;i++)
{
cin>>l>>r;
if(l == 1 && r == n) {puts("0"); continue;}
Segment now = {l,r}; int tms = 0;
for(int i = 18;i >= 0;i--)
{
Segment to = getval(i,now.l,now.r);
if(!(to.l == 1 && to.r == n))
now = to,tms += (1 << i);
}
now = getval(0,now.l,now.r);
if(now.l != 1 || now.r != n) {puts("-1"); continue;}
cout<<tms + 1<< '\n';
}
return 0;
}
F
咕。