「NOI2017」游戏

「NOI2017」游戏

RainAir

October 12, 2019

1232views

2 comments

4821 words

题解

建议大家去 UOJ 交题：链接

有 $n$ 场游戏和三种车，每个游戏可以选择用一种车，每个游戏可能要求不能使用某种车，也可能没有要求。
给出 $m$ 个要求，表示如果第 $u$ 个游戏用了 $x$ 车，那么第 $v$ 个游戏要用 $y$ 车。求一种合法方案。
$n \leq 5 \times 10^4,m \leq 10^5$，没有要求的游戏个数 $d$ 不超过 $8$。

前置小知识：2-SAT
[mdx_post]https://blog.aor.sd.cn/archives/873[/mdx_post]

首先考虑如果没有没有要求的游戏个数的话是不是一个经典的 2-SAT 问题。
注意到三个字母的状态其实是假的，每个游戏其实只有两个状态。
然后我们就可以对于每一个限制 $(u,x,v,y)$ 分类讨论了：

$u$ 游戏不能选 $x$
直接忽略掉就好了，对答案无影响。
$u$ 可选 $x$，$v$ 游戏不能选 $y$
意思就是 $u$ 不能选择 $x$，（不存在对应的 $v$）在图上对应着边 $u_{x} \to u_{\lnot x}$
$u$ 可选 $x$，$v$ 可选 $y$
就是限制当 $u=x$ 时 $v=y$，直接连边$u _ x \to v _ y,v _ {\lnot y} \to u_{\lnot x}$。

发现没有要求的游戏个数很小，选择 $O(2^d)$ 枚举，时间复杂度 $O(2^d(N+M))$

然后交到 BZOJ，惊奇的发现：
菜鸡的 BZOJ 提交记录
然后你按照博主的指引交到了 UOJ，发现：
菜鸡的 UOJ 提交记录
仔细一看原来被人叉了。有人构造了一组非常大的无解数据，这样会跑满，运算量大概是 $7.68\times 10^7$。并且 UOJ 限时 $1s$ 直接 T 了。
我们猜想满足条件的 $x$ 应该是很多的，于是我们枚举改为随机，然后卡时，然后加上 Ofast，用上关流的 cin，找个吉时就过了！

/*
 * Author: RainAir
 * Time: 2019-10-12 09:06:50
 */
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define U unsigned
#define P std::pair
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(register int i = a;i <= b;++i)
#define ROF(i,a,b) for(register int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 5e4 + 5;
const int MAXM = 1e5 + 5;

struct Edge{
    int to,nxt;
}e[MAXM<<1];
int head[MAXM],cnt;
char str[MAXN];
clock_t start;
std::vector<int> ps;
int n,d,m;
// a,b 和其他字符

inline void add(int u,int v){
    e[++cnt] = (Edge){v,head[u]};head[u] = cnt;
}

struct Query{
    int i,j;char hi,hj;
}q[MAXM];
char t0[MAXN],t1[MAXN],ch[23];
int dfn[MAXM],low[MAXM],col[MAXM];
int st[MAXM],tp,tot;
bool ins[MAXM];

inline void dfs(int v){
    static int ts = 0;
    dfn[v] = low[v] = ++ts;ins[v] = true;st[++tp] = v;
    for(int i = head[v];i;i = e[i].nxt){
        if(!dfn[e[i].to]){
            dfs(e[i].to);low[v] = std::min(low[v],low[e[i].to]);
        }
        else if(ins[e[i].to]) low[v] = std::min(low[v],dfn[e[i].to]);
    }
    if(low[v] == dfn[v]){
        int t = -1;++tot;
        do{
            t = st[tp--];
            col[t] = tot;
            ins[t] = false;
        }while(t != v);
    }
}

inline void clear(){
    CLR(head,0);CLR(dfn,0);CLR(ins,0);CLR(col,0);
    tp = tot = cnt =  0;
}

inline void Solve(){
//    puts("NEW BEGINNING");
    FOR(i,1,n){
        if(str[i] == 'A') t0[i] = 'B',t1[i] = 'C';
        else if(str[i] == 'B') t0[i] = 'A',t1[i] = 'C';
        else t0[i] = 'A',t1[i] = 'B';
    }
//    FOR(i,1,n) printf("%c %cn",t0[i],t1[i]);
    FOR(i,1,m){
        int u = q[i].i,v = q[i].j; 
        if(t0[u] == q[i].hi){
            if(str[v] == q[i].hj) add(u,u+n);
            else{
                if(t0[v] == q[i].hj) add(u,v),add(v+n,u+n);
                if(t1[v] == q[i].hj) add(u,v+n),add(v,u+n);
            }
        }
        if(t1[u] == q[i].hi){
            if(str[v] == q[i].hj) add(u+n,u);
            else{
                if(t0[v] == q[i].hj) add(u+n,v),add(v+n,u);
                if(t1[v] == q[i].hj) add(u+n,v+n),add(v,u);
            }
        }
    }
    FOR(i,1,2*n) if(!dfn[i]) dfs(i);
    FOR(i,1,n) if(col[i] == col[n+i]){
        clear();return;
    }
    // num[i] > num[i+1]
    // col[i] < col[n+i]
    FOR(i,1,n) putchar(col[i] < col[n+i] ? t0[i] : t1[i]);exit(0);
    // 缩点后编号小的拓扑序大
}

inline double now(){
    clock_t end = clock();
    return 1.0*(end-start)/CLOCKS_PER_SEC;
}

int G[MAXN];

int main(){
    std::ios::sync_with_stdio(false);
    srand(time(NULL));
    start = clock();
//    scanf("%d%d",&n,&d);
    std::cin >> n >> d;
    std::cin >> (str+1);
//    scanf("%s",str+1);
    FOR(i,1,n) str[i] -= 32;
    FOR(i,1,n) if(str[i] == 'X') ps.pb(i);
//    scanf("%d",&m);
    std::cin >> m;
    FOR(i,1,m){
//        scanf("%d",&q[i].i);scanf("%s",ch);
        std::cin >> q[i].i >> ch;
        q[i].hi = ch[0];
//        scanf("%d",&q[i].j);scanf("%s",ch);
        std::cin >> q[i].j >> ch;
        q[i].hj = ch[0];
    }
    std::vector<int> G;
    FOR(S,0,(1<<d)-1) G.pb(S);
    std::random_shuffle(all(G));
    FOR(S,0,(1<<d)-1){
        FOR(i,0,d-1) str[ps[i]] = (G[S]&(1<<i)) ? 'A' : 'B';
        Solve();
        if(now() > 1.983) break;
    }
    puts("-1");
    return 0;
}

「NOI2017」游戏

RainAir • 2019 年 10 月 12 日

建议大家去 UOJ 交题：链接

前置小知识：2-SAT
[mdx_post]https://blog.aor.sd.cn/archives/873[/mdx_post]

$u$ 游戏不能选 $x$
直接忽略掉就好了，对答案无影响。
$u$ 可选 $x$，$v$ 游戏不能选 $y$
意思就是 $u$ 不能选择 $x$，（不存在对应的 $v$）在图上对应着边 $u_{x} \to u_{\lnot x}$
$u$ 可选 $x$，$v$ 可选 $y$
就是限制当 $u=x$ 时 $v=y$，直接连边$u _ x \to v _ y,v _ {\lnot y} \to u_{\lnot x}$。

发现没有要求的游戏个数很小，选择 $O(2^d)$ 枚举，时间复杂度 $O(2^d(N+M))$

/*
 * Author: RainAir
 * Time: 2019-10-12 09:06:50
 */
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define U unsigned
#define P std::pair
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(register int i = a;i <= b;++i)
#define ROF(i,a,b) for(register int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 5e4 + 5;
const int MAXM = 1e5 + 5;

struct Edge{
    int to,nxt;
}e[MAXM<<1];
int head[MAXM],cnt;
char str[MAXN];
clock_t start;
std::vector<int> ps;
int n,d,m;
// a,b 和其他字符

inline void add(int u,int v){
    e[++cnt] = (Edge){v,head[u]};head[u] = cnt;
}

struct Query{
    int i,j;char hi,hj;
}q[MAXM];
char t0[MAXN],t1[MAXN],ch[23];
int dfn[MAXM],low[MAXM],col[MAXM];
int st[MAXM],tp,tot;
bool ins[MAXM];

inline void dfs(int v){
    static int ts = 0;
    dfn[v] = low[v] = ++ts;ins[v] = true;st[++tp] = v;
    for(int i = head[v];i;i = e[i].nxt){
        if(!dfn[e[i].to]){
            dfs(e[i].to);low[v] = std::min(low[v],low[e[i].to]);
        }
        else if(ins[e[i].to]) low[v] = std::min(low[v],dfn[e[i].to]);
    }
    if(low[v] == dfn[v]){
        int t = -1;++tot;
        do{
            t = st[tp--];
            col[t] = tot;
            ins[t] = false;
        }while(t != v);
    }
}

inline void clear(){
    CLR(head,0);CLR(dfn,0);CLR(ins,0);CLR(col,0);
    tp = tot = cnt =  0;
}

inline void Solve(){
//    puts("NEW BEGINNING");
    FOR(i,1,n){
        if(str[i] == 'A') t0[i] = 'B',t1[i] = 'C';
        else if(str[i] == 'B') t0[i] = 'A',t1[i] = 'C';
        else t0[i] = 'A',t1[i] = 'B';
    }
//    FOR(i,1,n) printf("%c %cn",t0[i],t1[i]);
    FOR(i,1,m){
        int u = q[i].i,v = q[i].j; 
        if(t0[u] == q[i].hi){
            if(str[v] == q[i].hj) add(u,u+n);
            else{
                if(t0[v] == q[i].hj) add(u,v),add(v+n,u+n);
                if(t1[v] == q[i].hj) add(u,v+n),add(v,u+n);
            }
        }
        if(t1[u] == q[i].hi){
            if(str[v] == q[i].hj) add(u+n,u);
            else{
                if(t0[v] == q[i].hj) add(u+n,v),add(v+n,u);
                if(t1[v] == q[i].hj) add(u+n,v+n),add(v,u);
            }
        }
    }
    FOR(i,1,2*n) if(!dfn[i]) dfs(i);
    FOR(i,1,n) if(col[i] == col[n+i]){
        clear();return;
    }
    // num[i] > num[i+1]
    // col[i] < col[n+i]
    FOR(i,1,n) putchar(col[i] < col[n+i] ? t0[i] : t1[i]);exit(0);
    // 缩点后编号小的拓扑序大
}

inline double now(){
    clock_t end = clock();
    return 1.0*(end-start)/CLOCKS_PER_SEC;
}

int G[MAXN];

int main(){
    std::ios::sync_with_stdio(false);
    srand(time(NULL));
    start = clock();
//    scanf("%d%d",&n,&d);
    std::cin >> n >> d;
    std::cin >> (str+1);
//    scanf("%s",str+1);
    FOR(i,1,n) str[i] -= 32;
    FOR(i,1,n) if(str[i] == 'X') ps.pb(i);
//    scanf("%d",&m);
    std::cin >> m;
    FOR(i,1,m){
//        scanf("%d",&q[i].i);scanf("%s",ch);
        std::cin >> q[i].i >> ch;
        q[i].hi = ch[0];
//        scanf("%d",&q[i].j);scanf("%s",ch);
        std::cin >> q[i].j >> ch;
        q[i].hj = ch[0];
    }
    std::vector<int> G;
    FOR(S,0,(1<<d)-1) G.pb(S);
    std::random_shuffle(all(G));
    FOR(S,0,(1<<d)-1){
        FOR(i,0,d-1) str[ps[i]] = (G[S]&(1<<i)) ? 'A' : 'B';
        Solve();
        if(now() > 1.983) break;
    }
    puts("-1");
    return 0;
}

2 comments

Leave a Comment Cancel reply

NOI2021 退役记

SDOI2020 退役记

I'm back

点双连通分量 & 圆方树学习笔记

CSP2019 游记

此内容被密码保护

概率生成函数初探

CF 521 题解

TCO2017 Round 1A PolygonRotation

「CF803F」Coprime Subsequences

「NOI2017」游戏