#include<bits/stdc++.h> usingnamespace std; #define ll long long constint INF = 0x3f3f3f3f; constint maxn = 1e5 + 10; ll n, m, sx, sy, k; ll a[20][20]; int dx[]{ -1,1,0,0 }; int dy[]{ 0,0,-1,1 }; ll sum, ans; voiddfs(ll x, ll y, ll res, ll dep){ if (dep == k) { ans = max(ans, res); return; } ll tmp = a[x][y]; a[x][y] = 0; for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) { dfs(nx, ny, res + a[nx][ny], dep + 1); } } a[x][y] = tmp; } intmain(){ scanf("%lld%lld%lld%lld%lld", &n, &m, &sx, &sy, &k); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { scanf("%lld", &a[i][j]); sum += a[i][j]; } } if (k >= n * m) ans = sum + n * m * (n*m - 1) / 2 + n * m*(k - n * m); else { dfs(sx, sy, a[sx][sy], 1); ans += k * (k - 1) / 2; } cout << ans << endl; return0; }
H. 游戏
题意:有 1 到 n 这些数字各一个。你用这些数字进行若干轮游戏。 对于每一轮,如果剩下的数字个数超过 1 个,那么就等概率随机选择两个剩下的数字删去。如果这两个数字互质,得一分。重复以上操作直到没数字可以删除为止。请问最后期望得多少分?
#include<bits/stdc++.h> usingnamespace std; #define ll long long typedef pair<int, int> pii; constint N = 21; int vis[1 << N]; int n, m, q, st, ed; vector<int> G[N]; int a[1 << N][N], b[N]; int pre[N][1 << N]; intmain(){ cin >> n >> m >> q; for (int i = 1; i <= n; i++) scanf("%d", &a[1][i]); for (int i = 0, u, v; i < m; i++) { scanf("%d%d", &u, &v); G[v].push_back(u); } int now = 0; for (int i = 1; i <= n; i++) now += a[1][i] << (i - 1); vis[now] = 1; now = 0; for (int t = 2;; t++, now = 0) { for (int j = 1; j <= n; j++) { for (int k : G[j]) a[t][j] ^= a[t - 1][k]; now += a[t][j] << (j - 1); } if (vis[now]) { st = vis[now]; ed = t - 1; break; } vis[now] = t; } for (int i = 1; i <= ed; i++) { for (int j = 1; j <= n; j++) pre[j][i] = pre[j][i - 1] + a[i][j]; } while (q--) { int x; ll k; scanf("%d%lld", &x, &k); if (k == 0) { printf("0\n"); continue; } if (k > pre[x][ed]) { if (pre[x][ed] == 0) printf("-1\n"); else { ll ans = ed; k -= pre[x][ed]; int dif = pre[x][ed] - pre[x][st - 1]; if (dif == 0) { printf("-1\n"); continue; } ll t = (k - 1) / dif; ans += t * (ed - st + 1); k -= t * dif; ans += lower_bound(pre[x] + st, pre[x] + ed + 1, k + pre[x][st - 1]) - (pre[x] + st - 1); printf("%lld\n", ans - 1); } } elseprintf("%d\n", lower_bound(pre[x], pre[x] + ed + 1, k) - pre[x] - 1); } return0; }