牛客周赛 Round 60(思维、逆元、组合数、概率DP)

牛客周赛 Round 60(思维、逆元、组合数、概率DP)

F题，概率DP不会，学了再补

A. 困难数学题

• x ^ x = 0
• 0 ^ x = x
• ^ 表示二进制异或

#include<bits/stdc++.h>

using namespace std;

int main(){
	
	cout << 0 << endl;
	
	return 0;
}

B. 构造序列

注意是ABAB，还是ABABA

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main(){
	
    ll a, b;
    cin >> a >> b;
    
    cout << min(a, b) * 2 + (a != b) << endl;
    
	return 0;
}

C. 连点成线

统计每行每列出现的最大值和最小值，做差取max即可，

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 5;

vector<int> row[maxn], column[maxn];

int main(){
	
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		int x, y;
		cin >> x >> y;
		row[x].push_back(y);
		column[y].push_back(x);
	}
	
	int res = 0;
	for(int i = 1; i <= n; i++){
		if(row[i].size() > 1){
			sort(row[i].begin(), row[i].end());
			res = max(res, *(row[i].end() - 1) - row[i][0]);	// row[i].end() 是指针，表示row[i]最后一个元素的后一位的地址
		}
		if(column[i].size() > 1){
			sort(column[i].begin(), column[i].end());
			res = max(res, *(column[i].end() - 1) - column[i][0]);
		}
	}
	cout << res << endl;
	
	return 0;
}

D. 我们N个真是太厉害了(思维)

如果当前序列 A，任选元素加和，可以构成出排列 1、2、3、…、mx。

向序列A中加入元素 x 后，如果 x <= mx +1，这时可以构成的排列变为 1、2、3、…、mx、mx+1、…、mx + x。

根据题意，对a排序，依次遍历，不断维护mx，并判断 a[i] 是否小于等于 mx+1。如出现 a[i] > mx+1，则 mx+1 为第一个不能被加和得到的数。

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 5;

int a[maxn];

int main(){
	
	int ncase;
    cin >> ncase;
    
    while(ncase--){
        int n;
        cin >> n;
        for(int i = 1; i <= n; i++) cin >> a[i];
        
        sort(a+1, a+1+n);
        
        int res = -1;
        if(a[1] != 1) res = 1;
        else{
            int mx = 1;
            for(int i = 2; i <= n; i++){
                if(a[i] <= mx + 1) mx += a[i];
                else{
                    res = mx + 1;
                    break;
                }
                if(mx >= n) break; // 一点点优化
            }
        }
        if(res == -1) cout << "Cool!" << endl;
        else cout << res << endl;
    }
	
	return 0;
}

E. 折返跑(小费马定理求逆元、组合数)

对于一次查询 n 和 m，可以理解为在 n-2 个点中选 m - 1 个点出来，选择的方案数即为结果。（n-2：去除掉开始和结尾）

综上：$res=C_{n-2}^{m-1}$

用小费马定理求逆元计算组合数即可。
PS：第一眼以为是DP，稍微写一下状态转移方程，就可以发现是组合数。

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const ll mod = 1e9 + 7;
const int maxn = 1e6 + 5;

ll qpow(ll a, ll b){
    ll res = 1;
    while(b){
        if(b & 1) res = res * a % mod;
        a *= a;
        a %= mod;
        b >>= 1;
    }
    return res;
}

ll f[maxn], p[maxn];
ll C(ll a, ll b){
    return f[a] * p[b] % mod * p[a-b] % mod;
}

int main(){
	
    f[0] = 1;
    for(int i = 1; i < maxn; i++) f[i] = f[i-1] * i % mod;
    for(int i = 0; i < maxn; i++) p[i] = qpow(f[i], mod-2); // 费马小定理求逆元
    
	int ncase;
	cin >> ncase;
	while(ncase--){
		ll n, m;
        cin >> n >> m;
		n -= 2; m -= 1;
        if(n <= 0 || m <= 0) cout << 1 << endl;
        else cout << C(n, m) << endl;
	}
	
	return 0;
}

F. 口吃（概率DP）

先挖坑。

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const ll mod = 1e9 + 7;
const int maxn = 1e5 + 5;
ll a[maxn], b[maxn];

ll qpow(ll a, ll b){
	ll res = 1;
	while(b){
		if(b & 1) res *= a;
		res %= mod;
		a *= a;
		a %= mod;
		b >>= 1;
	}
	return res;
}

int main(){
	
	int n;
	cin >> n;
	for(int i = 1; i < n; i++) cin >> a[i];
	for(int i = 1; i < n; i++) cin >> b[i];
	
	ll num = 1 + b[1] * qpow(a[1], mod-2) % mod;
	ll res = num;
	for(int i = 2; i < n; i++){
		num = (a[i] + b[i]) * (a[i] + b[i]) % mod + num * b[i] % mod * b[i] % mod;
		num = num * qpow(a[i], mod-2) % mod * qpow(a[i], mod-2) % mod;
		res = (res + num) % mod;
	}
	
	cout << (res + 1) % mod << endl;
	
	return 0;
}