IOI 竞赛模拟试题（含详细答案解析）

IOI竞赛模拟试题（含详细答案解析）考试说明1.本套试题适配国际信息学奥林匹克竞赛中档难度，共2道大题，满分200分，考试时长3小时。2.程序必须读取标准输入、输出标准输出，无文件读写、无特殊调用。3.时间限制：每题1秒；空间限制：256MB。4.数据梯度包含：样例数据、小规模暴力数据、大规模极限数据，覆盖全部得分点。题目一：区间最优覆盖（100分）题目描述给定数轴上的n个闭区间，每个区间拥有左右端点[li,ri]以及对应的价值输入格式第一行一个整数n，表示区间数量。接下来n行，每行三个整数li输出格式输出一行一个整数，为可选区间的最大总价值。数据范围1≤n≤105，1≤样例输入5135243356674587样例输出13样例解释最优选择：区间[1,3]（价值5）+[5,8]（价值7），总价值12？修正：实际最优为[3,5]（6）+[5,8]（7），总价值13，两区间端点重合不冲突，符合规则。题目一详细答案解析1.解题思路本题是经典的带权区间不重叠最大选点问题，区别于无权贪心区间选点，带权场景无法直接贪心，必须使用动态规划+二分优化。核心逻辑：①先将所有区间按照右端点从小到大排序，保证处理区间时，前面的区间右端点都不大于当前区间；②定义dp[i]为处理前i个区间的最大价值；③对于第i个区间，有两种选择：不选该区间，dp[i]=dp[i-1]；选该区间，则需要找到最后一个不与该区间重叠的区间j，此时dp[i]=dp[j]+w[i]；④两种情况取最大值，即为当前最优解；⑤由于n达到1e5，遍历找j会超时，用二分查找快速定位合法j，将复杂度优化至O(nlog2.得分点拆解-30分：暴力DP，O(n-70分：排序+朴素二分，细节缺失导致部分边界出错；-100分：完整排序+二分优化DP，处理所有边界情况。3.完整AC代码（C++）cpp

#include<bits/stdc++.h>

usingnamespacestd;

typedeflonglongll;

constintN=1e5+10;

structNode{

intl,r,w;

}seg[N];

lldp[N];

intr_pos[N];//存储排序后的区间右端点，用于二分

boolcmp(Nodea,Nodeb){

returna.r<b.r;

}

intmain(){

intn;

cin>>n;

for(inti=1;i<=n;i++){

cin>>seg[i].l>>seg[i].r>>seg[i].w;

}

//按右端点排序

sort(seg+1,seg+n+1,cmp);

//预处理右端点数组

for(inti=1;i<=n;i++){

r_pos[i]=seg[i].r;

}

//DP转移

for(inti=1;i<=n;i++){

//不选当前区间

dp[i]=dp[i-1];

//二分找最后一个右端点<=当前区间左端点的区间

intl=0,r=i-1,res=0;

while(l<=r){

intmid=(l+r)/2;

if(r_pos[mid]<=seg[i].l){

res=mid;

l=mid+1;

}else{

r=mid-1;

}

}

//选当前区间的最优解

dp[i]=max(dp[i],dp[res]+seg[i].w);

}

cout<<dp[n]<<endl;

return0;

}题目二：最短路约束计数（100分）题目描述给定一张n个点、m条边的无向带权连通图，边权均为正整数。定义1号点为起点，对于每个点u，设dis[u]为起点到u的最短路长度。现在需要统计：图中满足dis[v]=dis[u]+len(u,v)的有向边(u→v)的数量（len(u,v)为边u-v的权值）。简单来说，统计所有处于最短路上的单向边数量。输入格式第一行两个整数n,m，分别为点数、边数。接下来m行，每行三个整数u,v,w，表示u和v之间有一条权值为w的无向边。输出格式输出一行一个整数，为合法单向边的总数量。数据范围1≤n≤105，1≤m≤2×样例输入33121231133样例输出4样例解释起点1的最短路：dis[1]=0，dis[2]=1，dis[3]=2。合法边：1→2、2→1、2→3、3→2，共4条。边1→3、3→1不满足最短路约束，不计入答案。题目二详细答案解析1.解题思路本题结合最短路算法与图论计数，是IOI高频综合题型，核心分为两步：①求解单源最短路：由于边权为正，使用堆优化Dijkstra算法，在O(mlog②遍历所有无向边，拆解为两条单向边，逐一校验约束条件：对无向边(u,v,w)，校验两个条件：-若dis[v]==dis[u]+w，则u→v合法，计数+1；-若dis[u]==dis[v]+w，则v→u合法，计数+1；最终累计所有合法单向边即为答案。2.易错点说明1.无向边必须拆分为两条单向边单独判断，不能只判断单向；2.必须使用堆优化Dijkstra，朴素Dijkstra会超时，SPFA无法应对正权大图数据；3.最短路数组需初始化为极大值，避免初始值干扰判断。3.得分点拆解-40分：朴素Dijkstra+暴力枚举，超时，仅过小数据；-80分：堆优化Dijkstra，遗漏单向边拆分，计数错误；-100分：完整优化+双向校验，覆盖全部数据。4.完整AC代码（C++）cpp

#include<bits/stdc++.h>

usingnamespacestd;

typedeflonglongll;

typedefpair<ll,int>pli;

constintN=1e5+10;

constllINF=1e18;

vector<pair<int,int>>g[N];

lldis[N];

intn,m;

//堆优化Dijkstra

voiddijkstra(){

fill(dis,dis+n+1,INF);

priority_queue<pli,vector<pli>,greater<pli>>q;

dis[1]=0;

q.push({0,1});

while(!q.empty()){

auto[d,u]=q.top();

q.pop();

if(d>dis[u])continue;

for(auto[v,w]:g[u]){

if(dis[v]>dis[u]+w){

dis[v]=dis[u]+w;

q.push({dis[v],v});

}

}

}

}

intmain(){

ios::sync_with_stdio(false);

cin.tie(0);

cin>>n>>m;

vector<tuple<int,int,int>>edge;

for(inti=1;i<=m;i++){

intu,v,w;

cin>>u>>v>>w;

g[u].emplace_back(v,w);

g[v].emplace_back(u,w);

edge.emplace_back(u,v,w);

}

dijkstra();

intans=0;

//遍历所有边，统计合法单向边

for(auto[u,v,w]:edge){

if(dis[v]==dis[u]+w)ans++;

if(dis[u]==dis