题解

A 截木棍（博弈论）

题意：

有个初始木棍长度 ，现在 PT 和 XC 分别以先后手的顺序执行操作，每次操作需要从数组 中选取一个数 ，使得 ，然后去除元素 ，当 时，游戏结束，当前即将操作的那方输掉比赛。

题解：

首先有数据范围可知，：

  • 当 时：
    • 可以发现所有的元素一定要全部取完，假设取不完，最坏情况就是最短的 没被取，即 ，但是这样就和上面的条件 矛盾了，所以此情况所有木棍必备取完，所以只需要判断 的奇偶性，奇数先手赢，偶数后手赢。
  • 当 时：
    • 可以发现，最后只有剩一个元素或者一个元素都不剩的情况，如果最后剩一个元素就结束的话，剩的那个元素只能是最小值 ，所以我们需要观察的是最小值的个数 ，首先如果 为奇数，那么先手肯定是要尽可能的取完所有元素，而想要取完所有数，就需要将最小值都取完，所以先手一定是一直取最小的数，如果 ，那么先手就会赢，否则后手赢；如果 为偶数，那么先手肯定是想要留一个元素就游戏结束，所以先手就会尽可能的取最大值，如果 ，那么先手就会赢，否则后手赢。

Code：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 100005;
i64 sum, cnt, mn = 100000000000LL;
i64 a[N + 1];
void solve() {
    i64 n, l, op; cin >> n >> l >> op;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i];
        mn = min(mn, a[i]);
    }
    for (int i = 1; i <= n; i++) {
        cnt += a[i] == mn;
    }
    sort(a + 1, a + n + 1);
    if (sum < l + mn) {
        if (n % 2 == 1) {
            cout << (op == 1 ? "PT" : "XC") << '\n';
        } else {
            cout << (op == 1 ? "XC" : "PT") << '\n';
        }
    } else {
        if (n % 2 == 0) cnt = n - cnt;
        if (cnt <= n / 2) {
            cout << (op == 1 ? "PT" : "XC") << '\n';
        } else {
            cout << (op == 1 ? "XC" : "PT") << '\n';
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
    // std::cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

B 神枪手（模拟）

题意：

fsj 手里有一把 发子弹的狙击枪，需要在比赛这 个时刻内，依次进行射击，如果当前时刻有靶子且有子弹，才可进行射击，击中范围大于等于靶子距离，则可击中靶子，最后计算比赛结束后，fsj能击中多少靶子。

题解：

模拟即可，模拟过程，注意特判无靶子情况以及有靶子但无子弹情况，然后根据距离，对答案进行加 / 减，另外如果没击中靶子也要对子弹数减减。

Code：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 100005;
int D[N + 1], d[N + 1];
int ans;
void solve() {
    int n, T; cin >> n >> T;
    for (int i = 1; i <= T; i++) cin >> D[i];
    for (int i = 1; i <= T; i++) cin >> d[i];
    for (int i = 1; i <= T; i++) {
        if (n == 0) break;
        if (D[i] == 0) continue;
        ans += D[i] <= d[i];
        n--;
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
    // std::cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

C 区间（线段树、模拟）

题解：

对于 。，可以发现 这个其实是个曼哈顿距离，所以相当于求的是区间 内任意两个下标 对应的曼哈顿距离的最大值，我们令 ，则由曼哈顿距离的性质可知，两点之间的曼哈顿距离可以分为四部分：

  • 当 时，那么就可以拆成 ，即 。

  • 当 时，那么就可以拆成 ，即 或者 。

  • 当 时，那么就可以拆成 ，即 或者 。

  • 当 时，那么就可以拆成 ，即 。

然后我们可以发现相当于是把每个点看成四种情况 ，这四种情况分别进行处理，然后排序，利用最大值减去最小值，即可得到四种情况的曼哈顿值，然后取四种情况的曼哈顿值的最大值，即是所要求的 。

推广成求区间内任意两点之间曼哈顿距离的最大值，用这个方法即可得到，我们可以用线段树来实现，分别维护一下这段区间内四种情况 的最大值以及最小值，然后就能得到这段区间四种情况的曼哈顿值，最后便得出答案。

对于每次查询：

  • 操作 是一个区间修改的操作，我们上面说过一个点会分为四部分 ，现在点由 变为 ，那么原来的四部分就会变为 ，我们能发现最大值只会由情况二和情况三得到，所以只需要对情况一和情况四置 即可，情况二和情况三只需要乘二即可。

  • 操作 只需要单点修改四种情况的值即可。

  • 操作 根据前面的方法即可求出。

  • 操作 根本上就是求一段区间内两两相邻的两个点曼哈顿距离的最大值和最小值，这个需要维护下每次区间合并时相邻两个点的曼哈顿距离，然后维护下最大值和最小值即可。

  • 操作 我们可以发现固定一段区间的开头，得到一个最短的区间满足其曼哈顿距离的最大值大于 ，是符合单调性的，那么我们只需要通过二分来处理下即可，也可直接线段树上二分做到单 。

证明下操作四的单调性：假设左端点固定为 ，现在给你两个右端点 ，其中 ，如果区间 的曼哈顿距离最大值大于 ，那么区间 一定会比区间 点来得多，点越多只使这段区间的曼哈顿距离越大，所以区间 一定是比区间 更加优的。

Code：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 5e5 + 5;
const i64 MOF = 0x3f3f3f3f3f3f3f3f;
i64 x, y;
i64 a[N + 1][2], b[4][N + 1];
struct Segtree{
	int siz;
	i64 lzy;
	i64 l[4], r[4];
	i64 mx[4], mn[4];
	i64 co_mx1, co_mn1;
	i64 co_mx2, co_mn2;
	Segtree(int siz = 0, i64 lzy = 0, i64 co_mx1 = 0, i64 co_mn1 = MOF, i64 co_mx2 = 0, i64 co_mn2 = MOF)
	: siz(siz), lzy(lzy), co_mx1(co_mx1), co_mn1(co_mn1), co_mx2(co_mx2), co_mn2(co_mn2) {
		for (int i = 0; i < 4; i++) {
			l[i] = r[i] = 0;
			mx[i] = -MOF;
			mn[i] = MOF;
		}
	}
	#define ls (root << 1)
	#define rs (root << 1 | 1)
	#define rt_ tree[root]
	#define ls_ tree[ls]
	#define rs_ tree[rs]
};

Segtree tree[N << 2];
inline Segtree hb(Segtree &_i, Segtree &_j) {
	Segtree k = Segtree();
	k.siz = _i.siz + _j.siz;
	if (k.siz == 0) return k;
	if (_i.siz == 0) return _j;
	if (_j.siz == 0) return _i;
	i64 mxx1 = 0, mxx2 = 0;
	for (int i = 0; i < 4; i++) {
		k.l[i] = _i.l[i];
		k.r[i] = _j.r[i];
		k.mx[i] = max(_i.mx[i], _j.mx[i]);
		k.mn[i] = min(_i.mn[i], _j.mn[i]);
		mxx1 = max(mxx1, abs(_i.r[i] - _j.l[i]));
		if (i == 1 || i == 2) mxx2 = max(mxx2, abs(_i.r[i] - _j.l[i]));
	}
	k.co_mx1 = max({_i.co_mx1, _j.co_mx1, mxx1});
	k.co_mn1 = min({_i.co_mn1, _j.co_mn1, mxx1});
	k.co_mx2 = max({_i.co_mx2, _j.co_mx2, mxx2});
	k.co_mn2 = min({_i.co_mn2, _j.co_mn2, mxx2});
	return k;
}

inline void push_up(int root) {
	tree[root] = hb(tree[ls], tree[rs]);
}

inline void build(int root, int l, int r) {
	if (l == r) {
		tree[root].siz = 1;
		for (int i = 0; i < 4; i++) {
			rt_.l[i] = b[i][l];
			rt_.r[i] = b[i][l];
			rt_.mx[i] = b[i][l];
			rt_.mn[i] = b[i][l];
		}
		return;
	}
	int mid = l + r >> 1;
	build(ls, l, mid);
	build(rs, mid + 1, r);
	push_up(root);
}

inline void push_mark(int root, int l, int r) {
	if (tree[root].lzy) {
		i64 sum = powl(2, tree[root].lzy);
		ls_.lzy += rt_.lzy;
		rs_.lzy += rt_.lzy;
		rt_.lzy = 0;
		for (int i = 0; i < 4; i++) {
			if (i == 0 || i == 3) {
				ls_.l[i] = rs_.l[i] = 0;
				ls_.r[i] = rs_.r[i] = 0;
				ls_.mx[i] = rs_.mx[i] = 0;
				ls_.mn[i] = rs_.mn[i] = 0;
			} else {
				ls_.l[i] *= sum;
				rs_.l[i] *= sum;
				ls_.r[i] *= sum;
				rs_.r[i] *= sum;
				ls_.mx[i] *= sum;
				rs_.mx[i] *= sum;
				ls_.mn[i] *= sum;
				rs_.mn[i] *= sum;
			}
		}
		if (ls_.siz != 1) {
			ls_.co_mx2 *= sum;
			ls_.co_mn2 *= sum;
			ls_.co_mx1 = ls_.co_mx2;
			ls_.co_mn1 = ls_.co_mn2;
		}
		if (rs_.siz != 1) {
			rs_.co_mx2 *= sum;
			rs_.co_mn2 *= sum;
			rs_.co_mx1 = rs_.co_mx2;
			rs_.co_mn1 = rs_.co_mn2;
			
		}
	}
}

inline void update(int root, int l, int r, int ql, int qr, int op) {
	if (r < ql || l > qr) return;
	if (l >= ql && r <= qr) {
		if (op == 1) {
			b[0][l] = x + y;
			b[1][l] = x - y;
			b[2][l] = y - x;
			b[3][l] = -(x + y);
			for (int i = 0; i < 4; i++) {
				rt_.l[i] = b[i][l];
				rt_.r[i] = b[i][l];
				rt_.mx[i] = b[i][l];
				rt_.mn[i] = b[i][l];
			}
		} else {
			rt_.lzy++;
			for (int i = 0; i < 4; i++) {
				if (i == 0 || i == 3) {
					rt_.l[i] = rt_.r[i] = 0;
					rt_.mx[i] = rt_.mn[i] = 0;
				} else {
					rt_.l[i] <<= 1;
					rt_.r[i] <<= 1;
					rt_.mx[i] <<= 1;
					rt_.mn[i] <<= 1;
				}
			}
			if (l != r) {
				rt_.co_mx2 <<= 1;
				rt_.co_mn2 <<= 1;
				rt_.co_mx1 = rt_.co_mx2;
				rt_.co_mn1 = rt_.co_mn2;
			}
		}
		return;
	}
	push_mark(root, l, r);
	int mid = l + r >> 1;
	update(ls, l, mid, ql, qr, op);
	update(rs, mid + 1, r, ql, qr, op);
	push_up(root);
}

inline Segtree query(int root, int l, int r, int &ql, int &qr) {
	if (r < ql || l > qr) return Segtree();
	if (l >= ql && r <= qr) return rt_;
	push_mark(root, l, r);
	int mid = l + r >> 1;
	auto LS = query(ls, l, mid, ql, qr), RS = query(rs, mid + 1, r, ql, qr);
	return hb(LS, RS);
}

void solve() {
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> x >> y;
		a[i][0] = x, a[i][1] = y;
		b[0][i] = x + y;
		b[1][i] = x - y;
		b[2][i] = y - x;
		b[3][i] = -(x + y);
	}
	build(1, 1, n);
	for (int i = 1; i <= m; i++) {
		int op; cin >> op;
		if (op == 0) {
			int l, r; cin >> l >> r;
			update(1, 1, n, l, r, op);
		} else if (op == 1) {
			int pos; cin >> pos >> x >> y;
			update(1, 1, n, pos, pos, op);
		} else if (op == 2) {
			int l, r; cin >> l >> r;
			auto ans = query(1, 1, n, l, r);
			i64 mx = 0;
			for (int i = 0; i < 4; i++) mx = max(mx, ans.mx[i] - ans.mn[i]);
			cout << mx << '\n';
		} else if (op == 3) {
			int l, r; cin >> l >> r;
			auto ans = query(1, 1, n, l, r);
			i64 sum1 = ans.co_mx1, sum2 = ans.co_mn1;
			cout << sum1 - sum2 << '\n';
		} else if (op == 4) {
			int l;
			i64 k; cin >> l >> k;
			int L = l + 1, R = n;
			while (L < R) {
				int mid = L + R >> 1;
				i64 ans = -MOF;
				auto d = query(1, 1, n, l, mid);
				for (int i = 0; i < 4; i++) ans = max(ans, d.mx[i] - d.mn[i]);
				if (ans <= k) L = mid + 1;
				else R = mid;
			}
			i64 ans = -MOF;
			if (L > n) {
				cout << "-1\n";
				continue;
			}
			auto d = query(1, 1, n, l, L);
			for (int i = 0; i < 4; i++) ans = max(ans, d.mx[i] - d.mn[i]);
			if (ans > k) cout << L - l + 1 << '\n';
			else cout << "-1\n";
		}
	}
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
    // std::cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

D HYNU（签到）

题意：

给你四个字符，是否能组成字符串 HYNU。

题解：

判断下字符 H、Y、N、U 是否都出现即可。

Code：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int H, Y, N, U;
void solve() {
    for (int i = 0; i < 4; i++) {
        char c; cin >> c;
        if (c == 'H') H = 1;
        else if (c == 'Y') Y = 1;
        else if (c == 'N') N = 1;
        else if (c == 'U') U = 1;
    }
    int sum = H + Y + N + U;
    if (sum == 4) cout << "HYNU\n";
    else cout << "Bad\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
    // std::cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

E 异或与交换（思维）

题意：

给定两个字符串 ，现在你有两种操作方式，操作一是异或操作：可以选择字符串 和 其中一个的某个位置 ，使得 或者 ；操作二是交换操作：可以选择某个位置 ，然后 ，现在问你将两个字符串都变为全 字符串所需要的最少操作次数。

题解：

首先对于操作一，可以发现，只要该字符串中某个位置出现了数字 ，便可以将该字符串变为全 字符串，所需要的次数为该字符串中数字 的出现次数；而对于操作二，什么情况会用到呢，当然是两个字符串中一个出现了数字 ，而另外一个全是数字 ，这种情况就需要进行交换操作，使得后者拥有数字 ，最后这样就能使得两个字符串变为全 字符串了。

对于两者都有数字 的情况，答案为两个字符串中数字 的数目；对于其中一者有数字 ，而另外一个字符串为全 字符串，答案为数字 的数目加 ；对于两者都是全 字符串，输出 -1。

Code：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
    int n; cin >> n;
    string a, b; cin >> a >> b;
    int ca = 0, cb = 0;
    for (auto c : a) ca += c == '0';
    for (auto c : b) cb += c == '0';
    if (ca == n && cb == n) cout << "-1\n";
    else cout << ca + cb + (ca == n) + (cb == n) << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
    // std::cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

F 葡萄提子（签到）

题意：

小 P 有 个葡萄，小 T 有 个提子，如果 ，则小 P 可以花费 个葡萄将其转换为 个提子，此时 ，现在想知道小 P 是否能通过一些操作使得 。

题解：

可以发现，每次操作， 都会减少 ，而 都会增加 ，故 与 的差值会减少 。

所以，若初始时 ，则直接输出 NO；否则如果 ，则输出 YES，否 NO。

Code：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
    i64 x, y, k; cin >> x >> y >> k;
    if (x < y || (x - y) % (k + 1) != 0) cout << "NO\n";
    else cout << "YES\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
    std::cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

G 递归函数（组合数学）

题意：

给定一个整数 ，求解 。

题解：

根据公式，可以发现 一定是一些质数之和，假设 ，由于每次只能删除最大质因子或最小质因子，所以相当于每次要么去最左边的数要么去最右边的数，直到最后只剩一个质因子 为止，令 ，那么每个位置 对应的 出现的次数为 ，最后答案 ，所以只需要将所有质数存入数组排序，依次加起来即可求出答案。

Code：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
typedef pair<i64, i64> PI;
const int N = 1000005;
const i64 mod = 998244353;
i64 qp(i64 a, i64 b) {
    i64 res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod; b >>= 1;
    }
    return res;
}

i64 add(i64 a, i64 b) {
    i64 res = (a + b) % mod;
    return res;
}

i64 fac[N + 1], inv[N + 1];
void init() {
    fac[0] = inv[0] = 1;
    for (int i = 1; i <= N; i++) fac[i] = fac[i - 1] * i % mod;
    inv[N] = qp(fac[N], mod - 2);
    for (int i = N - 1; i >= 1; i--) inv[i] = inv[i + 1] * (i + 1) % mod;
}

i64 C(i64 n, i64 m) {
    if (n < m) return 0LL;
    return fac[n] * inv[n - m] % mod * inv[m] % mod;
}

i64 ans, sum, res;
void solve() {
    int m; cin >> m;
    vector<i64> c;
    for (int i = 0; i < m; i++) {
        i64 p, a; cin >> p >> a;
        sum += a;
        while (a--) c.push_back(p);
    }
    sum--;
    sort(c.begin(), c.end());
    for (auto p : c) {
        ans = add(ans, p * C(sum, res) % mod);
        res++;
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
    init();
    // std::cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

H 数论（质因数分解+计数dp）

题意：

求解 的值。

题解：

我们对 进行化简：

可以发现，分母的 可以直接快速幂逆元 的时间复杂度求出，现在对分子进行处理，可以发现 ：

现在已知 ，除了中间 的乘积，其他都可以 求出，又发现这里的 都是对 进行 ，那么我们就可以直接枚举因子处理，但是枚举因子的话会有重复的出现，所以我们可以考虑枚举质因子的次幂值，即 ，那么对于 ， 以内的一个数的质因子最多有 个（比如：），而一个质因子的次幂 ，所以时间复杂度为 ，当然也可以直接 。

Code：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 1000005;
const i64 mod = 998244353;
i64 qp(i64 a, i64 b) {
    i64 res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod; b >>= 1;
    }
    return res;
}

i64 add(i64 a, i64 b) {
    i64 res = (a + b) % mod;
    return res;
}

struct pre{
    int N;
    vector<i64> preim;
    vector<i64> a;
    pre(int N_) : a(N_ + 1) {
        N = N_;
        for (i64 i = 2; i <= N; i++) {
            if (!a[i]) {
                a[i] = i;
                preim.push_back(i);
            }
            for (auto p : preim) {
                if (i * p > N) break;
                a[i * p] = p;
                if (a[i] == p) {
                    break;
                }
            }
        }
    }
    
    inline bool ispreim(i64 x) {
        return (a[x] == x && x != 0);
    }
};
pre t(1000005);
i64 cnt[1000005][21], pr[1000005][21];
void solve() {
	for (int i = 1; i <= 1000000; i++) {
		for (int j = 0; j <= 20; j++) {
			cnt[i][j] = pr[i][j] = 1;
		}
	}
    int n; cin >> n;
	i64 g = 0, g2 = 1, ans = 0;
	for (int i = 1; i <= n; i++) {
		i64 x; cin >> x;
		g = std::gcd(g, x);
		if (i != 1) {
			while (x > 1) {
				i64 p = t.a[x];
				i64 ct = 0;
				i64 res = 1;
				while (x % p == 0) {
					pr[p][ct] = pr[p][ct] * res % mod;
					x /= p;
					res = res * p % mod;
					ct++;
					g2 = g2 * cnt[p][ct] % mod;
				}
				g2 = g2 * pr[p][ct] % mod;
				cnt[p][ct] = cnt[p][ct] * res % mod;
			}
			ans = add(ans, g2 * qp(qp(g, i - 1), mod - 2) % mod);
		} else {
			while (x > 1) {
				i64 p = t.a[x];
				i64 ct = 0;
				i64 res = 1;
				while (x % p == 0) {
					pr[p][ct] = pr[p][ct] * res % mod;
					x /= p;
					res = res * p % mod;
					ct++;
				}
				cnt[p][ct] = cnt[p][ct] * res % mod;
			}
		}
	}
	cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
    // std::cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

I 环树（思维）

题意：

给你一颗树，现在需要添加一条非树边，使得树中恰好有一个环，且环上的点恰好连接一个环外的点，环外的点也恰好连接一个环上的点。

题解：

若 或 ，如果添加一条非树边后，树应该长什么样呢，如下：

alt alt

可以发现环上的点度数都为 ，而环外的点度数都为 ，由于环上点数必须大于等于 ，所以只有 为偶数且 的情况下才可能有解，现在把那条非树边去除，只可能去除环上的某条边，这样就变成有 个节点度数为 ，有 个节点度数为 ，有 个节点度数为 。

首先我们预处理出所有节点的度数，现在我们需要判断出度数为 的环外节点应该和哪位环内节点连接，当然就是他唯一连接的那个节点，但是我们需要标记下，因为可能会出现两个环外节点都连接一个环内节点的情况，这种情况是不符合要求，因为环内节点必须恰好连接一个环外节点，不能多也不能少，如果都符合，直接输出度数为 的两个节点即可。

以下是两个环外节点都连接一个环内节点的情况：

alt

Code：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 200005;
int deg[N + 1], vis[N + 1];
vector<int> g[N + 1], f[N + 1];
void solve() {
    int n; cin >> n;
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        f[u].push_back(v);
        f[v].push_back(u);
        deg[u]++; deg[v]++;
    }
    if ((n & 1) || n < 6) {
        cout << "-1\n";
        return;
    }
    for (int i = 1; i <= n; i++) g[deg[i]].push_back(i);
    if (g[1].size() == n / 2 && g[2].size() == 2 && g[3].size() == n / 2 - 2) {
        for (int v : g[1]) {
            if (vis[f[v][0]]) {
                cout << "-1\n";
                return;
            }
            vis[f[v][0]] = 1;
        }
        cout << min(g[2][0], g[2][1]) << ' ' << max(g[2][0], g[2][1]) << '\n';
    } else {
        cout << "-1\n";
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
    // std::cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

J 序列最小值（容斥+组合数学推导+第二类斯特林）

题意：

给定两个整数 ，现在有 种数组 ，满足 ，需要求出所有可能的数组 的 之和。

题解：

对于 ：

  • 我们先假设 ，此时区间数目只有 个，我们现在需要求的是每个区间不同情况对应的最小值，而每个区间的最小值只有 种情况，我们暴力枚举每个区间，再枚举每个区间对应的最小值，但是如何求解这个值呢？当然如果这个区间内的最小值是 ，那是不是说明区间内至少一个数为 ，其他数都得大于等于 ，但是如何求出至少一个数为 的总情况数呢，我们假设区间长度为 ，那么区间内至少一个数为 的情况数为 ，表示恰好选 个 和其他数选大于 的数，这样求复杂度为 ，肯定会超时，现在我们对 进行化简，根据前面的意思，我们求至少一个数大于 的总情况数是不是就等于求区间内所有数都选大于等于 的数减去区间内所有数都选大于 的数，用容斥思想便可 求出式子的值，即 ，所以最终式子为 ，此时时间复杂度为 。

  • 现在如果 ，之前的时间复杂度绝对超时，但是根据式子 ，可以发现，如果区间长度一样，所产生的贡献值是一样的，所以式子就变为 ，此时时间复杂度为 。

  • 现在如果 ，很显然 太大了，无法直接进行暴力枚举，所以我们需要将 进行优化，回看式子 ：

    现在我们只需要求解出任何数次幂之和即可，如何快速求解呢？这里我们可以用到第二类斯特林数来推导，对于单独的 的实际意义是不是表示给你 个不同的箱子，并且给你 个不同的小球，问你有多少种将小球全部放入箱子的方式；而对于第二类斯特林数 表示，给你 个不同的小球，将其放入 个相同的非空箱子的方案数，只要乘以 就可以将相同的非空箱子转化为不同非空箱子了，所以最终式子为：

    现在可以发现对于 和 我们都可以 预处理出来，然后公式部分便也可以 求出来了，时间复杂度 。

主要是自然数次幂之和的推导过程关键，虽然他有很多方式推导，但是感觉用第二类斯特林推导最方便。

Code：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 6005;
const i64 mod = 998244353;
i64 S[N + 1][N + 1], infac[N + 1], inv[N + 1], fac[N + 1];
i64 add(i64 x, i64 y) {
    i64 res = (x + y) % mod;
    return res;
}

i64 sub(i64 x, i64 y) {
    i64 res = (x - y + mod) % mod;
    return res;
}

i64 qp(i64 x, i64 y, i64 p) {
    i64 res = 1;
    while (y) {
        if (y & 1) res = res * x % p;
        x = x * x % p; y >>= 1;
    }
    return res;
}

void init() {
	fac[0] = inv[0] = infac[0] = S[0][0] = 1;
	for (int i = 1; i <= N; i++) fac[i] = fac[i - 1] * i % mod;
	for (int i = 1; i <= N; i++) infac[i] = qp(fac[i], mod - 2, mod);
	for (int i = 1; i <= N; i++) inv[i] = qp(i, mod - 2, mod);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= i; j++) {
			S[i][j] = add(S[i - 1][j - 1], S[i - 1][j] * j % mod);
		}
	}
}

i64 C[N + 1], Pm[N + 1];
void solve() {
	i64 n, m; cin >> n >> m;
	Pm[0] = C[0] = 1;
	for (int i = 1; i <= n; i++) Pm[i] = Pm[i - 1] * m % mod;
	for (int i = 1; i <= n + 1; i++) {
		if (i > m + 1) continue;
		i64 t = 1;
		for (int j = 0; j < i; j++) {
			t = t * (m - j + 1) % mod;
		}
		C[i] = t * infac[i] % mod;
	}
	i64 ans = 0;
	for (int L = 1; L <= n; L++) {
		i64 res = 0;
		for (int j = 1; j <= L; j++) {
			res = add(res, S[L][j] * fac[j] % mod * C[j + 1] % mod);
		}
		ans = add(ans, res * Pm[n - L] % mod * (n - L + 1) % mod);
	}
	cout << ans << '\n';
}

int main() {
	ios::sync_with_stdio(false);	
	cin.tie(0), cout.tie(0);
	int _ = 1;
	init();
	// init2(N);
//	std::cin >> _;
	while (_--) solve();
	return 0;
}

K 奇偶 （思维、贪心）

题意：

给定一个数组 和一个数组 ，现在希望你找到一些数对 ，满足 与 奇偶性不同且 与 奇偶性也不同，求不相交的数对最多有多少对。

题解：

我们不横着看，可以试着换成竖着看，就变成 ，对应的奇偶性种类有 四个种类，其中 只能和 匹配， 只能和 匹配，这样就有两种匹配方式，我们只需要两个取最小值相加就是最终答案。

Code：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 100005;
int a[N + 1], b[N + 1], cnt[1 << 2];
void solve() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] %= 2;
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
        b[i] %= 2;
    }
    for (int i = 1; i <= n; i++) {
        int sum = 0;
        if (a[i]) sum += 1;
        if (b[i]) sum += 2;
        cnt[sum]++;
    }
    int ans = min(cnt[1], cnt[2]) + min(cnt[0], cnt[3]);
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
    // std::cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

L 字典序（思维）

题意：

给定一个字符串 ，找到最小的 ，使得 ，其中 指的是区间内所有字符升序排序后的字符串。

题解：

这题不能直接二分，比如：字符串 "" 就不能直接二分答案，因为不满足单调性，现在我们对比 和 有什么区别呢，可以发现他们排序后只和 和 的大小有关系，前者小于等于后者，就满足长度要求，否则 不满足要求，所以我们只需要 暴力判断每个对应的长度是否符合条件即可。

Code：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
    int n; string s;
    cin >> n >> s;
    s = "$" + s;
    for (int i = 1; i <= n; i++) {
        bool vis = true;
        for (int j = i + 1; j <= n; j++) {
            if (s[j] < s[j - i]) {
                vis = false;
                break;
            }
        }
        if (vis) {
            cout << i << '\n';
            return;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
    // std::cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

M "k" 排列（构造）

题意：

构造一个长度为 的排列 ，满足所有的 ，都有 。

题解：

可以发现 时， 一定为 ，所以接下来 这个位置就只能选 ，而对于 也一样的情况，最后判断下是否每个位置都有对应的数值，如果没有就说明没有任何情况满足要求。

Code：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 500005;
int p[N + 1];
void solve() {
    int n, k; cin >> n >> k;
    for (int i = 1; i <= n - k; i++) {
        if (p[i]) continue;
        p[i] = i + k;
        p[i + k] = i;
    }
    for (int i = 1; i <= n; i++) {
        if (p[i] == 0) {
            cout << "-1\n";
            return;
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << p[i] << ' ';
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
    // std::cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 18:05
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-03 17:16
点赞 评论 收藏
分享
06-09 15:54
合肥工业大学 嵌入式硬件工程师
点赞 评论 收藏
分享
07-03 10:57
门头沟学院 Java
诶？骗人的吧？我不是笨蛋来着吗？
挑战最晚暑期实习offerTimelin：6.23&nbsp;一面&nbsp;1h简历深挖➕二分查找数组peak➕闲聊6.24&nbsp;通知一面过了，约二面6.25&nbsp;二面&nbsp;1h简历深挖➕手绘Transformer结构lc编辑距离➕情景题（读表格找最大行）6.26&nbsp;下午不同hr打电话通知二面过了，约hr面6.27&nbsp;hr面&nbsp;30mins简历深挖，之前实习做了什么，难度在哪里比赛含金量和工作（压力面，会一直追问）告知2-3个工作日给结果6.30&nbsp;周一火速追问hr进展，整个下午没有回复，以为已经挂了，结果是hr离职了7.1&nbsp;千辛万苦找到了另一个hr的联系方式主动联系，得知hr面的面试官请假了7.2&nbsp;得知面试都通过了，进行offe...
点赞 评论 收藏
分享
评论
4
收藏
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 三一集团提前批进度交流 #
21634次浏览 138人参与
# 百度工作体验 #
227890次浏览 1999人参与
# 现代汽车前瞻技术研发急速编程挑战赛 #
35988次浏览 268人参与
# 非技术岗投递进展 #
143911次浏览 1264人参与
# 机械人与华为的爱恨情仇 #
118072次浏览 951人参与
# 毕业旅行去哪玩儿 #
7191次浏览 119人参与
# 没有合适的工作，你会先找个干着，还是考公考研 #
115523次浏览 1133人参与
# 发工资后，你做的第一件事是什么 #
68909次浏览 232人参与
# 材料进Fab厂真的劝退吗？ #
42676次浏览 184人参与
# 工作中，努力重要还是选择重要？ #
138195次浏览 1689人参与
# 平台or薪资 硬件uu更看重哪个 #
128156次浏览 595人参与
# 如果你有一天可以担任公司的CEO，你会做哪三件事？ #
29332次浏览 471人参与
# 上班到公司第一件事做什么？ #
59244次浏览 508人参与
# 秋招什么时候开投比较合适？ #
30526次浏览 363人参与
# 银行笔面经互助 #
134579次浏览 1170人参与
# 为什么那么多公司毁约 #
177592次浏览 1331人参与
# 正在春招的你，也参与了去年秋招吗？ #
308247次浏览 2522人参与
# 工作中哪个瞬间让你想离职 #
26629次浏览 179人参与
# 不考虑转正，实习多久合适 #
32946次浏览 159人参与
# 2023毕业生求职有问必答 #
178571次浏览 1622人参与
# 大家每天通勤多久？ #
46250次浏览 348人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务