传送门
题意:给你一个大小为n集合,集合内的数各不相同,且n一定被5整除,q个限制。每个限制给你一个upToi 一个 quantityi,说明集合在[1,uptoi]内有quantityi个数。
问你是否存在满足这些限制且满足被5取余后各个余数数目相同的集合。
题解:可以看成网络流,满载流量为n,S点连余数为0,1,2,3,4的集合代表的流量为n/5,然后sort一下限制,对每一个新出现在新范围内的数字与对应余数连容量为1的边,最后判断下是否满足n==最大流。还要特判一下一些限制是否合法。
#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <map> #include <queue> #include <vector> #include <cstring> #include <iomanip> #include <set> #include<ctime> //CLOCKS_PER_SEC #define se second #define fi first #define ll long long #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define Pii pair<int,int> #define Pli pair<ll,int> #define ull unsigned long long #define pb push_back #define fio ios::sync_with_stdio(false);cin.tie(0) const double Pi=3.14159265; const int N=1e6+1e5; const ull base=163; const int INF=0x3f3f3f3f; using namespace std; int n,m,s,t; int head[100010],to[N],cur[100010],nx[N]; int cap[N]; int tot=0; int d[N]; void add(int u,int v,int c){to[tot]=v;cap[tot]=c;nx[tot]=head[u];head[u]=tot++;to[tot]=u;cap[tot]=0;nx[tot]=head[v];head[v]=tot++; } void init(){tot=0;memset(head,-1,sizeof(head)); }int bfs(){memset(d,-1,sizeof(d));queue<int>q;q.push(s);d[s]=1;while(!q.empty()){int u=q.front();q.pop();for(int i=head[u];~i;i=nx[i]){int v=to[i];if(d[v]==-1&&cap[i]>0){d[v]=d[u]+1;q.push(v);}}}return d[t]!=-1; } int dfs(int s,int a){if(s==t||a==0)return a;int flow=0,f;for(int &i=cur[s];~i;i=nx[i]){int v=to[i];if(d[s]+1==d[v] && cap[i]>0 && (f=dfs(v,min(a,cap[i])))>0){flow+=f;cap[i]-=f;cap[i^1]+=f;a-=f;if(a==0)break;}}return flow; } int dinic(){int ans=0;while(bfs()){for(int i=0;i<=t;i++)cur[i]=head[i];while(int di=dfs(s,INF)){ans+=di;}}return ans; } Pii p[N]; int main(){int n,b,q;fio;cin>>n>>b>>q;init();s=0,t=10100;for(int i=1;i<=q;i++){cin>>p[i].fi>>p[i].se;}q++;p[q].fi=b,p[q].se=n;sort(p+1,p+1+q);for(int i=1;i<=q;i++){int tmp=p[i].se-p[i-1].se;if(tmp<0)return cout<<"unfair\n",0;}p[0]={0,0};for(int i=1;i<=5;i++)add(s,i,n/5);for(int i=1;i<=q;i++){add(5+i,t,p[i].se-p[i-1].se);for(int j=1;j<=5;j++){int l=p[i].fi/5+(p[i].fi%5>=j);int r=p[i-1].fi/5+(p[i-1].fi%5>=j);add(j,5+i,l-r);}}if(dinic()!=n)return cout<<"unfair",0;else cout<<"fair";return 0; }