AtCoder Beginner Contest 216 个人题解
比赛链接：AtCoder Beginner Contest 216
每篇一图
A题 Signed Difficulty
题目大意：
给出一个小数，根据小数部分改写 \(+，-\)
思路解析：
直接判断即可
AC代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
int x,y;
scanf("%d.%d",&x,&y);
if(y<=2)cout<<x<<"-"<<endl;
else if(y<=6)cout<<x<<endl;
else cout<<x<<"+"<<endl;
}
B题 Same Name
题目大意：
给出 \(n\) 个人的名字，每个人的名字由两部分组成，问是否有重名的人
思路解析：
- 暴力枚举匹配
- STL-map判断
AC代码：
暴力
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
struct node{
string x,y;
}s[maxn];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>s[i].x>>s[i].y;
int flg=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j)continue;
if(s[i].x==s[j].x&&s[i].y==s[j].y)flg=1;
}
}
if(flg)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
map
#include<bits/stdc++.h>
using namespace std;
map<string,map<string,int> >a;
string s,t;
int n;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>s>>t;
if(a[s][t]){
cout<<"Yes"<<endl;
return 0;
}
a[s][t]=1;
}
cout<<"No"<<endl;
}
C题 Many Balls
题目大意：
有一个盒子，你可以进行两种操作：1.往盒子里放一个球 2.使盒子里的球翻倍
问一个可行的操作方案使盒子里的球从 \(0\) 到 \(n\) ，操作最多 \(120\) 次
思路解析：
我们很容易想到可以从 \(n\) 往回推，这样操作 \(1\) 就变成了 \(/2\) ，操作 \(2\) 就变成了 \(-1\) ，当\(n\) 为偶数，就可以 \(/2\) 当 ，\(n\) 为奇数就可以 \(-1\) ，直到盒子里的球为 \(0\)
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ll n;
cin>>n;
string ans;
while(n){
if(n%2==0){
ans+=‘B‘;
n/=2;
}
else{
ans+=‘A‘;
n--;
}
}
for(int i=ans.size()-1;i>=0;i--)cout<<ans[i];
}
D题 Pair of Balls
题目大意：
我们有 \(n\) 种颜色的球，每种颜色有两个球，总共有 \(2n\) 个球，这些球被放在 \(m\) 个栈中，每次只能从两个不同栈顶取出相同颜色的球，问是否可以把球全部取出（好像消消乐）
思路解析：
首先我们思考，很直观的考虑，什么时候会不能达成目的：
灵魂画手上线：
由题意我们很容易看出，如果要想清空一个栈的话每个栈顶的数字一定需要先于他下面的数删除，所以这就形成了拓扑关系。
在观察数据，我们又可以发现由于每个数字存在两个，所以以每个数字为节点，至多向外连两条有向边，我们就可以把问题转化为了有向图的拓扑排序来处理。
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=4e5+5;
int e[maxn],h[maxn],nex[maxn],id;
int ans,in[maxn];
queue<int>q;
void add(int x,int y){
e[++id]=y;
nex[id]=h[x];
h[x]=id;
}
int main(){
int n,m;
cin>>n>>m;
for(int j=1;j<=m;j++){
int k,pre,x;
cin>>k>>pre;
for(int i=2;i<=k;i++){
cin>>x;
add(x,pre);
in[pre]++;
}
}
for(int i=1;i<=n;i++){
if(in[i]==0)q.push(i);
}
while(q.size()){
int top=q.front();
q.pop();
ans++;
for(int i=h[top];i;i=nex[i]){
int j=e[i];
in[j]--;
if(in[j]==0)q.push(j);
}
}
if(ans==n)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
E题 Amusement Park
题目大意：
给你 \(n\) 个数，你可以选择 \(k\) 次，每次选择一个数后这个数就会 \(-1\) ，问你能得到选择数的和的最大值
思路解析：
首先我们考虑暴力的做法：直接把数都扔到set里，每次取最大然后让他-1再把它扔回去就行了，但是这么做稳T
如何优化：推一推，手搓一下就完了
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
ll n,k,a[maxn],cnt,ans;
bool cmp(ll x,ll y){
return x>y;
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++){
ll x=a[i]-a[i+1];
if(cnt+i*x<=k){
ans+=(a[i]+a[i+1]+1)*x/2*i;
cnt+=i*x;
}
else{
k-=cnt;
ans+=(a[i]+a[i]-(k/i)+1)*(k/i)/2*i;
ans+=(k%i)*(a[i]-(k/i));
break;
}
}
cout<<ans<<endl;
}
F题 Amusement Park
题目大意：
给你两个长度为 \(n\) 数组 \(A\) ，\(B\) ，分别对应位置 \(1-n\) ，问有多少个S of {1，2，...，n}的子集满足 \(max_{i\in S}A_i \geq \sum_{i\in S}B_i\)
思路解析：
AC代码：
G题 01Sequence
题目大意：
你需要构造一个 \(01\) 串,满足给出的每个 \(L_i,R_i,X_i,\) 在 \([L,R]\) 中至少有 \(X\) 个 \(1\)
输出满足条件的 \(01\) 串且 \(01\) 串中 \(1\) 最少
思路解析：
AC代码：