2026河南萌新联赛(六)郑州大学

萌新联赛(六)郑州大学题目链接官方预测难度​EasyG. 找不同、C. 报数Easy - Mid L. 神秘数字、D. 垂直电梯、J. 空调、B. 果树​MidI. 耳鸣、F. 虚狩武器、H. Clank!Mid - HardE. 演唱会、K. 跳楼机​HardM. 你追我逃、A. 强烈的以太波动赛事做题难度​Easy:C. 报数、G. 找不同Easy - Mid: L. 神秘数字、B. 果树、D. 垂直电梯​Mid: J. 空调、F. 虚狩武器、I. 耳鸣Mid - Hard: H. Clank!​Hard:E. 演唱会、M. 你追我逃、K. 跳楼机、A. 强烈的以太波动感觉这周题目跨度很大签到题的两道特别简单但后面的题一道也做不出来C题咋一看数据范围很大但找规律会发现结果恒等于“1”直接输出即可#includebits/stdc.h using namespace std; int main(){ int n; cinn; cout1endl; return 0; }G题数据范围不大开个双层循环找到两个不同的字符输出它俩的位置即可找不到输出“-1”#includebits/stdc.h using namespace std; void solve(){ int n; cinn; string s; cins; for(int i0;in;i){ for(int j0;ji;j){ if(s[i]!s[j]){ coutj iendl; return ; } } } cout-1endl; } int main(){ int t; t1; while(t--)solve(); return 0; }L题题意有一个神秘数 x(1 ≤ x ≤ n 1\le x \le n1≤x≤n)。 你可以造出 m 个集合。对于每个集合你会得到回答x 是否在这个集合里是 / 否对应 1/0。 每个数字 x 会得到一个长度为 m 的 01 应答序列。要求1~n 每个数字对应的 01 序列互不相同这样根据回答序列就能唯一确定 x。 求最小的 m并输出一组集合构造方案。本质每个数字分配唯一的 m 位二进制编码。m 满足 (2 m ≥ n 2^m \ge n2m≥n)m 是满足条件的最小整数。示例 n5(2 2 4 5 2 3 8 ≥ 5 2^2452^38\ge52245238≥5)最小 m3。做法 1二进制位法思路把数字 (1 ∼ n 1\sim n1∼n) 转成 m 位二进制。第 i 个集合存放二进制第 i 位为 1的所有数字。每个数的应答就是它二进制每一位的值每个数二进制串唯一保证可区分。举例子 n5m3表格数字二进制 (3 位)第 1 位 (最低)第 2 位第 3 位 (最高)10011002010010301111041000015101101集合 集合 1第 0 位为 1{1,3,5} 集合 2第 1 位为 1{2,3} 集合 3第 2 位为 1{4,5}代码实现#includebits/stdc.h using namespace std; int n; vectorint ans[50]; /** * brief 构造m个集合二进制位法 * param m 需要构造的集合最小数量 * 思路把数字1~n转成m位二进制 * 第i个集合存放【二进制第i位为1】的数字 */ void solve(int m){ // i代表二进制的第i位(从0开始最低位为0) for(int i 0; i m; i){ // j是0~n-1对应真实数字 j1 for(int j 0; j n; j){ // 判断 j 的第i个二进制位是否等于1 if(j (1 i)){ ans[i1].push_back(j1); // 把真实数字存入第i1个集合 } } } } int main(){ cin n; int m 1; while( (1 m) n )m; solve(m); cout m; // 依次输出每一个集合 for(int i 1; i m; i){ // 换行输出本集合元素个数 cout \n ans[i].size(); // 遍历输出集合内所有数字 for(int x : ans[i]){ cout x; } } return 0; }方法2递归对半拆分法核心思想模拟二分查找的过程。每一层递归对应一个集合。 对于当前区间 ([l,r])取中点 mid把区间切分成两半 ([l,mid]) 和 ([mid1,r])。将其中一半比如左半部分全部加入当前集合另一半不加入。如果数字属于这一半回答为 1否则回答 0。得到 1 比特区分信息。下一个集合step1分别递归处理左右两个子区间继续对半切分。当区间只有一个数字 (lr)无法继续切分直接返回。每一层递归对应 1 个集合递归总层数恰好等于最小的 m。 每个数字一路递归得到的一串 0/1就是它的回答序列保证全部唯一。#includebits/stdc.h using namespace std; int n; vectorint ans[50]; /** * param step 当前正在构造第step个集合 * param l 当前处理数字区间左边界 * param r 当前处理数字区间右边界 */ void solve(int step, int l, int r){ if(l r) return; //区间只剩1个数不用再区分直接返回 int mid (l r) / 2; //把右半区间 [mid1, r] 的数字加入当前step集合 for(int i mid 1; i r; i){ ans[step].push_back(i); } //递归处理左半区间使用下一个集合 step1 solve(step 1, l, mid); //递归处理右半区间使用下一个集合 step1 solve(step 1, mid 1, r); } int main(){ cin n; int m 1; while((1 m) n){ m; } solve(1, 1, n); //从第1个集合区间1~n开始递归 cout m; for(int i 1; i m; i){ cout \n ans[i].size(); for(int x : ans[i]){ cout x; } } return 0; }D题题意一栋楼一共 n 层电梯编号 (1 ∼ n − 1 1\sim n-11∼n−1)。第 i 号电梯停靠楼层所有是 (i 1 \boldsymbol{i1}i1) 的因数或是( i 1 ) (\boldsymbol{i1})(i1)的倍数且楼层 (≤ n \le n≤n)。 例5 号电梯(i16)停靠 6 的因数、倍数1,2,3,6,12…坐一台电梯从 x 坐到 y费用公式(m y − x \boldsymbol{my-x}my−x)。 可以无限次换乘电梯起点 a 层目标 b 层求从 a 到 b 的最小总费用。 无解输出No Solution。输入多组 T 组数据每组 (n,m,a,b)(a ≠ b a\neq bab)。 数据范围(T ≤ 10 5 , n ≤ 10 9 T\le 10^5,\;n\le10^9T≤105,n≤109)。思路总费用只和乘坐电梯次数 k 有关要最小化 k。可以一次直达 (k1) 的两种情况满足其一即可 ① (gcd(a,b)2)a、b 同为 gcd 的倍数 ②a × b ≤ n a\times b\le na×b≤na、b 同为1-n之间某数的的因数。上面都不满足最少要坐 2 次电梯 (k2)。费用公式k1(Wm-ab)k2(W2m-ab)本题保证一定有解不用处理无解。#includebits/stdc.h using namespace std; void solve(){ long long n,m,a,b; cinnmab; // g初始 m b - a对应k1次电梯的总费用 long long gm-ab; if(__gcd(a,b)1||a*bn) g0; //可以直接1次到达保持k1的费用不变什么都不干 else gm; // 条件不成立再加一份m →变成2*m b-ak2次 coutgendl; } int main(){ int t; cint; while(t--)solve(); return 0; }J题题意空调初始温度 26模式 1 按键一共 3 种温度 1最高到 R到 R 不再上涨-温度‑1最低到 L到 L 不再下降模式模式循环切换(1 → 2 → … → K → 1 1\to2\to…\to K\to11→2→…→K→1)总共按了 n 次按键不知道每一次按的是什么。 MSJ 声称最后温度是t模式是m。完全不可能实现输出Lie说谎存在至少一种按键序列可以达成输出Maybe思路算出温度最小加减步数ans1 abs(t‑26)模式最少模式按键ans0 m‑1。如果最小总消耗ans0ans1 n→直接 Lie。剩下多余按键rest n‑ans0‑ans1。rest≥0rest 必须是偶数多余按键成对按 ‑抵消。同时要考虑可以额外多按 K 次模式键模式循环一圈不变再重新算 rest。并且要看温度区间 [L,R] 是否允许消耗这些多余按键如果 LR不能有多余按键。只要存在一组合法 b模式按键数全部满足条件输出 Maybe否则 Lie。输出 Maybe存在某套按键序列Lie完全不可能。这道题不涉及任何算法就是纯模拟的过程#includebits/stdc.h using namespace std; void solve(){ int L,R,K,n,t,m; cinLRKntm; int ans00,ans10; ans0m-1; ans1abs(t-26); if(ans1ans0n){ coutLieendl; return; } int bn-ans0-ans1; if(b%20||tL||tR||bans1R-26(R-t)||bans126-Lt-L){ coutMaybeendl; return ; } if(bK||K%20){ coutLieendl; return ; } coutMaybeendl; } int main(){ int t; cint; while(t--)solve(); return 0; }B题题意n 棵树下标(0 , 1 , 2 … n − 1 0,1,2\dots n-10,1,2…n−1)。正常只摘偶数下标树上苹果先把所有偶数位置总和算出来记为sum。最多反转一次区间([l,r])可以不反转区间内数组顺序颠倒。求操作后偶数下标最多能拿到多少苹果。反转区间会发生什么 区间内部位置奇偶发生交换 原来偶数下标 ⇔ 变成奇数下标原来奇数下标 ⇔ 变成偶数下标。 区间外面位置完全不变。反转([l,r])带来的收益区间里奇数位置的苹果现在可以被摘区间里原本偶数位置苹果现在不能摘。 收益 区间内奇数位置苹果和 −区间内偶数位置苹果和。 我们希望找到最大收益加到原始 sum 上。核心思路只有 l与r奇偶性不同时反转才会改变偶数位集合l偶r奇反转后(l,l1;l2,l3…)两两交换。收益序列(a [ l 1 ] − a [ l ] , a [ l 3 ] − a [ l 2 ] … a[l1]-a[l],\ a[l3]-a[l2]…a[l1]−a[l],a[l3]−a[l2]…)l奇r偶反转后收益序列(a [ l ] − a [ l 1 ] , a [ l 2 ] − a [ l 3 ] … a[l]-a[l1],\ a[l2]-a[l3]…a[l]−a[l1],a[l2]−a[l3]…)所以拆成两组差分v1i为偶数起点(a[i1]-a[i])(i0,2,4…)对应l偶r奇的反转收益单元v2i为奇数起点(a[i]-a[i1])(i1,3,5…)对应l奇r偶的反转收益单元问题转化在 v1、v2 数组分别求最大子段和得到mx1、mx2。如果最大子段是负数代表不如不反转收益取 0。答案(s u m max ⁡ ( m x 1 , m x 2 , 0 ) \boldsymbol{sum\max(mx1,mx2,0)}summax(mx1,mx2,0))#includebits/stdc.h using namespace std; typedef long long ll; vectorllv1,v2; int main(){ v1.clear(); v2.clear(); int n; cinn; ll sum0; vectorlla(n,0); for(int i0;in;i){ cina[i]; if(i%20)suma[i]; } for(int i1;in-1;i2){ v1.push_back(a[i]-a[i1]); } for(int i0;in-1;i2){ v2.push_back(a[i1]-a[i]); } ll mx10,mx20; ll ans10,ans20; for(int i0;iv1.size();i){ ans1max(v1[i],ans1v1[i]); mx1max(mx1,ans1); } for(int i0;iv2.size();i){ ans2max(v2[i],ans2v2[i]); mx2max(mx2,ans2); } coutsummax(mx1,mx2)endl; return 0; }I题题意n 行 m 列网格图。 每次查询((x,y))触发耳鸣距离( ( x , y ) ≤ a ) ((x,y)\le a)((x,y)≤a)的所有格子都被探测覆盖。 最后求至少被 1 次查询覆盖的格子总数量。 距离是欧几里得距离(( x 1 − x 2 ) 2 ( y 1 − y 2 ) 2 ≤ a \sqrt{(x_1-x_2)^2(y_1-y_2)^2}\le a(x1​−x2​)2(y1​−y2​)2​≤a)等价(( d x ) 2 ( d y ) 2 ≤ a 2 (dx)^2(dy)^2 \le a^2(dx)2(dy)2≤a2)约束(n ⋅ m ≤ 10 6 ) ( q × a ≤ 10 6 n\cdot m\le10^6)(q\times a \le 10^6n⋅m≤106)(q×a≤106)。思路把二维网格一维化一维差分diff做区间加。对于一次查询((x,y)) 遍历每一行jj的范围 ([ x − a , x a ] [x-a,\ xa][x−a,xa])同时要钳位到([1,n])。 (d x ∣ j − x ∣ dx|j-x|dx∣j−x∣)(d x 2 d y 2 ≤ a 2 ⟹ d y 2 ≤ a 2 − d x 2 dx^2dy^2 \le a^2 \implies dy^2 \le a^2-dx^2dx2dy2≤a2⟹dy2≤a2−dx2) (l e n ⌊ a 2 − d x 2 ⌋ len\lfloor \sqrt{a^2-dx^2} \rfloorlen⌊a2−dx2​⌋) 本行j有效列区间 ([ y ‑ l e n , y l e n ] [y‑len,\ ylen][y‑len,ylen])钳位([1,m])记(l,r)。第j行一维下标起点((j‑1)*m1)。 本行区间([l,r])对应一维下标 (L(j‑1)*m l) (R(j‑1)*m r) 一维差分diff[L]diff[R1]--。全部查询做完遍历一维数组求前缀和k。 只要k0这个格子被至少一次耳鸣覆盖计数 1输出总数。#includebits/stdc.h #define int long long using namespace std; void solve(){ int n, m, a, q; cin n m a q; vectorint diff(n * m 5, 0); for(int i 1; i q; i){ int x, y; cin x y; for(int j max(1ll, x - a); j min(n, x a); j){ int sheng a * a - (x - j) * (x - j); int len (int)(sqrt(sheng)); while((len 1) * (len 1) sheng){ len; } int l max(1ll, y - len), r min(m, y len); diff[(j - 1) * m l]; diff[(j - 1) * m r 1]--; } } int ans 0, k 0; for(int i 1; i n * m; i){ k diff[i]; if(k! 0){ ans; } } cout ans \n; return; } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); return 0; }