UOJ 176 新年的繁荣
一个奇特的想法。我们考虑从大到小枚举边权，显然每次合并的话只用考虑比当前枚举的i多一位的数 因为如果两个数有其它的重叠部分 就一定会在之前被合并掉了
复杂度：$O(2^m*alpha(n))$
//Love and Freedom. #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #define ll long long #define inf 20021225 #define N 1<<18 using namespace std; int read() { int s=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1; ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘) s=s*10+ch-‘0‘,ch=getchar(); return s*f; } int f[N]; int find(int x){return x==f[x]?x:f[x]=find(f[x]);} int main() { int n=read(),m=read(),x; ll ans=0; for(int i=1;i<=n;i++) { x=read(); if(f[x]) ans+=x; else f[x]=x; } int top=1<<m; top--; for(int i=top;i;i--) { int tmp=f[i]; for(int j=0,ff;j<m;j++) { if(i&(1<<j)) continue; if(tmp) { if(f[i|(1<<j)] && (ff=find(f[i|(1<<j)]))!=tmp) ans+=i,f[ff]=tmp; } else if(f[i|(1<<j)]) tmp=find(f[i|(1<<j)]); } f[i]=tmp; } printf("%lld\n",ans); return 0; }
UOJ 308 UOJ拯救计划
看到%6应该就有些想法了 我们考虑只做%2 和 %3的答案 原来的柿子长这样
$ans=\sumA(k,i)*[用i个颜色染色的方案数]$
所以当i>=3的时候一定是满足%3%2=0的 于是我们只需要考虑用1/2种颜色染色的方案数 简单dp即可
//Love and Freedom. #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #define ll long long #define inf 20021225 #define N 100010 using namespace std; int read() { int s=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1; ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘) s=s*10+ch-‘0‘,ch=getchar(); return s*f; } struct node{int to,lt;}e[N<<2]; int n,k,m; int vis[N],in[N],cnt; void add(int x,int y) { e[++cnt].to=y; e[cnt].lt=in[x]; in[x]=cnt; e[++cnt].to=x; e[cnt].lt=in[y]; in[y]=cnt; } bool check(int x,bool f) { for(int i=in[x];i;i=e[i].lt) { int to=e[i].to; if(vis[to]==vis[x]) f|=1; else if(vis[to]==-1) vis[to]=vis[x]^1,f|=check(to,f); } return f; } int main() { int T=read(),x,y,ans2,ans3; while(T--) { memset(in,0,sizeof(in)); memset(vis,-1,sizeof(vis)); cnt=0; n=read(),m=read(); for(int i=1;i<=m;i++) x=read(),y=read(),add(x,y); ans2=!m,ans3=1; for(int i=1;i<=n;i++) ans3=(ans3<<1)%3; for(int i=1;i<=n;i++) if(vis[i]==-1) { vis[i]=1; bool f=check(i,0); if(!f) ans3=(ans3<<1)%3; else{ans3=0; break;} } if(ans2) { if(!ans3) printf("3\n"); else if(ans3==1) printf("1\n"); else printf("5\n"); } else { if(!ans3) printf("0\n"); else if(ans3==1) printf("4\n"); else printf("2\n"); } } return 0; }
BJOI 连连看
我们观（luan）察（gao）发现这其实是一个二分图 所以直接费用流就可以了
//Love and Freedom. #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<queue> #include<vector> #define ll long long #define inf 20021225 #define N 1010 using namespace std; int read() { int s=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1; ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘) s=s*10+ch-‘0‘,ch=getchar(); return s*f; } struct edge{int to,lt,f,c,fr;}e[N*100]; int in[N],cnt=1,s,t,dep[N]; bool vis[N]; queue<int> que; int lst[N]; void add(int x,int y,int f,int c) { e[++cnt].to=y; e[cnt].fr=x; e[cnt].lt=in[x]; e[cnt].f=f; e[cnt].c=c; in[x]=cnt; e[++cnt].to=x; e[cnt].fr=y; e[cnt].lt=in[y]; e[cnt].f=0; e[cnt].c=-c; in[y]=cnt; } bool spfa() { while(!que.empty()) que.pop(); memset(dep,-48,sizeof(dep)); memset(vis,0,sizeof(vis)); vis[s]=1; dep[s]=0; que.push(s); while(!que.empty()) { int x=que.front(); que.pop(); vis[x]=0; for(int i=in[x];i;i=e[i].lt) { int y=e[i].to; if(e[i].f&&dep[y]<dep[x]+e[i].c) { dep[y]=dep[x]+e[i].c; lst[y]=i; if(!vis[y]) vis[y]=1,que.push(y); } } } return dep[t]>dep[0]; } void dinic() { int cost=0,par=0; while(spfa()) { int flow=inf; for(int i=lst[t];i;i=lst[e[i].fr]) flow=min(flow,e[i].f); for(int i=lst[t];i;i=lst[e[i].fr]) cost+=flow*e[i].c,e[i].f-=flow,e[i^1].f+=flow; par+=flow; } printf("%d %d\n",par,cost); } int col[N],a,b; int gcd(int x,int y){return y?gcd(y,x%y):x;} vector<int> edg[N]; #define pb push_back void dfs(int x) { for(int i=0;i<edg[x].size();i++) if(col[edg[x][i]]==-1) col[edg[x][i]]=col[x]^1,dfs(edg[x][i]); } int main() { a=read(),b=read(); for(int i=a;i<=b;i++) for(int j=i+1;j<=b;j++) { int w=j*j-i*i; int d=sqrt(w); if(d*d==w && gcd(i,d)==1) edg[i].pb(j),edg[j].pb(i); } memset(col,-1,sizeof(col)); s=N-3; t=s+1; for(int i=a;i<=b;i++) if(col[i]==-1) col[i]=0,dfs(i); for(int i=a;i<=b;i++) { if(col[i]) add(i,t,1,0); else { add(s,i,1,0); for(int j=0;j<edg[i].size();j++) add(i,edg[i][j],1,i+edg[i][j]); } } dinic(); return 0; }
BZOJ4231 回忆树
一道全部由NOIp内容组成的好题（逃
我们发现这个答案显然具有差分性 所以我们可以对于每个点求答案然后链上差分掉 具体实现就是树状数组 还剩一种情况就是模式串跨LCA 这样的长度不超过两倍的模式串长度 所以我们把它提出来做KMP就好啦 （就写的很开心
//Love and Freedom. #include<cstring> #include<cmath> #include<algorithm> #include<cstdio> #include<queue> #include<vector> #define LG 19 #define ll long long #define inf 20021225 #define N 500001 #define lowbit(x) (x&-x) using namespace std; int read() { int s=0,f=1; char ch=getchar(); while(ch<‘0‘ || ch>‘9‘) {if(ch==‘-‘) f=-1;ch=getchar();} while(ch>=‘0‘ && ch<=‘9‘) s=s*10+ch-‘0‘,ch=getchar(); return f*s; } struct Edge{int to,lt;}e[N<<1]; int in[N],cnt; struct node{int fail,son[26];}; struct edge{int to,lt; char c;}a[N<<1]; int ia[N],ant,n,m; int dfn[N][2],tm; void add(int x,int y,char c) { a[++ant].to=y; a[ant].lt=ia[x]; a[ant].c=c; ia[x]=ant; a[++ant].to=x; a[ant].lt=ia[y]; a[ant].c=c; ia[y]=ant; } void add(int x,int y) { e[++cnt].to=y; e[cnt].lt=in[x]; in[x]=cnt; } void dfs(int x) { dfn[x][0]=++tm; for(int i=in[x];i;i=e[i].lt) dfs(e[i].to); dfn[x][1]=tm; } struct BIT { int n,a[N]; void add(int x,int y){x=dfn[x][0]; while(x<=n) a[x]+=y,x+=lowbit(x);} int qry(int x){int ans=0; while(x) ans+=a[x],x-=lowbit(x); return ans;} int ask(int x){return qry(dfn[x][1])-qry(dfn[x][0]-1);} }; struct ACA { node t[N]; int rt,poi; queue<int> q; int id(char c){return c-‘a‘;} void init(){rt=poi=0;} int insert(char *ch) { int n=strlen(ch),pos=rt; for(int i=0,d=id(ch[i]);i<n;i++,d=id(ch[i])) { if(!t[pos].son[d]) t[pos].son[d]=++poi; pos=t[pos].son[d]; } return pos; } void getfail() { for(int i=0;i<26;i++) if(t[rt].son[i]) q.push(t[rt].son[i]); while(!q.empty()) { int x=q.front(); q.pop(); for(int i=0;i<26;i++) if(t[x].son[i]) t[t[x].son[i]].fail=t[t[x].fail].son[i],q.push(t[x].son[i]); else t[x].son[i]=t[t[x].fail].son[i]; } for(int i=1;i<=poi;i++) add(t[i].fail,i); dfs(rt); //for(int i=1;i<=poi;i++) printf("%d\n",dfn[i][0]); } }A; BIT tr; int f[N][LG],dep[N]; char cf[N]; void getfa(int x,int fa) { dep[x]=dep[fa]+1; f[x][0]=fa;// cf[x]=0; for(int i=1;i<LG;i++) f[x][i]=f[f[x][i-1]][i-1]; for(int i=ia[x];i;i=a[i].lt) { int y=a[i].to; if(y==fa) continue; getfa(y,x); cf[y]=a[i].c; } } int jump(int x,int len) { for(int i=0;i<LG;i++) if((len>>i)&1) x=f[x][i]; return x; } int LCA(int x,int y) { if(dep[x]<dep[y]) swap(x,y); x=jump(x,dep[x]-dep[y]);// printf("%d %d\n",x,y); if(x==y) return x; for(int i=LG-1;~i;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i]; return f[x][0]; } int nxt[N]; int kmp(char *s,char *t) { int sn=strlen(s),tn=strlen(t); for(int i=1;i<=tn;i++) { int j=nxt[i]; while(j&&t[i]!=t[j]) j=nxt[j]; if(t[j]==t[i]) nxt[i+1]=j+1; else nxt[i+1]=0; } int ans=0; for(int j=0,i=0;i<sn;i++) { while(j&&t[j]!=s[i]) j=nxt[j]; if(t[j]==s[i]) j++; if(j==tn) ans++; } return ans; } #define pa pair<int,int> #define mp make_pair #define fs first #define se second vector<pa> pq[N]; int ans[N]; void DFS(int x,int y) { //printf("%d %d\n",x,y); tr.add(y,1);// printf("%d\n",y); for(int i=0;i<pq[x].size();i++) { pa o=pq[x][i];// printf("%d %d %d %d %d\n",y,x,o.fs,o.se,tr.ask(o.se)); if(o.fs>0) ans[o.fs]+=tr.ask(o.se); else ans[-o.fs]-=tr.ask(o.se); } for(int i=ia[x];i;i=a[i].lt) if(a[i].to!=f[x][0]) DFS(a[i].to,A.t[y].son[a[i].c-‘a‘]); tr.add(y,-1); } char tmp[N]; int cross(int x,int y,char *s) { int sn=strlen(s); int lca=LCA(x,y); int dx=min(dep[x],dep[lca]+sn-1); x=jump(x,dep[x]-dx); int dy=min(dep[y],dep[lca]+sn-1); y=jump(y,dep[y]-dy); int cnt=0; for(;x!=lca;x=f[x][0]) tmp[cnt++]=cf[x]; int remcnt=cnt; for(;y!=lca;y=f[y][0]) tmp[cnt++]=cf[y]; reverse(tmp+remcnt,tmp+cnt); tmp[cnt]=0; return kmp(tmp,s); } char ch[N]; int main() { n=read(),m=read(); int x,y; char c; for(int i=1;i<n;i++) x=read(),y=read(),c=getchar(),add(x,y,c); getfa(1,0); for(int i=1;i<=m;i++) { x=read(),y=read(); scanf("%s",ch); int len=strlen(ch); ans[i]=cross(x,y,ch); int lca=LCA(x,y),pos;// printf("%d\n",ans[i]); if(dep[y]-dep[lca]>=len) pos=A.insert(ch),pq[y].push_back(mp(i,pos)),pq[jump(y,dep[y]-dep[lca]-len+1)].push_back(mp(-i,pos)); reverse(ch,ch+len); if(dep[x]-dep[lca]>=len) pos=A.insert(ch),pq[x].push_back(mp(i,pos)),pq[jump(x,dep[x]-dep[lca]-len+1)].push_back(mp(-i,pos)); } A.getfail();// printf("QAQ"); tr.n=tm; DFS(1,0); for(int i=1;i<=m;i++) printf("%d\n",ans[i]); return 0; }
CF Gym 102129 I Incomparable Pairs
大火题（雾 把问题转化成区间本质不同子串对数 然后后缀自动机和线段树维护即可 后缀自动机维护的时候其实用到了SDOI树点染色的思想 用LCT维护结构 Access来保证复杂度 然后就是写起来很爽而已
//Love and Freedom. #include<cstring> #include<cmath> #include<algorithm> #include<cstdio> #include<vector> #define N 400010 #define ll long long #define inf 20021225 #define id(x) (x-‘a‘) #define ll __int128 using namespace std; int read() { int s=0,f=1; char ch=getchar(); while(ch<‘0‘ || ch>‘9‘) {if(ch==‘-‘) f=-1;ch=getchar();} while(ch>=‘0‘ && ch<=‘9‘) s=s*10+ch-‘0‘,ch=getchar(); return f*s; } #define ls (x<<1) #define rs (x<<1|1) struct SGT { ll a[N<<2],tag[N<<2],a2[N<<2]; void put(int x,int l,int r,ll v) { tag[x]+=v; a[x]+=(r-l+1)*v; a2[x]+=v*(r-l+1)*(r+l)/2; } void pushdown(int x,int l,int r) { if(!tag[x]) return; int mid=l+r>>1,t=tag[x]; tag[x]=0; put(ls,l,mid,t); put(rs,mid+1,r,t); } void pushup(int x){a[x]=a[ls]+a[rs]; a2[x]=a2[ls]+a2[rs];} void modify(int x,int l,int r,int LL,int RR,ll v) { if(LL<=l&&RR>=r){put(x,l,r,v); return;} int mid=l+r>>1; pushdown(x,l,r); if(LL<=mid) modify(ls,l,mid,LL,RR,v); if(RR>mid) modify(rs,mid+1,r,LL,RR,v); pushup(x); } ll query(int x,int l,int r,int LL,int RR) { if(LL<=l&&RR>=r) return a[x]; int mid=l+r>>1; pushdown(x,l,r); ll ans=0; if(LL<=mid) ans+=query(ls,l,mid,LL,RR); if(RR>mid) ans+=query(rs,mid+1,r,LL,RR); pushup(x); return ans; } ll query2(int x,int l,int r,int LL,int RR) { if(LL<=l&&RR>=r) return a2[x]; int mid=l+r>>1; pushdown(x,l,r); ll ans=0; if(LL<=mid) ans+=query2(ls,l,mid,LL,RR); if(RR>mid) ans+=query2(rs,mid+1,r,LL,RR); return ans; } }T; #undef ls #undef rs #define ls(x) t[x].son[0] #define rs(x) t[x].son[1] #define nrt(x) (t[t[x].fa].son[0]==x || t[t[x].fa].son[1]==x) struct sam{int son[26],fa,len;}s[N]; struct lct{int son[2],fa,val,tag;}t[N]; int lt,poi,rt,pos[N],ful[N]; char ch[N]; int n,top; void init(){pos[0]=lt=poi=rt=1;} void insert(int id,int c) { int p=lt,np=lt=++poi; pos[id]=np; s[np].len=s[p].len+1; ful[np]=id; for(;p&&!s[p].son[c];p=s[p].fa) s[p].son[c]=np; if(!p){s[np].fa=rt; return;} int q=s[p].son[c]; if(s[q].len==s[p].len+1){s[np].fa=q; return;} int nq=++poi; s[nq].len=s[p].len+1; memcpy(s[nq].son,s[q].son,sizeof(s[q].son)); s[nq].fa=s[q].fa; s[q].fa=s[np].fa=nq; for(;p&&s[p].son[c]==q;p=s[p].fa) s[p].son[c]=nq; } void mark(int x,int v) { t[x].tag=t[x].val=v; } void pushdown(int x) { if(!t[x].tag) return; int tx=t[x].tag; t[x].tag=0; if(ls(x)) t[ls(x)].val=t[ls(x)].tag=tx; if(rs(x)) t[rs(x)].val=t[rs(x)].tag=tx; } void push(int x){if(nrt(x)) push(t[x].fa); pushdown(x);} void rotate(int x) { if(!x || !nrt(x)) return; int f=t[x].fa,gf=t[f].fa; int p=rs(f)==x,k=p^1; if(nrt(f)) t[gf].son[rs(gf)==f]=x; t[x].fa=gf; t[f].fa=x; if(t[x].son[k]) t[t[x].son[k]].fa=f; t[f].son[p]=t[x].son[k]; t[x].son[k]=f; } void splay(int x) { if(!x) return; push(x); while(nrt(x)) { int f=t[x].fa,gf=t[f].fa; if(nrt(f)) (rs(f)==x)^(rs(gf)==f)?rotate(x):rotate(f); rotate(x); } } #define pa pair<int,int> #define mp make_pair #define fs first #define se second #define pb push_back pa seq[N]; vector<pa> qry[N]; void modify(int l,int r,ll v){T.modify(1,1,n,l,r,v);} void access(int x,int val) { int y=0; top=0; while(x) { splay(x); top++; //printf("%d %d\n",s[x].len,t[x].val); seq[top]=mp(s[x].len,t[x].val); t[x].son[1]=y; mark(x,val); y=x; x=t[x].fa; } //t[x].val=val; } vector<int> e[N]; void add(int x,int y) { e[x].pb(y); } void dfs(int x) { for(int i=0;i<e[x].size();i++) dfs(e[x][i]),ful[x]=ful[e[x][i]]; } void build() { init(); for(int i=1;i<=n;i++) insert(i,id(ch[i])); for(int i=2;i<=poi;i++) add(s[i].fa,i); } void solve() { ll ans=0; build(); dfs(1); for(int i=2;i<=poi;i++) //printf("%d ",ful[i]), qry[ful[i]].push_back(mp(ful[i]-s[i].len+1,ful[i]-s[s[i].fa].len)); for(int i=1;i<=poi;i++) t[i].fa=s[i].fa; for(int i=1;i<=n;i++) { modify(1,i,1); access(pos[i],i); //printf("%d %d\n",pos[i],i); int lst=0; for(int j=top;j>1;j--) { pa tmp=seq[j]; //printf("%d %d\n",tmp.fs,tmp.se); if(tmp.fs) { if(tmp.se) modify(tmp.se-tmp.fs+1,tmp.se-lst,-1); lst=tmp.fs; } } for(int j=0;j<qry[i].size();j++) { pa tmp=qry[i][j];// printf("%d %d\n",tmp.fs,tmp.se); ans+=T.query2(1,1,n,tmp.fs,tmp.se); //printf("%lld\n",T.query2(1,1,n,tmp.fs,tmp.se)); ans-=T.query(1,1,n,tmp.fs,tmp.se)*(tmp.fs-1); if(tmp.se!=i) ans+=T.query(1,1,n,tmp.se+1,i)*(tmp.se-tmp.fs+1); } //printf("%lld ",ans); } ll sum=0; for(int i=2;i<=poi;i++) sum+=s[i].len-s[s[i].fa].len; sum=sum*(sum+1)/2;// printf("%d\n",ans); printf("%llu\n",(unsigned long long)sum-ans); } int main() { scanf("%s",ch+1); n=strlen(ch+1); solve(); return 0; }
SCOI2016 萌萌哒
用ST表来表示区间 然后并查集合并看做标记 最后统计答案的时候把ST表上的标记全部下传 没想到并查集还可以这么用系列
//Love and Freedom. #include<cstdio> #include<cmath> #include<algorithm> #include<cstring> #define ll long long #define inf 20021225 #define N 100010 #define LG 19 #define mdn 1000000007 #define inv 700000005 using namespace std; int read() { int s=0; char ch=getchar(); while(ch<‘0‘||ch>‘9‘) ch=getchar(); while(ch<=‘9‘&&ch>=‘0‘) s=s*10+ch-‘0‘,ch=getchar(); return s; } int f[N*LG],id[N][LG],pos[N*LG],tot; int find(int x){return f[x]==x?x:f[x]=find(f[x]);} void merge(int x,int y){f[find(x)]=find(y);} void pushdown(int x,int l) { int tmp=find(id[x][l]); if(tmp==id[x][l]) return; int y=pos[tmp]; merge(id[x][l-1],id[y][l-1]); merge(id[x+(1<<l-1)][l-1],id[y+(1<<l-1)][l-1]); } int main() { int n=read(),m=read(); for(int i=0;i<LG;i++) for(int j=1;j+(1<<i)-1<=n;j++) id[j][i]=++tot,pos[tot]=j,f[tot]=tot; while(m--) { int l1=read(),r1=read(),l2=read(),r2=read(); int len=r1-l1+1; for(int i=0;i<LG;i++) if(len&(1<<i)) merge(id[l1][i],id[l2][i]),l1+=1<<i,l2+=1<<i; } for(int i=LG-1;i;i--) for(int j=1;j+(1<<i)-1<=n;j++) pushdown(j,i); int ans=1; for(int i=1;i<=n;i++) if(find(f[id[i][0]])==id[i][0]) ans=1ll*ans*10%mdn; ans=1ll*ans*inv%mdn*9%mdn; printf("%d\n",ans); return 0; }
好像还有很多校内题不方便放 那先这样吧qaq
原文：https://www.cnblogs.com/hanyuweining/p/11371466.html
