Atcoder347 A到E 题解

不会C++的noah

2025-12-20 23:02:05

发布于：浙江

29阅读

0回复

0点赞

省流：ABC过水，DE说得过去
~~你AT还在蒸蒸日上~~

A:
$ans=12a+b$ ，秒了。

B:
纯模拟，过。

C:
贪心，按照 $p_i+w_i$ 的顺序排序得出排序 $a'$ ，可以证明这一定是最优的
于是我们枚举 $k$ 从 $n \to 0$ ，显然，若存在 $\sum_{1 \le i \le k}w_i \le \sum_{k+1 \le i \le n}p_i$ ，立刻输出 $k$ 即可。
代码略，下边给出策略证明：
设 $S$ 为乘坐雪橇的驯鹿集合。则题目条件可表示为：

$\sum_{i \notin S} p_i \geq \sum_{i \in S} w_i$

将 $\sum_{i \notin S} p_i = \sum_{i=1}^n p_i - \sum_{i \in S} p_i$ 代入上式，可得：

$\sum_{i \in S} (w_i+p_i) \leq \sum_{i=1}^n P_i$

由于等式右侧为常数，最优策略就是按照 $w_i+p_i$ 排序。

D:
推理，对于 $a_i$ ,令其在 $b$ 中第一个 $>=a_i$ 的下标为 $rt$ , $sm_i=\sum_{1 \le j \le i}b_i$ ,易证易得 $a_i$ 的贡献为：

$|sm_{rt-1}-(rt-1)a_i)|+|(sm_m-sm_{rt-1})-(m-rt+1)a_i|$

~~读者自证不难~~

用二分和前缀和分别计算 $sm_i$ 和 $rt$ 即可

代码：

#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:
~~谁懂我最后一分钟调出来的救赎感~~

注意到对于数列 $A_i$ ,他总是可以从 $A_0$ 经过一系列操作到达，于是我们考虑建立数列间的关系树。

(以下定义 $S$ 为下标不同但字典序相同的数列，可以理解为一个数列的重复，但下方推理时默认其为一个数列)

于是我们可以定义 $idx_{A_i}$ 为数列 $A_i$ 在关系树中对应的节点， $add(A,v)$ 意为在数列 $A$ 后加入一个数 $v$ 后所得到的新数列，然后定义 $tr_{S,v}$ 为数列为 $add(S,v)$ 的集合。
如果还不能理解，请结合下图理解：

最后，题目要求输出 $A_1,A_2,\cdots,A_n$ 的字典序排序，只需要按照我们这里建立的关系树，从 $0(A_0(\because idx_{A_0}=0))$ 开始，按照 $tr_{S,v}$ 中 $v$ 的大小升序遍历，每到一个非根节点就输出当前节点中 $S$ 所存储的所有数列小标即可，可以证明这是对的。

当然，如果还不懂的话，建议看看下方代码，有详细的解释（比赛结束后加的）。

代码：

#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;
}

有帮助，赞一个

去预览

0/2000

全部评论 4

Eucatastrophe‌
昨天没打

2025-12-21 来自浙江
0
cjdst
感觉这场质量挺高的，应该就是正常ABC水平（除了D），没有出板题糊弄人

2025-12-20 来自广东
0
- 不会C++的noah
  回复
  cjdst
  EE,我觉得 D 也没有那么板子吧（至少我没做过）
  
  2025-12-21 来自浙江
  0
- cjdst
  回复
  不会C++的noah
  D应该是一般ABC C水平
  
  2025-12-21 来自广东
  0
cjdst
/bx

2025-12-20 来自广东
0
不会C++的noah
ddd

2025-12-20 来自浙江
0

全部评论 4

热门讨论