A.Road To Zero
题意:
给定,并且给定,有两种操作:
- 花费,可以让其中一个
- 花费,可以让都
询问最少的花费使得均变为0
题解:
比较和的大小即可
#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 = 1e9 + 7; void solve() { ll a, b, x, y; scanf("%lld%lld%lld%lld", &x, &y, &a, &b); ll n1 = (x + y) * a, n2 = min(x, y) * b + abs(x - y) * a; printf("%lld\n", n1 < n2 ? n1 : n2); } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }
B.Binary Period
题意:
给定一个串,可以在任意位置添加任意多的,要求最终生成的串长度不超过原来的两倍,并且这个串是个循环串且循环节最短
题解:
如果为全或者为全,那么就是串本身,否则只要补成即可
#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 = 1e9 + 7; void solve() { string s, a; cin >> s; for (auto p : s) a += "01"; if (s.find('0') == string::npos || s.find('1') == string::npos) cout << s << endl; else cout << a << endl; } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }
C.Yet Another Counting Problem
题意:
给定和组询问,每组询问给定和,询问之间有多少个满足
题解:
可以发现会是一个循环,并且可算,所以只要算出一个循环内的所有结果,最终结果就是
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 4e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; int sum[maxn]; ll a, b, q; ll calc(ll x) { return 1ll * x / (a * b) * sum[a * b] + 1ll * sum[x % (a * b)]; } void solve() { memset(sum, 0, sizeof(sum)); scanf("%lld%lld%lld", &a, &b, &q); for (int i = 1; i <= a * b; i++) sum[i] += sum[i - 1] + (i % a % b != i % b % a); while (q--) { ll l, r; scanf("%lld%lld", &l, &r); printf("%lld ", calc(r) - calc(l - 1)); } puts(""); } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }
D.Multiple Testcases
题意:
给定个数和,其中。现在要将划分成一些组,要求每个组内的数不超过。求划分出最少的组数和每组的构成方案。
题解:
对于第一问,先将升序排序,对于的个数为那么。对于第二问只要将放入第一组,放入第二组...依次放入即可
#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 = 1e9 + 7; int a[maxn], c[maxn]; int main() { int n, k; scanf("%d%d", &n, &k); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for (int i = 1; i <= k; i++) scanf("%d", &c[i]); sort(a + 1, a + n + 1); int ans = 0; for (int i = 1; i <= n; i++) ans = max(ans, (n - i + 1 + c[a[i]] - 1) / c[a[i]]); printf("%d\n", ans); for (int i = 1; i <= ans; i++) { int cnt = 0; for (int j = i; j <= n; j += ans) cnt++; printf("%d ", cnt); for (int j = i; j <= n; j += ans) printf("%d ", a[j]); puts(""); } return 0; }
E.Placing Rooks(组合数学)
题意:
在一个的棋盘上放置个车,满足以下两个条件:
- 棋盘上的每一个空格子都能被至少一只车走到
- 恰好存在对车可以相互攻击
询问所有车的摆放方案数
题解:
要满足第一个条件,则每一行/每一列都有一个车,两者至少满足其一。对于这两种情况是等价的,下面只考虑每一行都有车,最终结果乘即可
在满足第二个条件的情况下,可以发现至少有列是空着的,那么问题就相当于把个不同的车放入个不同的列,发现就是一个第二类斯特林数。那么可以用容斥原理,,那么最终答案就是。
要注意特判一下当时,答案就为,当时,答案为
了解第二类斯特林数戳我~
#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; ll fac[maxn]; ll qpow(ll a, ll b) { int res = 1; while (b) { if (b & 1) res = res * a % mod; a = a * a % mod; b >>= 1; } return res; } void init() { fac[0] = 1; for (int i = 1; i < maxn; i++) fac[i] = fac[i - 1] * i % mod; } ll c(int x, int y) { return fac[x] * qpow(fac[y] * fac[x - y] % mod, mod - 2) % mod; } int main() { init(); int n, k; scanf("%d%d", &n, &k); if (k == 0) { printf("%lld\n", fac[n]); return 0; } if (k >= n) { puts("0"); return 0; } ll ans = 0; for (int i = 0; i <= n - k; i++) ans += 1ll * qpow(mod - 1, i) * c(n - k, i) % mod * qpow(n - k - i, n) % mod; ans %= mod; printf("%lld\n", 2ll * ans % mod * c(n, n - k) % mod); return 0; }