A:
发现最优的方案一定是选 $ l $ 和 $ 2 * l $, 题目保证有解, 直接输出即可
- #include <bits/stdc++.h>
- #define Fast_cin iOS::sync_with_stdio(false), cin.tie();
- #define rep(i, a, b) for(register int i = a; i <= b; i++)
- #define per(i, a, b) for(register int i = a; i>= b; i--)
- #define DEBUG(x) cerr <<"DEBUG" <<x << ">>>" <<endl;
- using namespace std;
- typedef unsigned long long ull;
- typedef long long ll;
- template <typename _T>
- inline void read(_T &f) {
- f = 0; _T fu = 1; char c = getchar();
- while(c <'0' || c> '9') { if(c == '-') fu = -1; c = getchar(); }
- while(c>= '0' && c <= '9') { f = (f <<3) + (f <<1) + (c & 15); c = getchar(); }
- f *= fu;
- }
- template <typename T>
- void print(T x) {
- if(x <0) putchar('-'), x = -x;
- if(x <10) putchar(x + 48);
- else print(x / 10), putchar(x % 10 + 48);
- }
- template <typename T>
- void print(T x, char t) {
- print(x); putchar(t);
- }
- int T, l, r;
- int main() {
- read(T);
- while(T--) {
- read(l); read(r);
- print(l, ''); print(2 * l,'\n');
- }
- return 0;
- }
- B:
情况 1: 所有字母都相同, 输出 $ n * (n - 1) / 2 $ 即可
情况 2: 左边有连续 $ x $ 个字母相同, 右边有 $ y $ 个, 第一个字母和最后一个字符相同, 输出 $ (x + 1) * (y + 1) $
情况 3: 左边有连续 $ x $ 个字母相同, 右边有 $ y $ 个, 第一个字母和最后一个字符不同, 输出 $ x + y + 2 - 1 $, 最后的 $ -1 $ 是因为整个串被算了 $ 2 $ 次
- #include <bits/stdc++.h>
- #define Fast_cin iOS::sync_with_stdio(false), cin.tie();
- #define rep(i, a, b) for(register int i = a; i <= b; i++)
- #define per(i, a, b) for(register int i = a; i>= b; i--)
- #define DEBUG(x) cerr <<"DEBUG" <<x << ">>>" <<endl;
- using namespace std;
- typedef unsigned long long ull;
- typedef long long ll;
- template <typename _T>
- inline void read(_T &f) {
- f = 0; _T fu = 1; char c = getchar();
- while(c <'0' || c> '9') { if(c == '-') fu = -1; c = getchar(); }
- while(c>= '0' && c <= '9') { f = (f <<3) + (f <<1) + (c & 15); c = getchar(); }
- f *= fu;
- }
- template <typename T>
- void print(T x) {
- if(x <0) putchar('-'), x = -x;
- if(x <10) putchar(x + 48);
- else print(x / 10), putchar(x % 10 + 48);
- }
- template <typename T>
- void print(T x, char t) {
- print(x); putchar(t);
- }
- const int N = 2e5 + 5, md = 998244353;
- char c[N];
- int cnt[23333];
- int n, cut1 = -1, cut2 = -1;
- inline int mul(int x, int y) { return (ll)x * y % md; }
- int main() {
- read(n); scanf("%s", c + 1);
- for(register int i = 2; i <= n; i++) if(c[i] != c[i - 1]) { cut1 = i - 1; break; }
- for(register int i = n - 1; i>= 1; i--) if(c[i] != c[i + 1]) { cut2 = i + 1; break; }
- if(cut1 == -1) cout <<(ll)n * (n - 1) / 2 % md <<endl;
- else if(c[1] == c[n]) cout << mul(cut1 + 1, n - cut2 + 2) << endl;
- else cout << cut1 + 1 + n - cut2 + 2 - 1 << endl;
- return 0;
- }
- C:
答案本质上是把一个圆切成答案份
那么圆心角确定了, 就可以算出一个圆周角的大小, 如果切成 360 份可以拼出任意角度, 所以枚举这个角度即可
- #include <bits/stdc++.h>
- #define Fast_cin iOS::sync_with_stdio(false), cin.tie();
- #define rep(i, a, b) for(register int i = a; i <= b; i++)
- #define per(i, a, b) for(register int i = a; i>= b; i--)
- #define DEBUG(x) cerr <<"DEBUG" <<x << ">>>" <<endl;
- using namespace std;
- typedef unsigned long long ull;
- typedef long long ll;
- template <typename _T>
- inline void read(_T &f) {
- f = 0; _T fu = 1; char c = getchar();
- while(c <'0' || c> '9') { if(c == '-') fu = -1; c = getchar(); }
- while(c>= '0' && c <= '9') { f = (f <<3) + (f <<1) + (c & 15); c = getchar(); }
- f *= fu;
- }
- template <typename T>
- void print(T x) {
- if(x <0) putchar('-'), x = -x;
- if(x <10) putchar(x + 48);
- else print(x / 10), putchar(x % 10 + 48);
- }
- template <typename T>
- void print(T x, char t) {
- print(x); putchar(t);
- }
- int T;
- int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
- int main() {
- read(T); while(T--) {
- int d; read(d); int ans = -1;
- for(register int i = 3; i <= 23333; i++) {
- if(d * i % 180 == 0 && d <= 180 - 360 / (double)i) {
- ans = i; break;
- }
- }
- print(ans, '\n');
- }
- return 0;
- }
- D:
$ f[i][j] $ 表示到了第 $ i $ 个字母,$ hard $ 已经匹配到了第 $ j $ 个字母的最小代价
直接 $ dp $ 即可
- #include <bits/stdc++.h>
- #define int long long
- #define Fast_cin iOS::sync_with_stdio(false), cin.tie();
- #define rep(i, a, b) for(register int i = a; i <= b; i++)
- #define per(i, a, b) for(register int i = a; i>= b; i--)
- #define DEBUG(x) cerr <<"DEBUG" <<x << ">>>" <<endl;
- using namespace std;
- typedef unsigned long long ull;
- typedef long long ll;
- template <typename _T>
- inline void read(_T &f) {
- f = 0; _T fu = 1; char c = getchar();
- while(c <'0' || c> '9') { if(c == '-') fu = -1; c = getchar(); }
- while(c>= '0' && c <= '9') { f = (f <<3) + (f <<1) + (c & 15); c = getchar(); }
- f *= fu;
- }
- template <typename T>
- void print(T x) {
- if(x <0) putchar('-'), x = -x;
- if(x <10) putchar(x + 48);
- else print(x / 10), putchar(x % 10 + 48);
- }
- template <typename T>
- void print(T x, char t) {
- print(x); putchar(t);
- }
- const int N = 1e5 + 5;
- int f[N][5], w[N];
- char c[N];
- int n;
- int calc(char t) {
- if(t == 'h') return 1;
- if(t == 'a') return 2;
- if(t == 'r') return 3;
- if(t == 'd') return 4;
- return 0;
- }
- #undef int
- int main() {
- #define int long long
- memset(f, -1, sizeof(f));
- read(n); scanf("%s", c + 1);
- for(register int i = 1; i <= n; i++) read(w[i]);
- f[0][0] = 0;
- for(register int i = 0; i <n; i++) {
- int val = calc(c[i + 1]);
- for(register int j = 0; j <= 3; j++) {
- if(f[i][j] == -1) continue;
- if(val == j + 1) {
- if(f[i + 1][j + 1] == -1) f[i + 1][j + 1] = f[i][j];
- else f[i + 1][j + 1] = min(f[i + 1][j + 1], f[i][j]);
- if(f[i + 1][j] == -1) f[i + 1][j] = f[i][j] + w[i + 1];
- else f[i + 1][j] = min(f[i + 1][j], f[i][j] + w[i + 1]);
- } else {
- if(f[i + 1][j] == -1) f[i + 1][j] = f[i][j];
- else f[i + 1][j] = min(f[i + 1][j], f[i][j]);
- }
- }
- }
- int ans = f[n][0];
- for(register int i = 0; i <= 3; i++) if(f[n][i] != -1) ans = min(ans, f[n][i]);
- cout <<ans << endl;
- return 0;
- }
- E:
没写出来, 先咕了
F:
分别计算 $ -1 $ 和 $ -1 $ 的贡献,$ -1 $ 和数字的贡献, 数字和数字的贡献
第一个用 $ dp $ 求出, 第二个用前缀和求出, 第三个用树状数组求出
$ sb $ 的我能用前缀和的地方写了树状数组
- #include <bits/stdc++.h>
- #define Fast_cin iOS::sync_with_stdio(false), cin.tie();
- #define rep(i, a, b) for(register int i = a; i <= b; i++)
- #define per(i, a, b) for(register int i = a; i>= b; i--)
- #define DEBUG(x) cerr <<"DEBUG" <<x << ">>>" <<endl;
- using namespace std;
- typedef unsigned long long ull;
- typedef long long ll;
- template <typename _T>
- inline void read(_T &f) {
- f = 0; _T fu = 1; char c = getchar();
- while(c <'0' || c> '9') { if(c == '-') fu = -1; c = getchar(); }
- while(c>= '0' && c <= '9') { f = (f <<3) + (f <<1) + (c & 15); c = getchar(); }
- f *= fu;
- }
- template <typename T>
- void print(T x) {
- if(x <0) putchar('-'), x = -x;
- if(x <10) putchar(x + 48);
- else print(x / 10), putchar(x % 10 + 48);
- }
- template <typename T>
- void print(T x, char t) {
- print(x); putchar(t);
- }
- const int N = 2e5 + 5, md = 998244353;
- inline int mul(int x, int y) { return (ll)x * y % md; }
- inline int add(int x, int y) {
- x += y;
- if(x>= md) x -= md;
- return x;
- }
- inline int sqr(int x) { return mul(x, x); }
- inline int fpow(int x, int y) {
- int ans = 1;
- while(y) {
- if(y & 1) ans = mul(ans, x);
- y>>= 1; x = sqr(x);
- }
- return ans;
- }
- int a[N], s[N], f[N], fac[N];
- int n, inv2 = (md + 1) / 2, ans1;
- inline int lowbit(int x) { return x & -x; }
- void change(int x, int y) {
- for(register int i = x; i <= n; i += lowbit(i))
- f[i] += y;
- }
- int query(int x) {
- int ans = 0;
- for(register int i = x; i; i -= lowbit(i))
- ans += f[i];
- return ans;
- }
- int main() {
- read(n); fac[0] = 1;
- for(register int i = 1; i <= n; i++) read(a[i]), fac[i] = mul(fac[i - 1], i), s[i] = 1;
- for(register int i = n; i>= 1; i--) {
- if(a[i] == -1) continue;
- ans1 = add(ans1, query(a[i]));
- change(a[i], 1);
- }
- memset(f, 0, sizeof(f));
- for(register int i = 1; i <= n; i++) {
- if(a[i] != -1) s[a[i]] = 0;
- }
- for(register int i = 1; i <= n; i++) s[i] += s[i - 1];
- ans1 = mul(ans1, fac[s[n]]);
- for(register int i = 1; i <= s[n]; i++) f[i] = add(f[i - 1], mul(mul(fac[s[n]], fpow(i, md - 2)), mul(i - 1, mul(i, inv2))));
- ans1 = add(ans1, f[s[n]]); memset(f, 0, sizeof(f));
- for(register int i = 1; i <= n; i++) if(a[i] == -1) change(i, 1);
- for(register int i = 1; i <= n; i++) {
- if(a[i] == -1) continue;
- int val = mul(s[a[i]], query(n) - query(i));
- val = add(val, mul(s[n] - s[a[i]], query(i)));
- val = mul(val, fac[s[n] - 1]);
- ans1 = add(ans1, val);
- }
- print(mul(ans1, fpow(fac[s[n]], md - 2)), '\n');
- return 0;
- }
- G:
看到背包问题就会想到卷积, 因为背包的转移和卷积的形式相同
对于最开始的 $ k $ 个数构造生成函数, 计算 $ n / 2 $ 次幂, 每一位的平方加起来就是答案啦
- #pragma GCC target("avx")
- #pragma GCC optimize(2)
- #pragma GCC optimize(3)
- #pragma GCC optimize("unroll-loops")
- #pragma GCC optimize("Ofast")
- #include <bits/stdc++.h>
- #define Fast_cin iOS::sync_with_stdio(false), cin.tie();
- #define rep(i, a, b) for(register int i = a; i <= b; i++)
- #define per(i, a, b) for(register int i = a; i>= b; i--)
- #define DEBUG(x) cerr <<"DEBUG" <<x << ">>>" <<endl;
- using namespace std;
- typedef unsigned long long ull;
- typedef long long ll;
- template <typename _T>
- inline void read(_T &f) {
- f = 0; _T fu = 1; char c = getchar();
- while(c <'0' || c> '9') { if(c == '-') fu = -1; c = getchar(); }
- while(c>= '0' && c <= '9') { f = (f <<3) + (f <<1) + (c & 15); c = getchar(); }
- f *= fu;
- }
- template <typename T>
- void print(T x) {
- if(x <0) putchar('-'), x = -x;
- if(x <10) putchar(x + 48);
- else print(x / 10), putchar(x % 10 + 48);
- }
- template <typename T>
- void print(T x, char t) {
- print(x); putchar(t);
- }
- const int P = 998244353;
- inline int add(int x, int y) {
- x += y;
- if(x>= P) x -= P;
- return x;
- }
- inline int sub(int x, int y) {
- x -= y;
- if(x <0) x += P;
- return x;
- }
- inline int mul(int x, int y) {
- return (ll)x * y % P;
- }
- inline int fpow(int x, int y) {
- int ans = 1;
- while(y) {
- if(y & 1) ans = mul(ans, x);
- y>>= 1; x = mul(x, x);
- }
- return ans;
- }
- namespace ntt {
- int base = 1, root = -1, maxbase = -1;
- vector roots = {0, 1}, rev = {0, 1};
- void init() {
- int tmp = P - 1; maxbase = 0;
- while(!(tmp & 1)) {
- tmp>>= 1;
- maxbase++;
- }
- root = 2;
- while(1) {
- if(fpow(root, 1 <<maxbase) == 1 && fpow(root, 1 <<(maxbase - 1)) != 1) break;
- root++;
- }
- }
- void ensure_base(int nbase) {
- if(maxbase == -1) init();
- if(nbase <= base) return;
- assert(nbase <= maxbase);
- rev.resize(1 << nbase);
- for(register int i = 1; i < (1 << nbase); i++) rev[i] = (rev[i>> 1]>> 1) | ((i & 1) <<(nbase - 1));
- roots.resize(1 <<nbase);
- while(base < nbase) {
- int z = fpow(root, 1 << (maxbase - base - 1));
- for(register int i = (1 << (base - 1)); i < (1 << base); i++) {
- roots[i << 1] = roots[i];
- roots[i << 1 | 1] = mul(roots[i], z);
- }
- base++;
- }
- }
- void dft(vector &a) {
- int n = a.size(), zeros = __builtin_ctz(n);
- ensure_base(zeros);
- int shift = base - zeros;
- for(register int i = 0; i <n; i++) if(i < (rev[i]>> shift)) swap(a[i], a[rev[i]>> shift]);
- for(register int mid = 1; mid <n; mid <<= 1) {
- for(register int i = 0; i <n; i += (mid << 1)) {
- for(register int j = 0; j < mid; j++) {
- int x = a[i + j], y = mul(a[i + j + mid], roots[mid + j]);
- a[i + j] = add(x, y); a[i + j + mid] = sub(x, y);
- }
- }
- }
- }
- vector pmul(vector a, vector b, bool is_sqr = false) {
- int need = a.size() + b.size() - 1, nbase = 0;
- while((1 <<nbase) < need) nbase++;
- ensure_base(nbase); int size = 1 << nbase;
- a.resize(size); dft(a); if(!is_sqr) b.resize(size), dft(b); else b = a;
- int inv = fpow(size, P - 2);
- for(register int i = 0; i < size; i++) a[i] = mul(a[i], mul(b[i], inv));
- reverse(a.begin() + 1, a.end()); dft(a); a.resize(need); return a;
- }
- vector psqr(vector a) { return pmul(a, a, 1); }
- vector inv(vector a, int size) {
- if(size == 1) return vector { fpow(a[0], P - 2) };
- vector b = inv(a, size>> 1); a = pmul(a, psqr(b)); b.resize(size);
- for(register int i = 0; i <size; i++) b[i] = sub(add(b[i], b[i]), a[i]);
- return b;
- }
- vector pinv(vector a) {
- int nbase = 0; while((1 <<nbase) <a.size()) nbase++;
- return inv(a, 1 << nbase);
- }
- }
- using ntt::pmul;
- using ntt::psqr;
- vector wxw, ans;
- int n, k, sum;
- int main() {
- read(n); read(k); wxw.resize(10);
- for(register int i = 1; i <= k; i++) {
- int t; read(t); wxw[t] = 1;
- }
- n>>= 1; ans = wxw; n--;
- while(n) {
- if(n & 1) ans = pmul(ans, wxw);
- n>>= 1; wxw = psqr(wxw);
- }
- for(register int i = 0; i < ans.size(); i++) sum = add(sum, mul(ans[i], ans[i]));
- cout << sum << endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2901020.html