锐客网

  1. 首页 > it技术 > >

线段树|191012CSP-J模拟题解

线段树连通性ACAM

【线段树|191012CSP-J模拟题解】T2算答案加成了矩阵的一行然后调了我2个小时
T1：
求图的仅在一个简单环中的边
显然点双
Code：

#include #define pb push_back #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; } const int N=1000005; int adj[N],in[N],nxt[N<<1],to[N<<1],cnt=1; inline void addedge(int u,int v){nxt[++cnt]=adj[u],adj[u]=cnt,to[cnt]=v; } int dfn[N],low[N],tim,id[N],bcc,num[N],ee[N],ans[N]; int stk[N],top,n,m,vis[N]; pair E[N]; vector cir[N]; void dfs(int u,int fa){ dfn[u]=low[u]=++tim; stk[++top]=u; for(int e=adj[u]; e; e=nxt[e]){ int v=to[e]; if(v==fa)continue; if(!dfn[v]) dfs(v,u),low[u]=min(low[u],low[v]); else {low[u]=min(low[u],dfn[v]); continue; } if(low[v]>=dfn[u]){ int tmp; bcc++; do{ tmp=stk[top]; cir[bcc].pb(tmp); num[bcc]++; top--; }while(tmp!=v); cir[bcc].pb(u); num[bcc]++; } } } inline void file(){freopen("graph.in","r",stdin); freopen("graph.out","w",stdout); } int main(){ n=read(),m=read(); for(int i=1; i<=m; i++){ int u=read(),v=read(); E[i].fi=u,E[i].se=v; addedge(u,v),addedge(v,u); } dfs(1,0); for(int i=1; i<=bcc; i++){ for(int j=0; jdfn[v]){ee[i]++; ans[i]^=e>>1; } } } } int res=0; for(int i=1; i<=bcc; i++) if(ee[i]==num[i])res^=ans[i]; cout<

T2：求长度为n的最大价值的串，串中每出现一个给定子串价值会加上一个对应的给定值
串总和200，n规模1e12
显然矩阵快速幂优化AC自动机上DP
Code：
#include #define pb push_back #define mp make_pair #define ll long long #define fi first #define se second #define db double using namespace std; inline ll read(){ ll 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=205,M=201; const ll INF=1e18; int cnt=0; struct Mat{ ll a[M][M]; inline void init(){ for(int i=0; i<=cnt; ++i) for(int j=0; j<=cnt; ++j) a[i][j]=-INF; } inline Mat operator * (const Mat &b)const{ Mat res; res.init(); for(int i=0; i<=cnt; ++i) for(int k=0; k<=cnt; ++k) if(a[i][k]!=-INF) for(int j=0; j<=cnt; ++j) if(b.a[k][j]!=-INF) res.a[i][j]=max(res.a[i][j],a[i][k]+b.a[k][j]); return res; } }trans,bs; inline Mat ksm(Mat a,ll b){ Mat res=a; for(; b; b>>=1,a=a*a) if(b&1) res=res*a; return res; } char s[N]; namespace ACAM{ struct trie{ int son[26]; ll val; }tr[N*10]; inline void ins(int len,ll w){ int now=0; for(int i=1; i<=len; i++){ if(!tr[now].son[s[i]-'a']) tr[now].son[s[i]-'a']=++cnt; now=tr[now].son[s[i]-'a']; } tr[now].val+=w; } int fail[N*10]; inline void buildfail(){ queueq; for(int i=0; i<26; i++) if(tr[0].son[i]) q.push(tr[0].son[i]); while(!q.empty()){ int x=q.front(); q.pop(); for(int i=0; i<26; i++){ if(tr[x].son[i]) fail[tr[x].son[i]]=tr[fail[x]].son[i],q.push(tr[x].son[i]),tr[tr[x].son[i]].val+=tr[fail[tr[x].son[i]]].val; else tr[x].son[i]=tr[fail[x]].son[i]; } } } inline void buildmartix(){ for(int i=0; i<=cnt; i++) for(int j=0; j<26; j++) trans.a[tr[i].son[j]][i]=tr[tr[i].son[j]].val; } } using namespace ACAM; ll a[N]; inline void file(){freopen("string.in","r",stdin); freopen("string.out","w",stdout); } int main(){ ll n=read(); int m=read(); for(int i=1; i<=m; i++) a[i]=read(); for(int i=1; i<=m; i++){ scanf("%s",s+1); int len=strlen(s+1); ins(len,a[i]); } buildfail(); trans.init(); buildmartix(); trans=ksm(trans,n-1); ll ans=0; for(int i=0; i

T3：有n个位置，某些位置有初始数，再给出m个限制，形如 [ l , r ] [l,r] [l,r]中有k个位置的数严格大于这个区间的其他数，求合法解或者无解，给出的位置总和不超过3e5，位置不超过1e5，限制不超过2e5
显然线段树优化建图+拓扑排序
Code：
#include #define pb push_back #define mp make_pair #define ll long long #define fi first #define se second #define db double 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=5e6+5; int n; int p[N<<1],val[N],a[N]; int vis[N<<1],head[N],nxt[N<<1],tot=0,c[N<<1],in[N]; inline void add(int x,int y,int z){in[y]++; vis[++tot]=y; c[tot]=z; nxt[tot]=head[x]; head[x]=tot; } int cnt=0; inline void build(int k,int l,int r){ if(l==r){p[k]=l; return; } p[k]=++cnt; int mid=l+r>>1; build(k<<1,l,mid),build(k<<1|1,mid+1,r); add(p[k<<1],p[k],0),add(p[k<<1|1],p[k],0); } inline void modify(int k,int l,int r,int ql,int qr,int pos){ if(ql<=l && r<=qr) return add(p[k],pos,1); int mid=l+r>>1; if(ql<=mid) modify(k<<1,l,mid,ql,qr,pos); if(qr>mid) modify(k<<1|1,mid+1,r,ql,qr,pos); } bool f=0; inline bool topsort(){ queueq; for(int i=1; i<=cnt; i++) if(!in[i]) q.push(i); while(!q.empty()){ int x=q.front(); q.pop(); if(val[x]>1e9 || (a[x] && val[x]>a[x])) return false; val[x]=max(1,max(val[x],a[x])); for(int i=head[x]; i; i=nxt[i]){ int y=vis[i]; val[y]=max(val[y],val[x]+c[i]); --in[y]; if(in[y]==0) q.push(y); } } for(int i=1; i<=n; i++) if(in[i]) return false; f=1; return true; } int main(){ n=read(); cnt=n; int s=read(),m=read(); for(int i=1; i<=s; i++){int x=read(); a[x]=read(); } build(1,1,n); while(m--){ int l=read(),r=read(),k=read(); int last=l-1,inode=++cnt; for(int i=1; i<=k; i++){ int x=read(); add(inode,x,0); if(last+1<=x-1) modify(1,1,n,last+1,x-1,inode); last=x; } if(last+1<=r) modify(1,1,n,last+1,r,inode); } puts(topsort()?"Possible":"Impossible"); if(f) for(int i=1; i<=n; i++) cout<

    推荐阅读


    上一篇：InkScape练习

    下一篇：倍增|191026考试题解