2022牛客蔚来杯第十场 FHIE

2022牛客蔚来杯第十场

F.Shannon Switching Game?

• 题意

  • 给定一个游戏图，有一枚棋子，给定起点s和终点t
  • 有cut, join两名玩家，cut可以切断一条棋子所在点连接的边，join可以把棋子按某条边移动一次
  • cut先手，若能到达终点join胜利，否则cut胜利，问给定图是谁胜利

• 题解

  • 博弈论+图论，对于某条能够到达终点的路径上，所有点都有两条以上的路径到达终点，那么必胜。因为每个点只要有两条能到终点，就不可能被cut切断路径
  • 只需bfs找必胜的路径即可，从终点向前依次找必胜点(由终点出发的有两条边能到的点)，如果能到起点那么就找到了必胜路径；不能到起点，意味着起点不是必胜点，所以必败
  • 从终点开始bfs是为了方便记录必胜点，只需有必胜点依次扩展而来的必然比必胜态，而终点是一个必胜点，所以从终点开始

• 代码

#include 
#include 

using namespace std;
const int N=105,M=10010;

int n,m,s,t;
int h[N],e[2*M],ne[2*M],idx;//图的存储结构
int st[N];
int q[M];//队列数组

void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

bool bfs()
{
    memset(st,0,sizeof st);//初始化
    int hh=0,tt=-1;//初始化队列
    q[++tt]=t;//起点入队

    while(hh<=tt){//宽搜
        int x=q[hh++];//取出队头

        for(int i=h[x];i!=-1;i=ne[i]){//扩展队列
            int j=e[i];st[j]++;
            if(st[j]>=2){
                q[++tt]=j;
                if(j==s) return true;
            }
        }
    }

    return false;
}

void solve()
{
    cin>>n>>m>>s>>t;
    memset(h,-1,sizeof h); idx=0;//初始化邻接表
    while(m--){
        int a,b;
        cin>>a>>b;
        add(a,b);add(b,a);
    }

    cout<<(bfs() ? "Join Player":"Cut Player")<<'\n';
}

int main() {
    int T;
    cin>>T;
    while(T--) solve();
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

H.Wheel of Fortune

• 题意

  • 给定两个阵营，每个阵营有一个boss+7个小兵的血量，boss死了那个阵营就输了
  • 游戏中随机选择一个boss或者小兵攻击，扣除10点血
  • 问己方阵营赢的概率为多少

• 题解

  • 只有boss死才能决定游戏的输赢，小兵的死活对游戏输赢的概率没有影响，所以只考虑boss

  • 假设己方boss被攻击A次死亡，敌方B次死亡；那么要赢的话可能进行的轮次为B+i(0<=i

  • 计算：

    进行B轮结束:C_{B-1}^{0}*(1/2^B),B轮攻敌方,己方不受攻击;最后一次攻击必是敌方,所以最后一次不纳入组合选择基数中
    B+1轮结束:C_{B+1-1}^{1}*(1/2^(B+1)),B轮地方,己方一次;最后一次必是敌方,不放入基数中
    ...
    B+A-1轮结束:C_{B+A-1-1}^{A-1}*(1/2^(B+A-1))
    1
    2
    3
    4

    以上累加即可，同时需要优化，可以预处理组合数以及2的幂

• 代码

#include 

using namespace std;
#define int long long
const int N=1e6+10,mod=998244353;

int A,B,x,res=0;
int fac[2*N],infac[N],pow2[2*N];//阶乘，阶乘逆元(用来求组合数)；2的幂

int qp(int a,int b) {//快速幂
    int res=1;
    while(b) {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}

void init() {//初始化阶乘，阶乘逆元，2的幂
    fac[0]=fac[1]=1;
    for(int i=2;i<2*N;i++) fac[i]=fac[i-1]*i%mod;
    infac[N]=qp(fac[N],mod-2);
    for(int i=N-1;i;i--) infac[i]=infac[i+1]*(i+1)%mod;
    
    pow2[0]=1;
    for(int i=1;i<2*N;i++) pow2[i]=2*pow2[i-1]%mod;
}

int C(int a,int b) {//求组合数
    if(a<b) return 0;
    if(b==0) return 1;
    if(a==b) return 1;
    return fac[a]*infac[b]%mod*infac[a-b]%mod;
}

signed main() {
    init();
    cin>>A;
    for(int i=0;i<7;i++) cin>>x;
    cin>>B;
    for(int i=0;i<7;i++) cin>>x;
    A=(A+9)/10;B=(B+9)/10;//承受攻击次数
    
    int res=0;
    for(int i=0;i<A;i++) {//枚举a承受的攻击轮数，总轮数就是i+B
        int ans=C(i+B-1,i)*qp(pow2[i+B],mod-2)%mod;//此种概率
        res=(res+ans)%mod;//答案加和
    }
    cout<<res<<'\n';
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

I.Yet Another FFT Problem?

• 题意

  • 给一个长度为n的数组a，一个长度为m的数组b
  • 问能否找到|ai-aj|=|bk-bl|,(i!=j,k!=l)，输出4个下标

• 题解

  • 如果直接暴力求解，就O(n^2)处理出两个数组中存在的差，同时用map存某个差的下标，再O(n)遍历一个数组的差map找在另一个数组差中是否存在。时间复杂度爆了
  • 考虑优化，题目式子等价于找ai+bk=aj+bl，所以可以用上述map的思路预处理和。为什么这样做呢？因为数组元素的范围1e7，ai+bk<=2e7。假设a,b各自数组中没有重复元素，那么用map记录和时，最多纪录2e7+1次就能找到一个解，以上是运用鸽巢原理的伪暴力。注意要特判有重复元素的情况

• 代码

#include 
#include 
#include 

using namespace std;
const int N=1e6+5,M=1e7+5;
typedef pair<int,int> PII;

int n,m,a[N],b[N],posa[M],posb[M];//数组长度，数组，数组值的下标
int id[M],ai,aj,bi,bj;//判重数组，一组解4个下标
bool vis[2*M];//某个和是否存在过
PII mp[2*M];//某个和对应的a，b数组的两个下标

int main() {
    cin.tie(0)->sync_with_stdio(false);
    
  //特判有重复元素的情况
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i],posa[a[i]]=i;
    for(int i=1;i<=m;i++) cin>>b[i],posb[b[i]]=i;
    for(int i=1;i<=n;i++) {
        if(id[a[i]]) { ai=id[a[i]]; aj=i; break;}
        id[a[i]]=i;
    }
    memset(id,0,sizeof id);
    for(int i=1;i<=m;i++) {
        if(id[b[i]]) { bi=id[b[i]]; bj=i; break;}
        id[b[i]]=i;
    }
    if(ai && aj && bi && bj) {cout<<ai<<' '<<aj<<' '<<bi<<' '<<bj<<'\n'; return 0;}
    
  //无重复元素解的情况
    sort(a+1,a+1+n); n=unique(a+1,a+1+n)-(a+1);//去重
    sort(b+1,b+1+m); m=unique(b+1,b+1+m)-(b+1);
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            int num=a[i]+b[j];
            if(vis[num]) {
                ai=mp[num].first,bi=mp[num].second;
                aj=posa[a[i]],bj=posb[b[j]];
                cout<<ai<<' '<<aj<<' '<<bi<<' '<<bj<<'\n';
                return 0;
            }
            else {
                vis[num]=1;
                mp[num]={posa[a[i]],posb[b[i]]};
            }
        }
    }
    puts("-1");//无解
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

E.Reviewer Assignment

• 题意

  • n个审稿人，m篇论文，给出每个审稿人能审论文的编号集合；每个审稿人只分配一篇论文
  • 令f(i)表示至少被i个审稿人审过的论文数量，(f(1),f(2),…,f(n))的字典序最大，输出分配方式

• 题解

  • 二分图匹配，可以用最大流或者匈牙利算法解决。不会最大流
  • f(1)其是就是典型的二分图匹配，有所不同的是还需要计算f(2)…f(n)，而对于每一个f(i)其实也都是二分图匹配的过程，相当于给男的(论文)找多轮老婆(审稿人)。那么对于i=1,2,…,n，在f(1),f(2),…,f(i-1)不改变的情况下，使得f(i)最大即可。相当于一个女的只有一个老公，男生(论文)都找多个老婆(审稿人)，使得有多个老婆的男生数量最大，并且输出女生的配偶

• 代码

#include 
#include 

using namespace std;
const int N=405;

int n,m;
string s;
int h[N],e[N*N],ne[N*N],idx;//建图，注意数组大小
int st[N],match[N];//匈牙利
int cnt[N];//记录每个论文被几个审稿人审

void add(int a,int b) {//加边
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

bool find(int x) {//能否为x稿子找到一个审稿人。匈牙利算法
    for(int i=h[x];~i;i=ne[i]) {
        int j=e[i];
        if(!st[j]) {
            st[j]=x;
            if(!match[j] || find(match[j])) {
                match[j]=x;
                return true;
            }
        }
    }
    
    return false;
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
    
    cin>>n>>m;
    bool flag=1;//如果有审稿人一篇都不能审，那么不存在匹配
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++) {//审稿人
        cin>>s;
        bool f=0;
        for(int j=0;j<m;j++)//论文
            if(s[j]=='1') {//可审，加边
                add(j+1,i);//只加男生指向女生的边，即论文->审稿人
                f=1;
            }
        flag&=f;
    }
    if(!flag) { puts("-1"); return 0; }//没有匹配
    
    int minn=0;//存在男的选到选minn个老婆
    flag=1;//是否要进行下一轮的二分匹配
    while(flag) {
        flag=0;
        for(int i=1;i<=m;i++) {//对于每个论文(男)找审稿人(女)
            if(cnt[i]!=minn) continue;//如果这个男的都没有在上一轮找到老婆，那么这一轮也不能
            memset(st,0,sizeof st);//二分匹配对于每个男的选择的时候，需要置空标记的st
            if(find(i)) cnt[i]++,flag=1;//这个男的能找到老婆，老婆数量++；同时标记此轮二分匹配存在匹配成功，那么可以进行下一轮二分匹配
        }
        minn++;//每进行一轮都把标准++
    }
    for(int i=1;i<=n;i++) cout<<match[i]<<' ';//输出每个女生的配偶
    puts("");
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65