A.膜法记录
题解:
观察到的数据范围很小,那么只要暴力枚举行的所有策略,最后判断是否存在一种策略使得行数小于等于,同时所需的列数小于等于即可 表示用这种行策略能够处理掉的列数,就表示用这种行策略下仍需要使用列的个数
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 1e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 998244353; char s[25][maxn]; ll cnt[1100000]; int main() { int t; for (scanf("%d", &t); t >= 1; t--) { ll n, m, a, b; scanf("%lld%lld%lld%lld", &n, &m, &a, &b); for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1); for (int i = 0; i < (1 << n); i++) cnt[i] = 0; for (int j = 1; j <= m; j++) { ll p = 0; for (int i = 1; i <= n; i++) if (s[i][j] == '*') p |= (1 << i - 1); cnt[p]++; } for (int i = 1; i <= n; i++) for (int j = 0; j < (1 << n); j++) if ((j & (1 << i - 1)) == 0) cnt[j | (1 << i - 1)] += cnt[j]; bool flag = false; for (int i = 0; i < (1 << n); i++) if (__builtin_popcount(i) <= a && m - cnt[i] <= b) { flag = true; break; } puts(flag ? "yes" : "no"); } return 0; }
B.阶乘
题意:
给定一个正整数
求一个最小的正整数,使得是的倍数
题解:
如果是的倍数,那么就需要分解质因数在中同样存在并且中的幂数大于等于中的幂数
将质因数分解,然后二分寻找最小的
其中计算中质因子的数量:
ll cal(ll n, ll x) { ll num = 0; while (n) { num += n / x; n = n / x; } return num; }
完整代码:
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 2e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 998244353; vector<pair<ll, ll>> V; bool check(int x) { for (auto i : V) { ll cnt = 0, t = x; while (t) { cnt += t / i.first; t /= i.first; } if (cnt < i.second) return false; } return true; } void solve() { V.clear(); ll p, l, r; scanf("%lld", &p); l = 1, r = p; for (ll i = 2; i * i <= p; i++) { if (p % i == 0) { ll x = 0; while (p % i == 0) { p /= i; x++; } V.push_back(make_pair(i, x)); } } if (p > 1) V.push_back(make_pair(p, 1ll)); while (l < r) { ll mid = l + r >> 1; if (check(mid)) r = mid; else l = mid + 1; } printf("%lld\n", l); } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }
C.完全图
题意:
给定一个包含个顶点的完全图但是删掉最多条,请问删去边之后的图最多能有几个连通块?
题意:
这题标答写得挺好,就直接贴过来了
反过来想,一开始是个孤立节点,我要添加恰好条边,让他连通块尽量多。
第一条肯定会让连通块数减少1,第二条也只能让连通块减少1,现在形成了一条包含三个点的链,接下来一条把这链的两个端点连起来,这一步没有让连通块的个数变少,再接下来一条边只能让连通块个数减少1......重复这
样的过程:除非必须要把孤立点连进来,否则我就在大连通块内部连点。
形成个连通块能用完的最大边数依次为:
二分可以解决
观察到,可能超过long long的范围,所以用python会方便很多
for t in range(int(input())): n, m = map(int, input().split()) add = max(0, n * (n - 1) // 2 - m) l, r = 0, n - 1 while l < r: mid = l + r >> 1 if (mid * (mid + 1) >> 1) >= add: r = mid else: l = mid + 1 print(n - l)
D.病毒传染(组合数学+概率)
题解:
这道题求的一部分我现在还没想明白,就只能贴下官方题解顺便加点我想懂的地方了。
注意这是个条件概率
先求全局条件下“有t个人参加party之前就被感染,且最后共k人感染”的概率,令
其中为用容斥原理算出个人在party上被感染的概率
对每个,假设用上式算出的概率是
那么对于一个,所求的条件概率就是
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int maxn = 1e6 + 5; const int INF = 0x3f3f3f3f; const ll mod = 1e9 + 7; ll inv[maxn], fact[maxn], _fact[maxn]; ll p[1005]; ll ksm(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans = ans * a % mod; a = a * a % mod; b >>= 1; } return ans; } void init() { inv[0] = inv[1] = 1; for (int i = 2; i < maxn; i++) inv[i] = inv[mod % i] * (mod - mod / i) % mod; fact[0] = _fact[0] = 1; for (int i = 1; i < maxn; i++) { fact[i] = fact[i - 1] * i % mod; _fact[i] = _fact[i - 1] * inv[i] % mod; } } ll C(ll n, ll m) { if (m < 0 || m > n || n < 0) return 0; return fact[n] * _fact[m] % mod * _fact[n - m] % mod; } int main() { init(); ll n, m, k, P, tot = 0; scanf("%lld%lld%lld%lld", &n, &m, &k, &P); for (int t = 1; t <= k; t++) { auto &ans = p[t]; ans = C(n, t) * ksm(P, t) % mod * ksm(100 - P, n - t) % mod * C(n - t, k - t) % mod; ll tmp = 0; for (int i = 0; i <= k - t; i++) { if (i & 1) tmp = (tmp - C(k - t, i) * C(n * (n - 1) / 2 - t * (n - k + i), m)) % mod; else tmp = (tmp + C(k - t, i) * C(n * (n - 1) / 2 - t * (n - k + i), m)) % mod; } ans = ans * tmp % mod; tot = (tot + ans) % mod; } for (int i = 1; i <= k; i++) { ll ans = p[i] * ksm(tot, mod - 2) % mod; printf("%lld\n", (ans + mod) % mod); } return 0; }
E.A+B问题(水题)
题意:
给定一个,求出所有的方案数总和,其中,,均在32位有符号整数能存储的范围内。
题解:
因为,,均在32位有符号整数能存储的范围内,所以在给定范围内任意给定一个都能找到一个在范围内的,使得,所以总方案数就是
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 2e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 998244353; int main() { puts("4294967296"); return 0; }
F.美丽的序列I
题解:
这道题官方题解写得很好,直接贴过来了
用前缀积就可以做到
但是要注意的是并不是全部都满足,只有当的时候才满足,所以计算的时候要判断一下的情况,这种情况下到这一部分是取不到的,但是前面计算的时候加上了这一部分,所以要减去
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int maxn = 1e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; ll l[maxn], r[maxn], sum[maxn], len[maxn]; ll ksm(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans = ans * a % mod; a = a * a % mod; b >>= 1; } return ans; } ll getsum(ll n) { n %= mod; return (n * (n + 1) >> 1) % mod; } int main() { int n; scanf("%d", &n); ll tot = 1; for (int i = 1; i <= n; i++) { scanf("%lld%lld", &l[i], &r[i]); len[i] = (r[i] - l[i] + 1); tot = tot * len[i] % mod; } ll ans = tot; for (int i = 2; i <= n; i++) { ll a = l[i], b = min(r[i], r[i - 1]); if (a > b) continue; ll t = ((b - a + 1) * r[i - 1]) % mod; if (l[i - 1] > l[i]) { ll c = min(l[i - 1] - 1, r[i]); t = (t - (l[i - 1] - 1) * (c - a + 1)) % mod; a = c + 1; } t = (t - (getsum(b) - getsum(a - 1))) % mod; t = t * tot % mod; t = (t * ksm(len[i - 1], mod - 2) % mod * ksm(len[i], mod - 2)) % mod; ans = (ans + t) % mod; } printf("%lld\n", (ans + mod) % mod); return 0; }
G.树上求和(贪心)
题解:
很经典的题型了,算出每条边包含在多少条路径中,然后按出现次数降序排序,出现次数越多的给的权值越少即可
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 1e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 998244353; int n, head[maxn], cnt, tot; ll sz[maxn], num[maxn]; struct Edge { int to, nxt; } e[maxn << 2]; void init() { memset(head, -1, sizeof(head)); cnt = tot = 0; } void addedge(int u, int v) { e[cnt].to = v; e[cnt].nxt = head[u]; head[u] = cnt++; } void dfs1(int u, int fa) { sz[u] = 1; for (int i = head[u]; ~i; i = e[i].nxt) { int v = e[i].to; if (v == fa) continue; dfs1(v, u); sz[u] += sz[v]; } } void dfs2(int u, int fa) { for (int i = head[u]; ~i; i = e[i].nxt) { int v = e[i].to; if (v == fa) continue; num[tot++] = sz[v] * (n - sz[v]); dfs2(v, u); } } int main() { init(); scanf("%d", &n); for (int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); addedge(u, v); addedge(v, u); } dfs1(1, 0); dfs2(1, 0); sort(num, num + tot); ll ans = 0, idx = n - 1; for (int i = 0; i < tot; i++) { ans += idx * num[i]; idx--; } printf("%lld\n", ans); return 0; }
H.奇怪的背包问题增加了(贪心)
题意:
有一个容量为的背包,和件物品,第件物品的体积为,你需要从中选出若干件,使得选出的物品的体积恰好等于背包容量。这些物品有一个奇怪的特性,那就是,其中,即所有都是的幂。
题解:
如果,那肯定可以凑出,只需要把所有的数字从大到小排序,依次加入数字,肯定在某个时刻和就等于。
因为低位可以合并成高位,而高位不能分解成低位,所以从大到小排序,把大的先放了不够的就可以用小的数来凑
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int maxn = 1e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 998244353; bool ans[maxn]; pll p[maxn]; int main() { int t; for (scanf("%d", &t); t >= 1; t--) { int n; scanf("%d", &n); ll sum = 0; for (int i = 1; i <= n; i++) { int x; scanf("%d", &x); p[i].first = 1 << x; p[i].second = i; sum += p[i].first; } if (sum < (1 << 30)) { puts("impossible"); continue; } sort(p + 1, p + n + 1, greater<pll>()); for (int i = 1; i <= n; i++) ans[i] = 0; ll res = 1 << 30; for (int i = 1; i <= n; i++) if (p[i].first <= res) { res -= p[i].first; ans[p[i].second] = 1; } for (int i = 1; i <= n; i++) printf("%d", ans[i]); puts(""); } return 0; }
I.寻找字串(水题)
题意:
给定字符串,请你找出字典序最大的子串。
题解:
字典序最大的子串肯定是个后缀,直接在所有的后缀中取就可以
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 2e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 998244353; int main() { string s, ans; cin >> s; for (int i = 0; i < s.length(); i++) ans = max(ans, s.substr(i)); cout << ans << endl; return 0; }
J.最大的差(水题)
题意:
给定个数字,请你从中选出两个数字,使得这两个数字的差尽量大,输出这个最大的差。
题解:
找出最大值和最小值,最大值减最小值即可
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 2e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 998244353; int main() { int n; scanf("%d", &n); int mx = -INF, mn = INF; for (int i = 0, x; i < n; i++) { scanf("%d", &x); mx = max(mx, x); mn = min(mn, x); } printf("%d\n", mx - mn); return 0; }