锐客网

  1. 首页 > it技术 > >

主席树|191101CSP模拟题解

主席树网络流状压DP

T1：给定 n , k , l n,k,l n,k,l，求 n n n个数每个取值 [ 0 , l ] [0,l] [0,l]，其一个子序列和为 k k k的方案数， n , k ≤ 20 n,k\le 20 n,k≤20
补集转化，是个背包，然后状压算方案，dp of dp
Code：

#include #define ll long long #define mod 998244353 using namespace std; inline int read(){ int res=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') f=-f; ch=getchar(); } while(isdigit(ch)) {res=(res<<1)+(res<<3)+(ch^48); ch=getchar(); } return res*f; } inline int add(int x,int y){x+=y; if(x>=mod) x-=mod; return x; } inline int dec(int x,int y){x-=y; if(x<0) x+=mod; return x; } inline int mul(int x,int y){return 1ll*x*y%mod; } inline void Mul(int &x,int y){x=1ll*x*y%mod; } inline void inc(int &x,int y){x+=y; if(x>=mod) x-=mod; } inline int ksm(int a,int b){int res=1; for(; b; b>>=1,Mul(a,a)) if(b&1) Mul(res,a); return res; } const int N=21,M=(1<<20); int n,k,l,S,lim; int f[N][M]; inline void file(){freopen("sequence.in","r",stdin); freopen("sequence.out","w",stdout); } int main(){ n=read(),k=read(),l=read(); S=(1<k) inc(f[i][s],mul(f[i-1][s],(l-k)%mod)); } int res=0; for(int s=0; s<=S; s++) inc(res,f[n][s]); cout<

【主席树|191101CSP模拟题解】T2：给定一棵树，每个点有一个值，定义一个点的权值为子树的值之和，求对于每一个点，它能到达的，路径上既有权值比他大又有比他小的点的权值的或和， ∑ a i ≤ 1 e 6 ， n ≤ 4 e 5 \sum a_i\le1e6，n\le 4e5 ∑ai?≤1e6，n≤4e5
显然是走子树外，然后一定有一个权值比它大的，那么就是询问子树外权值比它小的点的或和，dfs序拆成一个前缀和一个后缀用主席树维护即可
Code：
#include #define mp make_pair #define pii pair #define ll long long #define pli pair #define fi first #define se second using namespace std; inline int read(){ int res=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') f=-f; ch=getchar(); } while(isdigit(ch)) {res=(res<<1)+(res<<3)+(ch^48); ch=getchar(); } return res*f; } char xx; const int N=1e6+5,M=4e5+5; struct President_tree{ struct seg{int l,r,sum; }tr[(N<<2)+M*40]; int cnt; #define ls(k) tr[k].l #define rs(k) tr[k].r #define mid (l+r>>1) void build(int &rt,int l,int r){ rt=++cnt; tr[rt].sum=0; if(l==r) return; build(ls(rt),l,mid); build(rs(rt),mid+1,r); } void ins(int &rt1,int rt2,int l,int r,int pos,int x){ tr[rt1=++cnt]=tr[rt2]; tr[rt1].sum|=x; if(l==r) return; if(pos<=mid) ins(ls(rt1),ls(rt2),l,mid,pos,x); else ins(rs(rt1),rs(rt2),mid+1,r,pos,x); } int query(int rt1,int l,int r,int ql,int qr){ if(ql>r || qrmid) return query(rs(rt1),mid+1,r,ql,qr); else return query(ls(rt1),l,mid,ql,mid)|query(rs(rt1),mid+1,r,mid+1,qr); } }T[2]; int vis[M<<1],head[M],nxt[M<<1],tot=0; inline void add(int x,int y){vis[++tot]=y; nxt[tot]=head[x]; head[x]=tot; } int dfn[M],sign=0,id[N]; int f[M]; int siz[M]; void dfs(int v,int fa){ siz[v]=1; dfn[v]=++sign; id[sign]=v; for(int i=head[v]; i; i=nxt[i]){ int y=vis[i]; if(y==fa) continue; dfs(y,v); f[v]+=f[y]; siz[v]+=siz[y]; } } int R; int rt[M][2]; char yy; inline void file(){freopen("forever.in","r",stdin); freopen("forever.out","w",stdout); } int main(){ file(); T[0].cnt=T[1].cnt=0; int n=read(); R=read(); for(int x,y,i=1; i

T3：BZOJ建设游乐场
想起建图方法的时候只有10min了，就是TC SRM 500多的一道题，一毛一样
#include using namespace std; inline int read(){ int res=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') f=-f; ch=getchar(); } while(isdigit(ch)) {res=(res<<1)+(res<<3)+(ch^48); ch=getchar(); } return res*f; } const int N=2e5,INF=1e9; const int NN=1000; int vis[N],nxt[N],head[N],c[N],e[N],tot=1; inline void add(int x,int y,int z,int w){ vis[++tot]=y; nxt[tot]=head[x]; head[x]=tot; c[tot]=z; e[tot]=w; vis[++tot]=x; nxt[tot]=head[y]; head[y]=tot; c[tot]=0; e[tot]=-w; } int d[N],pt[N]; int S,T; inline bool spfa(){ memset(d,0x3f,sizeof(d)); queueq; q.push(S); d[S]=0; while(!q.empty()){ int x=q.front(); q.pop(); pt[x]=0; for(int i=head[x]; i; i=nxt[i]){ int y=vis[i]; if(d[y]>d[x]+e[i] && c[i]){ d[y]=d[x]+e[i]; if(!pt[y]) pt[y]=1,q.push(y); } } } return d[T]1 && s[i-2][j-1]!='w') add(id1[i][j],id2[i-1][j],1,0); if(i1 && s[i-1][j-2]!='w') add(id2[i][j],id1[i][j-1],1,0); if(j

    推荐阅读


    上一篇：线段树|[线段树]区间and or xor

    下一篇：[线性DP][杨氏矩阵和勾长公式]Mr.|[线性DP][杨氏矩阵和勾长公式]Mr. Young's Picture Permutations