首页 > 其他分享 >【Atcoder训练记录】AtCoder Beginner Contest 373

【Atcoder训练记录】AtCoder Beginner Contest 373

时间:2024-09-28 21:34:30浏览次数:7  
标签:Atcoder return Beginner AtCoder int long solve using include

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

相关文章

  • Buildings(AtCoder Beginner Contest 372)
    #include<bits/stdc++.h>#defineendl'\n'usingll=longlong;typedefunsignedlonglongull;usingnamespacestd;voidGordenGhost();signedmain(){#ifdefGordenfreopen("E:/ProgramFiles/CLion2023.2.2/my/exe/in.txt&quo......
  • AtCoder Beginner Contest 372(4/7)
    比赛链接:https://atcoder.jp/contests/abc372开头:过去一个多月了,虽然暑假就上了蓝,但感觉自已一直还没达到蓝的水准,网络赛也打了两场,打的一般,开学之后一直比较忙,现在稳定了下来,接下来打算尽量每周3-4篇atcoder的题解吧,这是这周第一篇,虽然有点水(A.delete.思路:签......
  • AtCoder Regular Contest 184 D Erase Balls 2D
    转化计数对象。直接数最终剩下的球的集合似乎并不好做。考虑数选择的球的集合(显然选择的顺序不重要,只有选择了哪些球重要)。先把所有球按\(x\)坐标从小到大排序。设我们选择的球的下标为\(i_1<i_2<\cdots<i_k\)。那么能选择这些球当且仅当\(y_{i_1}>y_{i_2}>\cdots......
  • AtCoder Beginner Contest 372 补题记录
    A-delete题意:输出删除字符串中.后的字符串思路:只输出字符串中不是.的字符voidsolve(){strings=sread();for(autoit:s)if(it!='.')cout<<it;cout<<endl;}B-3^A题意:给出M,求将M拆分成N个3的\(A_i\)次方相加思路:贪心,从大到小用......
  • AtCoder Beginner Contest 372(A - F)
    A:直接输出。B:把\(M\)三进制拆分,最多10位,每位最多为2,\(N\le20\)足够了。C:暴力修改,每次只产生\(O(1)\)影响。D:预处理st表,二分每个\(j\)会断哪些\(i\)产生贡献,差分一下。E:启发式合并平衡树,\(k\)更大也能做。F:只保留有特殊边经过的点,把\(i,j\)之间的\(j-i......
  • Atcoder Beginner Contest 372
    AtcoderBeginnerContest372A模拟即可。#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;voidsolve(){charch;while(cin>>ch){if(ch!='.'){cout<<ch;}}}......
  • AtCoder Beginner Contest 372
    省流版A.暴力即可B.转换3进制即可C.考虑答案的组成,仅修改发生变化的部分即可D.维护答案数组\(ans_i\),考虑枚举\(j\)对哪些\(i\)有贡献,通过单调栈找到对应的区间\(i\),通过差分维护区间加法即可E.并查集维护连通块,\(set\)维护点标号大小,合并\(set\)时启发式合并,查询......
  • UNIQUE VISION Programming Contest 2024 Autumn (AtCoder Beginner Contest 372)
    总结(我的塘人局):单调栈是忘得差不多了 A-delete.题意:输出删除所有'.'的字符串思路:遍历输出不是'.'复杂度:O(n) Code:#include<bits/stdc++.h>usingnamespacestd;usingLL=longlong;usingi64=int64_t;voidsolve(){strings;cin......
  • [atcoder agc 004 c] AND Grid
    题目链接题目简述给定一个H×WH\timesWH×W的网格图,有些位置已经被涂色。要求构造两个相同大小的网格图......
  • AtCoder Beginner Contest 371
    A-Jiro输入\(AB,BC,AC\)的大小关系,输出中位数。手动模拟一下。点击查看代码#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#defineullunsignedlonglongintread(){intx=0;boolf=false;charc=getchar();while(c<'......