AtCoder Beginner Contest 328
链接:Toyota Programming Contest 2023#7(AtCoder Beginner Contest 328) - AtCoder
A
题意:给定n个数,将小于等于x的数加起来输出。
#include <bits/stdc++.h>
#define int long long
#define endl '\n';
using namespace std;
void solve(){
int n,x;
cin>>n>>x;
int ans=0;
for(int i=0;i<n;i++){
int y;
cin>>y;
if(y<=x) ans+=y;
}
cout<<ans<<endl;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;
//cin>>T;
while(T--)solve();
return 0;
}
B
(开始还把题意理解错了)
#include <bits/stdc++.h>
#define int long long
#define endl '\n';
using namespace std;
void solve(){
int n;
cin>>n;
int ans=0;
for(int i=1;i<=n;i++){
int y;
cin>>y;
int z=i;
int x=i%10;
while(z){
if(x!=z%10){
x=-1;
break;
}
z/=10;
}
if(x==-1) continue;
z=x;
while(z<=y){
ans++;
z=z*10+x;
}
}
cout<<ans<<endl;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;
//cin>>T;
while(T--)solve();
return 0;
}
C
前缀和预处理一下就行。
#include <bits/stdc++.h>
#define int long long
#define endl '\n';
using namespace std;
const int N = 3e5 + 10;
int pre[N];
void solve(){
int n,q;
string s;
cin>>n>>q;
cin>>s;
s=" " + s;
for(int i=1;i<n;i++)
if(s[i]==s[i+1]) pre[i]++;
for(int i=1;i<=n;i++) pre[i]+=pre[i-1];
for(int i=0;i<q;i++){
int l,r;
cin>>l>>r;
cout<<pre[r-1]-pre[l-1]<<endl;
}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;
//cin>>T;
while(T--)solve();
return 0;
}
D
思路有点向括号匹配,将字符压进栈。如果遇见ABC就把ABC弹出。
#include <bits/stdc++.h>
#define int long long
#define endl '\n';
using namespace std;
void solve(){
string s;
deque<char> path;
cin>>s;
for(int i=0;i<s.size();i++){
path.push_back(s[i]);
if(path.size()>=3){
int len=path.size();
if(path[len-1]=='C'&&path[len-2]=='B'&&path[len-3]=='A')
for(int i=0;i<3;i++) path.pop_back();
}
}
for(auto v:path) cout<<v;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;
//cin>>T;
while(T--)solve();
return 0;
}
E
在m条边里面选n-1条构成生成树。
可以深搜把所有选择都找出来然后暴力试试能不能构成生成树。
AC代码
#include <bits/stdc++.h>
#define int long long
#define endl '\n';
using namespace std;
const int N = 10100;
struct edg{
int u,v,w;
}edge[N];
int n,m,k;
int fa[N];
vector<vector<int>> check;
vector<int> path;
int Find(int x){
return x==fa[x] ? x :fa[x]=Find(fa[x]);
}
void dfs(int starindex,int deepth){
if(deepth==n){
check.push_back(path);
return;
}
for(int i=starindex;i<m;i++){
path.push_back(i);
dfs(i+1,deepth+1);
path.pop_back();
}
}
void solve(){
cin>>n>>m>>k;
for(int i=0;i<m;i++) cin>>edge[i].u>>edge[i].v>>edge[i].w;
dfs(0,1);
int ans=k+1;
//cout<<check.size()<<endl;
for(auto q:check){
for(int i=1;i<=n;i++) fa[i]=i;
int sum=0;
bool OK=true;
for(auto x:q){
int u=edge[x].u;
int v=edge[x].v;
int w=edge[x].w;
int ta=Find(u);
int tb=Find(v);
if(ta==tb){
OK=false;
break;
}
fa[ta]=tb;
sum=(sum+w)%k;
}
if(OK)ans=min(sum,ans);
}
cout<<ans<<endl;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;
//cin>>T;
while(T--)solve();
return 0;
}
F
一个很典的带权并查集
#include <bits/stdc++.h>
#define int long long
#define endl '\n';
using namespace std;
const int N = 2e5 + 10;
int fa[N];
int w[N];
int Find(int x){
if(fa[x]!=x){
int pa = Find(fa[x]);
w[x] += w[fa[x]];
fa[x] = pa;
}
return fa[x];
}
void solve(){
int n,q;
cin>>n>>q;
for(int i=1;i<=n;i++){
fa[i]=i;
}
for(int i=0;i<q;i++){
int a,b,d;
cin>>a>>b>>d;
int ta=Find(a);
int tb=Find(b);
if(ta!=tb){
w[ta] = w[b] + d - w[a];
fa[ta] = tb;
cout<<i+1<<" ";
}else if(w[a]-w[b]==d)
cout<<i+1<<" ";
}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;
//cin>>T;
while(T--)solve();
return 0;
}
- Beginner AtCoder Contest 328beginner atcoder contest 328 328 beginner atcoder contest contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 334 beginner atcoder contest 332 beginner atcoder contest 327