牛客周赛 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;
}