2026 ICPC EC网络预选赛第一场-171主机测评

第一次打网络赛，真是惨败收场呀，一定要好好补题了

下面将由我认为的难度顺序讲一下网络赛的几道题

F 50 Years Of Excellent

签到题

M Check In

map

C Permutation Inversions

拓扑排序+单调队列

D Sequence

贪心+构造

贪心证明

一、先回到最本质的对应关系

二、核心定理：切换字符会让小值永久消失

三、贪心策略的严格证明

A Recall

离散化/map+模拟+贪心

题目大意

为什么直接模拟不可行？

核心思路：过期时间标记 + 惰性弹出

关键观察

步骤一：预处理每个压入操作的过期时间

步骤二：正序遍历，惰性弹出栈顶

为什么这个逻辑是严谨的？

L Longest Common Prefix

字典树

F 50 Years Of Excellent

签到题

#include<bits/stdc++.h>
using namespace std;
const int N=55;
int main()
{
int n,m;
cin>>n>>m;
int last=0;
int res=0;
for(int i=1;i<=n;i++)
{
int sum=0;
for(int j=1;j<=m;j++)
{
int x;
cin>>x;
sum+=x;
}
if(sum<last)res++;
last=sum;
}
cout<<res<<endl;
return 0;
}

M Check In

map

这个题也比较简单，用map存一下字符串就好了

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
unordered_map<string,int>mp;
unordered_map<string,int>a;
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
string s;
cin>>s;
mp[s]++;
}
for(int i=1;i<=m;i++)
{
string s;
cin>>s;
if(mp[s]==0)
{
cout<<"WRONG"<<endl;
}
else if(a[s]==0)
{
a[s]++;
cout<<"OK"<<endl;
}
else cout<<"REPEAT"<<endl;
}
return 0;
}

C Permutation Inversions

拓扑排序+单调队列

这个题当时真是应该想到的

我们可以根据题目给出的大小关系构建一个拓扑图，小的指向大的，p1->p2->p3…..

最后遍历整个图，按照拓扑序赋值，但是由于题目要求最后的答案逆序对尽可能小，也就是要字典序最小的答案，我们就不能只是简单的BFS，而是要用单调队列

如果图中存在环，即最后遍历的点数<n,那么就输出-1

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int t,n,m;
int e[N],ne[N],h[N],idx;
int q[N];
int d[N];
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int res[N];
int main()
{
cin>>t;
while(t–)
{
cin>>n>>m;
vector<pair<int,int>>edges;
for(int i=1;i<=m;i++)
{
int l,r;
cin>>l>>r;
int k=r-l+1;
for(int j=0;j<k;j++)
{
cin>>q[j];
}
for(int j=0;j<k-1;j++)
{
edges.push_back({q[j],q[j+1]});
}
}
sort(edges.begin(),edges.end());
edges.erase(unique(edges.begin(),edges.end()),edges.end());
for(int i=1;i<=n;i++)h[i]=-1;
for(int i=1;i<=n;i++)d[i]=0;
idx=0;
for(int i=0;i<edges.size();i++)
{
int a=edges[i].first,b=edges[i].second;
add(a,b);
d[b]++;
}
priority_queue<int,vector<int>,greater<int>>heap;
for(int i=1;i<=n;i++)
{
if(!d[i])heap.push(i);
}
int cnt=0;
while(heap.size())
{
int t=heap.top();
heap.pop();
res[t]=++cnt;
for(int i=h[t];i!=-1;i=ne[i])
{
int j=e[i];
if(–d[j]==0)
{
heap.push(j);
}
}
}
if(cnt!=n)cout<<-1<<endl;
else
{
for(int i=1;i<=n;i++)cout<<res[i]<<' ';
cout<<endl;
}
}
return 0;
}

D Sequence

贪心+构造

这个题当时做的时候真是吃了英语不好的亏了，不知道multiset是什么意思，不然是能做出来的

很显然，这个结果一定是2的x次方,因为每个位置只能有两个取值，0或1

那么，什么时候*2呢？

当第i位取0或者取1值都一样时，res就该*=2，即p[i-1]==(i-1)-p[i-1]时，和前一位有关系

当p[i-1]!=(i-1)-p[i-1]时，该取什么值呢？

这里有一个关键的结论：先取较小的一个

为什么呢？根据感觉，较小的值，肯定时更稀缺，因为p肯定时有一个越来越大的趋势，但是“稀缺”这个概念比较感性，于是我让AI给了我一个比较严谨的数学证明

贪心证明

一、先回到最本质的对应关系

我们先把 p 值和 01 串的对应关系扒透：设前 (i-1) 位里，有 (c_0) 个 0，(c_1) 个 1，显然 (c_0 + c_1 = i-1)。

如果第 i 位选0：和它不同的字符是 1，共 (c_1) 个 → (p_i = c_1)
如果第 i 位选1：和它不同的字符是 0，共 (c_0) 个 → (p_i = c_0)

所以每一步的两个候选值，本质就是当前的 (c_0) 和 (c_1)。选哪个候选值，等价于选当前位放哪个字符。

二、核心定理：切换字符会让小值永久消失

假设当前 (c_0 < c_1)（也就是两个候选值 (a=c_0)，(b=c_1)，(a<b)）。

我们来看两种选择的后果：

选小的 a（放 1）：1 的数量加 1 → 新的 (c_1' = c_1+1)，(c_0) 不变。下一步的两个候选值还是 (c_0) 和 (c_1+1)，a 这个值还在。

选大的 b（放 0）：0 的数量加 1 → 新的 (c_0' = c_0+1)，(c_1) 不变。下一步的两个候选值变成 (c_0+1) 和 (c_1)，(a = c_0) 这个值永久消失了。因为之后 (c_0) 只会越来越大（放 0 就加 1，放 1 就不变），再也不会回到 (c_0) 这个数值。

三、贪心策略的严格证明

命题：如果当前小候选值 a 还有库存，就必须优先选 a，否则必然无解。

反证法：假设当前 a 还有库存，但我们选了大的 b（切换字符）。根据上面的结论，a 这个值会永久消失，后续所有步骤的候选值都不会再出现 a。而库存里还剩有 a，意味着这些 a 再也没有机会被用掉了，最终库存无法清零，和 “题目有解” 矛盾。

因此，只要小值还有库存，就绝对不能切换字符，必须一直选小值，直到把它用完。这就是 swap(a,b) 然后优先选小的的严格依据，不是凭感觉，是不选就一定会无解。

#include <iostream>
#include <cstdio>
#include <map>

using namespace std;

const int N = 100010;
const int MOD = 998244353;

int p[N];

int main()
{
int n;
scanf("%d", &n);

map<int, int> cnt;
for (int i = 0; i < n; i ++ )
{
int x;
scanf("%d", &x);
cnt[x] ++ ;
}

long long res = 1;
for (int i = 1; i <= n; i ++ )
{
int a = p[i – 1];
int b = (i – 1) – p[i – 1];

if (a > b) swap(a, b);

if (cnt[a] > 0)
{
p[i] = a;
cnt[a] — ;
}
else
{
p[i] = b;
cnt[b] — ;
}

if (a == b)
res = res * 2 % MOD;
}

printf("%lld\\n", res);
return 0;
}

A Recall

离散化/map+模拟+贪心

题目大意

我们有一个初始为空的栈，支持三种操作：

+ x：将元素 x 压入栈中

? x：查询元素 x 是否存在于栈中，查询结果分为 T x（存在）和 F x（不存在）

-：弹出栈顶元素（执行时保证栈非空）

现在给定一段操作的记录，但记录中只保留了所有的 + x 和 T x / F x，丢失了全部的 – 操作。请你补全所有的 – 操作，重构出完整的操作序列，满足：

任意时刻栈中的元素都互不重复

所有查询的结果都和记录完全一致输出任意一个合法的序列即可。

为什么直接模拟不可行？

很多同学会尝试按顺序直接模拟栈的操作：遇到 T 就保证元素在栈里，遇到 F 就保证元素不在栈里。但这种思路存在本质缺陷，最终一定会出错：

栈的操作限制：栈只能在栈顶进行压入和弹出，无法直接操作中间的元素。如果为了满足某个查询，需要弹出不在栈顶的元素，这本身就是非法操作，违反栈的基本规则。

保留时机无法判断：一个元素压入后，你无法提前知道它需要保留到什么时候。提前弹出会导致后面的 T 查询失败，一直保留又会导致后面的 F 查询失败，还可能引发重复元素的冲突。

边界情况复杂：重复压入同一元素、T 和 F 查询交替出现的场景，直接模拟需要大量回溯和状态调整，逻辑极易出错，几乎不可能覆盖所有边界。

核心思路：过期时间标记 + 惰性弹出

这道题的标准最优解是贪心策略，核心思想是「给每个压入操作标记存活期限，只在栈顶惰性清理过期元素」，完全贴合栈的操作特性。

关键观察

每个 + x 操作的核心意义，都是为了满足它之后某个 T x 查询的要求。如果一个压入的元素，后面已经没有需要它的 T 查询了，那它就失去了存在的价值，可以安全弹出。反过来，只要还没到最后一个需要它的查询，它就必须留在栈里。

步骤一：预处理每个压入操作的过期时间

我们先从前往后遍历一遍所有操作：

遇到 + x 时，记录下 x 最新一次压入的位置下标
遇到 T x 时，找到对应的最新一次 + x，把这个压入操作的「过期时间」设为当前查询的下标

含义：这个压入的元素，必须在栈里存活到本次查询执行完毕；过了这个位置，它就没有用了，可以弹出。

步骤二：正序遍历，惰性弹出栈顶

再次从前往后遍历所有操作：

遇到 + 操作：将该操作的下标压入栈，答案字符串追加 +
遇到 T 或 F 操作：答案字符串追加 ?
每一步操作执行完后，循环检查栈顶：如果栈顶元素的过期时间 ≤ 当前下标（说明它已经没用了），就弹出栈顶，答案字符串追加 –

为什么这个逻辑是严谨的？

完全符合栈的规则：永远只弹出栈顶元素，没有任何非法操作，完全满足栈的后进先出特性。

自动满足所有 T 查询：对应的压入操作在查询位置还没过期，所以一定还在栈里，查询结果必然是 T。

自动满足所有 F 查询：如果 x 应该不存在，那它对应的压入操作早就过期弹出了，自然不在栈里，查询结果必然是 F。

自动保证元素不重复：同一个 x 的新压入出现时，旧的压入一定已经过期被弹出，栈里不会同时存在两个相同的 x。

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

vector<int> alls;
struct Op
{
char c;
int x;
};
vector<Op> a;

int find(int x)
{
int l = 0, r = alls.size() – 1;
int ans = -1;
while(l <= r)
{
int mid = l + r >> 1;
if(alls[mid] >= x)
{
ans = mid;
r = mid – 1;
}
else l = mid + 1;
}
return ans + 1;
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while(t–)
{
int n;
cin >> n;
alls.clear();
a.clear();
a.resize(n);

for(int i = 0; i < n; i++)
{
char c;
int x;
cin >> c >> x;
alls.push_back(x);
a[i] = {c, x};
}

sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
int m = alls.size();

vector<int> last_push(m + 2, -1);
vector<int> expire(n, -1);

for(int i = 0; i < n; i++)
{
int fx = find(a[i].x);
if(a[i].c == '+')
{
last_push[fx] = i;
}
else if(a[i].c == 'T')
{
expire[last_push[fx]] = i;
}
}

stack<int> sk;
string res;
for(int i = 0; i < n; i++)
{
if(a[i].c == '+')
{
sk.push(i);
res += '+';
}
else
{
res += '?';
}

while(!sk.empty() && expire[sk.top()] <= i)
{
res += '-';
sk.pop();
}
}

cout << res << '\\n';
}
return 0;
}

L Longest Common Prefix

本来想着这个题就不补了，但是好心学长主动把AC代码发给我，怎么说也要补了呀

字典树

字典树（Trie）的每个节点对应一个公共前缀：

节点的深度 = 该前缀的长度
节点的 cnt 值 = 有多少个字符串经过该节点（即有多少个串拥有这个前缀）

由此可以得到关键结论：对于任意 j，f [i][j] 等于所有 cnt ≥ j 的节点中，最大的深度值。也就是说，能选出 j 个串共享的最长前缀，就是出现次数不少于 j 次的前缀里最长的那个。

基于这个结论，我们可以在逐个插入字符串的过程中，增量维护答案：每插入一个字符串，它经过的所有节点的 cnt 都会加 1。对于每个节点，当 cnt 变为 k 时，说明现在存在 k 个串共享长度为 depth 的前缀。如果 depth 比当前 ans [k]（选 k 个串的最大 LCP）更大，就更新 ans [k]，同时同步更新总和 sum。

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int son[N][26];
int cnt[N],idx;
int ans[N];
long long sum;

void insert(string str,int id)
{
int p=0;
int fg=-1;
for(int i=0;i<str.size();i++)
{
int u=str[i]-'a';
if(!son[p][u])son[p][u]=++idx;
p=son[p][u];
cnt[p]++;
if(i+1>ans[cnt[p]])
{
sum+=(i+1)^cnt[p];
if(cnt[p]!=id||ans[cnt[p]])
sum-=ans[cnt[p]]^cnt[p];
else
fg=1;
ans[cnt[p]]=i+1;
}
}
if(fg==-1)sum+=id;
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
string s;
cin>>s;
insert(s,i);
cout<<sum<<'\\n';
}
return 0;
}

我看了一下外榜，只要是能做对这六道题，就能给学校争取到区域赛的正式名额了

2026 ICPC EC网络预选赛第一场

F 50 Years Of Excellent

签到题

M Check In

map