省选图论专题
开题顺序： \(GAJDCFO\)
\(A\) luogu P4151 [WC2011] 最大XOR和路径
\(B\) CF19E Fairy
\(C\) CF412D Giving Awards
-
建出反图后拓扑排序无法处理欠钱关系中存在环的情况，但可以借鉴其思路。
-
仍考虑自下而上叫人，在叫完所有子节点后再加入答案即可。
点击查看代码
struct node { int nxt,to; }e[200010]; int head[200010],vis[200010],cnt=0; vector<int>ans; void add(int u,int v) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; head[u]=cnt; } void dfs(int x) { vis[x]=1; for(int i=head[x];i!=0;i=e[i].nxt) { if(vis[e[i].to]==0) { dfs(e[i].to); } } ans.push_back(x); } int main() { // #define Isaac #ifdef Isaac freopen("in.in","r",stdin); freopen("out.out","w",stdout); #endif int n,m,u,v,i; cin>>n>>m; for(i=1;i<=m;i++) { cin>>u>>v; add(u,v); } for(i=1;i<=n;i++) { if(vis[i]==0) { dfs(i); } } for(i=0;i<ans.size();i++) { cout<<ans[i]<<" "; } return 0; }
\(D\) luogu P4819 [中山市选] 杀人游戏
-
缩完点后对所有入度为 \(0\) 的点询问一次即可。
-
一开始询问若不是杀手，则可以顺次知道所在 \(DAG\) 内能到达的所有人是否是杀手；否则就被直接干掉了。
-
形式化地，设最终有 \(c\) 个入度为 \(0\) 的点，每个点是杀手的概率是 \(\frac{1}{n}\) 则 \(1-\frac{c}{n}\) 即为所求。
-
特别地，需要在缩点后存在入度为 \(0\) 大小（缩点后的大小）为 \(1\) 且能到达的点的入度都 \(\ge 2\) 的点时进行特判，此时可以不对这个点进行询问也可以知道这个点的身份。
-
需要对边进行去重。
点击查看代码
struct node { int nxt,to; }e[600010]; int head[600010],dfn[600010],low[600010],ins[600010],col[600010],u[600010],v[600010],din[600010],siz[600010],tot=0,cnt=0,scc_cnt=0; stack<int>s; vector<int>E[600010]; map<pair<int,int>,int> vis; void add(int u,int v) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; head[u]=cnt; } void tarjan(int x) { tot++; dfn[x]=low[x]=tot; ins[x]=1; s.push(x); for(int i=head[x];i!=0;i=e[i].nxt) { if(dfn[e[i].to]==0) { tarjan(e[i].to); low[x]=min(low[x],low[e[i].to]); } else { if(ins[e[i].to]==1) { low[x]=min(low[x],dfn[e[i].to]); } } } if(dfn[x]==low[x]) { scc_cnt++; int tmp=0; while(x!=tmp) { tmp=s.top(); s.pop(); ins[tmp]=0; col[tmp]=scc_cnt; siz[scc_cnt]++; } } } int main() { // #define Isaac #ifdef Isaac freopen("in.in","r",stdin); freopen("out.out","w",stdout); #endif int n,m,ans=0,flag,i,j; cin>>n>>m; for(i=1;i<=m;i++) { cin>>u[i]>>v[i]; add(u[i],v[i]); } for(i=1;i<=n;i++) { if(dfn[i]==0) { tarjan(i); } } for(i=1;i<=m;i++) { if(col[u[i]]!=col[v[i]]&&vis[make_pair(col[u[i]],col[v[i]])]==0) { vis[make_pair(col[u[i]],col[v[i]])]=1; E[col[u[i]]].push_back(col[v[i]]); din[col[v[i]]]++; } } for(i=1;i<=scc_cnt;i++) { ans+=(din[i]==0); } for(i=1;i<=scc_cnt;i++) { if(din[i]==0&&siz[i]==1) { flag=1; for(j=0;j<E[i].size();j++) { flag&=(din[E[i][j]]>=2); } if(flag==1) { ans--; break; } } } printf("%.6lf\n",1.0-1.0*ans/n); return 0; }
\(E\) luogu P4630 [APIO2018] 铁人两项
\(F\) luogu P3403 跳楼机
-
同余最短路板子。
- 同余最短路常利用同余性质构造状态来进行优化空间，并使用最短路进行辅助转移，形如 \(f((i+y) \bmod x)=f(i)+y\) 。
- 模数 \(x\) 的选择会影响建边的数量，以至于影响时空复杂度，实际应用时应尽可能选择较小的 \(x\) 。
-
操作 \(4\) 没什么用，可以直接不管。
-
设 \(dis_{i}\) 表示仅通过操作 \(1,2\) 能到达的楼层中满足 \(\bmod z=i\) 时的最小楼层，使用同余最短路进行转移。最终有 \(\sum\limits_{i=1}^{n}[dis_{i} \le h] \times (\left\lfloor \frac{h-dis_{i}}{z} \right\rfloor+1)\) 即为所求。
-
因本题中 \(h\) 较大，不妨先让 \(h\) 减一并钦定起始楼层为 \(0\) 楼即可。
点击查看代码
struct node { ll nxt,to,w; }e[400010]; ll head[400010],dis[400010],vis[400010],cnt=0; void add(ll u,ll v,ll w) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; e[cnt].w=w; head[u]=cnt; } void dijkstra(ll s,ll h) { priority_queue<pair<ll,ll> >q; dis[s]=0; q.push(make_pair(-dis[s],s)); while(q.empty()==0) { ll x=q.top().second; q.pop(); if(vis[x]==0) { vis[x]=1; for(ll i=head[x];i!=0;i=e[i].nxt) { if(dis[e[i].to]>dis[x]+e[i].w) { dis[e[i].to]=dis[x]+e[i].w; q.push(make_pair(-dis[e[i].to],e[i].to)); } } } } } int main() { // #define Isaac #ifdef Isaac freopen("in.in","r",stdin); freopen("out.out","w",stdout); #endif ll h,x,y,z,ans=0,i; cin>>h>>x>>y>>z; for(i=0;i<=z-1;i++) { add(i,(i+x)%z,x); add(i,(i+y)%z,y); dis[i]=h; } h--; dijkstra(0,h); for(i=0;i<=z-1;i++) { ans+=(dis[i]<=h)*((h-dis[i])/z+1); } cout<<ans<<endl; return 0; }
\(G\) luogu P3275 [SCOI2011] 糖果
\(H\) luogu P7515 [省选联考 2021 A 卷] 矩阵游戏
\(I\) CF888G Xor-MST
\(J\) luogu P4768 [NOI2018] 归程
\(K\) luogu P6628 [省选联考 2020 B 卷] 丁香之路
\(L\) luogu P6624 [省选联考 2020 A 卷] 作业题
\(M\) luogu P6657 【模板】LGV 引理
\(N\) luogu P7736 [NOI2021] 路径交点
\(O\) luogu P2371 [国家集训队] 墨墨的等式
-
观察到 \(\{ b \}\) 可差分，然后同余最短路维护即可。
点击查看代码
struct node { ll nxt,to,w; }e[6000010]; ll head[6000010],dis[6000010],vis[6000010],a[6000010],cnt=0; void add(ll u,ll v,ll w) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; e[cnt].w=w; head[u]=cnt; } void dijkstra(ll s) { memset(dis,0x3f,sizeof(dis)); memset(vis,0,sizeof(vis)); priority_queue<pair<ll,ll> >q; dis[s]=0; q.push(make_pair(-dis[s],s)); while(q.empty()==0) { ll x=q.top().second; q.pop(); if(vis[x]==0) { vis[x]=1; for(ll i=head[x];i!=0;i=e[i].nxt) { if(dis[e[i].to]>dis[x]+e[i].w) { dis[e[i].to]=dis[x]+e[i].w; q.push(make_pair(-dis[e[i].to],e[i].to)); } } } } } int main() { // #define Isaac #ifdef Isaac freopen("in.in","r",stdin); freopen("out.out","w",stdout); #endif ll n,l,r,ans=0,i,j; cin>>n>>l>>r; l--; for(i=1;i<=n;i++) { cin>>a[i]; if(i>=2) { for(j=0;j<=a[1]-1;j++) { add(j,(j+a[i])%a[1],a[i]); } } } dijkstra(0); for(i=0;i<=a[1]-1;i++) { ans+=(dis[i]<=r)*((r-dis[i])/a[1]+1); ans-=(dis[i]<=l)*((l-dis[i])/a[1]+1); } cout<<ans<<endl; return 0; }