20220820牛客第十场
Wheel of Fortune
题目大意：
给定ab两个人的血量，现在有一个随机的攻击，每次攻击对象是随机的并且每次会使得每个人的血量-10，求最后a活下来的概率期望
input：
30 5 0 0 0 0 0 0
30 5 0 0 0 0 0 0
output：
499122177
解：
令a代表a能抗住多少次攻击，b同理
在对b施加b次攻击的基础上，a已经获胜，枚举a受到攻击的次数，然后用组合数去算出在所有攻击中a受到攻击的时刻，将结果累加
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 998244353;
int c[10000005];
int c2[10000005];
int qpow(int a, int b) {
int res = 1;
for (; b; b >>= 1) {
if (b & 1) {
res = res * a % mod;
}
a = a * a % mod;
}
return res;
}
signed main() {
int x[18], a, b;
for (int i = 1; i <= 16; i++) {
cin >> x[i];
}
a = x[1];
b = x[9];
a = (a + 9) / 10;
b = (b + 9) / 10;
c[b - 1] = 1;
int res = 0;
c2[0] = 1;
for (int i = 1; i <= a + b; i++) {
c2[i] = c2[i - 1] * 2 % mod;
}
for (int i = 0; i <= a - 1; i++) {
if (i != 0) {
c[i + b - 1] = (i + b - 1) % mod * c[i + b - 2] % mod * qpow(i, mod - 2) % mod;
}
int di = qpow(c2[b + i], mod - 2);
res += c[i + b - 1] * di % mod;
res %= mod;
}
cout << res << endl;
}Shannon Switching Game?
题目大意：
给定一张有n个节点的无向图，初始时token在s点，现在a和b两个人轮流操作，a可以选择token所在的点的一条边，删除这条边，接着b可以选择一条边沿着这条边向下走到另一个点并且删除这条边，问b是否能够走到t点
input：
3
2 1 1 2
1 2
2 2 1 2
1 2
1 2
3 3 1 2
1 2
2 3
1 3
output：
Cut Player
Join Player
Cut Player
解：
从t点开始建立集合，如果集合外的点能够有两条边到达集合内的任意一点，则把这个点加进来，因为对于一个点能否走到下一个点，如果这两个点之间会有两条边，那么不管减去哪一条边都是可以到达这个点的。一直建立直到无点可以进入集合，如果s点在集合中，那么就是有解的，否则wuji
#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<int> v[105];
int sets[105];
queue<int> q;
int paths[105];
int n, m, s, t;
void bfs() {
q.push(t);
sets[t] = 1;
while (q.size()) {
int cur = q.front();
q.pop();
for (int to: v[cur]) {
if (sets[to]) continue;
paths[to]++;
if (paths[to] >= 2) {
sets[to] = 1;
q.push(to);
}
}
}
}
signed main() {
int a;
cin >> a;
int x, y;
while (a--) {
cin >> n >> m >> s >> t;
for (int i = 1; i <= n; i++) {
paths[i] = 0;
sets[i] = 0;
v[i].clear();
}
for (int i = 1; i <= m; i++) {
cin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
bfs();
if (sets[s]) {
cout << "Join Player" << endl;
} else {
cout << "Cut Player" << endl;
}
}
}Yet Another FFT Problem?
题目大意：
给定两个数组a，b，要你找出i,j,k,l使得a[i]+b[k]=a[j]+b[l]，没找到输出-1
input：
4 4
2 4 8 16
3 9 27 81
output：
1 3 1 2
解：
先对a去重然后记录一对重复的值，并且创建一个新的已经对a去重的数组，还要记录好新的数组中的元素在原数组中的下标，在枚举b的时候如果找到了b中重复的对子，那么可以直接输出记录好的东西，否则就枚举去重的a数组中所有的元素，将当前的b数组中的元素与a数组中所有的元素相减再加上1e7，这样就能保证这个值会处在0和1e7之间，如果这个值已经出现过了，根据之前的记录是可以找到这四个数的。
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;
const int N = 1e6 + 5;
const int MM = 2e7 + 5;
int n, a[N], b[N], m;
int n1, A[N]; // A为去重后的a数组的下标
int nx[MM], ny[MM];
int vis[MM >> 1]; // vis[i]记录i在a/b中的下标
int ggx = 0, ggy; // 记录a中一对相同元素的下标
bool ok = 0;
int main() { // 鸽笼原理。复杂度O(V)。AC
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
if (vis[a[i]]) { // a[i]之前已经出现过
if (ggx == 0) { // 以前没发现对子
ggx = vis[a[i]]; // 上一个a[i]的下标
ggy = i; // 这个a[i]的下标
}
} else { // a[i]第一次出现
A[++n1] = i; // 记录去重后的a数组的下标
}
vis[a[i]] = i; // 记录a[i]出现的下标
}
for (int i = 1; i <= m; i++) {
scanf("%d", &b[i]); // 读入b[i]
}
memset(vis, 0, sizeof vis); // 清空vis,接下来vis[i]用来记录i在b中的下标
for (int i = 1; i <= m; i++) { // 遍历b[i]
if (vis[b[i]]) { // b[i]出现过
if (ggx) { // a中存在"对子"
printf("%d %d %d %d\n", ggx, ggy, vis[b[i]], i); // 输出两对相同元素
ok = 1; // 找到了
break;
}
continue;
}
// vis[b[i]]==0,b[i]第一次出现
vis[b[i]] = i;
for (int j = 1; j <= n1; j++) { // 枚举a中的元素（已通过A[i]去重）
int u = 1e7; // 偏移量
int o = b[i] - a[A[j]] + u; // 计算nx的下标
if (nx[o]) { // 找到一组"碰撞"
printf("%d %d %d %d\n", nx[o], A[j], ny[o], i);
ok = 1;
break;
}
nx[o] = A[j];
ny[o] = i;
}
if (ok) break; // 已经找到，提前退出
}
if (!ok) puts("-1"); // 没找到，输出-1
}
这段代码来自fn哥哥
#ACM#
查看1道真题和解析