https://atcoder.jp/contests/abc373/tasks
赛后反思
B题第一次读错题意,浪费了几分钟,需加强审题能力
对于图论有些生疏,D题为简单图论,在76min的时候才AC,需加强训练图论
A题
给定12个字符串,求字符串长度 \(= i\) 的个数,直接模拟
#include <bits/stdc++.h>
#define int long long
using namespace std;
void solve(){
int ans = 0;
for(int i = 1;i<=12;i++){
string s; cin>>s;
if(s.size() == i) ans++;
}
cout<<ans<<endl;
}
signed main(){
// int T; cin>>T; while(T--)
solve();
return 0;
}
B题
求移动的距离,直接从 A 到 Z 枚举即可,最开始是在 A 位置,开一个last记录上一个的位置,每次答案加上距离差绝对值即可
#include <bits/stdc++.h>
#define int long long
using namespace std;
void solve(){
string s; cin>>s;
int ans = 0;
map<char,int> a;
for(int i = 0;i<s.size();i++){
a[s[i]] = i;
}
int last = a['A'];
for(int i = 'A';i<='Z';i++){
ans += abs(a[i] - last);
last = a[i];
}
cout<<ans<<endl;
}
signed main(){
// int T; cin>>T; while(T--)
solve();
return 0;
}
C题
要使答案最大,找 \({a_i},{b_i}\) 的最大值,求和即可。
#include <bits/stdc++.h>
#define int long long
using namespace std;
void solve(){
int n; cin>>n;
vector<int> a(n + 1);
vector<int> b(n + 1);
for(int i = 1;i<=n;i++) cin>>a[i];
for(int i = 1;i<=n;i++) cin>>b[i];
sort(a.begin() + 1,a.end());
sort(b.begin() + 1,b.end());
cout<<a[n]+b[n]<<endl;
}
signed main(){
// int T; cin>>T; while(T--)
solve();
return 0;
}
D题
我们发现建图时 u->v +w 可以等效为 v->u -w,建双向边跑一次DFS更新答案即可
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 3;
int n,m;
int head[N];
int tot;
int ans[N];
bool vis[N];
struct node{
int u,v,w,nxt;
}edge[N<<1];
void add_edge(int u,int v,int w){
edge[++tot].u = u;
edge[tot].v = v;
edge[tot].w = w;
edge[tot].nxt = head[u];
head[u] = tot;
}
void dfs(int x,int fa){
for(int i = head[x];i;i=edge[i].nxt){
int u = edge[i].u;
int v = edge[i].v;
int w = edge[i].w;
if(v == fa || vis[v]) continue;
vis[u] = 1,vis[v] = 1;
// cout<<ans[u]<<" "<<ans[v]<<" "<<w<<endl;
ans[v] = ans[u] + w;
dfs(v,u);
}
}
void solve(){
cin>>n>>m;
for(int i = 1;i<=m;i++){
int u,v,w; cin>>u>>v>>w;
add_edge(u,v,w);
add_edge(v,u,-w);
}
for(int i = 1;i<=n;i++){
if(!vis[i])dfs(i,i);
}
for(int i = 1;i<=n;i++) cout<<ans[i]<<" ";
}
signed main(){
// int T; cin>>T; while(T--)
solve();
return 0;
}
标签:Atcoder,return,Beginner,AtCoder,int,long,solve,using,include
From: https://www.cnblogs.com/longxingx/p/18438449