G-wnd的魔法排序_河南萌新联赛2026第三场郑州轻工业大学解题过程涉及:DFS回溯搜索剪枝关键是确定全排列的条件 直接DFS回溯举例:eg: n 4[1,2,3,4]- -[1,4,3,2]–[2,1,4,3]–[2,3,4,1][3,2,1,4]–[3,4,1,2]–[4,1,2,3]–[4,3,2,1]变量:step当前正在填充第 step 个位置。ans 数组保存当前正在构造的排列。b 布尔数组标记数字是否已经被选过防止数字重复选取。prime 函数接收一个整数判断这个数是不是质数。条件:题目中很明显的无重复数字与相邻的一个数相加为质数第一步除外DFS出口:当 step 等于 n1代表 1~n 共 n 个数字已经全部填进 ans 数组此时直接打印当前 ans 里面的序列函数返回。实现代码#includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second #define YES coutYESendl; #define NO coutNOendl; using namespace std; ll n; ll ans[20]{0}; bool b[20]{0}; bool prime(ll x) { if(x2) return 0; if(x2)return 1; for(ll i2;i*ix;i) { if(x%i0) { return 0; } } return 1; } void dfs(ll step) { if(stepn1) { for(ll i1;in;i) { if(i1) { cout ; } coutans[i]; } coutendl; return ; } for(ll i1;in;i) { if(b[i]) { continue; } if(step!1!prime(ans[step-1]i)) { continue; } ans[step]i; b[i]true; dfs(step1); b[i]false; } } int main() { IOS cinn; dfs(1); // coutfixedsetprecision(x) ; return 0; }I-遗迹核心的临界容差_河南萌新联赛2026第三场郑州轻工业大学解题过程一个简单的二分实现代码#includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second #define YES coutYESendl; #define NO coutNOendl; using namespace std; ll n; vectorllc; ll cnt; ll k; bool check(ll x) { cnt0; for(ll i0;ic.size();i) { if(xc[i]) { cnt; } } return cntk-1; } int main() { IOS cinnk; vectorlla(n1); for(ll i1;in;i) { cina[i]; } for(ll i1;in;i) { c.push_back(abs(a[i]-a[i1])); } ll l0; ll r1e9; ll ans1e9; while(lr) { ll mid(lr)/2; if(check(mid)) { ansmid; rmid-1; } else { lmid1; } } coutansendl; // coutfixedsetprecision(x) ; return 0; }E-传话_河南萌新联赛2026第三场郑州轻工业大学有N NN个人编号为1 11到N NN。对于每个人i ii有一个固定的传话人p i p_ipi​。当p i p_ipi​知道消息后他会把消息传给i ii对应一条有向边p i → i p_i \to ipi​→i。p i p_ipi​可以重复也允许p i i p_iipi​i。因此每个人恰好有一个直接消息来源而一个人可以把消息传给任意多个人。收到消息的人会按相同规则继续传话。一个人重复收到消息不会产生新的影响。开始时你需要恰好选择一个人让他知道消息。求最终知道消息的人数的最大值。输入第一行输入一个整数T TT表示测试用例数。每个测试用例包含两行第一行输入一个整数N NN。第二行输入N NN个整数p 1 , p 2 , … , p N p_1,p_2,\ldots,p_Np1​,p2​,…,pN​。保证1 ≤ T ≤ 10 1\le T\le 101≤T≤101 ≤ N ≤ 2 × 10 5 1\le N\le 2\times 10^51≤N≤2×1051 ≤ p i ≤ N 1\le p_i\le N1≤pi​≤N所有测试用例的N NN之和不超过4 × 10 5 4\times 10^54×105。输出对于每个测试用例输出一行一个整数表示最终知道消息的人数的最大值。涉及:拓扑排序 内向基环树解题过程我们需要去求每个连通块的总大小(环环上挂树) 也算是去找最大的环难点:图里有环普通的DFS不能跑树和环也得分开处理说到环 (知道消息的人) 可以用拓扑排序把树上的点(未收到消息的人) 都处理掉然后剩下的就都是环了拓扑排序本来的用途就是:DAG有向无环图处理先后关系虽然基环树不是DAG但外面的树都是DAG关键是看到:每个点只有一条出边 → 内向基环树有环不能直接 DFS → 拓扑剥离树部分剩下找环sz 在拓扑过程向上累加环上遍历求和实现代码#includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second #define YES coutYESendl; #define NO coutNOendl; using namespace std; ll n; int main() { IOS ll t; cint; while(t--) { cinn; vectorlla(n1); vectorlldeg(n1,0); ll t0; vectorllsz(n1,1); vectorboolvis(n1,0); for(ll i1;in;i) { cina[i]; deg[a[i]]; } queuellq; for(ll i1;in;i) { if(deg[i]0) { q.push(i); } } while(!q.empty()) { ll tq.front(); q.pop(); ll faa[t]; sz[fa]sz[t]; deg[fa]--; if(deg[fa]0) { q.push(fa); } } ll ans0; for(ll i1;in;i) { if(!vis[i]deg[i]) { ll cnt0; ll ci; while(!vis[c]) { vis[c]1; cntsz[c]; ca[c]; } ansmax(ans,cnt); } } coutansendl; } // coutfixedsetprecision(x) ; return 0; }A-能量任务_河南萌新联赛2026第三场郑州轻工业大学涉及:二分解题过程看到关键词最小初始能量就想到用二分刚看到这个题目时居然没看出来是二分这个题最主要的还是cmp函数和check函数的写法关于cmp比较函数如果d0时对于这些数据是第一个想法肯定是先门槛最低的h任务去完成如果 d0的话如果有一组数据 中都d0的话 优先选择加上d后 能量数据大的如果一组数据中一方d0 另一方d0 优先选择 d大的代码实现#includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second #define YES coutYESendl; #define NO coutNOendl; using namespace std; ll n; struct da{ ll h; ll d; }a[200005]; bool check(ll mid) { ll xmid; for(ll i1;in;i) { if(xa[i].h) { return false; } else { xa[i].d; } } return true; } bool cmp(da a,da b) { if(a.d0||b.d0) { if(a.d0b.d0) { ll ca.ha.d; ll db.hb.d; return cd; } else { return a.db.d; } } return a.hb.h; } int main() { IOS cinn; for(ll i1;in;i) { cina[i].ha[i].d; } sort(a1,an1,cmp); ll l0; ll rLLONG_MAX; ll ans; ll mid; while(lr) { mid(lr)/2; if(check(mid)) { ansmid; rmid-1; } else { lmid1; } } coutansendl; // coutfixedsetprecision(x) ; return 0; }B-三色平衡_河南萌新联赛2026第三场郑州轻工业大学解题过程涉及:前缀差分 哈希存二元状态根据题目就可以知道是 让统计0、1、2相等连续区间的长度假如说是用一个cnt0、cnt1、cnt2数据存储数量那么在起始区间i到连续区间下标pos就有cnt0[pos]-cnt0[i]cnt2[pos]-cnt2[i]cnt0[pos]-cnt0[i]cnt1[pos]-cnt1[i]经过交换就可以得到两个这样的等式cnt2[i]-cnt0[i]cnt2[pos]-cnt0[pos]cnt1[i]-cnt0[i]cnt1[pos]-cnt0[pos]也就是说 如果区间 ([i,pos]) 满足 0、1、2 个数相等 – 前缀 i、前缀 pos 的两个差值一定相等。结论:只要两个前缀位置 (i,j) 的这两个差值完全一样中间子数组就合法{ t (cnt0-cnt1, cnt0-cnt2) }代码实现#includebits/stdc.h #define ll long long #define endl \n #define pii pairll,ll #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second #define YES coutYESendl; #define NO coutNOendl; using namespace std; mappii,llmp; int main() { IOS string s; ll n; cinn; cins; ll cnt00; ll cnt10; ll cnt20; ll ans0; mp[{0,0}]0; for(ll i1;in;i) { char cs[i-1]; if(c0) { cnt0; } if(c1) { cnt1; } if(c2) { cnt2; } pii t{cnt0-cnt1,cnt0-cnt2}; if(mp.count(t)) { ansmax(ans,i-mp[t]); } else { mp[t]i; } } coutansendl; // coutfixedsetprecision(x) ; return 0; }C-余数清理_河南萌新联赛2026第三场郑州轻工业大学涉及:同余解题过程全部总和sum-区间和%m0%msum-(pre[i]-pre[pos])%m0%mpre[pos]pre[i]-sum%msum%mtarpre[n];pre[pos]pre[i]-tar所以need(pre[i]-tar)%m代码实现#includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second #define YES coutYESendl; #define NO coutNOendl; using namespace std; ll n; ll m; int main() { IOS cinnm; vectorlla(n1,0); vectorllpre(n1,0); for(ll i1;in;i) { cina[i]; pre[i](pre[i-1]a[i])%m; } ll tarpre[n]; ll lenn1; vectorlllst(m,-1); lst[0]0; for(ll i1;in;i) { //区间和(pre[i]-pre[pos])%mtar%m ll need(pre[i]-tarm)%m; // pre[pos] (pre[i]-tar) mod m if(lst[need]!-1) { ll deli-lst[need]; if(deln) { lenmin(len,del); } } lst[pre[i]]i; } if(lenn) { cout-1endl; } else { coutn-lenendl; } // coutfixedsetprecision(x) ; return 0; }