【学习笔记】NOIP模拟赛25
据说是llsw出的题
我是没上200的丝薄
A. 遗忘十字路
记fu,Kf_{u,K}fu,K表示从uuu出发，走KKK次后价值和的最大值。
假设有mmm个儿子，那么fu,K=∑vfv,K/m+∑v′fv′,K/m+1f_{u,K}=\sum_v f_{v,K/m}+\sum_{v'}f_{v',K/m+1}fu,K=∑vfv,K/m+∑v′fv′,K/m+1 。
直接排序即可。应该可以感觉到状态数是线性的。
复杂度O(nlogn)O(n\log n)O(nlogn)。
#include
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
int T,n;
ll a[500005],K;
vectorg[500005];
vectorvec[500005];
vector>id[500005];
inline int read() {int x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}while(c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar(); }return x*f;
}
ll dfs(int u,int topf,ll K){int m=g[u].size()-(u!=1);if(m==0)return K*a[u];for(auto x:id[u])if(x.fi==K)return x.se;vec[u].clear();ll tot=0;for(auto v:g[u]){if(v!=topf){ll x=dfs(v,u,K/m),y=dfs(v,u,K/m+1);tot+=x,vec[u].pb(y-x);}}sort(vec[u].begin(),vec[u].end()),reverse(vec[u].begin(),vec[u].end());for(int j=0;jfreopen("crossroad.in","r",stdin);freopen("crossroad.out","w",stdout);T=read();while(T--){n=read(),K=read();for(int i=1;i<=n;i++)a[i]=read(),g[i].clear(),id[i].clear();for(int i=1;iint u=read(),v=read();g[u].pb(v),g[v].pb(u);}printf("%lld\n",dfs(1,0,K));}
}
B. 鹿角虫道
原题为「Gym102331C」Counting Cactus
姑且称之为仙人掌计数。
令f(u,S)f(u,S)f(u,S)表示uuu号节点为根，节点集合为SSS的方案数。
令g(u,S)g(u,S)g(u,S)表示uuu号节点为根，且uuu恰好只在一个环上，节点集合为SSS的方案数。
令dp(u,v,S)dp(u,v,S)dp(u,v,S)为钦定一个当前环的开头是uuu，环尾扩展到了vvv，节点集合为SSS的方案数。
转移方程为：
1.11.11.1 设vvv为编号最小的节点，并且v∈Tv\in Tv∈T，(fv,T+gu,T+{u})×fu,S−T→fu,S(f_{v,T}+g_{u,T+\{u\}})\times f_{u,S-T}\to f_{u,S}(fv,T+gu,T+{u})×fu,S−T→fu,S
1.21.21.2 若uuu在环上，且环的终点为vvv，(u,x)∈E(u,x)\in E(u,x)∈E，dpx,v,S−{u}→fu,S,gu,Sdp_{x,v,S-\{u\}}\to f_{u,S},g_{u,S}dpx,v,S−{u}→fu,S,gu,S
1.31.31.3 对于u→vu\to vu→v的链，在uuu上挂一个仙人掌，满足(u,x)∈E(u,x)\in E(u,x)∈E，u∈Tu\in Tu∈T，x,v∉Tx,v\notin Tx,v∈/T，dpx,v,S−T×fu,T→dpu,v,Sdp_{x,v,S-T}\times f_{u,T}\to dp_{u,v,S}dpx,v,S−T×fu,T→dpu,v,S
注意环有顺逆时针两种情况，所以要/2/2/2。
复杂度O(3nn3)O(3^nn^3)O(3nn3)。上界很松。通过固定转移系数fu,Tf_{u,T}fu,T可以优化至O(3nn2)O(3^nn^2)O(3nn2)。
有更好的方法，但是我不会。
#include
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
const int mod=998244353;
int n,m,a[13][13];
ll inv2,f[13][1<<13],dp[13][13][1<<13],g[13][1<<13],res;
void add(ll &x,ll y){x=(x+y)%mod;
}
ll fpow(ll x,ll y){ll z(1);for(;y;y>>=1){if(y&1)z=z*x%mod;x=x*x%mod;}return z;
}
int main(){freopen("stag.in","r",stdin);freopen("stag.out","w",stdout);cin>>n>>m,inv2=fpow(2,mod-2);for(int i=1;i<=m;i++){int u,v;cin>>u>>v,u--,v--,a[u][v]=a[v][u]=1;}for(int i=0;ifor(int i=0;iif(s>>i&1) {for(int j=0;jif(i==j||!(s>>j&1))continue;for(int k=0;kif(i==j||j==k||!(s>>k&1)||!a[i][k])continue;for(int s2=s-(1<if(s2>>i&1)add(dp[i][j][s],dp[k][j][s-s2]*f[i][s2-(1<for(int s2=s-(1<if(s2>>i&1)add(dp[i][j][s],f[i][s2-(1<if(!(s>>i&1)){int j=0;while(!(s>>j&1))j++;for(int s2=s;s2;s2=(s2-1)&s){if(!(s2>>j&1))continue;add(f[i][s],g[i][s2]*f[i][s-s2]);for(int k=0;kif((s2>>k&1)&&a[i][k]){add(f[i][s],f[j][s2-(1<if(i==j||!(s>>j&1)||!a[i][j])continue;for(int k=0;kif(i==k||j==k||!(s>>k&1)||!a[i][k])continue;add(f[i][s],dp[k][j][s]*inv2);add(g[i][s],dp[k][j][s]*inv2);}}}}}cout< C. 泪水之城
神秘多项式。。。
D. 生命血
原题为 「Gym102268D」Dates
应该可以看出来这是一个拟阵。
不妨将其转化为二分图匹配，使用hall\text{hall}hall定理，只需关注右部点中的一段连续区间。问题转述为，对于任意1≤i≤j≤m1\le i\le j\le m1≤i≤j≤m，srj−sli−1≥j−i+1s_{r_j}-s_{l_i-1}\ge j-i+1srj−sli−1≥j−i+1，其中sis_isi表示aia_iai的前缀和。
不妨将话说明白些。分参易得srj−j≥sli−1−i+1s_{r_j}-j\ge s_{l_i-1}-i+1srj−j≥sli−1−i+1。
我们将其视作位置iii的排名fif_ifi,gig_igi。那么对于任意j≥ij\ge ij≥i有fj≥gif_j\ge g_ifj≥gi。每次插入一个操作只会影响iii,jjj（相对位置），因此前面的排名不变，设插入位置为kkk，只需判断maxi=1kgi\max_{i=1}^k g_imaxi=1kgi与mini=kmfi\min_{i=k}^mf_imini=kmfi的大小关系，因此用两颗线段树维护。
复杂度O(nlogn)O(n\log n)O(nlogn)。
#include
#define ll long long
#define fi first
#define se second
#define pb push_back
#define int ll
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
int n,m,T,L[300005],R[300005],a[300005],s[300005],bit[300005];
struct node{int dat,max,min;
}t[300005*4];
struct node2{int v,l,r,id;bool operator <(const node2 &a)const{return v>a.v;}
}q[300005];
vectorvec;
void add(int x,int k){for(;x<=m;x+=x&-x)bit[x]+=k;
}
int ask(int x){int tot(0);for(;x;x-=x&-x)tot+=bit[x];return tot;
}
void pushup(int p){t[p].max=max(t[p<<1].max,t[p<<1|1].max);t[p].min=min(t[p<<1].min,t[p<<1|1].min);
}
void dat(int p,int x){t[p].max+=x,t[p].min+=x,t[p].dat+=x;
}
void pushdown(int p){if(t[p].dat)dat(p<<1,t[p].dat),dat(p<<1|1,t[p].dat),t[p].dat=0;
}
void build(int p,int l,int r){t[p].dat=0;t[p].min=inf,t[p].max=-inf;if(l==r)return;int mid=l+r>>1;build(p<<1,l,mid),build(p<<1|1,mid+1,r);
}
void mdy(int p,int l,int r,int x,int y,int z){if(l==r){t[p].min=y,t[p].max=z;return;}pushdown(p);int mid=l+r>>1;x<=mid?mdy(p<<1,l,mid,x,y,z):mdy(p<<1|1,mid+1,r,x,y,z);pushup(p);
}
void upd(int p,int l,int r,int ql,int qr,int x){if(ql>qr)return;if(ql<=l&&r<=qr){dat(p,x);return;}pushdown(p);int mid=l+r>>1;if(ql<=mid)upd(p<<1,l,mid,ql,qr,x);if(midif(ql>qr)return op?-inf:inf;if(ql<=l&&r<=qr)return op?t[p].max:t[p].min;pushdown(p);int mid=l+r>>1;if(qr<=mid)return qry(p<<1,l,mid,ql,qr,op);if(midfreopen("lifeblood.in","r",stdin);freopen("lifeblood.out","w",stdout);ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>T;while(T--){cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i],s[i]=s[i-1]+a[i];for(int i=1;i<=m;i++){int l,r,v;cin>>l>>r>>v;q[i]={v,l,r,i},L[i]=l,R[i]=r;}sort(q+1,q+1+m);vec.clear();ll res=0;build(1,1,m);for(int i=1;i<=m;i++)bit[i]=0;for(int i=1;i<=m;i++){int l=q[i].l,r=q[i].r,k=q[i].id;mdy(1,1,m,k,s[r]-ask(k),s[l-1]-ask(k)+1);upd(1,1,m,k+1,m,-1);if(qry(1,1,m,1,k,1)>qry(1,1,m,k,m,0)){mdy(1,1,m,k,inf,-inf),upd(1,1,m,k+1,m,1);}else {vec.pb(k),res+=q[i].v,add(k,1);}}cout<for(int i=0;icout<