由于评测机跑得快拿到了榜一。放一下我刚刚画的家产。P11649 [COCI 2024/2025 #4] 棋 / Šah - 洛谷 (luogu.com.cn)弱智。#includebits/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。#includebits/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_queueLL 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)首先最终的欧拉回路一定是所有点的 入度出度 的而所有有向边都是必须要走的我们可以先统计所有有向边的入度出度。只看无向边整个图就是一颗基环树。当然也可能没有环。我们直接用并查集断环为链其实就是选出那条导致成环的边。枚举这条边的状态不用 / 正向 / 反向。然后我们遍历整棵无向边树从树叶节点往上一条条确定无向边的方向。最后需要再用并查集确认一下整张图是否联通其实就是欧拉回路的模版。由于题目中有可能有自环和重边自环无论是有向还是无向都不用特殊考虑。有向边重边看原题意是需要当成不一样的两条边处理的。直接处理就好详见代码#includebits/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; vectorint 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; }