Easy：A、B、G、M
Mid：D、C、H、I
Hard：K、E、J、F
AK：L
A 水沝淼㵘
难度：*800、模拟、枚举
签到题，只需要找到输入的矩阵中的最大的三个值加起来看有没有超过 即可，排序就行。
时间复杂度
#include <bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned int;
using u128 = unsigned __int128;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
std::vector<int> g(n * n);
for (int i = 0; i < n * n; i++) {
std::cin >> g[i];
}
std::sort(g.begin(), g.end(), std::greater());
if ((g[0] + g[1] + g[2]) >= n / 2) {
std::cout << "YES\n";
} else {
std::cout << "NO\n";
}
return 0;
}
B Excel大神
难度：*800、模拟、字符串、进制
众所周知，字母表一共有 个英文字母，我们可以把它当做
进制来计算。
比如 就是
，一直到
是
。
好，问题来了，题目规定的是从 开始。
那简单，我们每次计算的时候把 自减，这样就对上了，不信的话可以自己试试。
所以最主要的做法就是将输入的 从
进制转换成
进制。
时间复杂度
#include <bits/stdc++.h>
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using u128 = unsigned __int128;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
i64 n;
std::cin >> n;
std::string ans = "";
while (n) {
n--;
int t = n % 26;
n /= 26;
ans += (char)('a' + t);
}
std::reverse(ans.begin(), ans.end());
std::cout << ans << "\n";
return 0;
}
G 质数排列
难度：*800、构造
题目要求我们索引为 的数对应的值
同为质数或者同为不是质数。
那直接让 就满足所有条件了。
所以直接输出 。
时间复杂度
#include <bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned int;
using u128 = unsigned __int128;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
for (int i = 1; i <= n; i++) {
std::cout << i << " ";
}
return 0;
}
M 火炎焱燚
难度：*800、模拟
根据题意模拟即可，注意死亡后移动不会拾取碎片，所以需要一个变量来记录当前是生还是死。
具体细节看代码：
时间复杂度
#include <bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned int;
using u128 = unsigned __int128;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m;
std::cin >> n >> m;
std::vector g(n + 1, std::vector<int>(n + 1));
for (int i = 0; i < m; i++) {
int x, y, z;
std::cin >> x >> y >> z;
g[x][y] = z;
}
bool isDie = false;
int res = 0;
int lx = 0, ly = 0;
for (int i = 0; i < n; i++) {
char op;
std::cin >> op;
if (op == 'M') {
int x, y;
std::cin >> x >> y;
lx = x, ly = y;
if (!isDie) {
res += g[x][y];
g[x][y] = 0;
}
} else if (op == 'D') {
g[lx][ly] += res / 2;
isDie = true;
res = 0;
} else {
isDie = false;
lx = 0, ly = 0;
}
}
int sum = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
sum += g[i][j];
}
}
std::cout << res << " " << sum << "\n";
return 0;
}
D 正方形遍历
难度：*800、打表、构造、欧拉路径
数据范围很小，可以直接手动画出来然后打表 输出。
因为要形成欧拉回路的必要条件就是每个节点的度数要为偶数，因此所有的 都符合这个条件，所以全是
。
大概就这样画就可以找到规律了。
当然也可以连边跑欧拉回路，也是个模版题，具体的可以看代码
时间复杂度
是边数
#include <bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned int;
using u128 = unsigned __int128;
constexpr int N = 100010;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
std::vector<std::vector<std::pair<int, int>>> e(N);
std::vector<bool> vis(N);
n++;
int idx = 0;
std::vector<bool> no(N);
no[n] = true;
for (int i = 1; i <= n - 1; i++) {
no[n + (n - 1) * i] = true;
}
auto add = [&](int u, int v) -> void {
e[u].push_back({v, idx});
e[v].push_back({u, idx++});
};
// 连横边
for (int i = 0; i < n; i++) {
for (int j = 1; j < n; j++) {
add(n * i + j, n * i + j + 1);
}
}
// 连竖边
for (int i = 1; i <= n; i++) {
for (int j = 0; j < n - 1; j++) {
add(n * j + i, n * (j + 1) + i);
}
}
// 连斜边
for (int i = 0; i < n - 1; i++) {
for (int j = 1; j <= n; j++) {
int now = n * i + j;
int nxt = now + n - 1;
if (!no[now] && now != n * i + 1) {
add(now, nxt);
}
}
}
std::vector<int> ans;
// 欧拉回路
auto dfs = [&](auto &&self, int u) -> void {
for (auto [v, id]: e[u]) {
if (vis[id]) {
continue;
}
vis[id] = true;
self(self, v);
}
ans.push_back(u);
};
dfs(dfs, 1);
std::cout << "Yes\n";
for (auto t : ans) {
std::cout << t << " ";
}
return 0;
}
C 圣杯
难度：*1000、概率、数论、快速幂
披着概率外套的快速幂求逆元模版题。
题目样例解释已经告诉了解法了，我们只需要对答案的分数进行取模。
分数取模其实很简单，就是分子乘分母的逆元就行了。
时间复杂度 注意计算次方的时候不能一个一个的乘，会超时，直接使用快速幂计算次方。
#include <bits/stdc++.h>
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using u128 = unsigned __int128;
constexpr int mod = 1000000007;
i64 power(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 inv(i64 x) {
return power(x, mod - 2);
}
void solve() {
int n;
i64 p, q;
std::cin >> n >> p >> q;
i64 res = 2 * p % mod * q % mod * inv(10000) % mod;
std::cout << power(res, n) << "\n";
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}
H 一闪一闪亮晶晶
难度：*1200、模拟、思维、位运算
结论不难，就是相同的为一组，直接用 统计就行，接下来给出证明。
我们首先记 。
已知 ，最大公约数的性质，
又因为 ，与运算的性质，
故左边 ，又因为右边
左边要等于右边，左边取最大的可能
得到了这个等式：
要使等式成立，则必须要求 ，所以同一组的星星必须亮度完全相同才行。
时间复杂度
#include <bits/stdc++.h>
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using u128 = unsigned __int128;
void solve() {
int n;
std::cin >> n;
std::set<int> st;
for (int i = 0; i < n; i++) {
int x;
std::cin >> x;
st.insert(x);
}
std::cout << st.size() << "\n";
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}
I 快乐风男
难度：*1200、组合数学
根据题目的描述，要求的是至少发生一起争吵的方案。
至少发生一起争吵方案的对立事件就是完全不发送争吵。
那么我们知道，完全不发生争吵，就是所有人的出装都一样才行，那么这样的方案数只可能有 种。
所以我们可以用所有的方案减去完全不发生争吵的方案。
所有的方案就是每个人都有 种出装方式，即
。
故答案就是 ，需要对
取模，所以
用快速幂计算即可。
注意 取模后可能比
小，这样就成负数了，所以我们要加个
再取模。
时间复杂度
#include <bits/stdc++.h>
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using u128 = unsigned __int128;
constexpr int mod = 1000000007;
i64 power(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 inv(i64 x) {
return power(x, mod - 2);
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
i64 m, n;
std::cin >> m >> n;
std::cout << (power(m, n) + mod - m) % mod << "\n";
return 0;
}
K 你是天命人吗
难度：*1400、贪心、模拟、动态规划
由题意可知，切手技的伤害比普通攻击高，所以我们要尽可能的使用切手技。
方法一：我们可以把全部使用普通攻击造成的伤害算出来，最后在和我们贪心使用切手技的伤害取最大的输出。
贪心策略：在 第一次攻击的时候闪避存一阶棍势，之后如果
攻击了就使用切手技造成
的伤害，如果是闪避则使用普通攻击，最后如果
是闪避，那么我们需要把存储的棍势清空，打出切手技。
我们需要将贪心的和全部使用普通攻击的取最大的输出，因为可能的情况是 只攻击一次。
方法二：也可以使用动态规划把所有情况递推出来取最大的情况， 表示操作完前
个指令后还剩
个棍式所造成的最大伤害，最后取
给出贪心的代码，时间复杂度
#include <bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned int;
using u128 = unsigned __int128;
void solve() {
i64 n, a, b;
std::cin >> n >> a >> b;
std::string s;
std::cin >> s;
bool f = false;
i64 ans = 0, res = a * n;
for (int i = 0; i < n; i++) {
if (f && s[i] == 'J') {
ans += 2 * b;
continue;
}
if (s[i] == 'K') {
ans += a;
}
if (!f && s[i] == 'J') {
f = true;
}
}
if (s[n - 1] == 'K' && f) {
ans += b - a;
}
std::cout << std::max(ans, res) << "\n";
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}
E 参加比赛
难度：*1500、模拟、动态规划
一个很清楚的思路，我们需要找到 的最长上升子序列的长度，这个子序列的值是连续的如
再进一步，假如我们当前 ，我们需要知道
在哪，
在哪。
所以我们的状态定义为 表示当前以
开始的最长上升子序列的长度。
我们倒着来，很容易的写出状态转移方程： 因为这样我们就保证了大的在后面。
初始值，如果我们要算 的时候，
还没有，那么我们的
就是
。
我们用 可以很容易实现。
#include <bits/stdc++.h>
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using u128 = unsigned __int128;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, q;
std::cin >> n;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
std::cin >> a[i];
}
std::map<int, int> dp;
for (int i = n; i >= 1; i--) {
int k = a[i];
dp[k] = dp.count(k + 1) ? dp[k + 1] + 1 : 1;
}
std::cin >> q;
while (q--) {
int x;
std::cin >> x;
std::cout << dp[x] << "\n";
}
return 0;
}
J 无量仙翁的救赎
难度：*1600、树链剖分、线段树
一道经典的树链剖分+线段树维护的模版题，不懂的话我觉得洛谷上的题解很清楚，就不讲了。
时间复杂度
#include <bits/stdc++.h>
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using u128 = unsigned __int128;
constexpr int INF = 1e9;
#define ls u << 1
#define rs u << 1 | 1
template<class Info, class Tag>
struct SegmentTree {
int n;
std::vector<Info> tr;
std::vector<Tag> tag;
SegmentTree(int _): n(_), tr(_ << 2), tag(_ << 2) {}
SegmentTree(std::vector<int> a): SegmentTree(int(a.size() - 1)) {
std::function<void(int, int, int)> build = [&](int u, int l, int r) -> void {
if (l == r) {
tr[u] = {l, r, a[l]};
return;
}
tr[u] = {l, r};
int mid = (l + r) >> 1;
build(ls, l, mid), build(rs, mid + 1, r);
pushup(u);
};
build(1, 1, n);
}
void apply(int u, const Tag& v) {
tr[u].apply(v);
tag[u].apply(v);
}
void pushdown(int u) {
if (tag[u].isEmpty()) return;
apply(ls, tag[u]);
apply(rs, tag[u]);
tag[u] = Tag();
}
void pushup(int u) {
tr[u] = tr[ls] + tr[rs];
}
void modify(int u, int l, int r, const Tag& v) {
if (l <= tr[u].l && r >= tr[u].r) {
apply(u, v);
return;
}
pushdown(u);
int mid = (tr[u].l + tr[u].r) >> 1;
if (l <= mid) {
modify(ls, l, r, v);
}
if (r > mid) {
modify(rs, l, r, v);
}
pushup(u);
}
void modify(int l, int r, const Tag& v) {
modify(1, l, r, v);
}
Info query(int u, int l, int r) {
if (l <= tr[u].l && tr[u].r <= r) {
return tr[u];
}
pushdown(u);
if (r <= tr[ls].r) {
return query(ls, l, r);
} else if (l >= tr[rs].l) {
return query(rs, l, r);
} else {
return query(ls, l, r) + query(rs, l, r);
}
}
Info query(int l, int r) {
return query(1, l, r);
}
};
struct Tag {
i64 add;
Tag(): add(0){}
Tag(i64 _add): add(_add) {}
void apply(Tag t) {
add += t.add;
}
bool isEmpty() {
return add == 0;
}
};
struct Info {
int l, r;
i64 sum;
void apply(Tag t) {
sum += (r - l + 1) * t.add;
}
};
Info operator+(Info a, Info b){
Info res;
res.l = a.l;
res.r = b.r;
res.sum = a.sum + b.sum;
return res;
}
struct HLD {
int n;
std::vector<std::vector<int>> adj;
std::vector<int> siz, dep;
std::vector<int> top, son, fa, dfn, id;
int cnt;
HLD(int n_) {
n = n_;
cnt = 0;
adj.resize(n + 1);
siz.resize(n + 1);
dep.resize(n + 1);
top.resize(n + 1);
son.resize(n + 1);
fa.resize(n + 1);
dfn.resize(n + 1);
id.resize(n + 1);
}
void add(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u);
}
std::function<void(int)> dfs1 = [&](int x) -> void {
siz[x] = 1;
dep[x] = dep[fa[x]] + 1;
for (auto y : adj[x]) {
if (y == fa[x]) continue;
fa[y] = x;
dfs1(y);
siz[x] += siz[y];
if (siz[y] > siz[son[x]]) {
son[x] = y;
}
}
};
std::function<void(int,int)> dfs2 = [&](int x, int t) -> void {
top[x] = t;
dfn[x] = ++ cnt;
id[cnt] = x;
if (son[x]) {
dfs2(son[x], t);
}
for (auto y : adj[x]) {
if (y == fa[x] || y == son[x]) continue;
dfs2(y, y);
}
};
int lca(int x, int y) {
while (top[x] != top[y]) {
if (dep[top[x]] > dep[top[y]]) {
x = fa[top[x]];
} else {
y = fa[top[y]];
}
}
return dep[x] < dep[y] ? x : y;
}
void modify_path(int u, int v, int k, SegmentTree<Info, Tag>& seg) {
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) {
std::swap(u, v);
}
seg.modify(dfn[top[u]], dfn[u], {k});
u = fa[top[u]];
}
if (dep[u] < dep[v]) {
std::swap(u, v);
}
seg.modify(dfn[v], dfn[u], {k});
}
void modify_tree(int u, int k, SegmentTree<Info, Tag>& seg) {
seg.modify(dfn[u], dfn[u] + siz[u] - 1, {k});
}
i64 query_path(int u, int v, SegmentTree<Info, Tag>& seg) {
i64 res = 0;
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) {
std::swap(u, v);
}
res += seg.query(dfn[top[u]], dfn[u]).sum;
u = fa[top[u]];
}
if (dep[u] < dep[v]) {
std::swap(u, v);
}
res += seg.query(dfn[v], dfn[u]).sum;
return res;
}
void work(int root = 1) {
dfs1(root);
dfs2(root, root);
}
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m, r;
std::cin >> n >> m >> r;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
std::cin >> a[i];
}
HLD hld(n);
for (int i = 1; i < n; i++) {
int u, v;
std::cin >> u >> v;
hld.add(u, v);
}
hld.work(r);
std::vector<int> w(n + 1);
for (int i = 1; i <= n; i++) {
w[i] = a[hld.id[i]];
}
SegmentTree<Info, Tag> seg(w);
while (m--) {
int op, a, b;
std::cin >> op >> a >> b;
if (op == 1) {
hld.modify_path(a, a, b, seg);
} else if (op == 2) {
hld.modify_tree(a, b, seg);
} else {
std::cout << hld.query_path(a, b, seg) << "\n";
}
}
return 0;
}
F 字符串
难度：*1800、位运算、最近公共祖先、树上前缀和
题目要求我们回答 简单路径重排后是否构成回文串。
首先，简单路径是什么？
简单路径就是从 出发，不经过重复的边到达
的一条路径，在解决这类问题的时候，一般都需要通过一个中间的结点（最近公共祖先）来分析问题。
引入最近公共祖先 之后，
的简单路径就可以分成
到
的距离加上
到
的距离。
每个结点都是一个字符，想一想我们通过什么方法可以快速的判断这条路径的结点构成的字符串重排后是否构成回文串。
我们知道回文串首尾必须一样，中间可以不一样。字符又可以重排，那么只要字符出现了偶数次，这个字符一定可以消掉（是回文），所以我们的问题就变成了统计字符串中的字符个数，这样遍历还是会超时。
那么就又要引入状态压缩的概念了，我们将每个字母映射到 位二进制表示的数字上，比如
就是
，
就是
，
就是
，以此类推
写成二进制的样子，我们就可以进行位运算的操作了，想想字符出现偶数次就消失了，是不是就对应了二进制的异或运算，相同的两个二进制位异或，就成了 。
所以我们可以把所有的字符表示的二进制异或起来，看看最后得到的值的二进制表示是否至多一个 ，如果是，那么就是回文了。
判断回文可以结束了，那么怎么快速得到这些结点表示的二进制呢。
这样就有了一个经典算法，树上前缀和。
我们可以将从根结点到所有结点的值都异或起来，存到每个结点上，如 表示从根结点到
的结点异或和。
这样处理完根结点到所有结点的异或和了，我们怎么得到任意路径的异或和呢？
假设我们有个序列 ，我们要求
的异或和，我们可以像前缀和一样预处理前缀异或和，就是从
异或到每个
的异或和，我们记为
，那么
因为异或两次相同的就抵消了。
我们在树上也可以这样用 之间的异或和，我们需要借助
，假设我们存的前缀异或和在
里，公式为：
其中 表示结点
对应的压缩后的字符表示的值。
至此结束，只需要在预处理 的时候顺便计算前缀异或和即可。
时间复杂度 瓶颈为倍增预处理
，计算二进制表示
的个数可以使用函数
__builtin_popcount(x)
#include <bits/stdc++.h>
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using u128 = unsigned __int128;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
std::vector<std::vector<int>> e(n + 1);
for (int i = 1; i < n; i++) {
int u, v;
std::cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
std::string str;
std::cin >> str;
std::vector<int> w(n + 1), a(n + 1);
for (int i = 0; i < n; i++) {
char c = str[i];
w[i + 1] = (1 << (c - 'a'));
a[i + 1] = w[i + 1];
}
std::vector<int> fa(n + 1), dep(n + 1);
std::vector<std::array<int, 17>> f(n + 1);
auto dfs = [&](auto &&self, int u) -> void {
dep[u] = dep[fa[u]] + 1;
f[u][0] = fa[u];
for (int j = 1; j < 17; j++) {
f[u][j] = f[f[u][j - 1]][j - 1];
}
for (auto v : e[u]) {
if (v == fa[u]) {
continue;
}
fa[v] = u;
w[v] ^= w[u];
self(self, v);
}
};
auto lca = [&](int x, int y) -> int {
if (dep[x] < dep[y]) {
std::swap(x, y);
}
for (int j = 16; j >= 0; j--) {
if (dep[f[x][j]] >= dep[y]) {
x = f[x][j];
}
}
if (x == y) {
return x;
}
for (int j = 16; j >= 0; j--) {
if (f[x][j] != f[y][j]) {
x = f[x][j];
y = f[y][j];
}
}
return f[x][0];
};
auto get = [&](int x, int y) {
return w[x] ^ w[y] ^ a[lca(x, y)];
};
dfs(dfs, 1);
int q;
std::cin >> q;
while (q--) {
int x, y;
std::cin >> x >> y;
int t = get(x, y);
if (__builtin_popcount(t) <= 1) {
std::cout << "YES\n";
} else {
std::cout << "NO\n";
}
}
return 0;
}
L K距离
难度：*1800、倍增、思维
最暴力的做法，预处理一个数组 表示第
个位置的后继在哪个位置，然后对
的每个数进行搜索，取最小。
暴力的时间复杂度为 不可取。
倍增就很好解决每次都要线性的一个一个找 个的问题，倍增可以用
的时间找到第
个的位置。
时间复杂度就变成了
那么 就表示我们一开始的
数组，
就表示下标为
的后
个数的下标，所以我们通过倍增的方法可以用
的时间预处理出来
数组。
遍历找距离它第 个数的位置。
#include <bits/stdc++.h>
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, k;
std::cin >> n >> k;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; ++i) {
std::cin >> a[i];
}
const int N = std::log2(n);
std::vector f(n + 1, std::vector<int>(N + 1));
std::vector<int> now(n + 2);
for (int i = n; i > 0; --i) {
f[i][0] = now[a[i] + 1];
now[a[i]] = i;
}
for (int j = 1; j <= N; ++j) {
for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
f[i][j] = f[f[i][j - 1]][j - 1];
}
}
auto find = [&](int x) -> int {
int t = k - 1;
for (int i = N; i >= 0; --i) {
if (t >= (1 << i)) {
t -= 1 << i;
x = f[x][i];
}
}
return x;
};
int ans = 1E9;
for (int i = 1; i <= n; ++i) {
int j = find(i);
if (j) {
ans = std::min(ans, j - i);
}
}
std::cout << (ans == 1E9 ? -1 : ans) << "\n";
return 0;
}
京公网安备 11010502036488号