牛客练习赛53 D德育分博弈政治课
链接：https://ac.nowcoder.com/acm/contest/1114/D来源：牛客网
题目描述
德育分学长最近玩起了骰子。他玩的骰子不同，他的骰子有六面，每面上写着一个 1 到 9 之间的数字，且六个面上的数字互不相同。现在他手上有 n 个这样的骰子。政治课学长为了在小学妹面前树立威信，决定难为一下德育分。他向德育分提出了 Q 个问题，每个问题是一个字符串，且只含有‘1’~‘9’之间的字符，若德育分可以用他手上的骰子组成这个字符串，则这一回合德育分获胜，否则政治课获胜。若字符串长度为 L,则德育分从他的骰子中选出 L 个，选定每个骰子朝上的面，以一定顺序排列后恰好是这个字符串，则定义为可以组成这个字符串。
输入描述:
第一行输入 n,Q。接下来 n 行，每行输入一个长度为 6 的字符串，每个字符都在‘1’~‘9’。接下来 Q 行，每行一个字符串，每个字符都在‘1’~‘9’。且 Q 个字符串的总长度不超过 2000000。1<=n<=500000,1<=Q<=100。输出描述:
对于每一回合，若德育分获胜，输出“dyf”。若政治课获胜，输出“zzk”。示例1
输入
3 3
137628
987654
123456
288
2288
333输出
dyf
zzk
zzk思路：
如图建立流量网络，
S是源点，T是汇点。
因为给的字符串\(s[i]\) 有很多种，不可以直接根据读入\(s[i]\) 建图，但是我们知道只有1~9字符，长度为6.
而且同6个数字的任意排列是等价的，如果把我们相同的数字集合缩成一种情况的话，只有\(C(9,6)\) 种。
依次来建立流量网络可以减少很多节点和流量弧。
可以用二进制压位来表示数字集合\(i\)，同时维护出现的个数\(cnt[i]\)
接下来建立网络：
源点S与每一个数字集合\(i\)建边，流量为\(cnt[i]\)（上图中的左边绿边）（因为每种数字集合最多贡献\(cnt[i]\)个数字）
每一个数字集合和他包括的digit建边，流量为\(cnt[i]\) （上图中的中间绿边）
对于每一个询问，将1到9分别于汇点T建立边，流量为询问字符中该数字出现的次数。（上图中的篮边）
然后从源点到汇点跑最大流，如果maxflow和询问的字符串长度相等即是可以完成，反而反之。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define ALL(x) (x).begin(), (x).end()
#define sz(a) int(a.size())
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(&x)
#define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
#define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c))
#define du2(a,b) scanf("%d %d",&(a),&(b))
#define du1(a) scanf("%d",&(a));
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) {a %= MOD; if (a == 0ll) {return 0ll;} ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;}
void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
inline void getInt(int *p);
const int maxn = 100010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
#define N 200
#define INF 100000000
struct Edge {
int from, to, cap, flow; // cap 并不减少，只是flow在增，有残余就是cap>flow
};
struct sd {
int n, m, s, t;
vector<Edge>edges;
vector<int>G[N];
bool vis[N];
int d[N], cur[N];
int p[N], num[N]; //比Dinic算法多了这两个数组，p数组标记父亲结点，num数组标记距离d[i]存在几个
void addedge(int from, int to, int cap)
{
edges.push_back((Edge) {from, to, cap, 0});
edges.push_back((Edge) {to, from, 0, 0});
int m = edges.size();
G[from].push_back(m - 2);
G[to].push_back(m - 1);
}
void init()
{
MS0(d);
edges.clear();
for (int i = 0; i <= n; ++i) {
G[i].clear();
}
}
int Augumemt()
{
int x = t, a = INF;
while (x != s) { //找最小的残量值
Edge &e = edges[p[x]];
a = min(a, e.cap - e.flow);
x = edges[p[x]].from;
}
x = t;
while (x != s) { //增广
edges[p[x]].flow += a;
edges[p[x] ^ 1].flow -= a;
x = edges[p[x]].from;
}
return a;
}
void bfs()//逆向进行bfs
{
memset(vis, 0, sizeof(vis));
queue<int>q;
q.push(t);
d[t] = 0;
vis[t] = 1;
while (!q.empty()) {
int x = q.front(); q.pop();
int len = G[x].size();
for (int i = 0; i < len; i++) {
Edge &e = edges[G[x][i]];
if (!vis[e.from] && e.cap > e.flow) {
vis[e.from] = 1;
d[e.from] = d[x] + 1;
q.push(e.from);
}
}
}
}
int Maxflow(int s, int t) //根据情况前进或者后退，走到汇点时增广
{
this->s = s;
this->t = t;
int flow = 0;
bfs();
memset(num, 0, sizeof(num));
for (int i = 0; i < n; i++) {
num[d[i]]++;
}
int x = s;
memset(cur, 0, sizeof(cur));
while (d[s] < n) {
if (x == t) { //走到了汇点，进行增广
flow += Augumemt();
x = s; //增广后回到源点
}
int ok = 0;
for (int i = cur[x]; i < G[x].size(); i++) {
Edge &e = edges[G[x][i]];
if (e.cap > e.flow && d[x] == d[e.to] + 1) {
ok = 1;
p[e.to] = G[x][i]; //记录来的时候走的边，即父边
cur[x] = i;
x = e.to; //前进
break;
}
}
if (!ok) { //走不动了，撤退
int m = n - 1; //如果没有弧，那么m+1就是n，即d[i]=n
for (int i = 0; i < G[x].size(); i++) {
Edge &e = edges[G[x][i]];
if (e.cap > e.flow) {
m = min(m, d[e.to]);
}
}
if (--num[d[x]] == 0) { break; } //如果走不动了，且这个距离值原来只有一个，那么s-t不连通，这就是所谓的“gap优化”
num[d[x] = m + 1]++;
cur[x] = 0;
if (x != s) {
x = edges[p[x]].from; //退一步，沿着父边返回
}
}
}
return flow;
}
} ISAP;
int n, m;
char temp[10];
char s[500000 + 10][10];
int id = 0;
int vis[maxn];
char sw[2000000 + 10];
int need[120];
int cnt[maxn];
int main()
{
//freopen("D:\\code\\text\\input.txt","r",stdin);
//freopen("D:\\code\\text\\output.txt","w",stdout);
du2(n, m);
repd(i, 1, n) {
scanf("%s", temp);
int num = 0;
for (int j = 0; j < 6; ++j) {
num |= (1 << (temp[j] - '0'));
}
if (!vis[num]) {
vis[num] = ++id;
cnt[id]++;
strcpy(s[id], temp);
// s[id] = temp;
} else {
cnt[vis[num]]++;
}
}
while (m--) {
scanf("%s", sw);
int len = strlen(sw);
if (len > n) {
printf("zzk\n");
} else {
int S = 0;
int T = id + 20;
ISAP.n = T + 1;
ISAP.init();
repd(i, 0, 9) {
need[i] = 0;
}
for (int i = 0; i < len; ++i) {
need[sw[i] - '0']++;
}
repd(i, 1, 9) {
if (need[i]) {
ISAP.addedge(i, T, need[i]);
}
}
repd(i, 1, id) {
ISAP.addedge(S, i + 10, cnt[i]);
int len__ = strlen(s[i]);
for (int j = 0; j < len__; ++j) {
ISAP.addedge(i + 10, s[i][j] - '0', cnt[i]);
}
}
int get = ISAP.Maxflow(S, T);
// chu(get);
if (get == len) {
printf("dyf\n");
} else {
printf("zzk\n");
}
}
}
return 0;
}
inline void getInt(int *p)
{
char ch;
do {
ch = getchar();
} while (ch == ' ' || ch == '\n');
if (ch == '-') {
*p = -(getchar() - '0');
while ((ch = getchar()) >= '0' && ch <= '9') {
*p = *p * 10 - ch + '0';
}
} else {
*p = ch - '0';
while ((ch = getchar()) >= '0' && ch <= '9') {
*p = *p * 10 + ch - '0';
}
}
}
京公网安备 11010502036488号