受某些原因而鸽了考试，然鹅题也没有做完，只能先鸽为妙。

woj4785~4789

曾经排队

阅读题，，实在是不想写了。只要注意long long平方会爆long long，只需要与1e9+1取min再做就行。

#include<bits/stdc++.h> using namespace std; #define in read() #define int long long int in{ int cnt=0,f=1;char ch=0; while(!isdigit(ch)){ ch=getchar();if(ch=='-')f=-1; } while(isdigit(ch)){ cnt=cnt*10+ch-48; ch=getchar(); }return cnt*f; } int n,q,minn; int a[700003]; int Gcd; int gcd(int a,int b){ if(!b)return a; return gcd(b,a%b); } signed main(){ n=in;minn=2e18; for(int i=1;i<=n;i++)minn=min(minn,a[i]=in); Gcd=a[1]; for(int i=2;i<=n;i++)Gcd=gcd(Gcd,a[i]); q=in; while(q--){ int x=in;int op=in; if(op==1){ if(Gcd%x)cout<<"No"<<'\n';else cout<<"Yes"<<'\n'; }else{ x=min(x,(int)(1e9+1)); if(x*x<minn)cout<<"Yes"<<'\n';else cout<<"No"<<'\n'; } } return 0; }

元素世界

类似莫队的桶桶题。维护与正解的差值，0才是好的。每次扫一遍。这道题对于赋0有启发意义。

先鸽，好困qw

层层回忆

题面好长哦。

每个点有子树和权值（均非负）。自己在不作为路径极值的情况下，求能到达的点集或和。

不能极值，分大或小两种。

既然非负，那我肯定比子树大。所以不往子树走。

往上都是比我大的，我不能是最小的。那我的目标肯定是非祖孙的点且要比自己小。

画一棵树，去掉自己的子树，所有比我还小的点，，这个dfs序很好做。

去掉子树，，前后各做一次不就好了吗qwq

友情提示，记得开栈。

#include<bits/stdc++.h> using namespace std; #define in read() int in{ int cnt=0,f=1;char ch=0; while(!isdigit(ch)){ ch=getchar(); if(ch=='-')f=-1; } while(isdigit(ch)){ cnt=cnt*10+ch-48; ch=getchar(); }return cnt*f; } int t[3000003],ans[500003],a[500003],first[500003],nxt[1000003],to[1000003],tot; void add(int a,int b){ nxt[++tot]=first[a];first[a]=tot;to[tot]=b; } int gin[500003],gout[500003],id,pre[500003]; vector<int> before[500003],after[500003]; int n,rt; void dfs(int u,int fa){ gin[u]=++id;pre[id]=u;; for(int i=first[u];i;i=nxt[i]){ int v=to[i];if(v==fa)continue; dfs(v,u);a[u]+=a[v]; }gout[u]=id; } int lowbit(int x){ return x&(-x); } void modify(int x,int key){ while(x<=3000000){ t[x]|=key;x+=lowbit(x); } } int query(int x){ int sum=0; while(x){ sum|=t[x];x-=lowbit(x); }return sum; } signed main(){ int size=40<<20;//40M //__asm__ ("movl %0, %%esp\n"::"r"((char*)malloc(size)+size));//调试用这个 __asm__ ("movq %0,%%rsp\n"::"r"((char*)malloc(size)+size));//提交用这个 //main函数代码 n=in;rt=in; for(int i=1,a,b;i<n;i++)a=in,b=in,add(a,b),add(b,a); for(int i=1;i<=n;i++)a[i]=in; dfs(rt,0); for(int i=1;i<=n;i++){ before[gin[i]-1].push_back(i); after[gout[i]+1].push_back(i); } for(int i=1;i<=n;i++){ modify(a[pre[i]],a[pre[i]]); for(int j=0;j<before[i].size();j++){ int x=before[i][j]; ans[x]|=query(a[x]-1); } } memset(t,0,sizeof(t)); for(int i=n;i>=1;i--){ modify(a[pre[i]],a[pre[i]]); for(int j=0;j<after[i].size();j++){ int x=after[i][j]; ans[x]|=query(a[x]-1); } } for(int i=1;i<=n;i++)cout<<ans[i]<<" "; exit(0); return 0; }

奇异序列

是我太菜，想过状压，但我完全没有把能否出现表示成状态的想法。先鸽。

乐园建设

这道题有毒。卡我费用流板子，，明天得换个板子。

很高兴能想出来怎么建图。

我的思维很不成熟，面对题目只能臆测算法。

这道题让我毫无头绪，数据范围让我回想起曾经被计数题吊打的悲惨回忆，想歪了很久。

然后惊觉：这根计数有个什么关系，，求最大贡献不应该想想网络流吗。

然后开始想费用流。

先想怎么合法。合法要全是回路。一个回路，，每个点度数都是2，，

于是第一反应先拆点，每个点有2的流量，向四个方向连边，弄出来每个点都弄满成2就有解。

四个方向，本质实际上是黑白染色，，不过我一开始没往那方面想，后面想贡献时才发现要染色。

但是要算贡献。拐弯的话？

网格图，，四个方向，，方向不同才能有贡献，，

方向不同？那再拆点啊。但流量为2？再加一个控流点。

贡献要打，先最大费用。然后考虑构图。显然，控流点向同一个方向得有两条边。先选大的，然后如果方向相同，会选一个0。

如果不同，两个都选大的。发现这样做，刚好多算了贡献的一次和。所以最后减去就行了。

写着写着发现不对，，没有黑白染色的话，贡献会算炸。于是染了色分开考虑。

然后T了。

#include<bits/stdc++.h> using namespace std; #define in read() int in{ int cnt=0,f=1;char ch=0; while(!isdigit(ch)){ ch=getchar();if(ch=='-')f=-1; } while(isdigit(ch)){ cnt=cnt*10+ch-48; ch=getchar(); }return cnt*f; } int n,m; int first[20003],nxt[200003],to[200003],w[200003],cost[200003],tot=1; int x[4]={-1,1,0,0},y[4]={0,0,-1,1}; int mapp[303][303],a[303][303],id[303][303][3],c[303][303]; int cnt,S,T,all; int Maxflow,Maxcost,maxcost[15003],pre[15003],ww[15003],last[15003],vis[15003]; queue<int> q; inline void add(int a,int b,int c,int d){ //cout<<a<<" "<<b<<" "<<c<<" "<<d<<endl; nxt[++tot]=first[a];first[a]=tot;to[tot]=b;w[tot]=c;cost[tot]=d; nxt[++tot]=first[b];first[b]=tot;to[tot]=a;w[tot]=0;cost[tot]=-d; } inline bool bfs(int s,int t){ memset(maxcost,-0x3f,sizeof(maxcost)); memset(ww,0x3f,sizeof(ww));memset(vis,0,sizeof(vis)); q.push(s);vis[s]=1;maxcost[s]=0;pre[t]=-1; while(!q.empty()){ int u=q.front();q.pop();vis[u]=0; for(register int i=first[u];i;i=nxt[i]){ int v=to[i];if(w[i]&&maxcost[v]<maxcost[u]+cost[i]){ maxcost[v]=maxcost[u]+cost[i]; ww[v]=min(ww[u],w[i]);pre[v]=u;last[v]=i; if(!vis[v])q.push(v),vis[v]=1; } } }return pre[t]!=-1; } inline void dinic(int s,int t){ while(bfs(s,t)){ Maxcost+=maxcost[t]*ww[t];Maxflow+=ww[t]; int now=t; while(now!=s){ w[last[now]]-=ww[t];w[last[now]^1]+=ww[t]; now=pre[now]; } } }int sumall; signed main(){ n=in;m=in; for(register int i=1;i<=n;i++)for(register int j=1;j<=m;j++)mapp[i][j]=in; for(register int i=1;i<=n;i++)for(register int j=1;j<=m;j++) a[i][j]=in,c[i][j]=(i+j)%2,sumall+=(mapp[i][j])?0:a[i][j],\ id[i][j][0]=++cnt,id[i][j][1]=++cnt,id[i][j][2]=++cnt; S=0;T=cnt+1; for(register int i=1;i<=n;i++){ for(register int j=1;j<=m;j++){ if(mapp[i][j])continue; if(c[i][j]){ all+=2;add(S,id[i][j][0],2,0); add(id[i][j][0],id[i][j][1],1,a[i][j]);add(id[i][j][0],id[i][j][1],1,0); add(id[i][j][0],id[i][j][2],1,a[i][j]);add(id[i][j][0],id[i][j][2],1,0); }else{ add(id[i][j][0],T,2,0); add(id[i][j][1],id[i][j][0],1,a[i][j]);add(id[i][j][1],id[i][j][0],1,0); add(id[i][j][2],id[i][j][0],1,a[i][j]);add(id[i][j][2],id[i][j][0],1,0); } } } //cout<<"#"<<endl; for(register int i=1;i<=n;i++){ for(register int j=1;j<=m;j++){ if(mapp[i][j])continue; if(!c[i][j])continue; for(register int k=0;k<4;k++){ int nx=i+x[k],ny=j+y[k]; if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&!mapp[nx][ny]){ if(k==0||k==1)add(id[i][j][1],id[nx][ny][1],1,0); else add(id[i][j][2],id[nx][ny][2],1,0); } } } } dinic(S,T); if(Maxflow<all){ cout<<"-1";return 0; } //cout<<sumall<<" "<<Maxcost<<" "<<Maxflow<<endl; cout<<Maxcost-sumall; return 0; }