由于评测机跑得快拿到了榜一。

放一下我刚刚画的家产。

P11649 [COCI 2024/2025 #4] 棋 / Šah - 洛谷 (luogu.com.cn)

弱智。

#include<bits/stdc++.h> using namespace std; const int N = 210; bool mp[N][N]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; memset(mp, 0, sizeof(mp)); for(int i = 1; i <= m; ++i) { char c; int x, y; cin >> c >> x >> y; mp[x][y] = 1; if(c == 'N') { if(x + 2 >= 1 && y - 1 >= 1) { mp[x + 2][y - 1] = 1; } if(x + 2 >= 1 && y + 1 <= n) { mp[x + 2][y + 1] = 1; } if(x + 1 >= 1 && y - 2 >= 1) { mp[x + 1][y - 2] = 1; } if(x + 1 >= 1 && y + 2 <= n) { mp[x + 1][y + 2] = 1; } if(x - 2 >= 1 && y - 1 >= 1) { mp[x - 2][y - 1] = 1; } if(x - 2 >= 1 && y + 1 <= n) { mp[x - 2][y + 1] = 1; } if(x - 1 >= 1 && y - 2 >= 1) { mp[x - 1][y - 2] = 1; } if(x - 1 >= 1 && y + 2 <= n) { mp[x - 1][y + 2] = 1; } } if(c == 'R') { for (int i = 1; i <= n; i ++) { mp[x][i] = 1; mp[i][y] = 1; } } if(c == 'Q') { for (int i = 1; i <= n; i ++) { mp[x][i] = 1; mp[i][y] = 1; } for (int i = x, j = y; i <= n && j <= n; i ++, j ++) { mp[i][j] = 1; } for (int i = x, j = y; i >= 1 && j >= 1; i --, j --) { mp[i][j] = 1; } for (int i = x, j = y; i <= n && j >= 1; i ++, j --) { mp[i][j] = 1; } for (int i = x, j = y; i >= 1 && j <= n; i --, j ++) { mp[i][j] = 1; } } } int ans = 0; for(int i = 1; i <= n; i ++) { for(int j = 1; j <= n; j ++) { if(mp[i][j] == 1) ans ++; } } cout << ans << "\n"; return 0; }

P11650 [COCI 2024/2025 #4] 力 / Benzinska - 洛谷 (luogu.com.cn)

弱智*2。

#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N = 2e5 + 10; struct node { LL x, y; } a[N]; bool cmp(node na, node nb) { if (na.x != nb.x) { return na.x < nb.x; } else { return na.y > nb.y; } } priority_queue<LL> Q; int main () { ios::sync_with_stdio(false); cin.tie(0); int n; LL D, X; cin >> n >> D >> X; for (int i = 1; i <= n; i ++) { cin >> a[i].x; } for (int i = 1; i <= n; i ++) { cin >> a[i].y; } sort(a + 1, a + n + 1, cmp); LL last = 0; int ans = 0; for (int i = 1; i <= n; i ++) { D -= (a[i].x - last); last = a[i].x; while (D < 0) { if (Q.empty()) { cout << "-1\n"; return 0; } D += Q.top(); Q.pop(); ans ++; } Q.push(a[i].y); } D -= (X - last); while (D < 0) { if (Q.empty()) { cout << "-1\n"; return 0; } D += Q.top(); Q.pop(); ans ++; } cout << ans << "\n"; return 0; }

P11651 [COCI 2024/2025 #4] Xor - 洛谷 (luogu.com.cn)

纪念场切我单开了。

【题解】[COCI 2024/2025 #4] Xor（三种做法）-CSDN博客

P11653 [COCI 2024/2025 #4] 猫 / Tura Mačkica - 洛谷 (luogu.com.cn)

首先最终的欧拉回路一定是，所有点的 入度=出度 的，

而所有有向边都是必须要走的，我们可以先统计所有有向边的入度出度。

只看无向边，整个图就是一颗基环树。当然也可能没有环。

我们直接用并查集断环为链，其实就是选出那条导致成环的边。

枚举这条边的状态，不用 / 正向 / 反向。

然后我们遍历整棵无向边树，从树叶节点往上，一条条确定无向边的方向。

最后需要再用并查集确认一下整张图是否联通（其实就是欧拉回路的模版）。

由于题目中有可能有自环和重边，自环无论是有向还是无向都不用特殊考虑。

有向边重边看原题意，是需要当成不一样的两条边处理的。

直接处理就好，详见代码：

#include<bits/stdc++.h> using namespace std; const int N = 2e4 + 10; int a[N], b[N]; // 存储有向边：a[i] → b[i] (1≤i≤m)，a[0],b[0]用于存储环边 int fa[N], n, m; int c[N]; // 每个节点的净度数差：出度 - 入度 int sum, ans; vector<int> G[N]; // 树边邻接表（存储生成树的边） int findfa(int x) { if (x == fa[x]) { return fa[x]; } return fa[x] = findfa(fa[x]); } bool dfs(int x, int xfa) { // 遍历所有子节点（树边） for (int y : G[x]) if(y != xfa) { // 跳过父节点 if(dfs(y, x) == 0) { return 0; // 子节点出现非法情况 } } // 如果不是根节点，决定到父节点的边的方向 if (xfa != 0) { if(c[x] == - 1) { // 当前子树需要入度+1 // 选择方向：父节点 → 当前节点 // 对当前节点：入度+1 → c[i]从-1变为0 // 对父节点：出度+1 → c[k]加1 c[x] ++; c[xfa] --; sum ++; // 使用了一条无向边 fa[findfa(x)] = findfa(xfa); // 合并连通分量 } else if (c[x] == 1) { // 当前子树需要出度+1 // 选择方向：当前节点 → 父节点 // 对当前节点：出度+1 → c[i]从1变为0 // 对父节点：入度+1 → c[k]减1 c[x] --; c[xfa] ++; sum ++; fa[findfa(x)] = findfa(xfa); // 合并连通分量 } else if (c[x] != 0) { // |c[i]| > 1，需要多条边才能平衡，但这里只有一条到父节点的边 return 0; // 非法 } // c[i] == 0 不需要任何操作 } return 1; } void solve() { for (int i = 1; i <= n; i ++) { fa[i] = i; c[i] = 0; } for (int i = 0; i <= m; i ++) { // 处理有向边 c[a[i]] ++; // 起点出度 + 1 c[b[i]] --; // 终点入度 + 1（等价于出度-1） } if (dfs(1, 0) == 0) return; for (int i = 1; i <= m; i ++) { fa[findfa(a[i])] = findfa(b[i]); } for(int i = 1; i <= m; i ++) { if(findfa(a[i]) != findfa(a[1])) return; } ans = min(ans, sum); } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 1; i <= n; i++) { fa[i] = i; } int x = 0, y = 0; for(int i = 1; i <= n; i ++) { int u, v; cin >> u >> v; int fu = findfa(u), fv = findfa(v); if(fu == fv) { // u 和 v 已经连通，这条边就是环上的边 x = u; y = v; } else { // 不是环边，加入生成树 fa[fu] = fv; G[u].push_back(v); G[v].push_back(u); } } for(int i = 1; i <= m; i++) { cin >> a[i] >> b[i]; } ans = INT_MAX; // 情况 1：不使用环边 a[0] = 0; b[0] = 0; // 0 表示没有这条边 sum = m; // 总边数 = 有向边数 solve(); // 情况 2：使用环边，方向 x → y a[0] = x; b[0] = y; sum = m + 1; // 总边数 = 有向边数 + 环边 solve(); // 情况 3：使用环边，方向 y → x a[0] = y; b[0] = x; sum = m + 1; // 总边数 = 有向边数 + 环边 solve(); // ===== 输出结果 ===== if(ans == INT_MAX) { cout << "-1"; // 三种情况都无解 } else { cout << ans; // 输出最小回路长度 } return 0; }