F-Shannon Switching Game?

来源: 牛客多校训练营10 算法: DFS, 博弈论题目链接: https://ac.nowcoder.com/acm/contest/33195/F 补完: Yes 完成时间: August 20, 2022

题解

给无向图和起始点, 轮流删边和移动, 问可否抵达.

发现想要到达终点 $t$ , 从上一个点 $t - 1$ 出发, 则在 $t - 1$ 到 $t$ 之间必须要有多重边, 若仅为单边则在删去该条边后无法抵达.

递归可得想要从点 $t - i - 1$ 出发直接到达到达点 $t - i$ , 则必须有点 $t - i - 1$ 和 $t - i$ 之间有多重边.

对于如此形成的多重边链 $t - i - k$ , 发现对于不在链上的点, 若可达一点即为可达其余带点, 想要任意点可达多重边链, 则必须有该点有多条边连向多重边链.

使用DFS从终点构造可达图, 判断起点是否在图上即可.

代码

#include<bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
using namespace std;

const int MAXN = 10005;

int n, m, s, t;
int u, v;
vector<int> e[MAXN];
int vis[MAXN];

void dfs(int u) {
    vis[u]++;
    if (vis[u]!=2)return;
    for (auto v : e[u])dfs(v);
}

void solve() {
    cin>>n>>m>>s>>t;
    rep (u, 1, n) {
        e[u].clear();
        vis[u] = 0;
    }
    rep (i, 1, m) {
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    vis[t]++;
    dfs(t);
    if(vis[s]>=2) printf("Join Player\n");
    else  printf("Cut Player\n");
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    cin>>T;// 无多组数据注释这一行
    while (T--) {
        solve();
    }
    return 0;
}

H-Wheel of Fortune

来源: 牛客多校训练营10 算法: 排列组合, 逆元题目链接: https://ac.nowcoder.com/acm/contest/33195/H 补完: Yes 完成时间: August 20, 2022

题解

设我受 $A$ 次攻击死亡, 对方受 $B$ 次攻击死亡, 则想赢得游戏需要在我受 $A$ 次攻击前, 对方先受 $B$ 次攻击, 此过程与随从无关, 若不攻击随从, 击中我们和对方的概率都为 $\frac{1}{2}$ .

则赢得游戏时, 对方已经受到 $B$ 次攻击, 设我已经受到 $k$ 次攻击, 则我们总共被攻击了 $B + k$ 次, 发生概率为:

$(\frac{1}{2})^{B + k}$

这 $B + k$ 次攻击中最后一次必是是对方受击, 则其余的 $B + k - 1$ 次攻击中有 $B - 1$ 次攻击对方, 在 $B + k - 1$ 次攻击中任取 $B - 1$ 次攻击, 为组合数, 故有概率:

$C_{B + k - 1}^{B - 1} (\frac{1}{2})^{B + k}$

只要我被攻击的次数不超过 $A$ 就可以赢得游戏, 故我有 $A$ 种赢法, 分别为我受 $0 \sim A - 1$ 次攻击, 累加得答案:

$a n s = \sum_{k = 0}^{A - 1} C_{B + k - 1}^{B - 1} (\frac{1}{2})^{B + k}$

公式整理出:

$a n s = \sum_{k = 0}^{A - 1} \frac{(B + k - 1)!}{(B + k)! k! 2^{B + k}}$

阶乘和幂提前计算, 同余除法用逆元处理.

代码

#include<bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
using namespace std;

#define ll long long

const ll P = 998244353;
const int MAXN = 2000005;

ll Add(ll a, ll b){
    return (a + b + P) % P;
}
ll Sub(ll a, ll b){
    return (a - b + P) % P;
}
ll Mul(ll a, ll b){
    return (a * b) % P;
}
ll Pow(ll a, ll n){
    ll ans = 1;
    while (n) {
        if (n & 1) ans = Mul(a, ans);
        a = Mul(a,a);
        n >>= 1;
    }
    return ans;
}
ll Div(ll a, ll b){
    b = Pow(b, P - 2);
    return Mul(a, b);
}

ll fact[MAXN];
void initFact(){
    fact[0] = 1;
    for (int i = 1; i<= MAXN; ++i) fact[i] = Mul(fact[i-1], i);
}
ll pow2[MAXN];
void initPow2(){
    pow2[0] = 1;
    for (int i = 1; i<= MAXN; ++i) pow2[i] = Mul(pow2[i-1], 2);
}

ll temp;
ll A, B;
ll ans;

void solve() {
    cin>>A;
    rep (i, 1, 7) cin>>temp;
    cin>>B;
    rep (i, 1, 7) cin>>temp;
    A = (A + 9) / 10;
    B = (B + 9) / 10;
    initFact();
    initPow2();
    rep (k, 0, A-1) {
        ans = Add(ans, Div(fact[B-1+k], Mul(Mul(fact[B-1], fact[k]), pow2[B+k])));
    }
    cout<<ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    // cin>>T;
    while (T--) {
        solve();
    }
    return 0;
}

I-Yet Another FFT Problem?

来源: 牛客多校训练营10 算法: 抽屉原理, 模拟题目链接: https://ac.nowcoder.com/acm/contest/33195/I 补完: Yes 完成时间: August 26, 2022

题目链接

题意简述

给定两个数组，a和b，问是否存在 $1 \leq i, j \leq n, 1 \leq k, l \leq m$ , 其中i和j不相等，k和l不相等，使得 $| a_{i} - a_{j} | = | b_{k} - b_{l} |$ 。

输出 $i ， j ， k ， l$ 。

$n ， m$ 在 $1 e 6$ 范围内，数组内数在 $1 e 7$ 范围内。

题目分析

本题题意非常清晰，找到两个数组内的两对数差值相等。

但很显然，朴素地去枚举差值再去判断相等，时间上肯定来不及。

尽管记录一个数组中的结果，让第二个数组查询是否有解的时候可以做到O（1）的复杂度，但在一个数组中枚举数对做差就是 $n^{2}$ 级别的复杂度了，且这个过程需要进行两次。

那么如何提升效率呢？

如果把要求中的 $| a_{i} - a_{j} | = | b_{k} - b_{l} |$ ，变成 $a_{i} + b_{l} = b_{k} + a_{j}$ 呢？

（由于下标没有谁大于谁的限制，所以不管去掉绝对值是否需要倒置，结果都没什么差别。）

这样一个移项的变换，把枚举同个数组中的数对差变为枚举两个数组中的数对和，看起来好像完全没有优化到。

然而，需要注意的是，在数据量比较大的时候，做差存储仍然是 $n^{2}$ 级别，可以预见的，数据中会有不少的重复。（意思是一个差值在多个数对中出现）

但是，做和的复杂度将会大大下降。

做和不仅不需要像做差一样，一个数组的所有数对枚举标记之后才能进入判断，而是在枚举过程中就可以和先前的结果进行比对；更重要的是，由于数据范围在 $1 e 7$ ，那么和的范围是 $2 e 7$ ，假设，跑的时候实在脸黑，每次都没找到和前面一样的结果，那最多从 $1$ 跑到 $2 e 7$ ，每个数字都跑出来一次，那再跑一次，由于数据在这个范围内，一定会出现重复，有了一组结果，遍历就可以结束了。

挺耳熟吧？是的，这是抽屉原理。

方案有了，思考一下操作起来的细节。

首先这个数据还是不小的，我们可以用桶数组去重。（代码中的 $c n t a$ 和 $c n t b$ ），由于我们只需要一组合法的数对，那么原始数据中重复的数字，只要保留一个就行。由于题目要输出下标，使用结构体记录下标以防丢失。

接着，考虑到重复数字可能构成差为0的情况，加入标记变量（代码中的 $f l a g a$ 和 $f l a g b$ ）记录这种情况，特殊处理一下，可以更快跑出这种特殊情况的解。并且处理掉相同数字带来的答案也是每个数字只保留一个的前提。（或者不跑这个的话去重的时候每个数字留最多两个也行）

最后，在对比的时候，怎么确定这个数对有没有出现过呢？

和的范围在 $2 e 7$ 内，勉强还能开出这个规模的数组。一个数组记录访问情况，另一个结构体用法类似桶，记录各个和对应的坐标即可。

完整代码

#include<iostream>
using namespace std;
struct number{
	int num;
	int id;
}a[1000005],b[1000005];
int cnta[10000005]={0},cntb[10000005]={0};
int visit[20000005]={0};
struct mark{
	int i;
	int j;
}mk[20000005];
int main(){
	int n,m;
	cin>>n>>m;
	int stpa=0,stpb=0;
	int flaga=0,flagb=0;
	int numa,numb;
	for(int i=1;i<=n;i++){
		int num;
		cin>>num;
		if(cnta[num]==1){
			//已经访问过即是第二次出现，标记后跳过。
			if(flaga!=0)continue;
			flaga=i;
			numa=num;
			continue;
		}
		cnta[num]++;
		a[stpa].num=num;
		a[stpa++].id=i;
	}
	
	for(int i=1;i<=m;i++){
		int num;
		cin>>num;
		if(cntb[num]==1){
			if(flagb!=0)continue;
			flagb=i;
			numb=num;
			continue;
		}
		cntb[num]++;
		b[stpb].num=num;
		b[stpb++].id=i;
	}
	
	if(flaga!=0&&flagb!=0){//输出差值为0的答案
		for(int i=0;i<stpa;i++)
			if(a[i].num==numa){
				cout<<a[i].id<<' '<<flaga<<' ';
			}
		for(int i=0;i<stpb;i++)
			if(b[i].num==numb){
				cout<<b[i].id<<' '<<flagb<<'\n';
			}
		return 0;
	}
	
	for(int i=0;i<stpa;i++){
		for(int j=0;j<stpb;j++){
			int ad=a[i].num+b[j].num;
			if(visit[ad]){
				cout<<mk[ad].i<<' '<<a[i].id<<' '<<mk[ad].j<<' '<<b[j].id<<'\n';
				return 0;
			}
			visit[ad]=1;
			mk[ad].i=a[i].id;//记录和为ad的数对的坐标
			mk[ad].j=b[j].id;
		}
	}
    cout<<"-1";
	return 0;
}

Shelter

2022牛客多校训练营10