A - Obesity题目描述用下面的公式计算出的数值叫做 $\mathrm{BMI}[\mathrm{kg}/\mathrm{m}^2]$ 。- $\text{Weight}[\mathrm{kg}] \div \text{Height}[\mathrm{m}] \div \text{Height}[\mathrm{m}]$在日本 $\mathrm{BMI}$ 大于或等于 $25 \; \mathrm{kg}/\mathrm{m}^2$ 的人被视为肥胖。请判断身高 $H[\mathrm{cm}]$ 、体重 $W[\mathrm{kg}]$ 的人在日本是否属于肥胖。解题思路A题不讲了。脑残题。完整代码#includebits/stdc.h #define fr1(i,a,b) for(int (i)(a);(i)(b);(i)) #define fr2(i,a,b) for(int (i)(a);(i)(b);(i)--) #define fv(i,p) for(auto (i):(p)) #define ll long long #define ull unsigned ll #define pii pairint,int #define pll pairll,ll #define _1st first #define _2nd second #define elif else if #define debug coutendl-------------------------------------------------------------endl using namespace std; int h,w; int main(){ ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); cinhw; if(400*wh*h){ coutYes; }else{ coutNo; } return 0; }B - Keep the Change题目描述高桥在 $N$ 家商店购物。最初他有 $10000$ 日元。在 $i$ th商店他购买了价值 $A_i$ 日元的商品支付了 $B_i$ 日元。这里 $A_i \leq B_i$ 成立。如果 $S_i $ keep 他没有收到零钱如果 $S_i $ take $A_i \leq B_i$ 成立 他收到了零钱。求与他在每家店都收到零钱的情况相比他损失了多少钱。准确地说设 $X$ 日元是高桥的最终金额并且让 $Y$ 日元成为高桥在每家店都收到零钱的情况下的最终金额。求出 $Y - X$ .解题思路最脑残的一次B题。完整代码#includebits/stdc.h #define fr1(i,a,b) for(int (i)(a);(i)(b);(i)) #define fr2(i,a,b) for(int (i)(a);(i)(b);(i)--) #define fv(i,p) for(auto (i):(p)) #define ll long long #define ull unsigned ll #define pii pairint,int #define pll pairll,ll #define _1st first #define _2nd second #define elif else if #define debug coutendl-------------------------------------------------------------endl using namespace std; int n,ans; int main(){ ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); cinn; fr1(i,1,n){ int a,b; string s; cinabs; if(skeep)ansb-a; } coutans; return 0; }C - Adjacent Sums(简单版)题目描述C 题的题目描述与E题相同。只有加粗的数据范围不同。给你一个整数序列 $A(A_1,A_2,\dots,A_N),B(B_1,B_2,\dots,B_{N-1})$ 它由介于 $0$ 与 $M-1$ 之间的整数组成。 $A$ 和 $B$ 的长度分别为 $N$ 和 $N-1$ 。您可以对 $A$ 执行以下操作任意多次。选择带有 $1 \leq i \leq N$ 的整数 $i$ 将 $1$ 加到 $A_i$ 中。求满足以下条件所需的最少运算次数。可以证明在本题的限制条件下该条件总是可以满足的。对于 $i1,2,\dots,N-1$ 来说 $A_iA_{i1}$ 除以 $M$ 的余数等于 $B_i$ 。数据范围$2 \leq N \leq 2 \times 10^5$$M2$$0 \leq A_i \leq M-1$$0 \leq B_i \leq M-1$所有输入值均为整数。解题思路数学转化核心M2模 2 等价异或模 2 加法等价于按位异或\((PQ) \bmod 2 P \oplus Q\) 把约束拆开\((A_ix_i) \oplus (A_{i1}x_{i1}) B_i\) 移项变形异或等式两边同时异或同一个数等式不变\(x_{i1} B_i \oplus A_i \oplus x_i \oplus A_{i1}\) .关键结论整个序列 \(x_1,x_2,\dots,x_N\) 完全由 \(x_1\) 决定若确定 \(x_1\)用上面公式能依次算出 \(x_2,x_3,\dots,x_N\)因为 \(M2\)\(x_1\) 在模 2 下只有两种可能0 或 1只需要枚举 \(x_10\)、\(x_11\) 两种情况分别算出全套 x 数组的总代价 \(\sum x_i\)取最小值就是答案。代价说明为什么代价直接累加 \(x_i\) \(x_i\) 是第 i 个元素一共加了多少次 1每加 1 算一次操作总操作次数就是所有 \(x_i\) 相加和题目定义完全一致。完整代码#includebits/stdc.h #define fr1(i,a,b) for(int(i)(a);(i)(b);(i)) #define fr2(i,a,b) for(int(i)(a);(i)(b);(i)--) #define fv(i,p) for(auto (i):(p)) #define ll long long #define ull unsigned ll #define pii pairint,int #define pll pairll,ll #define _1st first #define _2nd second #define elif else if #define debug coutendl-------------------------------------------------------------endl using namespace std; int n,m; int main(){ ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); cinnm; vectorinta(N1),b(N); fr1(i,1,N)cina[i]; fr1(i,1,N-1)cinb[i]; ll ansLLONG_MAX; fr1(start,0,1){ vectorintx(n1); x[1]start; ll costx[1]; fr1(i,1,n-1){ x[i1]b[i]^a[i]^x[i]^a[i1]; costx[i1]; } ansmin(ans,cost); } coutansendl; return 0; }D - Concentric Circles题目描述在 $xy$ \ 平面上是否存在满足以下所有条件的两个圆 $C_1$ 和 $C_2$ 这里 $C_1$ 和 $C_2$ 可能重合。- 两个不同的点 $(P_x, P_y)$ 和 $(Q_x, Q_y)$ 位于 $C_1$ 的圆周上。- 两个不同的点 $(R_x, R_y)$ 和 $(S_x, S_y)$ 位于 $C_2$ 的圆周上。- $C_1$ 与 $C_2$ 具有相同的圆心。给你 $T$ 个测试用例请逐一求解。数据范围$1 \leq T \leq 5 \times 10^4$$-10^9 \leq P_x,P_y,Q_x,Q_y,R_x,R_y,S_x,S_y \leq 10^9$$(P_x, P_y) \neq (Q_x, Q_y)$$(R_x, R_y) \neq (S_x, S_y)$所有输入值均为整数。解题思路一、几何前置结论两点确定圆心的约束若一个圆同时过两个不同点 \(A,B\)设圆心为 \(O(x_0,y_0)\)则\(|OA|^2 |OB|^2\) 展开距离平方并化简\((x_0-A_x)^2(y_0-A_y)^2 (x_0-B_x)^2(y_0-B_y)^2\) 消去 \(x_0^2,y_0^2\)整理得到一条直线方程\(2(B_x-A_x)x_0 2(B_y-A_y)y_0 B_x^2B_y^2 - A_x^2-A_y^2\) 这条直线就是线段 AB 的垂直平分线。关键所有能作为 “过 \(A,B\) 的圆的圆心” 的点全部落在 AB 的垂直平分线上。设\(L_1\)PQ 的垂直平分线所有合法 \(C_1\) 圆心集合\(L_2\)RS 的垂直平分线所有合法 \(C_2\) 圆心集合题目等价转化为直线 \(L_1\) 和 \(L_2\) 是否存在交点。若存在交点 O以 O 为圆心分别取 \(|OP|\)、\(|OR|\) 为半径作同心圆满足全部条件输出 Yes若不存在交点两直线平行且不重合没有公共圆心输出 No。二、分两类讨论 \(L_1\) 与 \(L_2\) 的位置关系两条直线只有两种位置不平行相交平行要么完全重合要么无交点。情况 1\(L_1\) 与 \(L_2\) 不平行 → 一定有交点 → 答案 Yes两条直线不平行等价于线段 PQ、RS 本身不平行。 线段平行判定取向量 \(\overrightarrow{PQ}(Q_x-P_x,Q_y-P_y)\)\(\overrightarrow{RS}(S_x-R_x,S_y-R_y)\)。 二维向量平行充要条件叉积为 0\(\text{cross} v_{1x} \cdot v_{2y} - v_{1y} \cdot v_{2x}\)\(\text{cross} \neq 0\)向量不平行 → \(L_1,L_2\) 不平行必有交点直接 Yes。ll v1xQx-Px,v1yQy-Py; ll v2xSx-Rx,v2ySy-Ry; ll crossv1x*v2y-v1y*v2x; if(cross!0){coutYes\n;}情况 2\(\text{cross}0\)即 \(PQ \parallel RS\)此时 \(L_1 \parallel L_2\)平行线分两种重合 / 分离。 只有两条垂直平分线完全重合时才存在无穷多公共圆心输出 Yes否则无公共圆心输出 No。那么如何判断两条垂直平分线 \(L_1,L_2\) 是否重合\(L_1\) 是 PQ 中垂线\(L_2\) 是 RS 中垂线且 \(PQ \parallel RS\)。 取 RS 上任意一点如 R判断 R 是否在 \(L_1\) 上再取 S 判断是否在 \(L_1\) 上。 若 \(R,S\) 都在 PQ 的中垂线上 → \(L_1,L_2\) 完全重合。R 在 PQ 中垂线的充要条件\(|RP|^2 |RQ|^2\) 展开距离平方\((R_x-P_x)^2(R_y-P_y)^2 (R_x-Q_x)^2(R_y-Q_y)^2\) 移项变形等价于\((2R_x-P_x-Q_x)^2 (2R_y-P_y-Q_y)^2 0\) 同理S 在 PQ 中垂线等价于\((2S_x-P_x-Q_x)^2 (2S_y-P_y-Q_y)^2 0\)比较平方和是否相等ll lhs(2*Rx-Px-Qx)*(2*Rx-Px-Qx)(2*Ry-Py-Qy)*(2*Ry-Py-Qy); ll rhs(2*Sx-Px-Qx)*(2*Sx-Px-Qx)(2*Sy-Py-Qy)*(2*Sy-Py-Qy); if(lhsrhs) coutYes\n; else coutNo\n;\(lhsrhs\)\(R、S\) 都在 PQ 中垂线上 → \(L_1L_2\)无数公共圆心Yes\(lhs≠rhs\)\(R、S\) 不在同一条中垂线两平行线分离无公共圆心No。整体流程概括对每组测试用例求向量 \(\overrightarrow{PQ},\overrightarrow{RS}\)计算叉积叉积≠0 → 两中垂线相交 → Yes叉积 0线段平行计算 R 到 PQ 中点距离平方、S 到 PQ 中点距离平方两值相等 → 中垂线重合存在公共圆心 → Yes两值不等 → 中垂线平行分离无公共圆心 → No。完整代码#includebits/stdc.h #define fr1(i,a,b) for(int (i)(a);(i)(b);(i)) #define fr2(i,a,b) for(int (i)(a);(i)(b);(i)--) #define fv(i,p) for(auto (i):(p)) #define ll long long #define ull unsigned ll #define pii pairint,int #define pll pairll,ll #define _1st first #define _2nd second #define elif else if #define debug coutendl-------------------------------------------------------------endl using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); int T; cinT; while(T--){ ll Px,Py,Qx,Qy,Rx,Ry,Sx,Sy; cinPxPyQxQyRxRySxSy; ll v1xQx-Px,v1yQy-Py; ll v2xSx-Rx,v2ySy-Ry; ll crossv1x*v2y-v1y*v2x; if(cross!0){ coutYes\n; }else{ ll lhs(2*Rx-Px-Qx)*(2*Rx-Px-Qx)(2*Ry-Py-Qy)*(2*Ry-Py-Qy); ll rhs(2*Sx-Px-Qx)*(2*Sx-Px-Qx)(2*Sy-Py-Qy)*(2*Sy-Py-Qy); if(lhsrhs) coutYes\n; else coutNo\n; } } return 0; }