ACGO挑战赛#13 部分题解 T1~4

jcf666

2025-01-05 20:39:24

发布于：浙江

17阅读

0回复

0点赞

T1: CityWalk

简化题意

求两个 o 字符之间的最短路径。

解题思路

可以把问题转化为：求两个 o 字符之间的曼哈顿距离。首先得到两个o在二维字符数组中的下标，然后用距离公式 $d(A,B)=\left| x_1-x_2 \right|+\left| y_1-y_2 \right|$ 即可快速求出问题的解。

个人代码

#include<bits/stdc++.h>
using namespace std;
char c;
int n,m,sx,sy,ex,ey;
//sx,sy 表示第一个出现的字符o在字符数组中处于的行、列
//ex,ey 表示第二个出现的字符o在字符数组中处于的行、列
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>c;
			if(c=='o'&&sx==0)sx=i,sy=j;
			else if(c=='o')ex=i,ey=j;
		}
	}
	cout<<abs(sx-ex)+abs(sy-ey);//曼哈顿距离计算公式
	return 0;
}

T2: 集合操作

简化题意

给定集合 $S$ ，按照输入数据对 $S$ 进行一系列操作。

解题思路

用 STL 中的 unordered_map 代替集合进行运算，统计每个数在集合中的出现次数。这个时候难点就出在了操作 $2$ 上。
操作 $2$ 解决方法：首先是最基础的，把 $x$ 的出现次数减 $c$ 或者变为 $0$ （等价于m[x]-=min(y,m[x])），如果 $x$ 的出现次数清零了，那么就要重新更新最大值和最小值了，所以要将其余出现在集合里的数都给遍历一遍，涉及到了map的遍历方法。map 的遍历方法就需要用一种新的关键字auto，感兴趣的可以自行搜索学习。

个人代码

#include<bits/stdc++.h>
using namespace std;
int maxn,minn=1e9,T,op,x,y;
//minn指集合中的数字的最小值
//maxn指集合中的数字的最大值
unordered_map<int,int>m;
//m记录每个数字在集合中的出现次数
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--){
		cin>>op;
		if(op==1){
			cin>>x;
			m[x]++;
			minn=min(minn,x);
			maxn=max(maxn,x);
		}
		if(op==2){
			cin>>x>>y;
			if(m.count(x)){
				m[x]-=min(y,m[x]);
				if(m[x]==0){
					m.erase(x);//去除这个数字
					if(x==maxn||x==minn){//更新最大最小值
						maxn=0;
						minn=1e9;
						for(auto [j,i]:m){
							if(j>maxn)maxn=j;
							if(j<minn)minn=j;
						}
					}
				}
			}
		}
		if(op==3)cout<<maxn-minn<<"\n";
	}
	return 0;
}

T3: 乌尔达哈城市分布图

简化题意

给定一张无向图，输出每个点只通过一条边可以到达的点的数量，并按顺序输出编号

解题思路

简单题，考察建图，我用邻接表建图。

个人代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int>edge[100005];//邻接表建图
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
        //无向图建双向边
		edge[x].push_back(y);
		edge[y].push_back(x);
	}
	for(int i=1;i<=n;i++){//遍历每个点
		sort(edge[i].begin(),edge[i].end());//排序
		cout<<edge[i].size()<<" ";//输出点数
		for(int j=0;j<edge[i].size();j++)cout<<edge[i][j]<<" ";//按顺序输出编号
		cout<<"\n";
	}
	return 0;
}

T4 恰好

简化题意

求有多少组连续的数之和为 $N$ 。

解题思路

这题比较毒瘤，对数学底子差的人不友好。另外这题有点类似于洛谷的这道题。
说说推法：
不妨先推出不含 $0$ 和负数的连续正整数数列之和等于 $N$ 的情况。
题目让我们求

$N= \sum_{i = l}^{r} {i}$

用小学学过的高斯求和公式可以推出，上面的式子可得

$\begin{aligned} N &= \frac{(l+r)(r-l+1)}{2}\\ 2N &= (l+r)(r-l+1)\\ \end{aligned}$

为了方便，我们直接把 $N$ 赋值为 $2N$
枚举数列项数由于公差为 $1$ ，可知项数不会大于 $l$ 与 $r$ 的和，所以枚举到 $\sqrt{ 2N }$ 就行了，再多就超时了。
设枚举用的变量为 $i$ 。判断时首先要满足 $N\mid i$ ，因为 $i$ 是项数，可得 $\frac{N}{i}$ 是首项与末项之和，而首项与末项一定为整数，所以 $\frac{N}{i}$ 一定为整数，所以 $N\mid i$ 这个条件必须成立才能进行下面的判断。
当以上条件成立后，首项与末项的差就是 $i-1$ ，然后就变成了一个和差问题（不会的请重修小学），可得

$\begin{aligned} sum=l+r= \frac{N}{i}\\ r= \frac{sum-i+1}{2}\\ l= \frac{sum+i-1}{2} \end{aligned}$

接下来就是判断，然后统计答案。当 $l$ 和 $r$ 满足 $r \mid 2$ 且 $\frac{l}{2} \le \frac{N}{2}$ 时就是一个合法的答案。
最后不要忘记将答案乘 $2$ 再输出，因为数列中还可以包含负数和 $0$ 。

个人代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,sum,ans;
signed main() {
    cin>>n;
    n*=2;
    for(int i=sqrt(n);i;i--){
    	if(n%i)continue;
    	sum=n/i;
    	if((sum-i+1)%2==0&&(sum+i-1)/2<=n/2)ans++;
	}
	cout<<ans*2;
    return 0;
}