ACGO挑战赛#13 题解
2025-01-18 21:41:50
发布于：浙江
T1: CityWalk
简化题意
求两个 o 字符之间的最短路径。
解题思路
可以把问题转化为：求两个 o 字符之间的曼哈顿距离。首先得到两个o在二维字符数组中的下标，然后用距离公式 即可快速求出问题的解。
个人代码
#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: 集合操作
简化题意
给定集合 ，按照输入数据对 进行一系列操作。
解题思路
用 STL 中的 unordered_map 代替集合进行运算，统计每个数在集合中的出现次数。这个时候难点就出在了操作 上。
操作 解决方法：首先是最基础的，把 的出现次数减 或者变为 （等价于m[x]-=min(y,m[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 恰好
简化题意
求有多少组连续的数之和为 。
解题思路
这题比较毒瘤，对数学底子差的人不友好。另外这题有点类似于洛谷的这道题。
说说推法：
不妨先推出不含 和负数的连续正整数数列之和等于 的情况。
题目让我们求
用小学学过的高斯求和公式可以推出，上面的式子可得
为了方便，我们直接把 赋值为
枚举数列项数由于公差为 ，可知项数不会大于 与 的和，所以枚举到 就行了，再多就超时了。
设枚举用的变量为 。判断时首先要满足 ，因为 是项数，可得 是首项与末项之和，而首项与末项一定为整数，所以 一定为整数，所以 这个条件必须成立才能进行下面的判断。
当以上条件成立后，首项与末项的差就是 ，然后就变成了一个和差问题（不会的请重修小学），可得
接下来就是判断，然后统计答案。当 和 满足 且 时就是一个合法的答案。
最后不要忘记将答案乘 再输出，因为数列中还可以包含负数和 。
个人代码
#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;
}
T5:符文锁
简化题意
求有多少种组合方法满足以下条件。
解题思路
？这不就是ABC356C吗？代码改都不用改。
题目中可得 ，范围极小，可以直接暴力 dfs 拆解，枚举每一个钥匙是否选择，选完后对这种方法进行查验，如果合法则统计答案。最后输出统计出来的答案数。
函数的写法（用于判断序列的合法性）
遍历每种试过的方法，如果这个数字曾经试过，则统计下来。当这个试过的情况统计完后，如果这个情况的结果是 o 则判断统计下来的总数，如果小于 则直接否定，因为可能另外没有被选到的数是正确的，否则继续遍历下一个试过的情况。 如果这个情况的结果是 x 则判断统计下来的总数，如果大于等于 则直接否定，因为把正确和不正确的数全都选下来了。
判断完后不要忘记返回 true 或 1
bool check(){
for(int i=1;i<=q;i++){
int sum=0;
for(int j=1;j<=k[i][0];j++){
if(vis[k[i][j]])sum++;//判断是否被选出
}
if(win[i]=='o'){//判断每种情况的结果
if(sum<m)return 0;
}
else{
if(sum>=m)return 0;
}
}
return 1;
}
的写法
设置 个参数，一个代表是否选择这个数()，一个代表这是第几个数()。当函数被调用时，首先给 标记为 代表这个数 是否已被选用。如果所有数都选完了，则判断这个数是否合法(调用 )，合法则统计。这个时候继续往下搜索，调用时 要 代表继续搜索下一个数， 需要分为两种情况搜索，就是为 (选择下一个数) 和为 (不选择下一个数) 的情况。
void dfs(int num,int step){
vis[step]=num;
if(step==n){
if(check())ans++;
return;
}
dfs(0,step+1);
dfs(1,step+1);
}
组合进 主函数
最后组合起来，读入后调用函数 dfs(0,0) 最后输出答案就行了。
个人代码
#include<bits/stdc++.h>
using namespace std;
int k[1001][1001],n,q,m,vis[1001],ans;
char win[10001];
bool check(){
for(int i=1;i<=q;i++){
int sum=0;
for(int j=1;j<=k[i][0];j++){
if(vis[k[i][j]])sum++;
}
if(win[i]=='o'){
if(sum<m)return 0;
}
else{
if(sum>=m)return 0;
}
}
return 1;
}
void dfs(int num,int step){
vis[step]=num;
if(step==n){
if(check())ans++;
return;
}
dfs(0,step+1);
dfs(1,step+1);
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>q>>m;
for(int i=1;i<=q;i++){
cin>>k[i][0];
for(int j=1;j<=k[i][0];j++)cin>>k[i][j];
cin>>win[i];
}
dfs(0,0);
cout<<ans;
return 0;
}
T6:集合操作2
简化题意
每次输入会输入一些指令，你需要按照指令去严格进行操作。
解题思路
其实这题最烦的地方就是操作类型 ，但是只会将所有元素都赋值为 ，我们可以建一个数组（），去记录这个数在被进行 操作后是否被修改，增大了多少数值，而 可以再建一个变量储存。进行 操作时需要将 清空，每次全清空会 TLE，所以还要建一个新数组()，存储被修改的值。进行操作 时，加减的操作直接在 里进行，不要忘记在 里记录。进行 操作时就无需多言了，进行简单处理后就可以输出了。当然，还需要建立一个布尔类型 记录在输入 后是否进行了 操作，如果进行了，则设为 ，否则为 ，最后只需要在 操作时输出 vis[y]+num+flag*a[y] 就行了。
个人代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,T,a[1000001],xia[1000001],op,x,y,flag=1,vis[1000001],num;
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
cin>>T;
while(T--){
cin>>op;
if(op==1){
cin>>x;
for(int i=1;i<=xia[0];i++)vis[xia[i]]=0;
flag=0;
xia[0]=0;
num=x;
}
if(op==2){
cin>>x>>y;
vis[x]+=y;
xia[++xia[0]]=x;
}
if(op==3){
cin>>y;
cout<<vis[y]+num+flag*a[y]<<"\n";
}
}
return 0;
}
感谢观看
如果对你有帮助的话，就请给我点一个赞呗（无耻地说出这句话），感谢大家的喜欢！
有帮助，赞一个