2023-08-26 洛谷 Div3

Nwayy / 2023-08-27 / 原文

前言：得分是 \(350\) 分，其中 A 题 \(50\) 分。破防了。

A.（赛时没切）

题意：给定两个数轴上的点，求出原点到这两个点的最短路。值域 \(200\)。

赛时思路：对这两个点正负性分类讨论即可。但是阴差阳错地交错代码，最后喜提 \(50\) 分。痛失 AK。

code：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
int n,m,i,j,ans,a,b;
int main(){
	scanf("%d%d",&a,&b);
	if(a==0 && b==0) printf("0");
	else if(a==0) printf("%d",abs(b));
	else if(b==0) printf("%d",abs(a));
	else if(a<0 && b>0) printf("%d",abs(a)+abs(b)+min(abs(a),abs(b)));
	else if(a>0 && b<0) printf("%d",abs(a)+abs(b)+min(abs(a),abs(b)));
	else printf("%d",max(abs(a),abs(b)));
	return 0;
}

B.（赛时切了）

题意：给定 \(n \times m\) 的地图，定义点 \(a_{i,j}\) 的朋友个数为与 \((i,j)\) 不相邻的格子且权值等于 \(a_{i,j}\) 的格子个数。\(1 \le n,m \le 2000\)，\(1 \le a_{i,j} \le 9\)。

赛时思路：考虑值域很小，用桶记录每个数出现次数，枚举 \(a_{i,j}\)，减去相邻等于自己的个数，累加即可。复杂度 \(O(nm)\)。

code：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
#define N 2005
#define ll long long
int n,m,i,j,mp[N][N],s[15];
ll ans;
int main(){
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++) scanf("%d",&mp[i][j]),s[mp[i][j]]++;
	}
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			int k=1;
			if(mp[i+1][j]==mp[i][j]) k++;
			if(mp[i-1][j]==mp[i][j]) k++;
			if(mp[i][j+1]==mp[i][j]) k++;
			if(mp[i][j-1]==mp[i][j]) k++;
			ans+=(ll)s[mp[i][j]]-(ll)k;
		}
	}
	printf("%lld\n",ans);
	return 0;
}

C.（赛时切了）

给定 \(n \times m\) 的地图，进行 \(q\) 次操作，每次选定某行或某列，进行全行加或全列加，输出最后每个格子对 \(k\) 取模非 \(0\) 的个数。\(1 \le n,m,q,k \le 5 \times 10^5\)。

赛时思路：全行加或全列加直接打上标记，然后统一对行和列取模，然后我们枚举行，看看哪些列与这行相加取模后非 \(0\)，由于我们已经取模，所以当前行必定 \(<k\)，所有列也必定 \(<k\)，加起来取模为 \(0\) 只有可能相加为 \(k\)，所以提前用桶记录对 \(k\) 取模后剩余的情况，当前行贡献即为总列数减去相加为 \(k\) 的个数，对于当前行为 \(0\) 的情况特判一下即可。复杂度线性。

code：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
#define N 500005
#define int long long
int n,m,i,j,ans,q,opt,x,k,h[N],l[N],mp[N],s;
signed main(){
	scanf("%lld%lld%lld%lld",&n,&m,&q,&k);
	while(q--){
		scanf("%lld%lld",&opt,&x);
		if(opt==1) h[x]++;
		if(opt==2) l[x]++;
	}
	for(i=1;i<=n;i++) h[i]%=k;
	for(i=1;i<=m;i++) l[i]%=k,mp[l[i]]++;
	for(i=1;i<=m;i++) if(l[i]) s++;
	for(i=1;i<=n;i++){
		if(h[i]==0){ans+=s;continue;}
		int p=m-mp[k-h[i]];
		ans+=p;
	}
	printf("%lld\n",ans);
	return 0;
}

D.（赛时切了）

题意：给定一棵树，有边权，有 \(q\) 次询问，每次询问把 \(n+1\) 号点连向 \(k\)，边权为 \(w\)，求全局距离和对 \(998244353\) 取模。询问间相互独立。\(1 \le n,q \le 2 \times 10^5\)。

赛时思路：先考虑拆式子。

设 \(hp_{x}\) 表示 \(x\) 到剩余所有点距离和。则容易得到：

\[\sum\limits_{i=1}^{n+1} \sum\limits_{j=1}^{n+1} cost(i,j)=\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} cost(i,j)+2 \times \sum\limits_{i=1}^{n} cost(i,n+1)=\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} cost(i,j)+2 \times hp_{k} \times n \]