没想到呀今天简单题卡壳了不过后面还好最终A了5个题看题吧目录A:小橙分硬币数学推导B:小橙玩游戏博弈论1. 小橙能直接获胜的情况2. n ≥ 3 时小橘必胜C:小橙买水果贪心推理过程特殊情况计算公式D:小橙访问传送门贪心二分E:小橙分配边权BFS并查集构造一、核心思路与结论二、无解的三个判定条件A:小橙分硬币以前签到题都直接带过但是今天要说道说道了毕竟居然卡了我十多分钟数学推导我们需要用 x 枚 2 元硬币、y 枚 1 元硬币满足 2 * x y half 0 ≤ x ≤ b 0 ≤ y ≤ a2 元硬币贡献的面值恒为偶数因此 half 的奇偶性只能由 1 元硬币决定若 half 为奇数至少需要 1 枚 1 元硬币若 half 为偶数最少可以用 0 枚 1 元硬币。同时2 元硬币最多只有 b 枚最多能贡献 2*b 元若 2*b ≥ half可以用足够的 2 元硬币凑出偶数部分仅需用 1 元硬币补齐奇偶性需要 1 元硬币数量为 half % 2。若 2b half用完所有 2 元硬币后剩余的 half - 2b 元必须全部用 1 元硬币补齐需要 1 元硬币数量为 half - 2*b。综上凑出 half 元需要的最少 1 元硬币数量为 need max (half % 2 , half - 2 * b)只要 need ≤ a说明 1 元硬币数量足够存在合法方案否则无解。#includebits/stdc.h using namespace std; typedef long long LL; LL a,b; int main() { cinab; LL sumab*2; if(sum1) { coutNOendl; return 0; } sum/2; if(asum) { coutYESendl; return 0; } sum-a; if(sum1) { coutNOendl; } else coutYESendl; return 0; }B:小橙玩游戏博弈论1. 小橙能直接获胜的情况当初始值n ≤ 2时小橙作为先手可以一步终结游戏n1减 1 → n0直接获胜n2减 2 → n0直接获胜2. n ≥ 3 时小橘必胜当 n≥3 时小橙无论选减 1 还是减 2操作后剩余的数一定 ≥1轮到小橘操作。 而对任意正整数 x小橘都存在必胜策略若 x ≤ 3小橘直接选减 3将 x 变为≤0 的数直接获胜若 x 3小橘选减 1将数变为 x-1仍≥3回到小橙回合。循环往复小橘总能将数值控制到≤3 时一步终结游戏因此只要 n≥3无论小橙如何操作主动权始终在小橘手中小橘必胜#includebits/stdc.h using namespace std; int main() { int t; cint; while(t--) { int n; cinn; if(n1||n2)coutxiaochengendl; else coutxiaojuendl; } return 0; }C:小橙买水果贪心推理过程免费获取是单向的只能从第 i 个水果免费得到第 i1 个顺时针方向无法反向获取。对于第 i 个水果如果前一个水果第 i-1 个的价格 a [i-1] a [i]那么只要获得了第 i-1 个水果就可以免费得到第 i 个无需购买。如果 a [i-1] a [i]那么第 i-1 个水果无法免费送出第 i 个第 i 个水果必须单独购买。购买第 i 个水果后后面所有连续价格不上升的水果都可以依次免费传递下去直到遇到下一个价格更高的位置。由于水果排成环形我们需要遍历每个位置判断当前价格是否大于前一个位置的价格若是则计入总花费。特殊情况如果所有水果价格都相等那么没有需要购买的上升点此时只需要购买任意一个水果即可依次免费获得全部水果总花费为任意一个水果的价格。计算公式设第 i 个水果的前一个为 prev (i) (i-1n) % n0 下标则最小总花费为 ans sum ( a [i] , 其中满足 a [i] a [prev (i)] ) 如果 ans 0所有价格相等则 ans a [0]#include bits/stdc.h using namespace std; typedef long long LL; int main() { int t; cin t; while (t--) { int n; cin n; vectorLL a(n); for (int i 0; i n; i) cin a[i]; LL ans 0; for (int i 0; i n; i) { int pre (i - 1 n) % n; if (a[i] a[pre]) ans a[i]; } if (ans 0) ans a[0]; cout ans endl; } return 0; }D:小橙访问传送门贪心二分这道题的本质是同色传送门可免费瞬移因此只需踩中任意一个同色门即可访问全部同色门。最优路径只有三种候选0 → 最近红门 → 传送到红蓝最近对 → 步行到蓝门 → 传送到最近蓝门 → 回 0代价minA d minB0 → 最近红门 → 传送到红蓝最近对 → 步行到蓝门 → 步行返回红门 → 回 0代价2*minA 2*d0 → 最近蓝门 → 传送到红蓝最近对 → 步行到红门 → 步行返回蓝门 → 回 0代价2*minB 2*d其中minA是红点到原点的最小距离minB是蓝点到原点的最小距离d是红蓝两点的最小间距。答案取三者最小值。#includebits/stdc.h using namespace std; int n,m; const int N1e510; int a[N],b[N]; typedef long long LL; int check1(int x)//b中大于等于x的最小值 { int l1,rm; int ans-1; while(lr) { int midlr1; if(b[mid]x) { ansmid; rmid-1; } else lmid1; } return ans; } int check2(int x) { int l1,rm; int ans-1; while(lr) { int midlr1; if(b[mid]x) { ansmid; lmid1; } else rmid-1; } return ans; } int main() { cinnm; int res11e9; for(int i1;in;i) { cina[i]; res1min(res1,abs(a[i])); } sort(a1,a1n); int res31e9; for(int i1;im;i) { cinb[i]; res3min(res3,abs(b[i])); } sort(b1,b1m); int res22e9; for(int i1;in;i) { int numcheck1(a[i]); if(num!-1)res2min(res2,abs(b[num]-a[i])); numcheck2(a[i]); if(num!-1)res2min(res2,abs(b[num]-a[i])); } LL resmin(1LL*res1res2res3,min(1LL*2*res11LL*2*res2,1LL*2*res31LL*2*res2)); coutresendl; return 0; }E:小橙分配边权BFS并查集构造一、核心思路与结论这道题的本质是验证最短路的可行性 构造合法边权核心结论可以一句话概括每条边的权值直接取两端点权值的绝对值差|a_u - a_v|只要满足两个连通性条件这个构造就一定合法。为什么这个构造是对的最短路下界对任意路径s→...→u总边权 Σ|a_i - a_j| ≥ |a_s - a_u| a_u三角不等式累加因此 s 到 u 的最短路一定不会小于 a_u。最短路上界如果存在一条从 s 出发、沿途点权值单调不减的路径到达 u那么路径总边权 Σ(a_{k1} - a_k) a_u - a_s a_u刚好等于 a_u。上下界相等因此最短路恰好等于 a_u满足题目要求。二、无解的三个判定条件只要满足任意一条直接输出-1没有权值为 0 的点起点 s 到自己的最短路必须为 0因此必须存在a_i 0的点作为起点。所有权值为 0 的点不连通所有 0 点之间的最短路必须为 0因此它们必须通过「两端都是 0 的边」互相连通否则两个 0 点之间最短路 0矛盾。从 0 点出发无法沿权值不减的方向到达所有点说明存在点的最短路无法达到 a_i构造不成立。剩下的就是建图了#includebits/stdc.h using namespace std; const int N2e510, M4e510; int n,m; int a[N]; int eu[N], ev[N]; int h[N], e[M], ne[M], idx; int p[N]; bool vis[N]; int find(int x) { if(p[x]!x) p[x]find(p[x]); return p[x]; } void add(int a, int b) { e[idx]b, ne[idx]h[a], h[a]idx; } int main() { cinnm; for(int i1;in;i) { cina[i]; p[i]i; } memset(h, -1, sizeof h); for(int i1;im;i) { int u,v; cinuv; eu[i]u, ev[i]v; if(a[u]0 a[v]0) { ufind(u), vfind(v); if(u!v) p[u]v; } if(a[u] a[v]) add(u, v); if(a[v] a[u]) add(v, u); } int s-1; for(int i1;in;i) { if(a[i]0) { si; break; } } if(s-1) { cout-1endl; return 0; } int rootfind(s); for(int i1;in;i) { if(a[i]0 find(i)!root) { cout-1endl; return 0; } } queueint q; q.push(s); vis[s]true; while(q.size()) { int uq.front(); q.pop(); for(int ih[u];~i;ine[i]) { int ve[i]; if(!vis[v]) { vis[v]true; q.push(v); } } } for(int i1;in;i) { if(!vis[i]) { cout-1endl; return 0; } } for(int i1;im;i) { coutabs(a[eu[i]] - a[ev[i]])endl; } return 0; }