AtCoder Beginner Contest 329 题解A~F

2023-11-20 23:01

本文主要是介绍AtCoder Beginner Contest 329 题解A~F,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

A - Spread

输入字符串,字符之间加上空格输出

B - Next

输出数组当中第二大的数

C - Count xxx

统计每个字符出现过的最长长度,再累加即可

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define INF 0x3f3f3f3f
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define int long long
#define pb push_back
#define vct vector
#define checkbit __builtin_popcount
#define gcd __gcd
#define use int T;cin>>T;while(T--)
#define LEN length()
#define all(a) a.begin(),a.end()
template<class T> bool mmax(T &u, T v) { return u < v ? (u = v, 1) : 0; }
template<class T> bool mmin(T &u, T v) { return u > v ? (u = v, 1) : 0; }
#define lowbit(x) (x&(-x))
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
using namespace std;
typedef pair<int,int>pii;
signed main()
{IOS
int n;cin>>n;
string a;
cin>>a;
vct<int>cnt(35,0);
vct<int>mas(35,0);
if(cnt[a[0]-'a']==0){cnt[a[0]-'a']++;mmax(mas[a[0]-'a'],cnt[a[0]-'a']);}
for(int i=1;i<n;i++){if(cnt[a[i]-'a']==0){cnt[a[i]-'a']++;mmax(mas[a[i]-'a'],cnt[a[i]-'a']);}if(a[i]==a[i-1]){cnt[a[i]-'a']++;}else {mmax(mas[a[i-1]-'a'],cnt[a[i-1]-'a']);cnt[a[i-1]-'a']=0;}
}int ans=0;
mmax(mas[a[n-1]-'a'],cnt[a[n-1]-'a']);
for(int i=0;i<35;i++){ans+=mas[i];
}
cout<<ans<<endl;return 0;
}

D - Election Quick Report

给定数组,每次第ia_i的票加一,每次都输出最多票的人,

我们用mas记录当前最大票数的人,在第i次投票时,答案只有masa_i两个人,每次视情况输出,并且更新mas的值即可.

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define INF 0x3f3f3f3f
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define int long long
#define pb push_back
#define vct vector
#define checkbit __builtin_popcount
#define gcd __gcd
#define use int T;cin>>T;while(T--)
#define LEN length()
#define all(a) a.begin(),a.end()
template<class T> bool mmax(T &u, T v) { return u < v ? (u = v, 1) : 0; }
template<class T> bool mmin(T &u, T v) { return u > v ? (u = v, 1) : 0; }
#define lowbit(x) (x&(-x))
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
using namespace std;
typedef pair<int,int>pii;
bool cmp(int a,int b){return a>b;
}
signed main()
{IOS
int n,m;cin>>n>>m;
vct<int>a(m+1);
vct<int>cnt(n+1);cin>>a[1];
int mas=a[1];cout<<a[1]<<endl;
cnt[a[1]]++;
for(int i=2;i<=m;i++){cin>>a[i];cnt[a[i]]++;if(a[i]!=mas){if(cnt[a[i]]>cnt[mas]){mas=a[i];printf("%lld\n",mas);}else if(cnt[a[i]]==cnt[mas]&&a[i]<mas){mas=a[i];printf("%lld\n",mas);}else {printf("%lld\n",mas);}}else{printf("%lld\n",mas);}}return 0;
}

 E - Stamp

给一张空白的纸,一个印章T,问是否可以印成S的样子(印章每次会覆盖重复的部分) 

利用BFS搜索

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define INF 0x3f3f3f3f
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define int long long
#define pb push_back
#define vct vector
#define checkbit __builtin_popcount
#define gcd __gcd
#define use int T;cin>>T;while(T--)
#define LEN length()
#define all(a) a.begin(),a.end()
template<class T> bool mmax(T &u, T v) { return u < v ? (u = v, 1) : 0; }
template<class T> bool mmin(T &u, T v) { return u > v ? (u = v, 1) : 0; }
#define lowbit(x) (x&(-x))
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
using namespace std;
typedef pair<int,int>pii;
const int N= 2e5+7;
signed main()
{IOSint n,m;cin>>n>>m;string s,t;cin>>s>>t;vct<bool>st(N);queue<int> q;for(int i=0;i+m-1<n;i++){bool flag=1;for(int j=0;j<m;j++){if(s[i+j]!=t[j])flag=0;}if(flag)q.push(i),st[i]=1;}while(!q.empty()){int u=q.front();q.pop();for(int j=0;j<m;j++)s[u+j]='#';for(int i=max(u-m+1,0*1ll);i<=u+m-1&&i+m-1<n;i++){if(!st[i]){int flag=1;for(int j=0;j<m;j++){if(s[i+j]!='#'&&s[i+j]!=t[j])flag=0;}if(flag)q.push(i),st[i]=1;}}}bool isok=1;for(int i=0;i<n;i++){if(s[i]!='#')isok=0;}if(isok)cout<<"Yes"<<endl;else cout<<"No"<<endl;return 0;
}

F - Colored Ball

每次操作将a位置当中的元素,放到b位置,因为是颜色,故用平衡树

如果按照题目的要求直接写不加优化的话亲测TLE

故当a当中的元素多于b的时候,交换a,b当中的元素,再插入a,效果相同,这样可以达到最优效果

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define INF 0x3f3f3f3f
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define int long long
#define pb push_back
#define vct vector
#define checkbit __builtin_popcount
#define gcd __gcd
#define use int T;cin>>T;while(T--)
#define LEN length()
#define all(a) a.begin(),a.end()
template<class T> bool mmax(T &u, T v) { return u < v ? (u = v, 1) : 0; }
template<class T> bool mmin(T &u, T v) { return u > v ? (u = v, 1) : 0; }
#define lowbit(x) (x&(-x))
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
using namespace std;
typedef pair<int,int>pii;
const int N= 2e5+7;
signed main()
{IOSint n,q;cin>>n>>q;int x;set<int>tot[n+1];for(int i=1;i<=n;i++){cin>>x;tot[i].insert(x);}while(q--){int a,b;cin>>a>>b;if(tot[a].size()>tot[b].size())swap(tot[a],tot[b]);for(auto z:tot[a]){tot[b].insert(z);}tot[a].clear();cout<<tot[b].size()<<"\n";}return 0;
}

这篇关于AtCoder Beginner Contest 329 题解A~F的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/398076

相关文章

2014 Multi-University Training Contest 8小记

1002 计算几何 最大的速度才可能拥有无限的面积。 最大的速度的点 求凸包, 凸包上的点( 注意不是端点 ) 才拥有无限的面积 注意 :  凸包上如果有重点则不满足。 另外最大的速度为0也不行的。 int cmp(double x){if(fabs(x) < 1e-8) return 0 ;if(x > 0) return 1 ;return -1 ;}struct poin

2014 Multi-University Training Contest 7小记

1003   数学 , 先暴力再解方程。 在b进制下是个2 , 3 位数的 大概是10000进制以上 。这部分解方程 2-10000 直接暴力 typedef long long LL ;LL n ;int ok(int b){LL m = n ;int c ;while(m){c = m % b ;if(c == 3 || c == 4 || c == 5 ||

2014 Multi-University Training Contest 6小记

1003  贪心 对于111...10....000 这样的序列,  a 为1的个数,b为0的个数,易得当 x= a / (a + b) 时 f最小。 讲串分成若干段  1..10..0   ,  1..10..0 ,  要满足x非递减 。  对于 xi > xi+1  这样的合并 即可。 const int maxn = 100008 ;struct Node{int

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

C - Word Ladder题解

C - Word Ladder 题解 解题思路: 先输入两个字符串S 和t 然后在S和T中寻找有多少个字符不同的个数(也就是需要变换多少次) 开始替换时: tips: 字符串下标以0开始 我们定义两个变量a和b,用于记录当前遍历到的字符 首先是判断:如果这时a已经==b了,那么就跳过,不用管; 如果a大于b的话:那么我们就让s中的第i项替换成b,接着就直接输出S就行了。 这样

【秋招笔试】9.07米哈游秋招改编题-三语言题解

🍭 大家好这里是 春秋招笔试突围,一起备战大厂笔试 💻 ACM金牌团队🏅️ | 多次AK大厂笔试 | 大厂实习经历 ✨ 本系列打算持续跟新 春秋招笔试题 👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸 ✨ 笔试合集传送们 -> 🧷春秋招笔试合集 🍒 本专栏已收集 100+ 套笔试题,笔试真题 会在第一时间跟新 🍄 题面描述等均已改编,如果和你笔试题看到的题面描述

LeetCode 第414场周赛个人题解

目录 Q1. 将日期转换为二进制表示 原题链接 思路分析 AC代码 Q2. 范围内整数的最大得分 原题链接 思路分析 AC代码 Q3. 到达数组末尾的最大得分 原题链接 思路分析 AC代码 Q4. 吃掉所有兵需要的最多移动次数 原题链接 思路分析 AC代码 Q1. 将日期转换为二进制表示 原题链接 Q1. 将日期转换为二进制表示 思路分析

牛客小白月赛100部分题解

比赛地址:牛客小白月赛100_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ A.ACM中的A题 #include<bits/stdc++.h>using namespace std;#define ll long long#define ull = unsigned long longvoid solve() {ll a,b,c;cin>>a>>b>

AtCoder Beginner Contest 370 Solution

A void solve() {int a, b;qr(a, b);if(a + b != 1) cout << "Invalid\n";else Yes(a);} B 模拟 void solve() {qr(n);int x = 1;FOR(i, n) FOR(j, i) qr(a[i][j]);FOR(i, n) x = x >= i ? a[x][i]: a[i][x];pr2(