个人难度评级
签到:$ABFH$
简单:$EIJ$
中等:$D$
困难:$CG$
A 比赛安排
等价于我们把三种比赛分成一组,如 $abc$ ,最后的结果一定是 $abcabc…a(b)$ ,所以我们检查是否满足
$$a-min(a,b,c)\leq 1\\b-min(a,b,c)\leq 1\\c-min(a,b,c)\leq 1$$
即可
void solve() {
ll a, b, c;
cin >> a >> b >> c;
int x = min({a, b, c});
if (a - x <= 1 && b - x <= 1 && c - x <= 1)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
B NCPC
显然最大的可以把所有小的全踢死;如果最大的有偶数个,那么自己也会死。
由以上结论我们可以得到:
- 如果最大有偶数个,它自己一定赢不了(因为清除不掉所有同级选手),但是可以帮助任何一个选手踢死其他所有对手,然后自杀,所以除了最大的每个都可能赢
- 如果最大有奇数个,最大踢死其他对手后不能找一个同级的撞死,所以只有最大能赢。
void solve() {
int n, mx = -1;
cin >> n;
vector<int> a(n);
unordered_map<int, int> cnt;
for (int i = 0; i < n; i++)
cin >> a[i], mx = max(mx, a[i]), cnt[a[i]]++;
bool f = cnt[mx] & 1;
for (int i = 0; i < n; ++i) {
if (f) {
if (a[i] == mx)
cout << 1;
else
cout << 0;
} else {
if (a[i] < mx)
cout << 1;
else
cout << 0;
}
}
cout << endl;
}
C 炮火轰炸
把炮火点看作图的节点,如果两个炮火点在8邻域(周围一圈8个格子)内,则连边。首先找出所有炮火点的连通块。每一个封闭的炮火圈对应一个连通块的外轮廓。对于每个连通块,我们需要找到它的外边界。只需要找到连通块中最左下角的点作为起点,然后沿着逆时针方向(始终保持炮火点在左手边)遍历边界,直到回到起点。在这个过程中,我们记录下边界上的有向边。
对于每个询问点 $(a,b)$ ,我们想象向右发射一条射线( $y=b,x>a$ )。计算这条射线与炮火圈边界的垂直边的交点数。如果边界边向上穿过射线,计数 $+1$ ;向下穿过,计数 $-1$ 。若最终计数的总和不为0,说明点在圈内,否则在圈外。
int dx[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
struct Point {
int x, y;
bool operator<(const Point &other) const {
if (x != other.x)
return x < other.x;
return y < other.y;
}
bool operator==(const Point &other) const {
return x == other.x && y == other.y;
}
};
void solve() {
int n, q;
cin >> n >> q;
map<Point, int> mp;
vector<Point> pts(n);
for (int i = 0; i < n; ++i) {
cin >> pts[i].x >> pts[i].y;
mp[pts[i]] = i;
}
vector<bool> vis(n);
map<int, vector<PII>> Eve;
for (int i = 0; i < n; ++i) {
if (vis[i])
continue;
vector<int> comp, q = {i};
vis[i] = 1;
int head = 0;
while (head < q.size()) {
int u = q[head++];
comp.pb(u);
for (int k = 0; k < 8; k++) {
Point nb = {pts[u].x + dx[k], pts[u].y + dy[k]};
if (mp.count(nb)) {
int v = mp[nb];
if (!vis[v]) {
vis[v] = true;
q.pb(v);
}
}
}
}
if (comp.size() < 2)
continue;
int st = comp[0];
for (int id : comp)
if (pts[id] < pts[st])
st = id;
int curr = st, cd = 4, steps = 0, ms = 4 * comp.size() + 100;
do {
int nn = -1, nd = -1;
for (int k = 0; k < 8; ++k) {
int dir = (cd + k) % 8;
Point nb = {pts[curr].x + dx[dir], pts[curr].y + dy[dir]};
if (mp.count(nb)) {
nn = mp[nb];
nd = dir;
break;
}
}
if (nn != -1) {
if (pts[nn].y > pts[curr].y)
Eve[pts[curr].y].pb({pts[curr].x, 1});
else if (pts[nn].y < pts[curr].y)
Eve[pts[nn].y].pb({pts[nn].x, -1});
curr = nn;
cd = (nd + 6) % 8;
} else
break;
steps++;
} while (curr != st && steps < ms);
}
map<int, vector<PII>> queries;
for (int i = 0; i < q; ++i) {
int a, b;
cin >> a >> b;
queries[b].pb({a, i});
}
vector<string> ans(q, "NO");
for (auto &[y, qs] : queries) {
if (!Eve.count(y))
continue;
auto &evs = Eve[y];
sort(all(evs));
sort(all(qs));
int winding = 0;
int ptr = 0;
for (auto &_pt : qs) {
while (ptr < evs.size() && evs[ptr].fi < _pt.fi) {
winding += evs[ptr].se;
ptr++;
}
if (winding != 0)
ans[_pt.se] = "YES";
}
}
for (auto v : ans)
cout << v << endl;
}
D 数字积木
我已急哭

直接枚举所有连通子图并计算 $\text{MEX}$ 显然不可行。我们利用 $\text{MEX}$ 的性质转化求和顺序。
根据 $\text{MEX}$ 的定义:
$$MEX(S)\geq k$$
当且仅当集合 ${0,1,…,k−1}$ 包含在子图 $S$ 的点权集合中。
利用恒等式 $MEX(S)=\sum\limits_{k=1}^n[MEX(S)≥k]$ ,我们可以将总答案转化为:
$$\sum\limits_{S}MEX(S)=\sum\limits_{S}\sum\limits_{k=1}^{n}[MEX(S)\geq k]=\sum\limits_{k=1}^{n}(\text{包含{0,…,k-1}的连通子图数量})$$
设 $V_k$ 为权值 ${0,…,k−1}$ 的节点集合。
要在树上连通地包含 $V_k$ ,这个子图必须包含 $V_k$ 在树上的极小连通生成子图 $H_k$ 。如果我们以权值为 $0$ 的节点为根:
- $H_k$ 一定包含根节点(因为 0 在其中)。
- $H_k$ 是从根节点出发,延伸到所有权值在 $1∼k−1$ 的节点的路径的并集。
对于一个固定的 $H_k$ ,任何包含它的合法连通子图都是由两部分组成:
- 必须包含完整的 $H_k$
- 对于 $H_k$ 上的每一个节点 $u$ ,可以挂载它那些不在 $H_k$ 中的子树
设 $dp[u]$ 为在原树中,以 $u$ 为根的子树内,包含 $u$ 的连通子图的个数。
状态转移方程为:
$$dp[u] = \prod_{v\in{children(u)}}(dp[v]+1)$$
那么, $N_k$ 的计算公式为:
$$N_k = \prod_{u\in{H_k}}(\frac{dp[u]}{\prod\limits_{v\in{children(u)\cap H_k}}(dp[v]+1)})$$
直观理解就是:$H_k$ 上所有节点原本的方案数乘起来,但要剔除掉那些已经变成了它的一部分的子节点分支的贡献(因为它们变成了必选,不再是可选可不选)。
如果我们对每个 $k$ 都重新遍历树计算 $N_k$ ,复杂度是 $O(N^2)$ ,会超时。我们注意到 $H_{k+1}$ 是在 $H_k$ 的基础上增加节点 $k$ 形成的。
设权值为 $k$ 的节点为 $tar$ 。
- 如果 $tar$ 已经在 $H_k$ 中(即它在 $0∼k−1$ 某点的路径上),则 $N_{k+1}=N_k$ 。
- 如果不在,我们需要把从 $tar$ 到 $H_k$ 的路径合并进核心。找到 $tar$ 往上跳直到碰到 $H_k$ 的路径。路径上的点是新加入核心的点。
- 设路径与原核心的交点为 $J$ ,路径上 $J$ 的那个子节点为 $B$ 。
- 原来 $B$ 是挂在 $J$ 下的一个可选分支,贡献是 $(dp[B]+1)$ 。现在它变成了核心的一部分,所以要从总乘积中除以 $(dp[B]+1)$ 。
- 对于路径上新加入的每个节点 $u$ ,我们要把它的贡献乘进总答案。它的贡献是它所有不在路径上的子树的选择方案。 即乘以 $dp[u]dp[\text{child on path}]+1$ 。对于 $tar$ 节点本身,直接乘以 $dp[tar]$ 。
对于卡逆元的解决办法:
维护一个结构体,记录数值 $val$ 和因子中 $0$ 的个数 $cnt$。
- 乘 $0$ 时:
cnt++ - 除 $0$ 时:
cnt-- - 取值时:若 $cnt > 0$ 则为 $0$ ,否则为 $val$ 。
struct SafeZ {
Z val = 1;
int cnt = 0;
SafeZ(Z v) {
mul(v);
}
void mul(Z x) {
if (x.val() == 0)
cnt++;
else
val *= x;
}
void div(Z x) {
if (x.val() == 0)
cnt--;
else
val /= x;
}
Z get() {
return cnt > 0 ? Z(0) : val;
}
};
void solve() {
int n;
cin >> n;
vector<int> a(n + 1), pos(n + 1);
for (int i = 1; i <= n; ++i)
cin >> a[i], pos[a[i]] = i;
vector<vector<int>> g(n + 1);
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
g[u].pb(v), g[v].pb(u);
}
vector<bool> vis(n + 1);
vector<int> pa(n + 1);
int s = pos[0];
vector<int> q;
int h = 0;
q.pb(s);
vis[s] = 1;
pa[s] = 0;
while (h < q.size()) {
int u = q[h++];
for (auto v : g[u]) {
if (vis[v])
continue;
vis[v] = 1;
pa[v] = u;
q.pb(v);
}
}
vector<Z> way(n + 1);
for (int i = n - 1; i >= 0; --i) {
int u = q[i];
way[u] = 1;
for (int v : g[u]) {
if (v != pa[u]) {
way[u] *= way[v] + 1;
}
}
}
vis.assign(n + 1, 0);
vis[s] = 1;
SafeZ cur = way[s];
Z ans = cur.get();
for (int k = 1; k < n; ++k) {
int tar = pos[k];
if (vis[tar]) {
ans += cur.get();
continue;
}
vector<int> path;
int curr = tar;
while (!vis[curr]) {
path.pb(curr);
curr = pa[curr];
}
reverse(all(path));
cur.div(way[path[0]] + 1);
for (int i = 0; i < path.size(); ++i) {
int u = path[i];
vis[u] = 1;
cur.mul(way[u]);
if (i < path.size() - 1) {
cur.div(way[path[i + 1]] + 1);
}
}
ans += cur.get();
}
cout << ans << endl;
}
E 01矩阵
打表发现,先构造一个严格下三角矩阵,在按 $p={0,n-1,1,n-2…}$ 重排行和列后,连通块数量正好为 $n$ 。
简单的证明:
- 原下三角矩阵每行(列)1 的个数是 $0\sim n-1$,行和列按同一置换重排,多重集合不变
- 由于 $p$ 高低交错:
- 固定一行 $i$ ,条件 $p[i]>p[j]$ 随 $j$ 变化至多翻转一次
- 所以每行、每列的 $1$ 都是一个连续区间
- 按值$k = 0 \sim n-1$ 分层:
- 当 $\min(p[i], p[j]) = k$ 时,会出现一个新的、与之前全部不连通的区域
- 每个 $k$ 恰好产生一个新的 $0/1$ 连通块,因此连通块总数 $=\sum\limits_{k=0}^{n-1}1=n$
void solve() {
int n;
cin >> n;
if (n == 1) {
cout << "0" << endl;
return;
}
vector<string> g(n, string(n, '0'));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
g[i][j] = '1';
}
}
int l = 0, r = n - 1;
vector<int> p;
while (l <= r) {
p.pb(l++);
if (l <= r)
p.pb(r--);
}
vector<string> ans(n, string(n, '0'));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
ans[i][j] = g[p[i]][p[j]];
}
}
for (int i = 0; i < n; ++i)
cout << ans[i] << endl;
}
F x?y?n!
如果 $\gcd(x,y) = n$ ,不难想到令 $x = n\cdot s,y = n\cdot t,\gcd(s,t)=1$ 即可满足条件,那么就有 $n\leq |x-y| \leq x\oplus y$
我们要让 $x \oplus y = n$ ,所以我们想到如果取 $s=2^r,t = 2^r+1$ (显然互质),即 $x = n\cdot 2^r,y = n\cdot (2^r+1)$,有
$$x\oplus y = n \text{当且仅当} x\& n = 0$$
我们只需要去找满足 $(n<<r)\& n=0$ 的 $r$ 即可。
void solve() {
int n;
cin >> n;
ll x = 0, y = 0, t = n;
for (int i = 1; i <= 31; ++i) {
t <<= 1;
if ((t & n) == 0) {
x = t, y = t + n;
break;
}
}
cout << x << " " << y << endl;
}
H 权值计算
我们不妨考虑数组中每个元素对最终答案贡献了多少。
函数 $f(l,r,s)$ 计算的是子数组 $s$ 的所有前缀中不同元素个数之和。换个角度,最终的总权值等于:对于所有的 $1≤l≤k≤r≤n$ ,如果 $a[l…k]$ 中 $a[i]$ 是第一次出现,则产生 $1$ 的贡献。
对于第 $i$ 个位置的元素 $a[i]$ ,它被统计的条件是:它必须在统计范围 $[l,k]$ 内(即 $l≤i≤k$ )。它必须是该范围内 $a[i]$ 的第一次出现。这意味着起始点 $l$ 必须在 $x$ 上一次出现的位置 $pos[x]$ 之后。因此,对于固定的 $i$ ,合法的 $(l,k,r)$ 组合满足:
- $l$ 的范围:$pos[x] < l <= i$ ,共有 $i−pos[x]$ 种选择。
- $k$ 的范围:$i≤k≤n$ 。
- $r$ 的范围:$k≤r≤n$ 。
对于每一个固定的 $k$( $k≥i$ ),合法的 $r$ 有 $n−k+1$ 个。所以对于固定的 $i$ ,右边部分 $(k,r)$ 的组合总数为:
$$\sum\limits_{k=i}^{n}(n-k+1) = 1+2+…+(n-i+1) = \frac{(n-i+1)(n-i+2)}{2}$$
所以最后答案为
$$\sum_{i=1}^{n}(i-pos[a[i]])\times \frac{(n-i+1)(n-i+2)}{2}$$
void solve() {
int n;
cin >> n;
map<int, int> pos;
ll tot = 0;
auto S = [&](ll x) {
return x * (x + 1) / 2;
};
for (int i = 1, x; i <= n; ++i) {
cin >> x;
tot += (i - pos[x]) * S(n - i + 1);
pos[x] = i;
}
cout << tot << endl;
}
I 01回文
回文串有两种基本形式:
- 长度为 $2$ 的:直接检查相邻元素。
- 长度大于 $2$ 的: 如果 $(i,j)$ 的所有邻居的值都与它不同(例如它是 $0$ ,周围全是 $1$ ),那么任何路径必然是 $0→1→…0→1→…$ 。要形成回文串,路径必须以 $0$ 结尾。最短的形式是 $0→1→0$ 。这意味着我们需要从 $(i,j)$ 出发,进入一片 $1$ 的区域,并能从这片区域走到另一个 $0$ 的位置。 推广来说,如果 $(i,j)$ 相邻的那些 $1$ 所在的连通分量连接了至少两个 $0$(其中一个是 $(i,j)$ 自己,另一个是目标终点),那么就存在 $0→1…1→0$ 这样的路径。 所以如果 $(i,j)$ 相邻的异色连通分量接触到了除 $(i,j)$ 以外的其他同色节点,输出 $\text{Y}$ 。这等价于:一个连通分量如果接触了超过 $1$ 个异色节点,那么这些异色节点都能通过该连通分量形成回文路径。
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
void solve() {
int n, m;
cin >> n >> m;
vector<string> g(n);
for (int i = 0; i < n; ++i)
cin >> g[i];
vector<string> ans(n, string(m, 'N'));
auto check = [&](int x, int y) {
return 0 <= x && x < n && 0 <= y && y < m;
};
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
for (int k = 0; k < 4; ++k) {
int nx = i + dx[k], ny = j + dy[k];
if (check(nx, ny)) {
if (g[nx][ny] == g[i][j]) {
ans[i][j] = 'Y';
break;
}
}
}
}
}
auto ssolve = [&](char tar) {
vector<vector<bool>> vis(n, vector<bool>(m));
vector<int> vis2(n * m, -1);
int id = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (g[i][j] == tar && !vis[i][j]) {
id++;
vector<PII> nei;
queue<PII> q;
q.push({i, j});
vis[i][j] = 1;
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
for (int k = 0; k < 4; ++k) {
int nx = x + dx[k], ny = y + dy[k];
if (check(nx, ny)) {
if (g[nx][ny] == tar) {
if (!vis[nx][ny]) {
vis[nx][ny] = 1;
q.emplace(nx, ny);
}
} else {
int idx = nx * m + ny;
if (vis2[idx] != id) {
vis2[idx] = id;
nei.eb(nx, ny);
}
}
}
}
}
if (nei.size() > 1) {
for (auto [x, y] : nei) {
ans[x][y] = 'Y';
}
}
}
}
}
};
ssolve('0');
ssolve('1');
for (int i = 0; i < n; ++i) {
cout << ans[i] << endl;
}
}
J 终于再见
首先根据每个城市的繁华度(度数)将城市进行分级。度数相同的城市属于同一级。将所有出现的度数从小到大排序,对应不同的级别 $L_1,L_2,…,L_k$ 。对于级别为 $i$ 的城市,我们需要找到通往级别 $>i$ 的城市的最短路径。这意味着我们可以从最高级别的城市开始,逐步向下处理。多源 $bfs$ 求解一下即可。
void solve() {
int n, m;
cin >> n >> m;
vector<vector<int>> g(n + 1);
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
g[u].pb(v), g[v].pb(u);
}
vector<vector<int>> gp(n);
for (int i = 1; i <= n; ++i) {
gp[g[i].size()].pb(i);
}
vector<vector<int>> L;
for (int d = 0; d < n; ++d) {
if (!gp[d].empty()) {
L.pb(gp[d]);
}
}
vector<int> dist(n + 1, inf), ans(n + 1, -1);
queue<int> q;
int K = L.size();
if (K > 0) {
for (int u : L[K - 1]) {
dist[u] = 0;
q.push(u);
}
}
auto bfs = [&]() {
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : g[u]) {
if (dist[v] > dist[u] + 1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
};
bfs();
for (int i = K - 2; i >= 0; --i) {
for (int u : L[i]) {
if (dist[u] != inf) {
ans[u] = dist[u];
} else {
ans[u] = -1;
}
}
for (int u : L[i]) {
if (dist[u] != 0) {
dist[u] = 0;
q.push(u);
}
}
bfs();
}
for (int i = 1; i <= n; ++i) {
cout << ans[i] << " ";
}
cout << endl;
}
头文件
#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define eb emplace_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define endl "\n"
using namespace std;
using ll = long long;
using ld = long double;
using ui = unsigned;
using ull = unsigned long long;
using i128 = __int128;
using PII = pair<int, int>;
using PLL = pair<ll, ll>;
using TIII = tuple<int, int, int>;
using TLLL = tuple<ll, ll, ll>;
void init() {
}
void solve() {
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
init();
int t = 1;
cin >> t;
cout << fixed << setprecision(15);
for (int _ = 1; _ <= t; ++_) {
solve();
}
return 0;
}
自动取模
constexpr int MOD = 998244353;
template <class T>
constexpr T ksm(T a, ll b) {
T res = 1;
while (b) {
if (b & 1)
res *= a;
b >>= 1;
a *= a;
}
return res;
}
template <int P>
struct MInt {
int x;
constexpr MInt() : x() {}
constexpr MInt(ll x) : x{norm(x % getMod())} {}
static int Mod;
constexpr static int getMod() {
if (P > 0) {
return P;
} else {
return Mod;
}
}
constexpr static void setMod(int Mod_) {
Mod = Mod_;
}
constexpr int norm(int x) const {
if (x < 0) {
x += getMod();
}
if (x >= getMod()) {
x -= getMod();
}
return x;
}
constexpr int val() const {
return x;
}
explicit constexpr operator int() const {
return x;
}
constexpr MInt operator-() const {
MInt res;
res.x = norm(getMod() - x);
return res;
}
constexpr MInt inv() const {
assert(x != 0);
return ksm(*this, getMod() - 2);
}
constexpr MInt &operator*=(MInt rhs) & {
x = 1LL * x * rhs.x % getMod();
return *this;
}
constexpr MInt &operator+=(MInt rhs) & {
x = norm(x + rhs.x);
return *this;
}
constexpr MInt &operator-=(MInt rhs) & {
x = norm(x - rhs.x);
return *this;
}
constexpr MInt &operator/=(MInt rhs) & {
return *this *= rhs.inv();
}
friend constexpr MInt operator*(MInt lhs, MInt rhs) {
MInt res = lhs;
res *= rhs;
return res;
}
friend constexpr MInt operator+(MInt lhs, MInt rhs) {
MInt res = lhs;
res += rhs;
return res;
}
friend constexpr MInt operator-(MInt lhs, MInt rhs) {
MInt res = lhs;
res -= rhs;
return res;
}
friend constexpr MInt operator/(MInt lhs, MInt rhs) {
MInt res = lhs;
res /= rhs;
return res;
}
friend constexpr istream &operator>>(istream &is, MInt &a) {
ll v;
is >> v;
a = MInt(v);
return is;
}
friend constexpr ostream &operator<<(ostream &os, const MInt &a) {
return os << a.val();
}
friend constexpr bool operator==(MInt lhs, MInt rhs) {
return lhs.val() == rhs.val();
}
friend constexpr bool operator!=(MInt lhs, MInt rhs) {
return lhs.val() != rhs.val();
}
};
template <>
int MInt<0>::Mod = 998244353;
template <int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();
using Z = MInt<MOD>;