CF626F. Bear and Fair Set

Solution

單走一個網絡流。
先對余數$0..4$分別建一個點，從$S?>0..4$分別連容量$n/5$的邊。

對于每一個限制，相當于把$[0,b]$分成了若干個小區間，并且可以求得每個小區間中數的個數，然后由$0..4$的點$t$分別向每個小區間$[l,r]$，連一條容量為${\sum }_{l\le i\le r}[imod5=t]$，即區間內模$5$余數為$t$的數的個數。

最后從每個區間向$T$連一條容量為區間長度的邊。

跑網絡流判斷是否滿流即可。

Code

#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <queue> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <ctime> #include <cassert> #include <string.h> //#include <unordered_set> //#include <unordered_map> //#include <bits/stdc++.h>#define MP(A,B) make_pair(A,B) #define PB(A) push_back(A) #define SIZE(A) ((int)A.size()) #define LEN(A) ((int)A.length()) #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define fi first #define se secondusing namespace std;template<typename T>inline bool upmin(T &x,T y) { return y<x?x=y,1:0; } template<typename T>inline bool upmax(T &x,T y) { return x<y?x=y,1:0; }typedef long long ll; typedef unsigned long long ull; typedef long double lod; typedef pair<int,int> PR; typedef vector<int> VI;const lod eps=1e-11; const lod pi=acos(-1); const int oo=1<<30; const ll loo=1ll<<62; const int mods=1e9+7; const int MAXN=300005; const int INF=0x3f3f3f3f;//1061109567 /*--------------------------------------------------------------------*/ inline int read() {int f=1,x=0; char c=getchar();while (c<'0'||c>'9') { if (c=='-') f=-1; c=getchar(); }while (c>='0'&&c<='9') { x=(x<<3)+(x<<1)+(c^48); c=getchar(); }return x*f; } PR a[MAXN]; queue<int> que; struct enode{int nxt,v,c; } e[MAXN]; int dist[MAXN],start[MAXN],head[MAXN],nodenum=1,n,R,m,S,T,N; int get(int l,int r,int k) {int ans=0;for (int i=l;i<=r;i++) ans+=(i%5==k);return ans; } void add(int u,int v,int c) { // cout<<u<<" "<<v<<" "<<c<<endl;if (!c) return;e[++nodenum]=(enode){head[u],v,c},head[u]=nodenum;e[++nodenum]=(enode){head[v],u,0},head[v]=nodenum; } int bfs() {for (int i=0;i<=N;i++) start[i]=head[i],dist[i]=INF;dist[S]=1,que.push(S);while (!que.empty()){int q=que.front(); que.pop();for (int i=head[q];i;i=e[i].nxt) {enode p=e[i];if (p.c<=0||dist[p.v]!=INF) continue;dist[p.v]=dist[q]+1;que.push(p.v);}}return dist[T]!=INF; } int dfs(int x,int T,int f) {if (x==T) return f;int ans=0;for (int &i=start[x];i;i=e[i].nxt){if (e[i].c<=0||dist[e[i].v]!=dist[x]+1) continue;int t=dfs(e[i].v,T,min(f,e[i].c));e[i].c-=t,e[i^1].c+=t,f-=t,ans+=t;}return ans; } int dinic() {int ans=0;while (bfs()) ans+=dfs(S,T,INF);return ans; } signed main() {n=read(),R=read(),m=read(),S=1,T=2;for (int i=1;i<=5;i++) add(S,i+2,n/5);for (int i=1;i<=m;i++) a[i].fi=read(),a[i].se=read();a[++m]=MP(0,0),a[++m]=MP(R,n);sort(a+1,a+m+1);for (int j=2;j<=m;j++) {if (a[j].se<a[j-1].se) { puts("unfair"); return 0; }add(j+6,T,a[j].se-a[j-1].se);}for (int i=0;i<=4;i++) for (int j=2;j<=m;j++)add(i+3,j+6,get(a[j-1].fi+1,a[j].fi,i));N=m+6;if (dinic()==n) puts("fair");else puts("unfair");return 0; }

總結

以上是生活随笔為你收集整理的CF626F. Bear and Fair Set的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。