CF Round 403D Football League 暴力

暴力"/>

CF Round 403D Football League 暴力

题意:n个二元组(a,b).a和b为字符串.
n次操作:第i次操作: 选法1:选择a的前三个字符,选法2:a的前两个字符和b的第一个字符.
规则1:要求选出的n个字符串没有相同的
规则2:若第i次使用了选法2,那么任意一次选法1都不能和第i次的选法1相同.
例如a=dinamo , b=bytecity  使用选法2：dib,那么其他操作不能用选法1得到:din
n<=1e3,3<=|a|,|b|<=20  输出选法的n个字符串 或者判断无解.


若每个选法1都不同,显然得到一解.
将选法1相同的放到同一个集合中.


若该集合size>1 那么该集合内元素都只能使用选法2.
做完上面的选择以后,size==1的集合他的选法1或者选法2可能被占用.
若集合size=1它的选法1被占用,那么判断是否能使用它的选法2.

直到所有集合size=1的选法1都没有被占用,此时显然得到一解.

#include <bits/stdc++.h>
using namespace std;
const int N=2e3+5;
int n,num=0,flag=true,vis[N];
struct node{string a,b,c;int id;
}p[N];
vector<node> c[N]; 
string res[N],a,b;
map<string,int> mp,mk;
int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>a>>b;p[i].a=a.substr(0,3);p[i].b=a.substr(0,2)+b.substr(0,1);p[i].id=i;if(!mp[p[i].a])	mp[p[i].a]=++num;c[mp[p[i].a]].push_back(p[i]);}for(int i=1;i<=num;i++){if(c[i].size()==1)	continue;for(int j=0;j<c[i].size();j++){if(!mk[c[i][j].b]){mk[c[i][j].b]=true;res[c[i][j].id]=c[i][j].b;//	cout<<c[i][j].id<<' '<<c[i][j].b<<'\n'; }else 	flag=false; }}bool ok=true;while(ok){	ok=false;for(int i=1;i<=num&&flag;i++){if(c[i].size()>1||vis[i])	continue;string x=c[i][0].a,y=c[i][0].b;if(mk[x]&&mk[y])	flag=false;if(mk[x]&&(!mk[y]))	mk[y]=true,res[c[i][0].id]=y,vis[i]=true,ok=true;}}for(int i=1;i<=num;i++){if(vis[i]||c[i].size()>1)	continue;res[c[i][0].id]=c[i][0].a;}if(flag==false){puts("NO");return 0;}puts("YES");for(int i=1;i<=n;i++)	cout<<res[i]<<'\n';return 0;
}

膜大佬的解法...

每个点初始有两种选法,两条边. 

若选法1的size>1 那么禁掉这条边即可.

左边是边,右边是选法,做二分图匹配O(n*m)).

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// headconst int N=1010;
int n,val[N][2];
char a[30],b[30];
string g[N][2],s[N];
map<string,int> vis,p;
int dfs(int u) {rep(v,0,2) if (val[u][v]&&!vis[g[u][v]]) {string c=g[u][v];vis[c]=1;if (p[c]==0||dfs(p[c])) { p[c]=u; s[u]=c; return 1;}}return 0;
}
int main() {scanf("%d",&n);rep(i,1,n+1) {scanf("%s%s",a,b);g[i][0]=string{a[0],a[1],a[2]};g[i][1]=string{a[0],a[1],b[0]};}rep(i,1,n+1) {val[i][0]=val[i][1]=1;rep(j,1,n+1) if (i!=j&&g[i][0]==g[j][0]) {val[i][0]=0; break;}vis.clear();if (!dfs(i)) {puts("NO");return 0;}}puts("YES");rep(i,1,n+1) printf("%s\n",s[i].c_str());
}