当前位置：首页 > ops >正文

AtCoder Beginner Contest 405(ABCD)

ops 2025/8/28 18:36:24

前言

道阻且长啊

一、A - Is it rated?

#include <bits/stdc++.h>
using namespace std;typedef long long ll;void solve()
{int r,x;cin>>r>>x;if(x==1){if(r>=1600&&r<3000){cout<<"Yes";}else{cout<<"No";}}else{if(r>=1200&&r<2400){cout<<"Yes";}else{cout<<"No";}}
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;//cin>>t;while(t--){solve();    }return 0;
}

签到题，没啥好说的。

二、B - Not All

#include <bits/stdc++.h>
using namespace std;typedef long long ll;void solve()
{int n,m;cin>>n>>m;vector<int>nums(n+1);vector<int>cnts(m+1);for(int i=1;i<=n;i++){cin>>nums[i];cnts[nums[i]]++;}for(int i=1;i<=m;i++){if(cnts[i]==0){cout<<0;return ;}}int ans=0;for(int i=n;i>=1;i--){ans++;if(--cnts[nums[i]]==0){cout<<ans;return ;}}
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;//cin>>t;while(t--){solve();    }return 0;
}

这个就是用个桶存每个数出现的次数，然后从后往前删一个就从桶里查次数，删没了就直接输出即可。

三、C - Sum of Product

#include <bits/stdc++.h>
using namespace std;typedef long long ll;void solve()
{int n;cin>>n;vector<ll>nums(n+1);for(int i=1;i<=n;i++){cin>>nums[i];}ll ans=0;ll sum=nums[n];//从i开始到最后的和for(int i=n-1;i>=1;i--){ans+=sum*nums[i];        sum+=nums[i];}cout<<ans;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;//cin>>t;while(t--){solve();    }return 0;
}

这个题看数据量就能发现暴力枚举O(n^2)的思路必TLE。

所以就改为观察这个数学式子，可以发现，对于每个Ai，要做的就是乘以从i+1开始一直到最后的数再累加，那么就可以合并成Ai乘以从i+1开始一直到最后的累加和。所以就考虑使用动态规划的思想，从最后开始往前用一个sum变量维护累加和，然后每次往ans里加上累加和乘以当前数的值即可。

四、D - Escape Route

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<int,int> pii;vector<int>mov={-1,0,1,0,-1};//上右下左//TLE原因 -> 不能从每个出口开始跑一遍bfs，时间复杂度太高了
//正解：将所有出口都入队，然后一次处理全部
void solve()
{int n,m;cin>>n>>m;vector<vector<char>>grid(n,vector<char>(m));vector<vector<int>>dis(n,vector<int>(m,INT_MAX));queue<pii>node;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>grid[i][j];if(grid[i][j]=='E'){dis[i][j]=0;node.push({i,j});}}}while(!node.empty()){int size=node.size();for(int i=0;i<size;i++){int x=node.front().first;int y=node.front().second;node.pop();for(int j=0;j<4;j++){int nx=x+mov[j];int ny=y+mov[j+1];if(nx>=0&&nx<n&&ny>=0&&ny<m&&grid[nx][ny]!='#'&&dis[x][y]+1<dis[nx][ny]){dis[nx][ny]=dis[x][y]+1;if(j==0){grid[nx][ny]='v';}else if(j==1){grid[nx][ny]='<';}else if(j==2){grid[nx][ny]='^';}else {grid[nx][ny]='>';}node.push({nx,ny});}}}}for(int i=0;i<n;i++){for(int j=0;j<m;j++){cout<<grid[i][j];}cout<<endl;}
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;//cin>>t;while(t--){solve();    }return 0;
}

我是sb……

这个题赛时思路完全对了，就是当时写的是对于每个出口都跑一遍bfs，那结果就是喜提TLE。

正解就是把对于每个出口都跑一遍bfs改成先往队列里加入所有出口，再一次性解决即可，这样只需要跑一遍整张图就行了。

整体思路不是太难想，就是考虑从每个出口出发向外扩，在这个过程中逆向填出方向即可。而又因为是一张二维网格，所以就可以考虑用宽度优先遍历bfs求多源最短路。那么对于bfs的过程，这几乎就是模板题了，就是准备一个队列，然后一次考虑所有在队列里的点并向外扩即可。这里如果改成正解的写法应该是不用dis数组每次看能不能更新最小距离的，只带着一个grid数组每次判断来没来过即可，只是我懒得改了（）