2024 9 月杂题
真正名义上的开学了，莫名其妙多了好多天假，爽。
[ABC134F] Permutation Oddness
题意
- 求 $\sum_{i=1}^n|i-p_i|=k$ 的 $n$ 阶排列数。
- $1\le n\le 50,0\le k\le n^2$
题解
看到绝对值先拆绝对值，于是考虑哪些东西产生正的贡献哪些产生负的。
发现假如某个数 $i$ 填入更大的空格中或者某个空格 $i$ 中填了更大的数都会产生 $-i$ 的贡献，如果是往小了搞就会产生 $i$ 的贡献。
于是考虑一个经典的 DP，设 $dp_{i,j,p}$ 表示考虑前 $i$ 个数/空格，有 $j$ 个数/空格需要和后面的匹配但还没匹配（注意到没匹配的数字和空格的数量必定是相同的），当前总贡献为 $p$ 的方案数。
转移有五种：
- 当前空格和数自己匹配： $dp_{i,j,p}\gets dp_{i-1,j,p}$
- 当空格和数都和后面的匹配：$dp_{i,j,p}\gets dp_{i-1,j-1,p+2i}$
- 都和前面的匹配：$dp_{i,j,p}\gets dp_{i-1,j+1,p-2i}\times (j+1)^2$
- 数和前面的匹配，空和后面的匹配：$dp_{i,j,p}\gets dp_{i-1,j,p}\times j$
- 空和前面的匹配，数和后面的匹配：$dp_{i,j,p}\gets dp_{i-1,j,p}\times j$
复杂度 $O(n^4)$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=55,mod=1e9+7;
int n,k,dp[N][N][N*N*2],A;
signed main(){
n=read();k=read();
int A=n*n;
dp[0][0][A]=1;
forup(i,1,n){
forup(j,0,i){
forup(p,-n*n,n*n){
dp[i][j][p+A]=dp[i-1][j][p+A];
if(j>0&&p+2*i<=i*i) (dp[i][j][p+A]+=dp[i-1][j-1][p+2*i+A])%=mod;
if(j<i-1&&p-2*i>=-i*i) (dp[i][j][p+A]+=1ll*dp[i-1][j+1][p-2*i+A]*(j+1)%mod*(j+1)%mod)%=mod;
(dp[i][j][p+A]+=2ll*dp[i-1][j][p+A]*j%mod)%=mod;
}
}
}
printf("%d\n",dp[n][0][k+A]);
}
P8162 [JOI 2022 Final] 让我们赢得选举 (Let's Win the Election)
题意
- 有一个人要参加选举，他需要通过演讲取得 $n$ 个市中至少 $k$ 个的支持。
- 每个市有两个参数 $a,b$，表示他至少要演讲 $a$ 小时才能获得支持，而如果演讲超过 $b$ 小时就能获得一个协助者。协助者可以和它一起演讲（相当于复制一个人），多人同时在同一城市演讲收益会叠加。
- 求所需最少时间，不考虑交通等其它事务消耗的时间。
- $1\le n\le 5000$，所有数字在 $1000$ 以内。
题解
首先有一个贪心：先枚举找了 $t$ 个协助者，然后将最小的 $t$ 个 $b$ 拎出来，再在剩下的 $a$ 中选最小的。
但这个有个问题：可能某个 $b$ 对应的 $a$ 非常小，让它的 $a$ 取贡献会更优。
那么最小的 $t$ 个 $b$ 中不选 $b$ 的必定选 $a$（如果两边都不选显然把更大的的 $b$ 换车这个会不劣）。
于是想到 DP，设 $f_{i,j}$ 表示考虑前 $i$ 小的 $b$，其中有 $j$ 个选择 $b$，其余选择 $a$ 的最小代价，统计答案和后面的拼一下即可，转移是简单的。
复杂度 $O(n^3)$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using ld=long double;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=505,inf=0x3f3f3f3f;
int n,k;
ld ans=inf;
struct Node{
int a,b,pos;
}s[N];
ld dp[2][N],mn[N][N];
signed main(){
n=read();k=read();
int cnt=0;
forup(i,1,n){
s[i].a=read();s[i].b=read();
s[i].pos=i;
ans+=s[i].a;
if(~s[i].b) ++cnt;
else s[i].b=inf;
}
sort(s+1,s+n+1,[&](Node a,Node b){return a.b<b.b;});
forup(i,0,n+1){
forup(j,0,n+1){
mn[i][j]=inf;
}
}
mn[n+1][0]=0;
fordown(i,n,1){
forup(j,0,n-i+1){
mn[i][j]=min(mn[i+1][j],mn[i+1][j-1]+s[i].a);
}
}
ans=mn[1][k];
forup(t,0,min(k,cnt)){
forup(j,0,n){
dp[0][j]=inf;
}
dp[0][0]=0;
forup(i,1,k){
int p=i&1,q=p^1;
forup(j,0,n) dp[p][j]=inf;
forup(j,0,min(i,t)){
dp[p][j]=dp[q][j]+1.0*s[i].a/(t+1);
if(j) dp[p][j]=min(dp[p][j],dp[q][j-1]+1.0*s[i].b/j);
}
ans=min(ans,dp[p][t]+mn[i+1][k-i]/(t+1));
}
}
printf("%Lf\n",ans);
}
JOISC 2015 Day1 T3「たのしいたのしい家庭菜園 / Growing Vegetables is Fun 2」
题意
- 有 $n$ 棵树，每棵树有一个高度 $h_i$，现在你可以砍掉其中一些，砍掉第 $i$ 棵需要 $c_i$ 的代价。砍掉相当于把高度变成 $0$，若一棵树没被砍掉且高度是对应位置的前缀最大值或后缀最大值则产生 $p_i$ 的贡献。
- 求贡献减代价的最大值。
- $3\le n\le 10^5$，所有数据在 $10^9$ 以内。
题解
简单 DP，但是蠢了导致浪费一早上。
容易想到必定是一个前缀中产生贡献的单调不减，后缀产生贡献的单调不增。显然必定最大值同时满足两边，于是考虑求出前后缀的答案再枚举最大值统计。
只考虑前缀，容易想到 DP，设 $f_i$ 表示考虑 $[1,i]$，且钦定 $i$ 产生贡献的最大答案。考虑从某个 $f_j$ 转移，显然 $[1,i]$ 区间内不能出现高于 $h_i$ 的树所以必然有 $h_j\le h_i$。
因为你想从 $j$ 转移过来，所以其实 $[j+1,i-1]$ 区间内的都不会产生贡献，即高于 $h_j$ 的都要砍掉，这样显然不会算漏，因为可以从这些地方转移过来。
那么对值域开一棵线段树维护区间最大值即可，复杂度 $O(n\log n)$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(i64 i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(i64 i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<i64,i64>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=1e5+5,inf=1e18;
i64 n,h[N],p[N],c[N],sz;
vector<i64> lsh;
struct SegTree{
#define mid ((l+r)>>1)
#define lson l,mid,id<<1
#define rson mid+1,r,id<<1|1
i64 mx[N<<2],mark[N<<2];
void PushUp(i64 id){
mx[id]=max(mx[id<<1],mx[id<<1|1]);
}
void PushDown(i64 id){
mx[id<<1]+=mark[id];
mark[id<<1]+=mark[id];
mx[id<<1|1]+=mark[id];
mark[id<<1|1]+=mark[id];
mark[id]=0;
}
void Build(i64 l=0,i64 r=sz,i64 id=1){
mx[id]=-inf;
mark[id]=0;
if(l==r) return;
Build(lson);Build(rson);
}
void Update(i64 P,i64 X,i64 l=0,i64 r=sz,i64 id=1){
if(l==r){
mx[id]=max(mx[id],X);
return;
}
if(mark[id]) PushDown(id);
if(P<=mid) Update(P,X,lson);
else Update(P,X,rson);
PushUp(id);
}
void Modify(i64 L,i64 R,i64 X,i64 l=0,i64 r=sz,i64 id=1){
if(L<=l&&r<=R){
mx[id]+=X;
mark[id]+=X;
return;
}
if(mark[id]) PushDown(id);
if(L<=mid) Modify(L,R,X,lson);
if(mid< R) Modify(L,R,X,rson);
PushUp(id);
}
i64 Query(i64 L,i64 R,i64 l=0,i64 r=sz,i64 id=1){
if(L<=l&&r<=R){
return mx[id];
}
if(mark[id]) PushDown(id);
i64 res=-inf;
if(L<=mid) res=max(res,Query(L,R,lson));
if(mid< R) res=max(res,Query(L,R,rson));
return res;
}
};
SegTree mt;
i64 f[N],g[N];
signed main(){
n=read();
forup(i,1,n){
h[i]=read();p[i]=read();c[i]=read();
lsh.push_back(h[i]);
}
sort(lsh.begin(),lsh.end());
lsh.erase(unique(lsh.begin(),lsh.end()),lsh.end());
sz=lsh.size();
forup(i,1,n){
h[i]=lower_bound(lsh.begin(),lsh.end(),h[i])-lsh.begin()+1;
}
forup(i,1,n){
msg("[%lld]%lld %lld %lld|\n",i,h[i],c[i],p[i]);
}
mt.Build();
mt.Update(0,0);
forup(i,1,n){
f[i]=mt.Query(0,h[i])+p[i];
mt.Modify(0,h[i],-c[i]);
mt.Update(h[i],f[i]);
msg("%lld ",f[i]);
}
msg("|\n");
mt.Build();
mt.Update(0,0);
fordown(i,n,1){
g[i]=mt.Query(0,h[i])+p[i];
mt.Modify(0,h[i],-c[i]);
mt.Update(h[i],g[i]);
msg("%lld ",g[i]);
}
msg("|\n");
i64 ans=0;
forup(i,1,n){
ans=max(ans,f[i]+g[i]-p[i]);
}
printf("%lld\n",ans);
}
LOJ#6191 「美团 CodeM 复赛」配对游戏
题意
- 有一长度为 $n$ 的括号序列，每个点等概率是左括号或又括号，求不能匹配的括号的期望数量。
- $1\le n\le 2000$
题解
有一堆 $O(n^3)$ 做法，发现 $n\le 2000$，于是直接打表就能过了。
但是有 $O(n^2)$ 做法，首先考虑计算每个点被留下来的概率。
不妨计算每个点以右括号留下来的概率，左括号是对称的。
设 $f_i$ 表示第 $i$ 个点以右括号留下来的概率，考虑枚举上一个留下来的 $j$。并且钦定 $[i+1,j-1]$ 中全不留下来。
则 $[i+1,j-1]$ 必定是一段合法括号序列，于是转移为 $f_i\gets f_j\times Cat(\frac{i-j-1}{2})\times 2^{-(i-j-1)}\times \frac{1}{2}$，要求 $(i-j-1)\bmod 2=0$。
然后统计答案就全部加起来即可。复杂度 $O(n^2)$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using ld=long double;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=2005;
int n;
ld Cat[N],f[N],g[N],pw[N];
signed main(){
n=read();
Cat[0]=Cat[1]=1;
forup(i,2,n){
forup(j,0,i-1){
Cat[i]+=Cat[j]*Cat[i-j-1];
}
}
f[0]=1;
pw[0]=1;
forup(i,1,n) pw[i]=pw[i-1]*0.5;
forup(i,1,n){
for(int j=i-1;j>=0;j-=2){
f[i]+=f[j]*Cat[(i-j-1)/2]*pw[i-j];
}
msg("%.3lf ",f[i]);
}
msg("|\n");
ld ans=0;
forup(i,1,n){
ans+=f[i]+f[n-i+1];
}
printf("%.3Lf\n",ans);
}
LOJ#6177 「美团 CodeM 初赛 Round B」送外卖2
题意
- 有一个 $n$ 个点 $m$ 条边的有向图表示一座城市，每条边有边权表示通过它所需时间。
- 你是一个外卖员，有 $q$ 个订单，第 $i$ 个订单从 $s_i$ 运送到 $t_i$，要求在 $l_i$ 之后取餐，$r_i$ 之前到达。
- 你 $0$ 时刻在 $1$ 号点，求最多能完成多少个订单。
- $1\le n\le 20,1\le m\le 400,1\le q\le 10$。
题解
容易想到三进制状压，考虑 DP，设 $f_{i,msk}$ 表示在点 $i$ 任务状态为 $msk$ 的最短时间。
容易想到只有任务的起点终点是重要的，我们只需要关注这些就好了，于是预处理全源最短路然后跑 DP，因为只会从时间小的转移到时间大的所以不需要考虑后效性，转移是简单的。
复杂度 $O(n^3+nq3^q)$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=25,M=405,Q=15,inf=0x3f3f3f3f;
int n,m,q,dp[N][60000],mx,pw3[N],ans;
int num[60000];
int l[N],r[N],s[N],t[N];
int grp[N][N];
int get(int x,int bt){
return (x/pw3[bt])%3;
}
signed main(){
n=read();m=read();q=read();
forup(i,1,n){
forup(j,1,n){
grp[i][j]=inf;
if(i==j) grp[i][j]=0;
}
}
forup(i,1,m){
int u=read(),v=read(),w=read();
grp[u][v]=min(grp[u][v],w);
}
forup(k,1,n){
forup(i,1,n){
forup(j,1,n){
grp[i][j]=min(grp[i][j],grp[i][k]+grp[k][j]);
}
}
}
pw3[0]=1;
forup(i,1,q){
pw3[i]=pw3[i-1]*3;
}
forup(i,0,q-1){
s[i]=read();t[i]=read();l[i]=read();r[i]=read();
mx=max(mx,r[i]);
}
int al=0;
forup(i,0,q-1) al+=pw3[i]*2;
forup(i,0,al){
forup(j,0,q-1){
if(get(i,j)==2) ++num[i];
}
}
mem(dp,0x3f);
dp[1][0]=0;
forup(i,0,al){
forup(j,1,n){
if(dp[j][i]==inf) continue;
ans=max(ans,num[i]);
forup(k,0,q-1){
int v=get(i,k);
if(v==0){
int tt=dp[j][i]+grp[j][s[k]],nxt=i+pw3[k];
if(tt<=r[k]) dp[s[k]][nxt]=min(dp[s[k]][nxt],max(tt,l[k]));
}else if(v==1){
int tt=dp[j][i]+grp[j][t[k]],nxt=i+pw3[k];
if(tt<=r[k]) dp[t[k]][nxt]=min(dp[t[k]][nxt],tt);
}
}
}
}
printf("%d\n",ans);
}
QOJ#6355 5
是的这道题真的就叫阿拉伯数字 “$5$”。
题意
- 给定一个长度为 $n$，总和为 $s$ 的非负整数序列 $a_i$，其中 $1$ 的数量大于等于 $\frac{s}{5}$。
- 称一个二元组 $(k,t)$ 合法当且仅当存在一个长度恰好为 $k$ 的子序列总和恰好为 $t$。
- 求合法二元组数量。
- $1\le n,s\le 2\times 10^5,0\le a_i\le s$
题解
首先这个问题显然与序列的顺序无关，可以看成可重集。
首先容易想到一些和 $1$ 的数量的性质无关的做法。比如一个想法是二维背包，设 $g_{p,i,j}$ 表示只考虑前 $p$ 种数（即将相同的数分为一组考虑），是否存在选了 $i$ 个数的可重集总和为 $j$。容易发现第一维是 $O(\sqrt{n})$ 级别的，大概能做到 $O(n^2\sqrt{n})$，并且显然第一维可以压掉。
这时候考虑“$1$ 很多”这个条件。容易发现这样会使得 DP 中 $1$ 的形状形如若干条斜向线段，因为每加一个一会使得两维都恰好 $+1$。那么不妨设 $g_{i,j}$ 表示（考虑前 $p$ 种数）总和减去数量的值为 $i$，数量为 $j$ 的可重集是否存在。这样的话 $1$ 的形状就形如每一行有若干区间了。
先不考虑 $1$ 会得到若干个点，因为 $1$ 至少有 $\frac{s}{5}$ 个，那么假如同一行两个点的横向距离小于等于 $\frac{s}{5}$ 它们就会连成一段区间。换句话说，每一行至多有 $\frac{5n}{s}$ 个连续段。
因为至多有 $\sqrt{s}$ 种不同的数，那么搞一下二进制拆分完全背包即可得到只需要转移 $\sqrt{s}\log s$ 次。
然后行数是 $O(s)$，每次转移要遍历每一行的至多 $O(\frac{n}{s})$ 个连续段，于是复杂度 $O(n\sqrt{s}\log s)$（据说其实二进制拆分不带 $\log$，但是我不确定），然后可以用 std::vector 维护连续段，转移的时候暴力重构即可，复杂度还是对的，因为反正你都要遍历一遍，重构的时候再遍历无伤大雅。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=2e5+5;
int n,s,a[N],sum,A,mx;
int cnt[N];
vector<pair<pii,int> > ss[N<<1];
using mit=map<pii,int>::iterator;
void maintain(int p,int l,int r){
vector<pair<pii,int> > v1=ss[p+A];ss[p+A].clear();
for(auto i:v1){
if(i.fi.se<l||r<i.fi.fi){
ss[p+A].push_back(i);continue;
}else{
if(i.fi.fi<=l&&l<=i.fi.se){
if(i.se){
l=i.fi.fi;
}else{
if(i.fi.fi<l) ss[p+A].push_back(mkp(mkp(i.fi.fi,l-1),0));
}
}
if(i.fi.fi<=r&&r<=i.fi.se){
if(i.se){
r=i.fi.se;
ss[p+A].push_back(mkp(mkp(l,r),1));
}else{
ss[p+A].push_back(mkp(mkp(l,r),1));
if(r<=i.fi.se) ss[p+A].push_back(mkp(mkp(r+1,i.fi.se),0));
}
}
}
}
mx=max(mx,p);
}
void upd(int val,int cnt){
fordown(p,min(mx,sum-val),0){
for(auto j:ss[p+A]){
if(!j.se) continue;
maintain(p+val,j.fi.fi+cnt,j.fi.se+cnt);
}
}
}
signed main(){
n=read();s=read();
sum=0;
forup(i,1,n){
a[i]=read();
++cnt[a[i]];
if(a[i]>1) sum+=a[i]-1;
if(a[i]==0) ++A;
}
forup(i,-A,sum){
ss[i+A].push_back(mkp(mkp(0,n),0));
}
maintain(0,0,cnt[1]);
forup(i,2,s){
if(!cnt[i]) continue;
int w=1;
while(cnt[i]>w){
upd((i-1)*w,w);
cnt[i]-=w;w<<=1;
}
upd((i-1)*cnt[i],cnt[i]);
}
i64 ans=0;
int w=1;
while(cnt[0]>w){
int val=-w,cc=w;
forup(p,-A+cc,sum){
for(auto j:ss[p+A]){
if(!j.se) continue;
maintain(p+val,j.fi.fi+cc,j.fi.se+cc);
}
}
cnt[0]-=w;w<<=1;
}
int val=-cnt[0],cc=cnt[0];
forup(p,-A+cc,sum){
for(auto j:ss[p+A]){
if(!j.se) continue;
maintain(p+val,j.fi.fi+cc,j.fi.se+cc);
}
}
forup(p,-A,sum){
for(auto j:ss[p+A]){
if(j.se) ans+=(j.fi.se-j.fi.fi+1);
}
}
printf("%lld\n",ans);
}
P10008 [集训队互测 2022] Range Minimum Element
题意
- 有一个长度为 $n$，值域为 $[1,c]$ 的整数序列 $a_i$，有一个长度为 $m$ 整数序列 $b_i$，其中 $b_i=\min_{j=l_i}^{r_i}\begin{Bmatrix}a_j\end{Bmatrix}$，其中 $l_i,r_i$ 是给定的 $m$ 个二元组。
- 求有多少种不同的 $b$。
- $1\le n\le 100,1\le m\le \binom{n}{2},1\le c < 998244353$，答案对 $998244353$ 取模。
题解
神秘思路。
容易发现顺着序列填数不好做，于是考虑能不能从小到大填数。思考一下可以发现假如在 $i$ 处填了一个数那么左侧和右侧会变成两个独立的子问题，于是考虑区间 DP。
设 $f_{i,j,k}$ 表示考虑区间 $[i,j]$（并且只考虑 $[i,j]$ 包含的区间 $[l_i,r_i]$），能填的最小的数为 $k$（就是值域为 $[k,c]$，不一定取满）的方案数。于是枚举转移点 $p$，并且钦定 $p$ 是区间内第一个恰好等于 $k$ 的点，于是有 $f_{i,j,k}\gets f_{i,p-1,k+1}\times f_{p+1,j,k}$。注意到若 $p$ 不被任何一个 $[l_i,r_i]$ 包含则这个钦定是没有意义的，于是我们可以只考虑被包含的情况。
然后又出现了一些问题，就是这个转移会算重。假设有两个转移点 $p_1,p_2$，并且包含它们的所有 $[l_i,r_i]$ 构成的集合分别是 $S_1,S_2$，容易发现若 $S_1\subseteq S_2$，那么在 $p_1$ 算过的所有情况都会在 $p_2$ 再算一遍（即所有 $S_2$ 全取 $k$ 的情况），这也能解释为什么不能从不被任何区间覆盖的转移点转移。
怎么解决呢？只要每次从 $p_1$ 跳到最小的不满足 $S_1\subseteq S_2$ 的 $p_2$ 即可，其实找到包含 $p_1$ 的最小的 $r_i$ 就行了，这个可以对于每一对 $(i,j)$ 暴力 $O(n^2)$ 预处理。
然后对这个东西做一遍后缀和即可求出 $f$ 的值了。
这样复杂度大约是 $O(n^3c)$ 的，显然就寄了嘛。但是注意到最多只会用到 $n$ 个不同的数，于是考虑能否对于 $1\le n'\le n$ 求出恰好使用 $n'$ 种不同的数的序列，然后组合数一下就搞定了。
一个想法是将第三维的意义改为至多使用 $k$ 个不同的数，转移是类似的，这样对 $f_{1,n,\ast}$ 二项式反演一下即可得到想要的答案了。
于是复杂度 $O(n^4)$，随便过。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=105,inf=0x3f3f3f3f,mod=998244353;
int ksm(int a,int b){
int c=1;
while(b){
if(b&1) c=1ll*a*c%mod;
a=1ll*a*a%mod;
b>>=1;
}
return c;
}
int n,m,c;
int dp[N][N][N];
pii rg[N*N];
int mn[N];
int binom[N][N];
int C[N],f[N];
signed main(){
n=read();m=read();c=read();
forup(i,0,n){
binom[i][0]=1;
forup(j,1,i){
binom[i][j]=(binom[i-1][j-1]+binom[i-1][j])%mod;
}
}
C[0]=1;
forup(i,1,min(n,c)){
C[i]=1ll*C[i-1]*(c+1-i)%mod*ksm(i,mod-2)%mod;
}
forup(i,1,m){
rg[i].fi=read();rg[i].se=read();
}
sort(rg+1,rg+m+1,[&](pii a,pii b){return a.se>b.se;});
forup(i,1,n+1){
forup(j,1,n){
dp[i][i-1][j]=1;
}
}
forup(len,1,n){
forup(L,1,n-len+1){
int R=L+len-1;
forup(i,1,m){
if(L<=rg[i].fi&&rg[i].se<=R){
forup(j,rg[i].fi,rg[i].se){
mn[j]=rg[i].se;
}
}
}
dp[L][R][1]=1;
forup(i,2,n){
forup(j,L,R){
if(mn[j]==0) continue;
(dp[L][R][i]+=1ll*dp[L][j-1][i-1]*dp[j+1][R][i]%mod)%=mod;
j=mn[j];
}
}
forup(i,2,n){
(dp[L][R][i]+=dp[L][R][i-1])%=mod;
}
forup(i,L,R) mn[i]=0;
}
}
int ans=0;
forup(i,1,min(n,c)){
forup(j,1,i){
(f[i]+=1ll*binom[i][j]*((i-j)&1?mod-1:1)%mod*dp[1][n][j]%mod)%=mod;
}
(ans+=1ll*f[i]*C[i]%mod)%=mod;
}
printf("%d\n",ans);
}
P4216 [SCOI2015] 情报传递
题意
- 给定一棵 $n$ 个点的树，有两种操作共 $q$ 次：
- 将一个点激活。设它是在第 $k$ 个操作激活的，那么在第 $p$ 次操作（$p\ge k$）时，它的权值为 $p-k$。
- 求某条路径的长度以及上面有多少个点的权值严格大于 $c$。
- $1\le n,q\le 2\times 10^5$
题解
你好，一眼离线主席树，刚准备开始写发现可以单 $\log$。
其实就是相当于每次链查有多少个激活时间小于等于某个值的点。
于是离线下来直接树上差分维护即可，复杂度 $O(n\log n)$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123=(e);i<=E123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123=(e);i>=E123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)){if(c=='-')f=-1;}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=2e5+5,inf=0x3f3f3f3f;
int n,q,ans[N],cntn,rt,len[N],ff[N];
vector<int> e[N];
struct query{
int u,v,c,pos,ll;
}s[N];
int dfn[N],sz[N],Tm,dpt[N];
int st[19][N];
void dfs(int x){
dfn[x]=++Tm;
sz[x]=1;
for(auto i:e[x]){
dpt[i]=dpt[x]+1;
ff[i]=x;
dfs(i);
sz[x]+=sz[i];
st[0][dfn[i]]=x;
}
}
int lca(int u,int v){
if(u==v) return u;
u=dfn[u];v=dfn[v];
if(u>v) swap(u,v);
++u;
int len=31^__builtin_clz(v-u+1);
return dfn[st[len][u]]<dfn[st[len][v-(1<<len)+1]]?st[len][u]:st[len][v-(1<<len)+1];
}
struct BIT{
int c[N];
void upd(int x,int k){for(;x<=Tm;x+=x&-x)c[x]+=k;}
int sum(int x){int res=0;for(;x>0;x-=x&-x)res+=c[x];return res;}
}mt;
signed main(){
n=read();
forup(i,1,n){
int f=read();
if(f) e[f].push_back(i);
else rt=i;
}
dfs(rt);
forup(i,0,17){
forup(j,1,n-(1<<(i+1))+1){
st[i+1][j]=dfn[st[i][j]]<dfn[st[i][j+(1<<i)]]?st[i][j]:st[i][j+(1<<i)];
}
}
q=read();
forup(i,1,q){
int op=read();
if(op==1){
s[i].u=read();s[i].v=read();s[i].c=i-read();
s[i].ll=lca(s[i].u,s[i].v);
len[i]=dpt[s[i].u]+dpt[s[i].v]-2*dpt[s[i].ll]+1;
}else{
s[i].u=read();s[i].v=-1;s[i].c=i;
}
s[i].pos=i;
}
sort(s+1,s+q+1,[&](query a,query b){return a.c<b.c;});
int L=1;
forup(i,1,q){
if(s[i].v!=-1){
while(L<=n&&s[L].c<s[i].c){
if(s[L].v==-1){
mt.upd(dfn[s[L].u],1);
mt.upd(dfn[s[L].u]+sz[s[L].u],-1);
}
++L;
}
ans[s[i].pos]=mt.sum(dfn[s[i].u])+mt.sum(dfn[s[i].v])-mt.sum(dfn[s[i].ll])-(s[i].ll==rt?0:mt.sum(dfn[ff[s[i].ll]]));
}
}
forup(i,1,q){
if(len[i]){
printf("%d %d\n",len[i],ans[i]);
}
}
}
QOJ#2562 Fake Plastic Trees 2
题意
- 有一棵 $n$ 个点的树，点有点权。
- 给定 $L,R,K$，问是否有一个恰好隔开 $K$ 条边的方案，使得割出来的每个连通块垫圈和均在 $[L,R]$ 中。
- $1\le n\le 2\times 10^5$ 所有数在 $[0,10^{18}]$ 中。
题解
神秘做法。
首先考虑一个平凡的 DP，设 $dp_{i,j,k}$ 表示考虑 $i$ 及其子树，割 $j$ 刀，$i$ 所在连通块总和为 $j$ 的方案是否存在，这样显然就不对啊，光是第三维就炸了。
这时候考虑一个我把头塞进马桶里都想不到的性质：有效的 $k$ 是不多的。
具体来说，假如 $dp_{i,j,a}=dp_{i,j,b}=dp_{i,j,c}=1(a < b < c)$，若 $c-a\le R-L+1$，那么其实可以不管 $b$，考虑最终 $i$ 所在的连通块，假设存在 $i$ 上传 $b$ 的方案，那么容易发现 $i$ 子树能提供的合法大小是一个长度为 $R-L+1$ 的区间，那么因为 $b$ 在这个区间内，则 $a,c$ 中必定有至少一个在这个区间内。于是把 $b$ 删掉不会影响答案。
考虑 $i$ 的子树点权和为 $S$，切下来的 $j$ 刀总和应在 $[j\cdot L,j\cdot R]$ 之间，说明剩下的这一块值域应该是 $[S-j\cdot R,S-j\cdot L]$，所以有效点数上界大致和 $j$ 是同级别的，带个二倍常数。
于是对每个 $dp_{i,j}$ 开一个 std::vector 存储所有合法的 $k$，转移就暴力合并，我觉得复杂度是 $O(nk^4)$ 的，但貌似可以用树形背包的套路分析成 $O(nk^3)$ 的，感觉很神奇，总之能过就对了。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(i64 i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(i64 i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<i64,i64>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=2e5+5,inf=1e18;
i64 n,m,L,R,a[N];
vector<i64> e[N];
vector<i64> dp[N][55];
i64 sz[N];
void dfs(i64 x,i64 fa){
sz[x]=1;
dp[x][0].push_back(a[x]);
for(auto i:e[x]){
if(i==fa) continue;
dfs(i,x);
vector<vector<i64> > ff(m+5);
fordown(k,min(sz[x],m),0){
forup(j,0,min(sz[i],m)){
if(k+j>m) break;
for(auto p:dp[i][j]){
for(auto q:dp[x][k]){
if(p+q<=R){
ff[k+j].push_back(p+q);
}
if(L<=p&&p<=R&&k+j+1<=m){
ff[k+j+1].push_back(q);
}
}
}
}
}
sz[x]+=sz[i];
forup(k,0,min(sz[x],m)){
vector<i64> vv;
dp[x][k].clear();
swap(vv,ff[k]);
sort(vv.begin(),vv.end());
vv.erase(unique(vv.begin(),vv.end()),vv.end());
if(vv.empty()) continue;
i64 sz=vv.size();
dp[x][k].push_back(vv[0]);
i64 lst=vv[0];
forup(i,2,sz-1){
if(vv[i]-lst>R-L+1){
dp[x][k].push_back(vv[i-1]);
lst=vv[i-1];
}
}
if(vv.size()>1) dp[x][k].push_back(vv.back());
}
}
// forup(i,0,min(sz[x],m)){
// msg("%d %d|",x,i);
// for(auto j:dp[x][i]){
// msg("%d ",j);
// }
// msg("|\n");
// }
}
void solve(){
n=read();m=read();L=read();R=read();
i64 mx=0;
forup(i,1,n){
a[i]=read();
mx=max(mx,a[i]);
e[i].clear();
forup(j,0,m) dp[i][j].clear();
}
forup(i,1,n-1){
i64 u=read(),v=read();
e[u].push_back(v);
e[v].push_back(u);
}
if(mx>R){
forup(i,0,m){
putchar('0');
}
puts("");
return;
}
dfs(1,0);
forup(i,0,m){
if(lower_bound(dp[1][i].begin(),dp[1][i].end(),L)!=dp[1][i].end()){
putchar('1');
}else{
putchar('0');
}
}
puts("");
}
signed main(){
i64 t=read();
while(t--){
solve();
}
}
P3591 [POI2015] ODW
题意
你妈的波兰人真的不会写题意吗？垃圾题意谁写的。
- 有一棵 $n$ 个点的树，点带权，$n-1$ 次询问两点之间简单路径上每次跳 $c_i$ 步经过的点权值和。
- $1\le n\le 50000$，点券在 $10000$ 以内。
题解
根号分治，小的对每个倍数维护前缀和，大的暴力跳即可。复杂度可以做到 $O(n\sqrt{n})$，但是我因为不会长剖所以写的带 $\log$。
复杂度 $O(n\sqrt{n}\log n)$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123=(e);i<=E123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123=(e);i>=E123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)){if(c=='-')f=-1;}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=5e4+5,B=230,inf=0x3f3f3f3f;
int n,a[N],b[N],c[N];
vector<int> e[N];
int hig[N],dfn[N],dpt[N],Tm,sz[N],son[N],mp[N],ff[N];
int sum[N][B+5];
void dfs1(int x,int fa){
sz[x]=1;
ff[x]=fa;
int f=x;
forup(i,1,B){
f=ff[f];
sum[x][i]=sum[f][i]+a[x];
}
dpt[x]=dpt[fa]+1;
for(auto i:e[x]){
if(i==fa) continue;
dfs1(i,x);
sz[x]+=sz[i];
if(son[x]==0||sz[i]>sz[son[x]]) son[x]=i;
}
}
void dfs2(int x,int fa,int hh){
dfn[x]=++Tm;mp[dfn[x]]=x;
hig[x]=hh;
if(son[x]){
dfs2(son[x],x,hh);
}
for(auto i:e[x]){
if(i==fa||i==son[x]) continue;
dfs2(i,x,i);
}
}
int lca(int u,int v){
while(hig[u]!=hig[v]){
if(dpt[hig[u]]<dpt[hig[v]]) swap(u,v);
u=ff[hig[u]];
}
if(dpt[u]<dpt[v]) swap(u,v);
return v;
}
int kth(int u,int k){
if(k>=dpt[u]) return 0;
while(dpt[u]-dpt[hig[u]]+1<=k){
k-=dpt[u]-dpt[hig[u]]+1;
u=ff[hig[u]];
}
return mp[dfn[u]-k];
}
signed main(){
n=read();
forup(i,1,n){
a[i]=read();
}
forup(i,1,n-1){
int u=read(),v=read();
e[u].push_back(v);
e[v].push_back(u);
}
forup(i,1,n) b[i]=read();
forup(i,1,n-1) c[i]=read();
dfs1(1,0);
dfs2(1,0,1);
forup(i,1,n-1){
int u=b[i],v=b[i+1];
if(c[i]<=B){
int p=lca(u,v),res=0;
int t=((dpt[u]-dpt[p])/c[i]+1)*c[i];
res+=sum[u][c[i]]-sum[kth(u,t)][c[i]];
t=(dpt[v]-dpt[p]+c[i]-1)/c[i]*c[i];
res+=sum[v][c[i]]-sum[kth(v,t)][c[i]];
printf("%d\n",res);
}else{
int p=lca(u,v),res=0;
while(dpt[u]>dpt[p]){
res+=a[u];
u=kth(u,c[i]);
}
while(dpt[v]>=dpt[p]){
res+=a[v];
v=kth(v,c[i]);
}
printf("%d\n",res);
}
}
}
QOJ#8822 Guess The Sequence 2
题意
- 给定一个长度为 $n$ 的排列 $a_i$，小明可以选择其中一些区间并得知其每个区间的区间最大值，设这样得到若干个三元组 $(l,r,v)$。
- 问在所有 $2^{\frac{n(n-1)}{2}}$ 中询问方式中，有多少种可以让小明猜出整个排列。
- $1\le n\le 5\times 10^5$，保证数据随机，答案对 $998244353$ 取模。
题解
什么神秘东西，阿拜多斯的小鸟游星野都没你神秘。
首先考虑假如你是小明你应该怎么猜出这个排列。考虑从小往大确定，那么不妨设在确定 $x$ 之前所有 $y < x$ 都被确定了，那么此时只要有一个区间 $(l,r,x)$ 就能唯一确定 $x$ 所在位置，因为区间 $[l,r]$ 中只有小于等于 $x$ 的数，而所有小于 $x$ 的数都被确定了。
如果只有这种情况是非常好做的（下文称这样是被自己确定），因为只需要单调栈预处理左右第一个大于 $a_i$ 的位置 $L_i,R_i$（后文会复用这个变量名，表达相同含义），每次乘 $2^{(R_i-i)\times(i-L_i)}-1$ 即可。问题就在于还有其它情况。
若小于等于 $i$ 的数除了 $x$ 以外都被确定了，那么这时候我们再询问一个区间 $[l,r]$ 同时包含 $i$ 和 $x$，那么我们是可以确定 $x$ 的，因为你知道序列上有一个空位，三元组 $(l,r,i)$ 可以说明这个空位的值域是 $[1,i]$，但是值域内其它数都被用过了。特别地，因为整个过程自带一个全局询问 $(1,n,n)$（显然不管你问不问你都知道这个三元组），所以假如有一个空位留到了最后也是可以确定的。
这个怎么做呢？不妨对空位进行 DP。因为需要“除了 $x$ 以外的数都被确定了”所以同时最多只有一个空位。设 $dp_x$ 表示考虑所有满足 $j\le x$ 的三元组 $(l,r,j)$，能确定所有 $j < x$ 但是不能确定 $x$ 的方案数。
首先 DP 初值是简单的，就是前面“非常好做”的那种情况，那么如何转移和统计答案呢？
考虑使用 DP 进行转移，先枚举 $x$ 后，设 $f_{i,0/1}$ 表示考虑所有三元组 $(l,r,j)(j\le i)$，钦定 $x$ 是最后一个没有被自己确定的点，$x$ 是/否被确定的方案数。
容易发现假如 $L_i < p_x <R_i$（$p_x$ 代表 $x$ 在排列中的位置），那么 $a_i$ 是可以确定 $x$ 的，反之则不行，于是分 $i$ 能否确定 $x$ 两种情况来转移。
首先是不能确定，那么显然 $f_{i,0}\gets f_{i-1,0}\times (2^{(R_{p_i}-p_i)\cdot(p_i-L_{p_i})}-1),f_{i,1}\gets f_{i-1,1}\times (2^{(R_{p_i}-p_i)\cdot(p_i-L_{p_i})}-1)$。
然后是能确定的，那么 $f_0\to f_0$ 的转移不能有包含 $p_x$ 的区间，$f_1$ 的还是随意。然后还要考虑在这里确定 $x$ 的。不妨设 $p_x<p_i$（反过来是对称的），则 $f_{i,0}\gets f_{i-1,0}\times (2^{(p_i-p_x)\cdot (R_{p_i}-p_i)}-1)$，$f_1$ 的转移和上面一样。再加上 $f_{i,1}\gets f_{i,0}\times (2^{(p_x-L_{p_i})\cdot (R_{p_i}-p_i)}-1)$，注意这个转移应该最后做。
根据定义，显然在任何位置都有转移 $f_{i,1}\to dp_{i+1}$。并且显然 $f_{n,0}$ 和 $f_{n,1}$ 应累加进答案里。
这样我们就会 $O(n^2)$ 做法了。
怎么优化呢？注意保证数据随机，那么这个序列的笛卡尔树深度是 $O(\log n)$ 的。换句话说，能确定 $x$ 的转移点只有 $O(\log)$ 个（这个可以用笛卡尔树求出），而其它转移点可以用前缀和 $+$ 差分搞定。于是复杂度可以容易地优化到 $O(n\log n)$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123=(e);i<=E123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123=(e);i>=E123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)){if(c=='-')f=-1;}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=5e5+5,inf=0x3f3f3f3f,mod=998244353;
int ksm(int a,int b){
int c=1;
while(b){
if(b&1) c=1ll*a*c%mod;
a=1ll*a*a%mod;
b>>=1;
}
return c;
}
int n,a[N],pos[N],rt,ans;
const int B=1<<15;
int p2[N],pt2[N];
int pow2(i64 x){
x%=(mod-1);
return 1ll*pt2[x>>15]*p2[x-((x>>15)<<15)]%mod;
}
int ff[N],L[N],R[N];
void buildtree(){
a[0]=a[n+1]=inf;
stack<int> stk;
stk.push(0);
forup(i,1,n){
int pl=0;
while(a[stk.top()]<a[i]){
pl=stk.top();
stk.pop();
}
if(pl) ff[pl]=i;
L[i]=stk.top();
stk.push(i);
}
while(stk.size()) stk.pop();
stk.push(n+1);
fordown(i,n,1){
int pl=0;
while(a[stk.top()]<a[i]){
pl=stk.top();
stk.pop();
}
if(pl) ff[pl]=i;
R[i]=stk.top();
stk.push(i);
}
}
int dp[N];
int pre[N],invp[N],sum[N],val[N];
void solve(){
n=read();
forup(i,1,n){
a[i]=read();
pos[a[i]]=i;
if(a[i]==n) rt=i;
ff[i]=dp[i]=sum[i]=0;
}
if(n==1) return puts("2"),void();
if(n==2) return puts("6"),void();
buildtree();
pre[0]=1;
forup(i,1,n){
int p=pos[i];
val[i]=pow2(1ll*(p-L[p])*(R[p]-p))-1;
pre[i]=1ll*pre[i-1]*val[i]%mod;
}
invp[n]=ksm(pre[n],mod-2);
fordown(i,n-1,1){
invp[i]=1ll*invp[i+1]*val[i+1]%mod;
}
ans=0;
int nw=1;
forup(i,1,n){
(sum[i]+=sum[i-1])%=mod;
(dp[i]+=nw)%=mod;
(dp[i]+=1ll*sum[i]*pre[i-1]%mod)%=mod;
int p=pos[i];
nw=1ll*nw*val[i]%mod;
int j=p,f0=dp[i],f1=0;
while(ff[j]){
int k=ff[j];
(sum[a[j]+1]+=1ll*f1*invp[a[j]]%mod)%=mod;
(sum[a[k]+1]+=(mod-1ll*f1*invp[a[j]]%mod))%=mod;
f0=1ll*f0*pre[a[k]-1]%mod*invp[a[j]]%mod;
f1=1ll*f1*pre[a[k]-1]%mod*invp[a[j]]%mod;
f1=1ll*f1*val[a[k]]%mod;
if(p<k){
f0=1ll*f0*(pow2(1ll*(k-p)*(R[k]-k))-1)%mod;
(f1+=1ll*f0*(pow2(1ll*(p-L[k])*(R[k]-k))-1)%mod)%=mod;
}else{
f0=1ll*f0*(pow2(1ll*(k-L[k])*(p-k))-1)%mod;
(f1+=1ll*f0*(pow2(1ll*(k-L[k])*(R[k]-p))-1)%mod)%=mod;
}
j=k;
}
(ans+=f0)%=mod;
(ans+=f1)%=mod;
}
(ans+=nw)%=mod;
printf("%d\n",ans);
}
signed main(){
p2[0]=1;
forup(i,1,B){
p2[i]=2ll*p2[i-1]%mod;
}
pt2[0]=1;
forup(i,1,B){
pt2[i]=1ll*pt2[i-1]*p2[B]%mod;
}
solve();
}
P3588 [POI2015] PUS
不是这他妈是波兰人的问题还是翻译的问题啊。什么狗屎题面。
题意
- 有一个长度为 $n$ 值域为 $[1,10^9]$ 的序列，其中 $s$ 个值已经给定了。
- 现在再给你 $m$ 个限制，第 $i$ 个限制 $(l_i,r_i,k_i,x_i)$（其中 $x_i$ 是一个长度为 $k_i$ 的序列，其余均为正整数）表示区间 $[l_i,r_i]$ 中前 $k_i$ 大的下标集合为 $x_i$，保证给定的 $x_i$ 单调递增。
- 构造序列或报告无解。
- $1\le s\le n\le 10^5,1\le m\le 2\times 10^5,0\le\sum k\le 3\times 10^5$。
题解
一眼线段树优化建图然后按拓扑序 DP，点数 $O(n+m+k)$，边数 $O(k\log n+n)$。
除去优化建图外其它都是平凡的，建图即从大向小连边，即 $k$ 个点向它们之间的缝隙连边，显然不能直接暴力连，那么建个虚点就完了。
然后 DP 状态就是这个点能取到的最大值，转移是简单的，得到 DP 后构造答案也是简单的。注意判断值域下界为 $1$。
复杂度 $O(n+m+k\log n)$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123=(e);i<=E123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123=(e);i>=E123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)){if(c=='-')f=-1;}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=1e5+5,inf=0x3f3f3f3f;
int n,s,m,a[N],mx[N*10],cntn,rd[N*10];
vector<int> e[N*10];
void adde(int u,int v){
e[u].push_back(v);
++rd[v];
}
struct SegTree{
#define mid ((l+r)>>1)
#define lson l,mid,id<<1
#define rson mid+1,r,id<<1|1
int nd[N<<2];
void Build(int l=1,int r=n,int id=1){
if(l==r){
nd[id]=l;
return;
}
nd[id]=++cntn;
Build(lson);Build(rson);
adde(nd[id],nd[id<<1]);
adde(nd[id],nd[id<<1|1]);
}
void Link(int P,int L,int R,int l=1,int r=n,int id=1){
if(L<=l&&r<=R){
adde(P,nd[id]);
return;
}
if(L<=mid) Link(P,L,R,lson);
if(mid< R) Link(P,L,R,rson);
}
}mt;
signed main(){
n=read();s=read();m=read();
forup(i,1,s){
int p=read(),d=read();
a[p]=d;
}
cntn=n;
mt.Build();
forup(i,1,m){
int l=read(),r=read(),k=read();
int dd=++cntn;
int lst=l;
vector<pii> vv;
forup(j,1,k){
int x=read();
if(x>lst){
vv.push_back(mkp(lst,x-1));
}
lst=x+1;
adde(x,dd);
}
if(lst<=r){
vv.push_back(mkp(lst,r));
}
for(auto j:vv){
mt.Link(dd,j.fi,j.se);
}
}
queue<int> q;
int cc=0;
forup(i,1,cntn){
if(!rd[i]) q.push(i);
mx[i]=1e9;
}
while(q.size()){
int u=q.front();q.pop();
++cc;
if(u<=n){
if(mx[u]<a[u]){
puts("NIE");
return 0;
}
if(!a[u]) a[u]=mx[u];
}
for(auto v:e[u]){
--rd[v];
if(u<=n){
mx[v]=min(mx[v],a[u]-1);
}else{
mx[v]=min(mx[v],mx[u]);
}
if(!rd[v]) q.push(v);
}
}
if(cc!=cntn){
puts("NIE");
return 0;
}
forup(i,1,n){
if(a[i]<1){
puts("NIE");
return 0;
}
}
puts("TAK");
forup(i,1,n){
printf("%d ",a[i]);
}
puts("");
}
QOJ#7605 Yet Another Mex Problem
题意
- 给定一个长度为 $n$ 的序列 $a_i$，值域为 $[0,n]$。
- 给定常数 $k$，你可以将序列划分为若干段，每一段长度均不能大于 $k$，为方便叙述，我们用一个序列 $s_0,s_1,s_2\dots s_p(s_i < s_{i+1} \le s_i+k,s_0=0,s_p=n)$ 表示一个 $p$ 段的划分，我们定义划分的权值为 $\sum_{i=1}^{p-1}\left(\mathrm{mex}{j=s_i+1}^{s{i+1}}a_i\right)\times \left(\sum_{j=s_i+1}^{s_{i+1}}a_i\right)$，求划分的最大权值。
- $1\le n\le 2\times 10^5$
题解
心魔击溃！去年 $11$ 月份就写上 Todo list 了现在才搞完。
首先容易想到一个 $O(n^2)$ DP，设 $f_i$ 表示考虑 $[1,i]$，在 $i$ 处切一刀的最大权值，转移就枚举上一刀即可。
考虑 DP 如何优化，设 $sum_i=\sum_{j=1}^i a_j$，转移即为：
$$ f_i=\max_{j=1}^{i-1}\begin{Bmatrix}f_j+\left(\mathrm{mex}{j=s_i+1}^{s{i+1}}a_i\right)\times (sum_i-sum_j)\end{Bmatrix} $$
那么我们无论如何都需要把这个 $\mathrm{mex}$ 拆开。
考虑一个 $\mathrm{mex}$ 的经典性质：在一个序列上，对于同一个左端点，区间 $\mathrm{mex}$ 随着右端点右移单调不减。证明显然，因为一个集合超集的 $\mathrm{mex}$ 不会比它更小。
注意到随着右端点右移，对于所有左端点的 $\mathrm{mex}$ 应该是若干个相等的区间。然后又能瞪出一个新的性质：这样的左端点区间至多更新 $O(n)$ 次（这么说比较抽象啊，可以把它看成若干个区间覆盖问题，这样的区间覆盖至多进行 $O(n)$ 次）。
证明也比较简单，不妨先以 $n$ 为右端点每次左移。那么初始至多有 $O(n)$ 个区间，然后假设要将右端点从 $i$ 移动到 $i-1$，设 $a_i$ 上一次出现为 $p_i$，那么就是将 $[p_i+1,i]$ 中所有数和 $a_i$ 取 $\min$。因为 $\mathrm{mex}$ 随着左端点左移单调不减，那么这就相当于将一个连续的区间修改为 $a_i$。于是右端点每左移一次至多新增一个区间，所以区间至多更新 $O(n)$ 次。
所以我们只需要找出每次更新的区间，然后去区间赋值就能一定程度上解决 $\mathrm{mex}$ 问题了。
然后考虑拆 DP 式子，因为是一些和 $i,j$ 均有关的东西相乘所以容易想到类似斜率优化 DP 的思路，设 $M=\mathrm{mex}{j=s_i+1}^{s{i+1}}a_i$，于是：
$$ \begin{aligned} f_i&=f_j+M\times (sum_i-sum_j)\\ &=f_j+M\cdot sum_i-M\cdot sum_j\\ &=(f_j-M\cdot sum_j)+M\cdot sum_i\\ \end{aligned} $$
那么就相当于要在两个地方做斜率优化，第一个是用 $M$ 去更新 $j$ 的时候需要求出 $f_j-M\cdot sum_j$ 的最大值，第二个是更新 $f_i$ 的时候括号内相当于一个常数，也能斜率优化解决。
有一个极其复杂的 $O(n\log^2 n)$ 写法，大概就是写几棵线段树套李超树，此处略过。我们不妨来讨论一个更好写（而且通常更快）的分块做法，设块长为 $B$。
首先考虑如何用 $M$ 去更新，那么分整块和散块解决（整块就是被 $M$ 区间完全覆盖的块，散块则是有交但未被完全覆盖的块）。整块就相当于在凸包上查询，由于 $\mathrm{mex}$ 单调不减所以可以用双端队列去维护凸包。总复杂度 $O(nB+\frac{n^2}{B})$，称这样的块为“纯色块”。
然后是散块，容易发现 $sum_i$ 单调递增，所以也可以用双端队列维护凸包来做，更新 $M$ 时暴力重构即可。复杂度 $O(nB)$，称这样的块为“混色块”。
然后查询是比较平凡的，散块暴力扫，整块则要分纯色块和混色块分别维护，复杂度 $O(nB+\frac{n^2}{B})$。
容易发现空间复杂度是 $O(n)$ 的，于是做完了。理论上 $B$ 取 $450$ 左右会比较优，实测发现由于扫整个块的操作会进行比较多次，所以 $B$ 取小一点会更优，我调了下块长认为 $200$ 最好。复杂度 $O(n\sqrt{n})$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using i128=__int128;
using pii=pair<i64,i64>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=2e5+5,B=200,T=1005;
i64 inf=1e18;
int n,m,a[N];
i64 sum[N];
int L[T],R[T],blg[N];
deque<pii> conv[T];
i128 cross(pii a,pii b){
return a.fi*b.se-a.se*b.fi;
}
pii operator -(const pii a,const pii b){
return mkp(a.fi-b.fi,a.se-b.se);
}
bool slp(pii a,pii b,pii c){
return cross(b-a,c-b)<=0;
}
bool slp(pii a,pii b,i64 k){
return (b.se-a.se)<=(i128)(b.fi-a.fi)*k;
}
i64 dp[N];
int mex[N],tag[T];
deque<pii> c2[T];
i64 mxv[T];
void work(int b){
deque<pii> &q=c2[b];
fordown(i,R[b],L[b]){
pii nw=mkp(-sum[i],-dp[i]);
if(q.size()&&nw.fi==q.back().fi) continue;
while(q.size()>=2&&slp(q[q.size()-2],q[q.size()-1],nw)) q.pop_back();
q.push_back(nw);
}
}
void update(int b,int v){
deque<pii> &q=c2[b];
while(q.size()>=2&&slp(q[0],q[1],v)) q.pop_front();
mxv[b]=q.front().fi*v-q.front().se;
}
void getconv(int j){
if(~tag[j]){
forup(k,L[j],R[j]){
mex[k]=tag[j];
}
tag[j]=-1;
}
deque<pii> &q=conv[j];
q.clear();
vector<pii> vv;
fordown(k,R[j],L[j]){
pii nw;
nw.fi=mex[k];nw.se=mex[k]*sum[k]-dp[k];
vv.push_back(nw);
}
sort(vv.begin(),vv.end());
for(auto i:vv){
if(q.size()&&i.fi==q.back().fi) continue;
while(q.size()>=2&&slp(q[q.size()-2],q[q.size()-1],i)) q.pop_back();
q.push_back(i);
}
}
int tt[N],m0,lst[N],pp[N];
vector<pair<pii,int> > modi[N];
map<pii,int> odt;
using mit=map<pii,int>::iterator;
mit split(int x){
mit it=odt.lower_bound(mkp(x,0));
if(it->fi.fi==x) return it;
--it;
int l=it->fi.fi,r=it->fi.se,c=it->se;
odt.erase(it);
odt.insert(mkp(mkp(l,x-1),c));
return odt.insert(mkp(mkp(x,r),c)).fi;
}
signed main(){
n=read();m=read();
forup(i,1,n){
a[i]=read();
sum[i]=sum[i-1]+a[i];
pp[i]=lst[a[i]];
lst[a[i]]=i;
}
int t=n/B;
forup(i,1,t){
L[i]=R[i-1]+1;R[i]=i*B;
forup(j,L[i],R[i]) blg[j]=i;
}
if(R[t]!=n){
++t;
L[t]=R[t-1]+1;R[t]=n;
forup(j,L[t],R[t]) blg[j]=t;
}
forup(i,1,t) tag[i]=-1;
fordown(i,n,0){
mex[i]=mex[i+1];
while(tt[mex[i]]) ++mex[i];
++tt[a[i]];
}
forup(i,0,n) tt[i]=0;
int lpos=0;
forup(i,1,n){
if(mex[i]!=mex[i-1]){
odt.insert(mkp(mkp(lpos,i-1),mex[i-1]));
lpos=i;
}
}
odt.insert(mkp(mkp(lpos,n),mex[n]));
fordown(i,n,1){
mit st=split(pp[i]);
int r=pp[i]-1;
for(mit it=st;it!=odt.end()&&it->se>=a[i];odt.erase(prev(++it))){
modi[i].push_back(*it);
r=it->fi.se;
}
if(r>=pp[i])odt.insert(mkp(mkp(pp[i],r),a[i]));
mex[i]=0;
}
mex[0]=0;
forup(i,1,n){
++tt[a[i]];
while(tt[m0]) ++m0;
dp[i]=0;
if(i<=m){
dp[i]=max(dp[i],m0*sum[i]);
}
vector<int> sv;
for(auto j:modi[i]){
int l=j.fi.fi,r=j.fi.se,c=j.se;
if(r==0) continue;
if(l==0) l=1;
if(blg[r]==blg[l]){
if(~tag[blg[l]]){
int p=blg[l];
forup(k,L[p],R[p]) mex[k]=tag[p];
tag[p]=-1;
}
forup(k,l,r){
mex[k]=c;
}
sv.push_back(blg[l]);
}else{
if(~tag[blg[l]]){
int p=blg[l];
forup(k,L[p],R[p]) mex[k]=tag[p];
tag[p]=-1;
}
if(~tag[blg[r]]){
int p=blg[r];
forup(k,L[p],R[p]) mex[k]=tag[p];
tag[p]=-1;
}
forup(k,l,R[blg[l]]) mex[k]=c;
forup(k,L[blg[r]],r) mex[k]=c;
sv.push_back(blg[l]);sv.push_back(blg[r]);
forup(j,blg[l]+1,blg[r]-1) tag[j]=c;
}
}
fordown(j,i-1,max(L[blg[i]],i-m)){
int mm=mex[j];
if(~tag[blg[j]]) mm=tag[blg[j]];
dp[i]=max(dp[i],dp[j]+mm*(sum[i]-sum[j]));
}
sort(sv.begin(),sv.end());
sv.erase(unique(sv.begin(),sv.end()),sv.end());
for(auto j:sv){
getconv(j);
}
if(i-m>=1&&blg[i]!=blg[i-m]){
fordown(j,blg[i]-1,blg[i-m]+1){
if(~tag[j]){
update(j,tag[j]);
dp[i]=max(dp[i],tag[j]*sum[i]+mxv[j]);
}else{
while(conv[j].size()>=2&&slp(conv[j][0],conv[j][1],sum[i])) conv[j].pop_front();
dp[i]=max(dp[i],conv[j].front().fi*sum[i]-conv[j].front().se);
}
}
fordown(j,R[blg[i-m]],i-m){
int mm=mex[j];
if(~tag[blg[j]]) mm=tag[blg[j]];
dp[i]=max(dp[i],dp[j]+mm*(sum[i]-sum[j]));
}
}
if(i==R[blg[i]]){
work(blg[i]);
getconv(blg[i]);
}
}
printf("%lld\n",dp[n]);
}
P6822 [PA2012] Tax
题意
- 给定一张 $n$ 个点 $m$ 条边的边带权无向图。
- 定义一条路径的代价为每个点的花费之和，每个点（出去起点终点）的花费为路径上和它相连的两条边的边权较大值，起点和终点的花费为和它相连的边的边权。
- 求从 $1$ 到 $n$ 的最小花费。
- $1\le n\le 10^5,1\le m\le 2\times 10^5$，边权在 $[1,10^6]$ 以内。
题解
看了一眼感觉像建分层图将贡献挪到边上然后跑最短路，仔细想想发现确实是这样的。
首先完全不考虑复杂度，可以将每个点拆成 $c$ 个点（$c$ 是值域上界），将每个点边权为 $p$ 的出边扔到对应的点上，然后对于边 $(u,v,p)$，若下一条边（即 $v$ 的出边）的边权 $q$ 小于 $p$ 则点 $v$ 产生 $p$ 的贡献，若大于等于 $p$ 则点 $v$ 产生 $q$ 的贡献。
那么边 $(u,v,p)$ 则从点 $u_p$（这样写应该能看懂）向点 $v_1\sim v_{p-1}$ 连边权为 $p$ 的边，向 $v_{p}\sim v_{c}$ 连边权为 $v$ 下标的边。这个可以前缀和优化建图。
但是点数仍然超标。容易发现我们其实只关注和一个点相邻的边，所以每个点只需要拆成出边个数个点即可。
于是点数边数均为 $O(n+m)$，复杂度 $O((n+m)\log (n+m))$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=1e5+5;
const i64 inf=1e18;
int n,m,cntn;
i64 dis[N*15];
int vis[N*15];
vector<pii> e[N*15],nd[N];
vector<int> pre[N],suf[N];
struct edge{
int u,v,w;
bool operator<(const edge &r)const{return w<r.w;}
}s[N*2];
struct Node{
i64 u,dis;
bool operator<(const Node &r)const{return dis>r.dis;}
};
void dijkstra(){
forup(i,1,cntn) dis[i]=inf;
priority_queue<Node> q;
dis[suf[1][0]]=0;
q.push(Node{suf[1][0],0});
while(q.size()){
int u=q.top().u;q.pop();
if(vis[u]) continue;
vis[u]=1;
for(auto i:e[u]){
int v=i.fi,w=i.se;
if(dis[v]<=dis[u]+w) continue;
dis[v]=dis[u]+w;
q.push(Node{v,dis[v]});
}
}
}
signed main(){
n=read();m=read();
forup(i,1,m){
s[i].u=read();s[i].v=read();s[i].w=read();
}
sort(s+1,s+m+1);
nd[n].push_back(mkp(0,++cntn));
forup(i,1,m){
int u=s[i].u,v=s[i].v,w=s[i].w;
if(nd[u].empty()||w!=nd[u].back().fi) nd[u].push_back(mkp(w,++cntn));
if(nd[v].empty()||w!=nd[v].back().fi) nd[v].push_back(mkp(w,++cntn));
}
forup(i,1,n){
int sz=nd[i].size();
pre[i].resize(sz);
suf[i].resize(sz);
forup(j,0,sz-1){
pre[i][j]=++cntn;
e[pre[i][j]].push_back(mkp(nd[i][j].se,0));
if(j) e[pre[i][j]].push_back(mkp(pre[i][j-1],0));
}
fordown(j,sz-1,0){
suf[i][j]=++cntn;
e[suf[i][j]].push_back(mkp(nd[i][j].se,nd[i][j].fi));
if(j<sz-1) e[suf[i][j]].push_back(mkp(suf[i][j+1],0));
}
}
forup(i,1,m){
int u=s[i].u,v=s[i].v,w=s[i].w;
int pu=lower_bound(nd[u].begin(),nd[u].end(),mkp(w,0))-nd[u].begin(),
pv=lower_bound(nd[v].begin(),nd[v].end(),mkp(w,0))-nd[v].begin();
e[nd[u][pu].se].push_back(mkp(pre[v][pv],w));
if(pv<(int)nd[v].size()-1) e[nd[u][pu].se].push_back(mkp(suf[v][pv+1],0));
e[nd[v][pv].se].push_back(mkp(pre[u][pu],w));
if(pu<(int)nd[u].size()-1) e[nd[v][pv].se].push_back(mkp(suf[u][pu+1],0));
}
dijkstra();
printf("%lld\n",dis[pre[n][0]]);
}
CF1007D Ants
题意
- 有一棵 $n$ 个点的树，有 $m$ 个路径对，你要在每一对中选一条涂黑，要求一条边不能被涂黑超过一次，求出一组解。
- $1\le n\le 10^5,1\le m\le 10^4$
题解
感觉就很 2-SAT，但是有个问题是假如直接树剖用线段树优化建图会连出自环。
怎么办呢？考虑扫描，每次把一条链和之前的连边，然后把它加到线段树上，这个使用标记永久化，并且在线段树每个结点上维护时间轴的前缀和优化建图。
因为每个点需要向前向后都连边，所以正着扫一次反着扫一次即可。
边数 $O(n\log^2 n)$，复杂度也是这个。注意数组适当开大一点，不要用 std::vector 存图，不然容易 MLE。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=1e5+5,inf=0x3f3f3f3f;
int n,m,cntn;
vector<int> e[N];
void adde(int u,int v){
e[u].push_back(v);
}
int sz[N],son[N],dfn[N],Tm,hig[N],dpt[N],ff[N];
void dfs1(int x,int fa){
sz[x]=1;
dpt[x]=dpt[fa]+1;
ff[x]=fa;
for(auto i:e[x]){
if(i==fa) continue;
dfs1(i,x);
sz[x]+=sz[i];
if(son[x]==0||sz[i]>sz[son[x]]) son[x]=i;
}
}
void dfs2(int x,int fa,int hh){
hig[x]=hh;
dfn[x]=++Tm;
if(son[x]){
dfs2(son[x],x,hh);
}
for(auto i:e[x]){
if(i==fa||i==son[x]) continue;
dfs2(i,x,i);
}
}
namespace Tarjan{
struct edge{
int v,nxt;
}e[N*270];
int head[N*135],cnte;
void adde(int u,int v){
e[++cnte]=edge{v,head[u]};head[u]=cnte;
}
int dfn[N*135],low[N*135],blg[N*135],Tm,csc;
bitset<N*135> ist;
stack<int> stk;
void Tarjan(int x){
dfn[x]=low[x]=++Tm;
stk.push(x);ist[x]=1;
for(int i=head[x];i;i=e[i].nxt){
int v=e[i].v;
if(!dfn[v]){
Tarjan(v);
low[x]=min(low[x],low[v]);
}else if(ist[v]){
low[x]=min(low[x],dfn[v]);
}
}
if(dfn[x]==low[x]){
++csc;
for(int v=0;v!=x;){
v=stk.top();
blg[v]=csc;
ist[v]=0;
stk.pop();
}
}
}
void solve(){
forup(i,1,cntn){
if(!dfn[i]) Tarjan(i);
}
forup(i,1,m){
if(blg[i*2]==blg[i*2-1]){
puts("NO");
exit(0);
}
}
}
}
struct SegTree{
#define mid ((l+r)>>1)
#define lson l,mid,id<<1
#define rson mid+1,r,id<<1|1
int nd[N<<2],mk[N<<2];
void Build(int l=1,int r=n,int id=1){
nd[id]=mk[id]=0;
if(l==r) return;
Build(lson);Build(rson);
}
void Update(int L,int R,int X,int l=1,int r=n,int id=1){
int nw=++cntn;
Tarjan::adde(nw,X);
if(nd[id]) Tarjan::adde(nw,nd[id]);
nd[id]=nw;
if(L<=l&&r<=R){
int nw=++cntn;
Tarjan::adde(nw,X);
if(mk[id]) Tarjan::adde(nw,mk[id]);
mk[id]=nw;
return;
}
if(L<=mid) Update(L,R,X,lson);
if(mid< R) Update(L,R,X,rson);
}
void Link(int L,int R,int X,int l=1,int r=n,int id=1){
if(mk[id]) Tarjan::adde(X,mk[id]);
if(L<=l&&r<=R){
if(nd[id]) Tarjan::adde(X,nd[id]);
return;
}
if(L<=mid) Link(L,R,X,lson);
if(mid< R) Link(L,R,X,rson);
}
};
SegTree mt;
void Update(int u,int v,int nw){
while(hig[u]!=hig[v]){
if(dpt[hig[u]]<dpt[hig[v]]) swap(u,v);
mt.Update(dfn[hig[u]],dfn[u],nw);
u=ff[hig[u]];
}
if(dpt[u]>dpt[v]) swap(u,v);
if(dfn[u]!=dfn[v]) mt.Update(dfn[u]+1,dfn[v],nw);
}
void Link(int u,int v,int nw){
while(hig[u]!=hig[v]){
if(dpt[hig[u]]<dpt[hig[v]]) swap(u,v);
mt.Link(dfn[hig[u]],dfn[u],nw);
u=ff[hig[u]];
}
if(dpt[u]>dpt[v]) swap(u,v);
if(dfn[u]!=dfn[v]) mt.Link(dfn[u]+1,dfn[v],nw);
}
struct opr{
int u1,v1,u2,v2;
}s[N];
signed main(){
n=read();
forup(i,1,n-1){
int u=read(),v=read();
e[u].push_back(v);
e[v].push_back(u);
}
dfs1(1,0);
dfs2(1,0,1);
m=read();
cntn=m*2;
forup(i,1,m){
int u1=read(),v1=read(),u2=read(),v2=read();
s[i]=opr{u1,v1,u2,v2};
int n1=i*2,n2=n1-1;
Link(u1,v1,n1);Link(u2,v2,n2);
Update(u1,v1,n2);Update(u2,v2,n1);
}
mt.Build();
fordown(i,m,1){
int u1=s[i].u1,v1=s[i].v1,u2=s[i].u2,v2=s[i].v2;
int n1=i*2,n2=n1-1;
Link(u1,v1,n1);Link(u2,v2,n2);
Update(u1,v1,n2);Update(u2,v2,n1);
}
Tarjan::solve();
puts("YES");
forup(i,1,m){
puts(Tarjan::blg[i*2]<Tarjan::blg[i*2-1]?"1":"2");
}
}
[ABC217F] Make Pair
题意
- 有 $2n$ 个人排成一排，其中有 $m$ 对好朋友。
- 每次要选一对相邻的好朋友出列，然后两侧的人就变成相邻的。
- 问有多少种出列方案，称两方案不同当且仅当存在某一对配对的人不同或存在某两对出列顺序不同。
- $1\le n\le 200,1\le m\le n(2n-1)$。
题解
容易想到区间 DP，类似于石子合并。设 $f_{l,r}$ 表示 $[l,r]$ 的人全部出列的方案数，转移有两种，若 $l,r$ 是一对好朋友则 $f_{l,r}\gets f_{l+1,r-1}$，另外还可以枚举一个分界点 $k$，然后 $f_{l,r}\gets f_{l,k-1}\times f_{k,r}\times \binom{\frac{r-l+1}{2}}{\frac{r-len}{2}}$。
但是有一个 BUG，一个方案可能有多个分界点，显然从每个分界点都可能转移，怎么办呢？我们可以钦定 $k$ 是最后一个分界点，那么 $(k,r)$ 必定是一对好朋友，于是转移改为 $f_{l,r}\gets f_{l,k-1}\times f_{k+1,r-1}\times \binom{\frac{r-l+1}{2}}{\frac{r-len}{2}}$（注意要求 $k,r$ 是一对好朋友）。
复杂度 $O(n^3)$，我写的时候没带脑子所以带了个 $\log$，好孩子不要学。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=405,inf=0x3f3f3f3f,mod=998244353;
int n,m,binom[N][N];
set<int> pi[N];
int dp[N][N];
signed main(){
n=read();m=read();
forup(i,0,n*2){
binom[i][0]=1;
forup(j,1,i){
binom[i][j]=(binom[i-1][j]+binom[i-1][j-1])%mod;
}
dp[i][i-1]=1;
}
forup(i,1,m){
int l=read(),r=read();
pi[r].insert(l);
}
for(int len=2;len<=2*n;len+=2){
forup(l,1,n*2-len+1){
int r=l+len-1;
if(pi[r].count(l)){
(dp[l][r]+=dp[l+1][r-1])%=mod;
}
for(int i=l+2;i<=r-1;i+=2){
if(pi[r].count(i)){
(dp[l][r]+=1ll*dp[l][i-1]*dp[i+1][r-1]%mod*binom[(r-l+1)/2][(i-l)/2]%mod)%=mod;
}
}
}
}
printf("%d\n",dp[1][n*2]);
}
QOJ#2606 Gachapon
题意
- 有一个抽卡游戏，里面有的物品有从 $0$ 到 $m$ 共 $m+1$ 种星级，一抽抽出 $i$ 星物品的概率是 $\frac{a_i}{\sum a}$。
- 此游戏和原神一样设有保底机制，即在一个 $i$ 级抽卡中至少抽出一个大于等于 $i$ 星的物品。我们这样定义 $i$ 级抽卡：
- $0$ 级抽卡为一抽。
- $i$ 级抽卡为 $b_i$ 个 $i-1$ 级抽卡。
- 称一个 $i$ 级抽卡是合法的（非常巧的是，在我国没有保底/井/兑换机制的抽卡游戏确实是违反法律的）当且仅当其中抽出了至少一个 $i$ 星物品，且构成这个 $i$ 级抽卡的 $i-1$ 级抽卡均为合法的。
- 设 $q$ 为一次 $n$ 级抽卡是合法的的概率，$p_i$ 为一次合法的 $n$ 级抽卡中抽出 $i$ 星物品的期望个数，对于 $i\in[0,m]$，求出 $p_i\cdot q$。
- $1\le n\le m\le 4000,1\le a_i\le 4000,2\le b_i\le 4000$，答案对 $998244353$ 取模。
题解
感觉没什么思路，不如我们先想想怎么求合法的概率。
容易想到 DP，设 $f_{i,j}$ 表示合法的 $i$ 级抽卡中抽出的物品最大不超过 $j$ 星的方案数，转移就是一个简单容斥，随便搞一搞就行了。
然后怎么求抽出每个物品的期望呢？考虑求出 $i$ 星物品的 $0$ 级抽卡有多大概率成为一个合法 $n$ 级抽卡的组成部分，不妨设这个概率为 $g_{0,i}$，于是答案就是 $p_i=g_{0,i}\times\frac{a_i}{\sum a}\times \prod b$。
那么 $g$ 可以从上往下 DP 求出，转移还是比较简单的，就是考虑这个 $i$ 级抽卡是不是 $i+1$ 级抽卡中的最大值计算即可。
复杂度 $O(nm)$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=4005,inf=0x3f3f3f3f,mod=998244353;
int ksm(int a,int b){
int c=1;
while(b){
if(b&1) c=1ll*a*c%mod;
a=1ll*a*a%mod;
b>>=1;
}
return c;
}
int n,m,a[N],b[N],f[N][N],g[N][N],sum,inv;
signed main(){
m=read();n=read();
forup(i,0,m){
a[i]=read();
sum+=a[i];
}
inv=ksm(sum,mod-2);
forup(i,1,n){
b[i]=read();
}
forup(i,0,m){
f[0][i]=1ll*a[i]*inv%mod;
}
forup(i,1,m){
(f[0][i]+=f[0][i-1])%=mod;
}
forup(i,1,n){
forup(j,i,m){
f[i][j]=(ksm(f[i-1][j],b[i])-ksm(f[i-1][j-1],b[i])+mod)%mod;
(f[i][j]+=f[i][j-1])%=mod;
}
}
forup(i,n,m) g[n][i]=1;
fordown(i,n-1,0){
int sum=0;
fordown(j,m,i+1){
g[i][j]=(sum+1ll*g[i+1][j]*ksm(f[i][j],b[i+1]-1)%mod)%mod;
(sum+=1ll*g[i+1][j]*(ksm(f[i][j],b[i+1]-1)+mod-ksm(f[i][j-1],b[i+1]-1))%mod)%=mod;
}
g[i][i]=sum;
}
int mul=1;
forup(i,1,n) mul=1ll*mul*b[i]%mod;
forup(i,0,m){
int ans=1ll*g[0][i]*a[i]%mod*inv%mod*mul%mod;
printf("%d\n",ans);
}
}
模拟赛神秘题目 【0907 B组】 D 绳网委托
《》
题意
- 有一个 $01$ 序列，你可以进行翻转 （相当于
std::reverse）一个区间的操作。 - 对于 $0\le i\le n$，求进行恰好 $i$ 次操作所能得到的最长不下降子序列长度。
- 给出序列的方式是 $n$ 个二元组 $(0/1,x_i)$，表示将这个二元组替换为 $x_i$ 个对应数字。
- $1\le n\le 2\times 10^5$
题解
愿天堂没有和题目完全无关的题目背景。
首先一次反转肯定不能把某一段裂开，所以相当于把序列长度缩减到 $n$。
考虑如何求答案，容易想到将 $1$ 替换成 $-1$，$0$ 替换成 $1$，答案就是 $1$ 的个数加上最大的前缀和（即这个前缀的 $0$ 产生贡献，后面的 $1$ 产生贡献）。
考虑最优策略肯定是每次把某一段接到最大前缀后面，这样最大前缀和就会变大。
于是考虑这样一个经典的反悔贪心，用线段树维护最大区间和，每次取出最大区间计入答案，然后区间乘 $-1$，这样假如以后的区间和这个区间有交就相当于把相交部分反悔。
注意一开始也要把选到的前缀乘 $-1$。
复杂度 $O(n\log n)$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(i64 i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(i64 i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<i64,i64>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=2e5+5;
i64 n,v[N];
struct Node{
i64 l,r,v;
bool operator<(const Node &p)const{return v<p.v;}
bool operator>(const Node &p)const{return v>p.v;}
Node operator+(const Node &p){
if(l==0) return p;
if(p.l==0) return *this;
return Node{min(l,p.l),max(r,p.r),v+p.v};
}
Node operator-(){
return Node{l,r,-v};
}
};
Node min(Node a,Node b){
if(a<b) return a;
return b;
}
Node max(Node a,Node b){
if(a>b) return a;
return b;
}
struct SegTree{
#define mid ((l+r)>>1)
#define lson l,mid,id<<1
#define rson mid+1,r,id<<1|1
Node mx[N<<2],lmx[N<<2],rmx[N<<2];
Node mn[N<<2],rmn[N<<2],lmn[N<<2];
Node sum[N<<2];
i64 mark[N<<2];
void PushUp(i64 id){
sum[id]=sum[id<<1]+sum[id<<1|1];
mx[id]=max(max(mx[id<<1],mx[id<<1|1]),rmx[id<<1]+lmx[id<<1|1]);
mn[id]=min(min(mn[id<<1],mn[id<<1|1]),rmn[id<<1]+lmn[id<<1|1]);
lmn[id]=min(lmn[id<<1],sum[id<<1]+lmn[id<<1|1]);
lmx[id]=max(lmx[id<<1],sum[id<<1]+lmx[id<<1|1]);
rmn[id]=min(rmn[id<<1|1],rmn[id<<1]+sum[id<<1|1]);
rmx[id]=max(rmx[id<<1|1],rmx[id<<1]+sum[id<<1|1]);
}
void modi(i64 id){
mark[id]^=1;
swap(mx[id],mn[id]);
swap(lmx[id],lmn[id]);
swap(rmx[id],rmn[id]);
mx[id]=-mx[id];mn[id]=-mn[id];
lmx[id]=-lmx[id];lmn[id]=-lmn[id];
rmx[id]=-rmx[id];rmn[id]=-rmn[id];
sum[id]=-sum[id];
}
void PushDown(i64 id){
modi(id<<1);modi(id<<1|1);
mark[id]=0;
}
void Build(i64 l=1,i64 r=n,i64 id=1){
mark[id]=0;
if(l==r){
mx[id]=lmx[id]=rmx[id]=v[l]>0?Node{l,r,v[l]}:Node{0,0,0};
mn[id]=lmn[id]=rmn[id]=v[l]<0?Node{l,r,v[l]}:Node{0,0,0};
sum[id]=Node{l,r,v[l]};
return;
}
Build(lson);Build(rson);
PushUp(id);
}
void Update(i64 L,i64 R,i64 l=1,i64 r=n,i64 id=1){
if(L>R) return;
if(L<=l&&r<=R){
modi(id);
return;
}
if(mark[id]) PushDown(id);
if(L<=mid) Update(L,R,lson);
if(mid< R) Update(L,R,rson);
PushUp(id);
}
Node Query(){
return mx[1];
}
};
SegTree mt;
i64 mx=0,val=0,sum=0,p=0;
signed main(){
n=read();
forup(i,1,n){
i64 c=read();
v[i]=read();
if(c) v[i]*=-1,val-=v[i];
sum+=v[i];
if(sum>mx){
mx=sum;
p=i;
}
}
mt.Build();
mt.Update(1,p);
val+=mx;
printf("%lld\n",val);
forup(i,1,n){
Node res=mt.Query();
if(res.v>0){
val+=res.v;
mt.Update(res.l,res.r);
}
printf("%lld\n",val);
}
}
P3734 [HAOI2017] 方案数
题意
- 对于两非负整数 $x,y$，我们用 $x\subseteq y$ 表示 $x\And y=x$，其中 $\And$ 代表按位与。
- 有一个三维坐标系，你最初在 $(0,0,0)$，每次可以选择一维，设这一维当前的值为 $a$，可以一步走到任何 $a'\ne a$ 满足 $a\subseteq a'$。
- 坐标中有 $n$ 个障碍物，你不能在这些点逗留，求从 $(0,0,0)$ 到 $(X,Y,Z)$ 的方案数。
- $1\le X,Y,Z\le 10^{18},1\le n\le 10^4$，保证所有坐标都小于等于对应维度的终点，障碍物坐标互不相同，且起点和终点不是障碍物，答案对 $998244353$ 取模。
题解
难点在于勇敢地对 $10^4$ 写 $O(n^2)$ 做法，但是全机房几乎没有一发过的。
首先没有障碍物怎么做呢？注意到每走一步相当于把某维坐标中的若干个 $0$ 改成 $1$。那么容易发现方案数只和每一维（起点和终点的差中） $1$ 的个数有关。于是设 $f_{i,j,k}$ 表示三维 $1$ 的个数分别是 $i,j,k$ 的方案数，可以简单转移，乘个组合数即可，复杂度 $O(\log^4 V)$，其中 $V$ 是值域。
然后就是经典容斥了，设 $dp_i$ 表示不经过其它障碍走到 $i$ 障碍的方案数，这个很经典就不多赘述了，复杂度 $O(n^2)$，注意转移顺序，考虑升序排列即可。
fun fact：__builtin_popcountll 是 $O(1)$ 的。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(i64 i=(s),E123123=(e);i<=E123123;++i)
#define fordown(i,s,e) for(i64 i=(s),E123123=(e);i>=E123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr.args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<i64,i64>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)){if(c=='-')f=-1;}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=1e4+5,mod=998244353;
i64 X,Y,Z,n;
i64 f[70][70][70],binom[70][70],dp[N];
struct Node{
i64 x,y,z;
}p[N];
i64 calc(Node a,Node b){
if(((a.x&b.x)!=a.x)||((a.y&b.y)!=a.y)||((a.z&b.z)!=a.z)) return 0;
int px=__builtin_popcountll(b.x^a.x),py=__builtin_popcountll(b.y^a.y),pz=__builtin_popcountll(b.z^a.z);
return f[px][py][pz];
}
signed main(){
X=read();Y=read();Z=read();
n=read();
forup(i,1,n){
p[i].x=read();p[i].y=read();p[i].z=read();
}
++n;
p[n].x=X;p[n].y=Y;p[n].z=Z;
forup(i,0,60){
binom[i][0]=1;
forup(j,1,i){
binom[i][j]=(binom[i-1][j-1]+binom[i-1][j])%mod;
}
}
f[0][0][0]=1;
forup(i,0,60){
forup(j,0,60){
forup(k,0,60){
if(!i&&!j&&!k) continue;
forup(p,0,60){
if(p<i) (f[i][j][k]+=f[p][j][k]*binom[i][p]%mod)%=mod;
if(p<j) (f[i][j][k]+=f[i][p][k]*binom[j][p]%mod)%=mod;
if(p<k) (f[i][j][k]+=f[i][j][p]*binom[k][p]%mod)%=mod;
}
}
}
}
sort(p+1,p+n+1,[&](Node a,Node b){
if(a.x!=b.x) return a.x<b.x;
if(a.y!=b.y) return a.y<b.y;
return a.z<b.z;
});
forup(i,1,n){
dp[i]=calc(Node{0,0,0},p[i]);
forup(j,1,i-1){
dp[i]=(dp[i]+mod-dp[j]*calc(p[j],p[i])%mod)%mod;
}
}
printf("%lld\n",dp[n]);
}
P4302 [SCOI2003] 字符串折叠
题意
- 定义字符串的折叠
x(S)表示 $x$ 个 $S$ 字符顺次连接。特别地，当 $x=1$ 时，数字 $x$ 和括号可以省略。 - 给定字符串 $T$，求最短折叠的长度（比如
abbbbabbbb的最短折叠是2(a4(b))，长度为 $8$）。 - $|T|\le 100$。
题解
一眼 DP，容易想到区间 DP，设 $f_{l,r}$ 表示区间 $[l,r]$ 的最短折叠。
转移可以把两段拼接起来或者将整个区间折叠起来，将整个区间折叠起来可以暴力枚举因数再 $O(len)$ 暴力 check，总复杂度 $O(n^3\tau(n))$，其中 $\tau$ 是约数个数函数，大约是 $O(\sqrt{n})$ 级别的。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=105,inf=0x3f3f3f3f;
int n;
char str[N];
int getlen(int x){
int p=0;
while(x){
x=x/10;
++p;
}
return p;
}
bool chk(int len,int l,int r){
if((r-l+1)%len) return false;
forup(i,l+len,r){
if(str[i]!=str[(i-l)%len+l]) return false;
}
return true;
}
int dp[N][N];
signed main(){
scanf(" %s",str+1);
n=strlen(str+1);
forup(i,1,n){
dp[i][i]=1;
}
forup(len,2,n){
forup(l,1,n-len+1){
int r=l+len-1;
dp[l][r]=(r-l+1);
forup(k,l,r-1){
dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]);
}
forup(k,1,r-l+1){
if(chk(k,l,r)){
dp[l][r]=min(dp[l][r],dp[l][l+k-1]+2+getlen((r-l+1)/k));
}
}
}
}
printf("%d\n",dp[1][n]);
}
UniversalOJ #884 509 号迷宫
唉，跳蚤题。
题意
- 有一张 $(n+1)\times (n+1)$ 的网格图（下标范围 $[0,n]$），上面除了第 $0$ 行外每一行都有一个障碍不能经过。
- 求从 $(0,0)$ 到 $(n,n)$ 的路径数，答案对 $509$ 取模，且保证 $n$ 是 $509$ 的倍数（除去样例一），保证起点和终点不是障碍物。
- $1\le n\le 509\times 500$。
题解
跳蚤题，太神秘，不看题解做不起。
令 $p=509$。
首先不考虑障碍是经典中的经典，答案是 $\binom{n+m-2}{n-1}$。
注意到一个组合数的性质，若 $n \ge p$，则 $\binom{n}{m}\bmod p$ 只在 $m=0,m=n$ 时取 $1$，其余均为 $0$。感觉这个结论在这道题看起来非常有用的样子。
然后 看一眼题解 就能想到对 $x+y$ 设状态，设 $dp_{i,x}$ 表示从起点到点 $(x,i\times p-x)$ 的路径数。即每隔 $P$ 条斜杠拿一条出来当成关键点进行 DP，因为 $n$ 是 $p$ 的倍数所以必然是关键点。于是有转移 $dp_{i+1,x}\gets dp_{i,x},dp_{i+1,x+p}\gets dp_{i,x}$，状态数 $O(\frac{n^2}{p})$
然后考虑两条斜杠之间的障碍，这个直接暴力是 $O(n^2)$ 的，注意到对于每个障碍只有一小部分（大致是一个三角形，但是直接搞成矩形也没啥影响）点能转移到它（其它因为上面的结论只会产生 $0$ 的贡献），因为每一行至多有一个障碍，而一条斜线在每一行也只有 $1$ 个点。所以只需要遍历这些点就行了。然后障碍往后转移到下一条斜线的关键点也是同理。复杂度 $O(np)$。
于是总复杂度 $O(\frac{n^2}{p}+np)$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=260000,P=520,inf=0x3f3f3f3f,p=509;
int n,binom[P<<1][P<<1],dp[P<<1][N],f[N],a[N];
signed main(){
n=read();
forup(i,1,n){
a[i]=read();
}
forup(i,0,p*2){
binom[i][0]=1;
forup(j,1,i){
binom[i][j]=(binom[i-1][j]+binom[i-1][j-1])%p;
}
}
dp[0][0]=1;
forup(t,0,2*n/p-1){
forup(j,0,n){
if(!dp[t][j]) continue;
int k=(t+1)*p;
if(0<=k-j&&k-j<=n) (dp[t+1][j]+=dp[t][j])%=p;
if(j+p<=n&&0<=k-j-p&&k-j-p<=n) (dp[t+1][j+p]+=dp[t][j])%=p;
}
mem(f,0);
forup(i,1,n){
if(t*p<=i+a[i]&&i+a[i]<=(t+1)*p){
forup(x,i-p,i){
if(x<0) continue;
int y=t*p-x;
if(0<=y&&y<=a[i]){
f[i]+=dp[t][x]*binom[i-x+a[i]-y][i-x]%p;
}
if(x<i&&f[x]&&a[x]<=a[i]){
f[i]=(f[i]+p-f[x]*binom[i-x+a[i]-a[x]][i-x]%p)%p;
}
}
forup(x,i,i+p){
if(x>n) continue;
int y=(t+1)*p-x;
if(y<a[i]||y>n) continue;
dp[t+1][x]=(dp[t+1][x]+p-f[i]*binom[x-i+y-a[i]][x-i]%p)%p;
}
}
}
}
printf("%d\n",dp[2*n/p][n]);
}
CF1572C Paint
题意
- 有一个长度为 $n$ 的序列，上面每个点有颜色 $a_i$。你每次可以选择一段极长连续同色段变成另一种颜色。
- 求把整个序列变成同一种颜色至少需要操作多少次。
- 带多测，$1\le \sum n\le 3000,1\le a_i\le n$，每种颜色至多出现 $20$ 次。
题解
首先答案有一个显然的上界：$n-1$，把颜色挨个变成某一种即可。考虑怎么让这个答案变小。
容易发现假如 $a_l=a_r$，那么在将 $[l+1,r-1]$ 全部变为 $a_l$ 后，只需要一次操作就可以将这两个颜色同时改变，那么我们就要最大化这个的数量。容易想到区间 DP。
设 $f_{l,r}$ 表示将 $[l,r]$ 变为同色最多能减少多少次操作，首先假如最后一次减少和 $l$ 无关则有转移 $f_{l,r}\gets f_{l+1,r}$，否则枚举最后一次减少和 $l$ 配对的点 $k$，那么 $f_{l,r}\gets f_{l+1,k-1}+1+f_{k,r}$（注意 $a_l=a_k$），为什么是从 $f_{k,r}$ 转移过来呢？容易发现 $l,k$ 的减少可能和 $k,r$ 的减少同时进行，于是从 $f_{k,r}$ 而非 $f_{k+1,r}$ 转移过来就不会算漏这种情况了。
复杂度 $O(n^2)$，显然你只需要枚举和 $l$ 同色的 $k$，所以每次转移至多枚举 $20$ 个。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=3005,inf=0x3f3f3f3f;
int n,a[N],dp[N][N];
vector<int> pos[N];
void solve(){
n=read();
forup(i,1,n){
a[i]=read();
pos[i].clear();
}
forup(i,1,n){
pos[a[i]].push_back(i);
}
forup(len,2,n){
forup(l,1,n-len+1){
int r=l+len-1;
dp[l][r]=dp[l+1][r];
for(auto p:pos[a[l]]){
if(p<=l||p>r) continue;
dp[l][r]=max(dp[l][r],dp[l+1][p-1]+1+dp[p][r]);
}
}
}
printf("%d\n",n-1-dp[1][n]);
}
signed main(){
int t=read();
while(t--){
solve();
}
}
P3736 [HAOI2016] 字符合并
题意
- 给定一长度为 $n$ 的 $01$ 序列，每次你可以选择长度恰好为 $k$ 的一段，替换为某个指定字符（$0$ 或 $1$）并产生一定贡献。具体替换成什么和产生什么贡献在题目上给定。
- 求最大能获得多少贡献。
- $1\le n\le 300,1 < k\le 8$
题解
看着就很区间 DP 吧？很像石子合并。然后因为 $k\le 8$ 容易想到状压，并且最大贡献肯定是缩到不能缩为止。
具体来说，设 $f_{l,r,msk}$ 表示区间 $[l,r]$ 得到序列 $msk$ 能获得的最大贡献，直接做大约是 $O(n^32^{k-1})$ 的，枚举第一个字符占了多长即可。这个不太能过，怎么优化呢？
容易发现因为能缩必缩，所以长度为 $len$ 的序列缩出来长度必定为 $len\bmod (k-1)+1$，那么其实只需要隔 $k-1$ 个枚举一个即可，复杂度 $O(\frac{n^3}{k}2^{k-1})$，然后就比较好过了。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(i64 i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(i64 i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<i64,i64>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=305,inf=1e18;
i64 n,m,to[N],val[N],a[N];
char str[N];
i64 dp[N][N][N];
signed main(){
n=read();m=read();
scanf(" %s",str+1);
forup(i,1,n) a[i]=str[i]-'0';
forup(i,0,(1<<m)-1){
to[i]=read();val[i]=read();
}
forup(i,1,n){
forup(j,i,n){
forup(k,0,(1<<m)-1){
dp[i][j][k]=-inf;
}
if(i==j) dp[i][j][a[i]]=0;
}
}
forup(len,2,n){
forup(l,1,n-len+1){
i64 r=l+len-1,dd=(r-l-1)%(m-1)+1;
forup(k,0,(1<<dd)-1){
dp[l][r][k+(a[l]<<dd)]=dp[l+1][r][k];
}
for(i64 k=l;k<r;k+=m-1){
i64 dd=(r-k-1)%(m-1)+1;
forup(p,0,(1<<dd)-1){
dp[l][r][p+(1<<dd)]=max(dp[l][r][p+(1<<dd)],dp[l][k][1]+dp[k+1][r][p]);
dp[l][r][p]=max(dp[l][r][p],dp[l][k][0]+dp[k+1][r][p]);
}
}
if((r-l)%(m-1)==0){
i64 mx0=-inf,mx1=-inf;
forup(k,0,(1<<m)-1){
if(to[k]){
mx1=max(mx1,dp[l][r][k]+val[k]);
}else{
mx0=max(mx0,dp[l][r][k]+val[k]);
}
dp[l][r][k]=-inf;
}
dp[l][r][0]=mx0;dp[l][r][1]=mx1;
}
}
}
i64 ans=-inf,dd=(n-1)%(m-1)+1;
forup(i,0,(1<<dd)-1){
ans=max(ans,dp[1][n][i]);
}
printf("%lld\n",ans);
}
P9907 [COCI 2023/2024 #1] Mostovi
题意
- 有一张 $n$ 个点 $m$ 条边的简单无向连通图，求有多少条边，使得删掉这条边及其两端点后图不连通。
- $1\le n\le 10^5,1\le m\le 3\times 10^5$
题意
不算难，但是细节巨多。下文称“删掉这条边及其两端点后图不连通”的边为“合法”
考虑在一棵 dfs 生成树上做，首先考虑树边 $(u,f)$ 是否合法（$f$ 是 $u$ 的父亲），容易发现它合法说明从 $u$ 或者 $f$ 的某个子树没有指向 $f$ 的祖先的返祖边，那么不妨对每个子树维护 $mn_i$ 表示这个子树能通过返祖边到达的点深度最小是多少，那么边 $(u,f)$ 合法当且仅当 $u$ 和 $f$ 的子树中 $mn$ 的最大值大于等于 $dpt_f$（注意考虑 $f$ 的子树）。
然后考虑非树边 $(u,v)$（$dpt_v<dpt_u$，dfs 树上只有返祖边），那么点大致能分为四类：$v$ 的外子树 $S_1$，$u$ 的外子树减去 $v$ 的外子树 $S_2$，$u$ 的子树 $S_3$，$v$ 的子树减去 $u$ 所在的那个。这种时候显然算不合法的会好算一点。
不合法即删掉这两个点仍然连通，那么 $u,v$ 的每个子树必然都有朝 $S_1$ 或 $S_2$ 的连边（这个我用的启发式合并维护），然后 $S_1$ 还必须和 $S_2$ 连通，那么有可能 $S_1,S_2$ 之间本来就有连边，或者 $u$ 的某个子树同时连向了 $S_1,S_2$，维护方法有很多，前者我直接倍增维护，后者我用每个 $u$ 的子树做了一个区间涂色，总之方法很多。然后我代码写的比较丑，判 $S_4$ 要和 $S_1$ 连通的部分写的很屎，没什么参考价值。
复杂度 $O(n\log^2 n)$，瓶颈在启发式合并。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123=(e);i<=E123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123=(e);i>=E123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)){if(c=='-')f=-1;}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=1e5+5,inf=0x3f3f3f3f;
int n,m,ans,cc[N];
vector<int> e[N],son[N],ntr[N],ntr_[N];;
int vis[N],dpt[N],sz[N],ff[N];
int mn[N],smn[N];
set<int> to[N];
bool flag[N];
void dfs(int x,int fa){
vis[x]=1;
dpt[x]=dpt[fa]+1;
mn[x]=dpt[x];
smn[x]=inf;
sz[x]=1;ff[x]=fa;
for(auto i:e[x]){
if(i==fa) continue;
if(vis[i]){
if(dpt[i]<dpt[x]){
to[x].insert(dpt[i]);
ntr[x].push_back(i);
ntr_[i].push_back(x);
++cc[i];
}
continue;
}
son[x].push_back(i);
dfs(i,x);
if(mn[i]<mn[x]){
smn[x]=mn[x];mn[x]=mn[i];
}else if(mn[i]<smn[x]){
smn[x]=mn[i];
}
sz[x]+=sz[i];
}
if(to[x].size()){
// msg("(%d %d)|||||\n",x,*to[x].begin());
int p=*to[x].begin();
if(p<mn[x]){
smn[x]=mn[x];mn[x]=p;
}else if(p<smn[x]){
smn[x]=p;
}
}
}
int f[18][N],gmn[18][N];
void dfs2(int x){
forup(j,1,17){
f[j][x]=f[j-1][f[j-1][x]];
gmn[j][x]=min(gmn[j-1][x],gmn[j-1][f[j-1][x]]);
}
for(auto i:son[x]){
if(mn[i]==mn[x]){
gmn[0][i]=smn[x];
}else{
gmn[0][i]=mn[x];
}
f[0][i]=x;
dfs2(i);
}
}
int Query(int u,int d){
int res=inf;
fordown(i,17,0){
if(dpt[f[i][u]]>=d){
res=min(res,gmn[i][u]);
u=f[i][u];
}
}
return res;
}
struct BIT{
int c[N];
void upd(int x,int k){for(;x<=n;x+=x&-x)c[x]+=k;}
void Update(int L,int R,int k){upd(L,k);upd(R+1,-k);}
int ask(int x){int res=0;for(;x>0;x-=x&-x)res+=c[x];return res;}
}mt;
void dfs3(int x){
set<int> inva;
flag[x]=false;
vector<pii> vv;
for(auto i:son[x]){
dfs3(i);
to[i].erase(to[i].lower_bound(dpt[x]),to[i].end());
if(to[i].empty()&&(x!=1||son[x].size()>1)) flag[x]=true;
if(to[i].size()==1){
inva.insert(*to[i].begin());
}
if(to[i].size()>1){
vv.push_back(mkp(*to[i].begin()+1,*prev(to[i].end())-1));
}
if(to[x].size()<to[i].size()) swap(to[x],to[i]);
for(auto j:to[i]) to[x].insert(j);
}
for(auto i:vv){
mt.Update(i.fi,i.se,1);
}
if(flag[x]){
ans+=ntr[x].size()+cc[x];
msg("E %d (%d)",x,cc[x]);
for(auto i:ntr[x]){
--cc[i];
msg("C %d %d|\n",x,i);
}
}else{
for(auto i:ntr[x]){
if(flag[i]){continue;}
if(inva.count(dpt[i])){
msg("A %d %d|\n",x,i);
--cc[i];
++ans;
continue;
}
if(i==1||dpt[i]>Query(x,dpt[i]+1)) continue;
if(mt.ask(dpt[i])) continue;
msg("%d %d|%d|",dpt[i],Query(x,dpt[i]+1),mt.ask(dpt[i]));
++ans;
--cc[i];
msg("B %d %d|\n",x,i);
}
}
for(auto i:vv){
mt.Update(i.fi,i.se,-1);
}
}
signed main(){
n=read();m=read();
forup(i,1,m){
int u=read(),v=read();
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1,0);
forup(x,2,n){
int mxn=0;
for(auto i:son[x]){
mxn=max(mxn,mn[i]);
}
for(auto i:son[ff[x]]){
if(i==x) continue;
mxn=max(mxn,mn[i]);
}
// msg("[%d %d]\n",x,mxn);
if(son[x].size()+son[ff[x]].size()-1+(ff[x]!=1)>1&&mxn>=dpt[x]-1){
++ans;
msg("D %d %d|\n",x,ff[x]);
}
}
dfs2(1);
dfs3(1);
printf("%d\n",ans);
}
[AGC062B] Split and Insert
题意
- 有一个 $n$ 阶排列 $a_i$，初始单调上升，你每次可以选择一个数字 $k$，然后将末尾 $k$ 个元素插入前面。形式化的，操作后的序列需要满足 $(a_1,a_2,\dots a_{n-k})$ 和 $(a_{n-k+1},a_{n-k+1},\dots a_n)$ 是新序列的两个子序列。
- 给定一长度为 $m$ 的数组 $c_i$，第 $i$ 次操作的代价为 $k\times c_i$，求能否在 $m$ 次操作中将 $a$ 变成一个指定排列 $p$，并求出最小代价。
- $1\le n,m\le 100$，所有数小于等于 $10^9$。
题解
妙妙题。
首先正着做不好搞，考虑倒过来，就是每次选一个子序列扔到序列末尾。
因为每次肯定要操作值域的一个区间，并且显然一个方案中区间要么相离要么包含，于是考虑区间 DP。
具体来说，设 $dp_{t,l,r}$ 表示在 $[t,k]$ 操作中值域区间 $[l,r]$ 已经排成升序的最小代价。转移和初值是简单的，转移就要么不操作，要么枚举这个区间是由上一次操作后的哪两个区间拼起来得到的，“拼起来”就是把更大的那个扔到序列末尾，代价是好算的。
复杂度 $O(n^3k)$
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(i64 i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(i64 i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<i64,i64>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=105,inf=1e18;
i64 n,m,c[N],a[N],p[N];
i64 dp[N][N][N];
signed main(){
n=read();m=read();
forup(i,1,m) c[i]=read();
forup(i,1,n){
a[i]=read();
p[a[i]]=i;
}
forup(i,1,n){
forup(j,1,n){
forup(k,1,m+1){
dp[k][i][j]=inf;
}
}
}
forup(i,1,n){
forup(j,i,n){
dp[m+1][i][j]=0;
if(p[j]>p[j+1]) break;
}
}
forup(len,1,n){
forup(l,1,n-len+1){
i64 r=l+len-1;
fordown(t,m,1){
dp[t][l][r]=dp[t+1][l][r];
forup(k,l,r-1){
dp[t][l][r]=min(dp[t][l][r],dp[t+1][l][k]+dp[t+1][k+1][r]+c[t]*(r-k));
}
}
}
}
if(dp[1][1][n]!=inf){
printf("%lld\n",dp[1][1][n]);
}else{
puts("-1");
}
}
P4585 [FJOI2015] 火星商店问题
题意
- 有一些商品，每个商品有一个类型 $x$，每个人有一个倾向 $y$，我们认为 $x\oplus y$ 代表这个人对这个商品的喜爱度，这个数越大这个人越喜欢这个商品，其中 $\oplus$ 表示按位异或。
- 有 $n$ 个商店，每个商店有一种特产，任何时候都能买，每天某一个商店会进货（即每次进货视为进入下一天）。有一些人会逛商场，具体地，他会进入区间 $[l,r]$ 的所有商场，并且买他最喜欢的物品。并且对于不是特产的物品，他只会买最近 $d$ 天进货的（即左开右闭区间 $(t-d,t]$，其中 $t$ 是当前日期）。
- 输出每一次逛商场的最大喜爱度。
- 所有数都在 $[0,10^5]$ 范围内。
题解
线段树套 Trie 树，Trie 的每个结点维护节点内最后加入的时间，特产视为在无限大时间加入。
复杂度 $O(n\log^2 n)$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123=(e);i<=E123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123=(e);i>=E123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)){if(c=='-')f=-1;}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=1<<17,inf=0x3f3f3f3f;
int n,m,sp[N];
struct Trie{
int tr[N*250][2],mx[N*250],cntn;
void insert(int x,int Tm,int rt){
int p=rt;
fordown(i,19,0){
int c=(x>>i)&1;
if(!tr[p][c]) tr[p][c]=++cntn;
p=tr[p][c];
mx[p]=max(mx[p],Tm);
}
}
int calcXOR(int x,int Tm,int rt){
int p=rt,res=0;
fordown(i,19,0){
int c=(x>>i)&1;
if(tr[p][!c]&&mx[tr[p][!c]]>=Tm){
res+=(1<<i);
p=tr[p][!c];
}else if(tr[p][c]&&mx[tr[p][c]]>=Tm){
p=tr[p][c];
}else{
return -inf;
}
}
return res;
}
}tr;
struct SegTree{
int root[N<<1];
void Build(){
forup(i,1,N+n){
root[i]=++tr.cntn;
}
}
void Update(int P,int X,int Tm){
for(int i=P+N;i;i>>=1){
tr.insert(X,Tm,root[i]);
}
}
int Query(int l,int r,int x,int Tm){
int res=0;
for(l+=N-1,r+=N+1;l^r^1;l>>=1,r>>=1){
if(!(l&1)) res=max(res,tr.calcXOR(x,Tm,root[l^1]));
if( r&1 ) res=max(res,tr.calcXOR(x,Tm,root[r^1]));
}
return res;
}
}mt;
signed main(){
n=read();m=read();
mt.Build();
forup(i,1,n){
sp[i]=read();
mt.Update(i,sp[i],inf);
}
int Tm=0;
forup(i,1,m){
int op=read();
if(op==0){
++Tm;
int u=read(),v=read();
mt.Update(u,v,Tm);
}else{
int l=read(),r=read(),x=read(),d=read();
printf("%d\n",mt.Query(l,r,x,Tm-d+1));
}
}
}
CF1521D Nastia Plays with a Tree
题意
- 有一棵 $n$ 个点的树，每次操作你要断一条边连一条边，不需要时刻保证这张图是树。
- 求把这棵树变成一条链的最小操作数，并构造方案。
- $1\le \sum n\le 10^5$
题解
考虑先把这棵树断成若干条链再依次连接。
容易想到若一个点只有不超过一个儿子就不操作它，否则将其和父亲之间的边断掉，再把多余的儿子断掉。这些边不断必然有一个结点度数大于 $2$，断它和父亲的是为了尽可能让父亲的儿子变少。
复杂度 $O(n)$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=2e5+5,inf=0x3f3f3f3f;
int n,lf[N];
vector<int> e[N];
vector<pii> del;
vector<pii> lk;
void dfs(int x,int fa){
lf[x]=x;
for(auto i:e[x]){
if(i==fa) continue;
dfs(i,x);
if(!lf[i]) continue;
if(lf[x]==x){
lf[x]=lf[i];
}else if(lf[x]){
if(fa){
del.push_back(mkp(x,fa));
}
lk.push_back(mkp(lf[x],lf[i]));
lf[x]=0;
}else{
del.push_back(mkp(i,x));
lk.push_back(mkp(i,lf[i]));
}
}
}
void solve(){
n=read();
lk.clear();del.clear();
forup(i,1,n) e[i].clear();
forup(i,1,n-1){
int u=read(),v=read();
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1,0);
if(lf[1]){
lk.push_back(mkp(1,lf[1]));
}
printf("%d\n",(int)del.size());
int pre=lk.back().fi;
int sz=del.size();
forup(i,0,sz-1){
printf("%d %d %d %d\n",del[i].fi,del[i].se,pre,lk[i].fi);
pre=lk[i].se;
}
}
signed main(){
int t=read();
while(t--){
solve();
}
}
[ARC121E] Directed Tree
题意
- 给定一棵 $n$ 个点的树，根为 $1$，每条边从父亲指向儿子。
- 求排列 $p_i$ 的数量，满足不存在 $p_i\to i$ 且经过至少一条边的路径。
- $1\le n\le 2000$
题解
挺有意思的容斥题。
首先题目条件相当于 $p_i$ 不能是 $i$ 的祖先，但是祖先不太好做，因为不存在偏序关系，考虑求逆排列 $p'$，那么就是 $p_i'$ 不能是 $i$ 的后代。
容易想到容斥，具体来说，设 $dp_{u,i}$ 表示考虑 $u$ 及其子树，钦定有 $i$ 个点不合法的方案数，转移就是简单树形背包，还是比较好做的就略过了。
设 $f_i$ 表示恰好 $i$ 个点不合法的方案数，$g_i$ 表示钦定 $i$ 个点不合法的方案数（即 $dp_{1,i}$），容易发现 $g_i=\sum_{j=i}^n\binom{j}{i}(-1)^{j-i}f_j$，那么根据二项式反演，答案即为 $f_0=\sum_{i=0}^n g_i(-1)^i$。
复杂度 $O(n^2)$，复杂度分析是经典树形背包。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=2005,inf=0x3f3f3f3f,mod=998244353;
int n,dp[N][N],sz[N];
vector<int> son[N];
int fact[N];
void dfs(int x){
sz[x]=1;
dp[x][0]=1;
for(auto i:son[x]){
dfs(i);
fordown(j,sz[x],0){
forup(k,1,sz[i]){
(dp[x][j+k]+=1ll*dp[x][j]*dp[i][k]%mod)%=mod;
}
}
sz[x]+=sz[i];
}
fordown(i,sz[x],1){
(dp[x][i]+=1ll*dp[x][i-1]*(sz[x]-i)%mod)%=mod;
}
}
signed main(){
n=read();
forup(i,2,n){
int f=read();
son[f].push_back(i);
}
fact[0]=1;
forup(i,1,n){
fact[i]=1ll*fact[i-1]*i%mod;
}
dfs(1);
int res=0;
forup(i,0,n){
(res+=1ll*(i&1?mod-1:1)*dp[1][i]%mod*fact[n-i]%mod)%=mod;
}
printf("%d\n",res);
}
[ARC121F] Logical Operations on Tree
题意
- 给定一棵树，求所有给点赋值 $0/1$，给边赋逻辑运算 与/或 的 $2^{2n-1}$ 种方案中，有多少种存在一种缩边顺序（缩边即将两端点按边上的运算得到一个新点）使得最后得到一个权值为 $1$ 的点。
- $1\le n\le 10^5$
题解
这种题肯定先考虑缩边策略，那么显然是先缩其中一种边再缩另一种，考虑应该先缩与还是或。
如果先缩或边，那么充分条件就是所有“或”连通块中都至少有一个 $1$。但这个显然就不必要，因为有可能缩起一条与边将两个或连通块并在一起，就删掉了一个没有 $1$ 的连通块。
如果先缩与边，那么充分条件就是存在一个“与”连通块内部全是 $1$。这个就必要了，假设所有与连通块都不是全 $1$，那么考虑缩一条或边将两个与连通块并起来，枚举这条或边端点的几种情况即可发现无论如何都不能凑出全 $1$ 的与连通块。
于是简单树形 DP 即可，注意到“存在一个 $1$”是不好算的，不妨算“全都是 $0$”的方案，减掉即可。
复杂度 $O(n)$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=1e5+5,inf=0x3f3f3f3f,mod=998244353;
int n,dp[N][2];
vector<int> e[N];
void dfs(int x,int fa){
dp[x][0]=dp[x][1]=1;
for(auto i:e[x]){
if(i==fa) continue;
dfs(i,x);
dp[x][0]=(1ll*dp[x][1]*dp[i][0]%mod+2ll*dp[x][0]*dp[i][0]%mod+1ll*dp[x][0]*dp[i][1]%mod)%mod;
dp[x][1]=(1ll*dp[x][1]*dp[i][0]%mod+1ll*dp[x][1]*dp[i][1]%mod)%mod;
}
}
signed main(){
n=read();
forup(i,1,n-1){
int u=read(),v=read();
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1,0);
int p2=1;
forup(i,1,n*2-1){
p2=2ll*p2%mod;
}
printf("%d\n",(p2+mod-dp[1][0])%mod);
}
[ABC135F] Strings of Eternity
题意
- 给定字符串 $S,T$，求出最大的 $k$，使得 $T$ 重复 $k$ 遍首尾相接能在无限个 $S$ 首尾相接中匹配，若 $k$ 取无限大输出 $-1$。
- $|S|,|T|\le 5\times 10^5$。
题解
首先容易发现若答案不为 $-1$，则若 $S \ge T$，则 $T$ 最多在两个 $S$ 的相连处得到最大的 $k$（考虑若连续 $k$ 个 $T$ 覆盖了整个 $S$，那么要么 $|S|$ 恰好是 $|T|$ 的倍数，要么 $T$ 等于自己的某个前缀加某个后缀，容易发现显然都能无限），若 $S < T$，则最多匹配一次（否则显然无限）。
那么无论如何，将 $\left\lfloor\frac{|T|}{|S|}\right\rfloor+2$ 个 $S$ 顺次连接得到 $S'$，那么让 $T$ 在 $S'$ 中匹配即可得到 $k$。
于是考虑何时答案为 $-1$，容易发现假如在上面的步骤中算出的 $k$ 满足 $k\times (|T|+1) \ge |S'|$，那么答案就是 $-1$。
复杂度 $O(n)$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=5e5+5,inf=0x3f3f3f3f;
int n,m;
char s[N<<5],t[N];
int nxt[N],dp[N<<5],ans;
signed main(){
scanf(" %s %s",s,t);
n=strlen(s);m=strlen(t);
int p=(m*2/n)+1;
forup(i,0,n-1){
forup(j,1,p){
s[i+j*n]=s[i];
}
}
nxt[0]=0;
int j=0;
forup(i,1,m-1){
while(j>0&&t[i]!=t[j]) j=nxt[j-1];
if(t[i]==t[j]) ++j;
nxt[i]=j;
}
j=0;
forup(i,0,n*(p+1)-1){
while(j>0&&(j==m||s[i]!=t[j])) j=nxt[j-1];
if(s[i]==t[j]) ++j;
if(j==m){
dp[i]=1;
if(i>=m) dp[i]+=dp[i-m];
ans=max(ans,dp[i]);
}
}
if((ans+1)*m>=n*(p+1)){
puts("-1");
}else{
printf("%d\n",ans);
}
}
[ABC136F] Enclosed Points
题意
- 给定一个平面上的点集 $S$，所有点 $(x_i,y_i)$ 均是整点，且保证所有点横坐标互不相同，纵坐标互不相同。
- 定义 $f(T)$（其中 $T\subseteq S$）表示满足 $a\le x_i\le b,c\le y_i\le c,(x_i,y_i)\in S$ 的点数，其中 $a,b,c,d$ 分别是 $T$ 中 $x$ 的最小值，最大值，$y$ 的最小值，最大值。
- 求 $\sum_{T\subseteq S}f(T)$。
- $1\le |S|\le 2\times 10^5$
题解
远古 abc 水紫，单纯不想写专题才来写的。
考虑计算每个点产生贡献的次数。
显然一个点产生贡献，要么它就在集合 $T$ 中，要么某个 $T$ 的矩形将其覆盖了。前者是好算的，总贡献为 $n\times 2^{n-1}$，考虑后者。
那么就是要算左上方和右下方均有至少一个点，或者左下方和右上方均有至少一个点，那么先二维数点统计完了再考虑怎么做。注意到剩下两个方向的点可以任意选，但是直接 $2^k$ 会算重，仔细思考一下发现只有四个方向均有点的情况会被统计两次，那么简单容斥一下减掉即可。
复杂度 $O(n\log n)$，瓶颈在于二位数点。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=2e5+5,inf=0x3f3f3f3f,mod=998244353;
int n,p2[N],ld[N],rd[N],lu[N],ru[N],ans;
vector<int> lsh;
struct Node{
int x,y;
}s[N];
struct BIT{
int c[N];
void upd(int x,int k){for(;x<=n;x+=x&-x)c[x]+=k;}
int sum(int x){int res=0;for(;x>0;x-=x&-x)res+=c[x];return res;}
}mt;
signed main(){
n=read();
p2[0]=1;
forup(i,1,n){
p2[i]=2ll*p2[i-1]%mod;
s[i].x=read();s[i].y=read();
lsh.push_back(s[i].y);
}
sort(lsh.begin(),lsh.end());
lsh.erase(unique(lsh.begin(),lsh.end()),lsh.end());
forup(i,1,n){
s[i].y=lower_bound(lsh.begin(),lsh.end(),s[i].y)-lsh.begin()+1;
}
sort(s+1,s+n+1,[&](Node a,Node b){return a.x<b.x;});
forup(i,1,n){
ld[i]=mt.sum(s[i].y);lu[i]=i-1-mt.sum(s[i].y);
mt.upd(s[i].y,1);
}
mem(mt.c,0);
fordown(i,n,1){
rd[i]=mt.sum(s[i].y);ru[i]=n-i-mt.sum(s[i].y);
mt.upd(s[i].y,1);
}
ans=1ll*n*p2[n-1]%mod;
forup(i,1,n){
(ans+=(1ll*(p2[ld[i]]-1)*(p2[ru[i]]-1)%mod*(p2[lu[i]+rd[i]])%mod
+1ll*(p2[rd[i]]-1)*(p2[lu[i]]-1)%mod*(p2[ru[i]+ld[i]])%mod
-1ll*(p2[rd[i]]-1)*(p2[lu[i]]-1)%mod*(p2[ru[i]]-1)%mod*(p2[ld[i]]-1)%mod)%mod)%=mod;
(ans+=mod)%=mod;
}
printf("%d\n",ans);
}
P3991 [BJOI2017] 喷式水战改
题意
- 有一架战斗机，战斗机有三种模式 $A,B,C$，三种模式消耗同一种燃料的效率不同，具体来说，每种燃料有三个参数 $a_i,b_i,c_i$，表示三种模式消耗一单位燃料的飞行距离。要求一次任务中途的模式依次是 $A,B,C,A$，四段均可以为空（即你不能进行形如先搞一段 $C$ 再搞一段 $B$ 之类的操作）。
- 有 $n$ 次添加燃料操作，你可以将燃料舱假想为一个序列，第 $i$ 次会在第 $p_i$ 单位燃料后插入 $x_i$ 单位燃料 $(a_i,b_i,c_i)$。
- 每次添加操作后求最远飞行距离相比上一次添加增加了多少。
题解
哎哟出题人不会出题只能在码长上恶心人了，最后还让不认真读题的人怀疑自己是不是写错了，差评。
平衡树直接维护，完了。
注意插入时可能需要裂开某个点，这就能体现 FHQ 的优点了，可以非常自然地实现这个东西。
我不知道带旋 Treap 和 Splay 怎么做。
居然是洛谷非匿名最优解。
复杂度 $O(n\log n)$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(i64 i=(s),E123123=(e);i<=E123123;++i)
#define fordown(i,s,e) for(i64 i=(s),E123123=(e);i>=E123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<i64,i64>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)){if(c=='-')f=-1;}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=1e5+5,inf=0x3f3f3f3f;
i64 n;
struct Trible{
i64 a,b,c,num;
};
struct Sum{
i64 a,b,c,num;
i64 ab,bc,ca;
i64 abc,bca;
i64 abca;
Sum operator+(const Sum &r)const{
Sum res;
res.a=a+r.a;
res.b=b+r.b;
res.c=c+r.c;
res.ab=max({ab+r.b,a+r.b,a+r.ab});
res.bc=max({bc+r.c,b+r.c,b+r.bc});
res.ca=max({ca+r.a,c+r.a,c+r.ca});
res.abc=max({abc+r.c,ab+r.c,ab+r.bc,a+r.bc,a+r.abc});
res.bca=max({bca+r.a,bc+r.a,bc+r.ca,b+r.ca,b+r.bca});
res.abca=max({abca+r.a,abc+r.a,abc+r.ca,ab+r.ca,ab+r.bca,a+r.bca,a+r.abca});
return res;
}
void operator=(const Trible &r){
num=r.num;
a=r.a*num;b=r.b*num,c=r.c*num;
ab=max(a,b);bc=max(b,c);ca=max(c,a);
abc=max({a,b,c});bca=max({b,c,a});
abca=max({a,b,c});
}
};
mt19937 mr(20071221);
struct Treap{
i64 sz[N*2],cnt[N*2],ls[N*2],rs[N*2],hv[N*2],cntn,root;
Trible tv[N*2];
Sum ss[N*2];
i64 New(i64 a,i64 b,i64 c,i64 num){
i64 nw=++cntn;
sz[nw]=cnt[nw]=num;
ls[nw]=rs[nw]=0;
hv[nw]=mr();
tv[nw]=Trible{a,b,c,num};
ss[nw]=tv[nw];
return nw;
}
void PushUp(i64 id){
sz[id]=sz[ls[id]]+cnt[id]+sz[rs[id]];
ss[id]=tv[id];
ss[id]=ss[ls[id]]+ss[id];
ss[id]=ss[id]+ss[rs[id]];
}
void Split(i64 id,i64 key,i64 &x,i64 &y){
if(!id){
x=y=0;
return;
}
if(sz[ls[id]]>=key){
y=id;
Split(ls[id],key,x,ls[y]);
PushUp(id);
}else if(sz[ls[id]]+cnt[id]>key){
key-=sz[ls[id]];
i64 at=New(tv[id].a,tv[id].b,tv[id].c,cnt[id]-key);
rs[at]=rs[id];PushUp(at);
rs[id]=0;cnt[id]=tv[id].num=key;PushUp(id);
x=id;y=at;
return;
}else{
x=id;
Split(rs[id],key-sz[ls[id]]-cnt[id],rs[x],y);
PushUp(id);
}
}
i64 Merge(i64 x,i64 y){
if(!x||!y) return x|y;
if(hv[x]>hv[y]){
rs[x]=Merge(rs[x],y);
PushUp(x);
return x;
}else{
ls[y]=Merge(x,ls[y]);
PushUp(y);
return y;
}
}
void Insert(i64 key,i64 a,i64 b,i64 c,i64 num){
i64 x,y;
Split(root,key,x,y);
root=Merge(Merge(x,New(a,b,c,num)),y);
}
i64 Query(){
return ss[root].abca;
}
}mt;
signed main(){
n=read();
i64 pre=0;
forup(i,1,n){
i64 p=read(),a=read(),b=read(),c=read(),num=read();
mt.Insert(p,a,b,c,num);
i64 nw=mt.Query();
printf("%lld\n",nw-pre);
pre=nw;
}
}
P2473 [SCOI2008] 奖励关
题意
- 有 $n$ 种物品，第 $i$ 中物品只有在拿完集合 $S_i$ 后才能拿，每拿一个第 $i$ 种物品会获得 $p_i$ 的分数。
- 现在会 $m$ 次给你一个物品，每次给的物品在 $n$ 个中均匀随机，你可以选择拿或者不拿。
- 求最优策略下的期望分数。
- $1\le m\le 100,1\le n\le 15,-10^6\le p_i\le 10^6$
题解
一看就是状压 DP。但是这个期望 DP 正着做很复杂，考虑能不能倒着做。
具体来说，设 $f_{i,msk}$ 表示拿完 $msk$ 中的物品后，$[i,k]$ 次选择物品能获得的期望分数。转移就枚举这次给你哪个物品，然后在是否选择这个物品的两个后继状态中取 $\max$ 转移即可。因为求的是期望所以还要除以 $n$。
复杂度 $O(m2^nn)$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using db=double;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=20,inf=0x3f3f3f3f;
int m,n;
int pre[N],val[N];
db dp[105][1<<15];
signed main(){
m=read();n=read();
forup(i,1,n){
val[i]=read();
while(1){
int u=read();
if(u==0) break;
pre[i]|=(1<<(u-1));
}
}
fordown(i,m,1){
forup(j,0,(1<<n)-1){
forup(k,1,n){
db nw=dp[i+1][j];
if((j&pre[k])==pre[k]){
nw=max(nw,dp[i+1][j|(1<<(k-1))]+val[k]);
}
dp[i][j]+=nw;
}
dp[i][j]=dp[i][j]/n;
}
}
printf("%.6lf\n",dp[1][0]);
}
P5492 [PKUWC2018] 随机算法
题意
- 对于一张 $n$ 个点 $m$ 条边的简单无向图，考虑以下的最大独立集算法：
- 将 $n$ 个点均匀随机排列（认为所有 $n!$ 种排列的出现概率是相等的）得到一个排列 $p_i$。
- 维护一个集合 $S$，最初为空集，从 $p_1$ 开始遍历排列，假如 $p_i$ 和 $S$ 中所有点都没有连边则加入 $S$。
- 对于给定的图，求这个算法的正确率。我们认为这个算法正确当且仅当求出的 $|S|$ 等于最大独立集大小。
- $1\le n\le 20,0\le m\le \binom{n}{2}$。
题解
容易想到对能求出正解的排列计数来算概率。一眼能看出 $O(3^nn)$ 的状压 DP，就是设 $f_{msk}$ 表示得到状态 $msk$ 的方案数，其中 $msk$ 是一个三进制数，每一位表示每个点的三种状态，转移枚举下一个点即可。最终统计答案只需遍历所有状态找到独立集最大的全部加起来。
仔细想想为什么要 $3^n$，因为每个点有三个状态：已经被遍历过了并且在 $S$ 中，已经被遍历过并且不在 $S$ 中，还没被遍历过。这个非常不好优化，因为转移时需要确定每个点的状态才能知道新点是否加入 $S$ 集合。
考虑能不能将一些东西捆绑在一起转移，因为我们统计答案时只关注独立集的大小，不难想到对没被遍历过的点做文章，将点分为三种：已经被遍历过（第一类），和 $S$ 有边并且没被遍历过（第二类），和 $S$ 没有边并且没被遍历过（第三类）。
这样有什么用呢？容易发现此时我们加入一个第二类的点时并不关心这个点具体是什么，因为它不会加入集合 $S$，在序列中可以任意排列不产生影响，所以我们只需要记录它的数量就可以转移了！这就做到了我们期望的“捆绑在一起转移”。
于是设 $f_{msk,i}$ 表示一二类点的并集为 $msk$，其中有 $i$ 个二类点的最大独立集大小，$g_{msk,i}$ 表示能得到这个状态的排列数，转移要么消耗一个三类点，要么消耗一个二类点，具体见代码。
初始状态是 $f_{0,0}=0,g_{0,0}=1$，最后合法的排列数就是 $g_{n,0}$。
复杂度 $O(n^22^n)$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=25,mod=998244353;
int ksm(int a,int b){
int c=1;
while(b){
if(b&1) c=1ll*a*c%mod;
a=1ll*a*a%mod;
b>>=1;
}
return c;
}
int n,m;
int grp[N],f[1<<20][N],g[1<<20][N];
signed main(){
n=read();m=read();
forup(i,0,n-1) grp[i]|=1<<i;
forup(i,1,m){
int u=read()-1,v=read()-1;//下标从 0 开始方便状态压缩。
grp[u]|=(1<<v);
grp[v]|=(1<<u);
}
f[0][0]=0;g[0][0]=1;
forup(msk,0,(1<<n)-1){
fordown(i,__builtin_popcount(msk),0){
if(!g[msk][i]) continue;
if(i){//消耗一个二类点，只影响 i。
if(f[msk][i]>f[msk][i-1]){
f[msk][i-1]=f[msk][i];
g[msk][i-1]=1ll*g[msk][i]*i%mod;//注意有 i 种选法。
}else if(f[msk][i]==f[msk][i-1]){
(g[msk][i-1]+=1ll*g[msk][i]*i%mod)%=mod;
}
}
forup(j,0,n-1){//消耗一个三类点，更新 msk 和 i。
if(msk&(1<<j)) continue;
int nxt=msk|grp[j],ni=i+__builtin_popcount(nxt^msk)-1;
if(f[msk][i]+1>f[nxt][ni]){
f[nxt][ni]=f[msk][i]+1;
g[nxt][ni]=g[msk][i];
}else if(f[msk][i]+1==f[nxt][ni]){
(g[nxt][ni]+=g[msk][i])%=mod;
}
}
}
}
int ff=1;
forup(i,1,n) ff=1ll*ff*i%mod;//计算排列总数，即阶乘，答案记得除以阶乘。
printf("%lld\n",1ll*g[(1<<n)-1][0]*ksm(ff,mod-2)%mod);
}
CF827D Best Edge Weight
题意
- 给定一张 $n$ 个点 $m$ 条边的简单连通无向图，边有边权。
- 对于每条边，求出在其它边权不变的情况下，它的边权最大变为多少能使得它在所有最小生成树中。
- $1\le n\le 2\times 10^5$，边权在 $[1,10^9]$ 区间内。
题解
简单题，但是想复杂了。
容易发现一条边在最小生成树中当且仅当它在任意一个环中都不是最大值，即小于它所在的所有环中最大值的最小值。
考虑一些最小生成树的性质，容易发现对于一条非树边，这个“最大值的最小值”就是它在最小生成树上围出的环中的最大值（除去它），对于一条树边，这个“最大值的最小值”就是所有围住它的树边的最小值。
于是随便维护一下即可，最优应该能做到 $O(n\log n)$，但是我写的 $O(n\log^2 n)$ 启发式合并。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=2e5+5,inf=0x3f3f3f3f;
int n,m,ans[N];
struct edge{
int u,v,w,pos;
}s[N];
vector<int> sv;
int fa[N];
int getfa(int x){return x==fa[x]?x:fa[x]=getfa(fa[x]);}
vector<pii> e[N];
int f[N][18],g[N][18],dpt[N];
void dfs(int x,int fa){
f[x][0]=fa;
dpt[x]=dpt[fa]+1;
forup(i,1,17){
f[x][i]=f[f[x][i-1]][i-1];
g[x][i]=max(g[x][i-1],g[f[x][i-1]][i-1]);
}
for(auto i:e[x]){
int v=i.fi,w=s[i.se].w;
if(v==fa) continue;
g[v][0]=w;
dfs(v,x);
}
}
pii lca(int u,int v){
int res=0;
if(dpt[u]>dpt[v]) swap(u,v);
fordown(i,17,0){
if(dpt[f[v][i]]>=dpt[u]){
res=max(res,g[v][i]);
v=f[v][i];
}
}
if(u==v) return mkp(u,res);
fordown(i,17,0){
if(f[u][i]!=f[v][i]){
res=max(res,g[u][i]);
res=max(res,g[v][i]);
u=f[u][i];v=f[v][i];
}
}
res=max(res,g[u][0]);res=max(res,g[v][0]);
return mkp(f[u][0],res);
}
vector<int> add[N],del[N];
multiset<int> ss[N];
void dfs2(int x,int fa){
for(auto i:e[x]){
int v=i.fi,p=i.se;
if(v==fa) continue;
dfs2(v,x);
if(ss[v].size()){
ans[s[p].pos]=*ss[v].begin()-1;
}else{
ans[s[p].pos]=-1;
}
if(ss[x].size()<ss[v].size()){
swap(ss[x],ss[v]);
}
for(auto i:ss[v]) ss[x].insert(i);
}
for(auto i:add[x]) ss[x].insert(i);
for(auto i:del[x]){
ss[x].erase(ss[x].find(i));
ss[x].erase(ss[x].find(i));
}
}
signed main(){
n=read();m=read();
forup(i,1,n){
fa[i]=i;
}
forup(i,1,m){
s[i].u=read(),s[i].v=read(),s[i].w=read();s[i].pos=i;
}
sort(s+1,s+m+1,[&](edge a,edge b){return a.w<b.w;});
forup(i,1,m){
int u=getfa(s[i].u),v=getfa(s[i].v);
if(u==v){
sv.push_back(i);
continue;
}
fa[u]=v;
e[s[i].u].push_back(mkp(s[i].v,i));
e[s[i].v].push_back(mkp(s[i].u,i));
}
dfs(1,0);
for(auto i:sv){
int u=s[i].u,v=s[i].v;
pii rr=lca(u,v);
ans[s[i].pos]=rr.se-1;
add[u].push_back(s[i].w);add[v].push_back(s[i].w);
del[rr.fi].push_back(s[i].w);
}
dfs2(1,0);
forup(i,1,m){
printf("%d ",ans[i]);
}
}
模拟赛神秘题目 【0914 B组】A 神灵庙
《》
题意
- 你需要构造一棵 $n$ 个叶子的二叉树，每个结点与左儿子的连边长为 $1$，与右儿子为 $2$，你还要将 $n$ 个权值 $a_i$ 分配给叶子，最小化 $\sum a_i\times dep_i$，其中 $dep_i$ 是结点与树根的距离。
- $1\le n\le 750,1\le a_i\le 10^5$。
题解
神秘。赛时只想到指数做法数组还开小了。
首先一个显然的性质是越小的数会放进深度越大的叶子。
考虑每个非叶子都会提供一个深度 $+1$ 和一个深度 $+2$ 的结点，于是不妨把这两层都放进状态。设 $f_{i,m,j,k}$，表示放完了前 $i$ 大的数，第 $m$ 层还有 $j$ 个没用过（即将来会变成非叶子或者放入一个 $a_i$）的结点，第 $m+1$ 层有 $j$ 个连向 $m-1$ 层的结点的最小代价，然后转移有两个 $f_{i,m,j,k}+a_i\times m\to f_{i+1,m,j-1,k}$ 和 $f_{i,m,j,k}\to f_{i,m+1,j+k,j}$。
怎么优化呢？我们可以拆贡献，容易发现每往后一层，每个没用过的数都会增加 $a_i$ 的贡献，于是可以不记 $m$，转移变成 $f_{i,j,k}\to f_{i+1,j-1,k}$ 和 $f_{i,j,k}+s_{n-i}\to f_{i,j+k,j}$，其中 $s_i$ 表示前 $i$ 小数的和。
复杂度 $O(n^3)$，需要滚动数组优化空间。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123=(e);i<=E123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123=(e);i>=E123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)){if(c=='-')f=-1;}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=755,inf=0x3f3f3f3f;
int n,a[N],ans,sum[N];
int dp[2][N][N];
signed main(){
n=read();
forup(i,1,n){
a[i]=read();
}
sort(a+1,a+n+1);
forup(i,1,n){
sum[i]=sum[i-1]+a[i];
}
mem(dp[0],0x3f);
ans=inf;
dp[0][1][0]=0;
forup(k,0,n){
int p=k&1,q=p^1;
mem(dp[q],0x3f);
forup(i,0,n){
forup(j,0,n){
if(dp[p][i][j]==inf) continue;
if(k<n&&i) dp[q][i-1][j]=min(dp[q][i-1][j],dp[p][i][j]);
if(i+j<=n) dp[p][i+j][i]=min(dp[p][i+j][i],dp[p][i][j]+sum[n-k]);
}
}
}
printf("%d\n",dp[n&1][0][0]);
}