Atcoder347 A到E 题解
2025-12-20 23:02:05
发布于：浙江
19阅读
0回复
0点赞
省流：ABC过水，DE说得过去
你AT还在蒸蒸日上
A:
，秒了。
B:
纯模拟，过。
C:
贪心，按照 的顺序排序得出排序 ，可以证明这一定是最优的
于是我们枚举 从 ，显然，若存在 ，立刻输出 即可。
代码略，下边给出策略证明：
设 为乘坐雪橇的驯鹿集合。则题目条件可表示为：
将 代入上式，可得：
由于等式右侧为常数，最优策略就是按照 排序。
D:
推理，对于 ,令其在 中第一个 的下标为 ,,易证易得 的贡献为：
读者自证不难
用二分和前缀和分别计算 和 即可
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
int n,m,a[300010],b[300010],sm[300010];
signed main()
{
cin>>n>>m;
for (int i=1;i<=n;++i){
cin>>a[i];
}
for (int i=1;i<=m;++i){
cin>>b[i];
}
sort(b+1,b+1+m);
for (int i=1;i<=m;++i){
sm[i]=sm[i-1]+b[i];
}
int ans=0;
for (int i=1;i<=n;++i){
int l=1,r=m,rt=0;
bool f=0;
while (l<=r){
int mid=(l+r)/2;
if (b[mid]>=a[i]){
f=1;
rt=mid;
r=mid-1;
}else{
l=mid+1;
}
}
if (rt==0){
ans=(ans+abs(sm[m]-m*a[i]))%mod;
}else{
ans=(ans+abs(sm[rt-1]-(rt-1)*a[i]))%mod;
ans=(ans+abs((sm[m]-sm[rt-1])-(m-rt+1)*a[i]))%mod;
}
}
cout<<ans%mod<<endl;
return 0;
}
E:
谁懂我最后一分钟调出来的救赎感
注意到对于数列 ,他总是可以从 经过一系列操作到达，于是我们考虑建立数列间的关系树。
(以下定义 为下标不同但字典序相同的数列，可以理解为一个数列的重复，但下方推理时默认其为一个数列)
于是我们可以定义 为数列 在关系树中对应的节点， 意为在数列 后加入一个数 后所得到的新数列，然后定义 为数列为 的集合。
如果还不能理解，请结合下图理解：
最后，题目要求输出 的字典序排序，只需要按照我们这里建立的关系树，从 开始，按照 中 的大小升序遍历，每到一个非根节点就输出当前节点中 所存储的所有数列小标即可，可以证明这是对的。
当然，如果还不懂的话，建议看看下方代码，有详细的解释（比赛结束后加的）。
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node{
vector<int> ars;//上方定义的 S
int va;//由上个节点数列拼接到此节点的数列所用的权值
void init(){
ars.clear();
va=0;
}
};
int n,ct;//题目意思，逻辑树节点数量
unordered_map<int,node> tr[300010];//逻辑树
vector<int> vas[300010];//节点 i 对应的数列 A 在树中可以加的所有值（也就是说存在A_j=add(A_i,vas[idx_A_i])）
int tri[300010];//序列 i 在树中对应的节点
bool vis1[300010];//用于判断vas[tri[u]]是否已经排序过
unordered_map<int,bool> vis[300010];//判断tr[u][va]是否被访问过
void ins(int u,int y,int na){
if (tr[u][y].ars.size()==0){
tri[na]=++ct;
tr[u][y].ars.push_back(na);
tr[u][y].va=y;
return ;
}else{
tri[na]=tri[tr[u][y].ars[0]];
tr[u][y].ars.push_back(na);
}
}
void dfs(int u){
for (int i=0;i<vas[u].size();++i){
int v=vas[u][i];
//cout<<"B "<<u<<" "<<v<<endl;
//cout<<"A ";
if (vis[u][v])continue;
for (int j=0;j<tr[u][v].ars.size();++j){
cout<<tr[u][v].ars[j]<<" ";
}
dfs(tri[tr[u][v].ars[0]]);
vis[u][v]=1;
}
}
signed main()
{
cin>>n;
for (int i=1;i<=n;++i){
int x,y;
cin>>x>>y;
ins(tri[x],y,i);
vas[tri[x]].push_back(y);
}
// for (int i=0;i<=n;++i){
// cout<<tri[i]<<" ";
// }
// cout<<endl;
for (int i=0;i<=n;++i){
if (vis1[tri[i]])continue;
sort(vas[tri[i]].begin(),vas[tri[i]].end());
vis1[tri[i]]=1;
// cout<<"V "<<tri[i]<<" ";
// for (int j=0;j<vas[tri[i]].size();++j){
// cout<<vas[tri[i]][j]<<" ";
// }
// cout<<endl;
}
dfs(0);
return 0;
}
有帮助，赞一个