Sciseed Programming Contest 2021（AtCoder Beginner Contest 219）个人题解
比赛链接：Sciseed Programming Contest 2021（AtCoder Beginner Contest 219）个人题解
A题 AtCoder Quiz 2
题目大意：
各个等级有一个最低分数，给出当前分数，问要加多少分才能上一个等级
思路解析：
直接判断即可
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn=1e5+5;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int x;
cin>>x;
if(x<40)cout<<40-x<<endl;
else if(x<70)cout<<70-x<<endl;
else if(x<90)cout<<90-x<<endl;
else cout<<"expert"<<endl;
}
B题 Maritozzo
题目大意：
依次给出3个字符串，再给出一串1,2,3的序列，表示依次输出第几个字符串
思路解析：
模拟即可
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn=1e5+5;
string s[maxn];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n=3;
for(int i=1;i<=n;i++){
cin>>s[i];
}
string a;
cin>>a;
for(int i=0;i<a.size();i++){
cout<<s[a[i]-'0'];
}
}
C题 Neo-lexicographic Ordering
题目大意：
给出 \(26\) 个字母的新字典序，给出 \(n\) 个字符串，按字符串字典序由小到大顺序输出
思路解析：
可以拿 map 把新字典序转换为原字典序，直接 sort 然后映射回来就可以
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn=1e5+5;
string s;
struct node{
int rk;
string s,val;
}a[maxn];
map<char,char>mp;
bool cmp(node x,node y){
return x.s<y.s;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>s;
for(int i=0;i<s.size();i++){
mp[s[i]]=i+'a';
}
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].val;
a[i].rk=i;
for(int j=0;j<a[i].val.size();j++){
a[i].s+=mp[a[i].val[j]];
}
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++){
cout<<a[i].val<<endl;
}
}
D题 Strange Lunchbox
题目大意：
给出 \(X\) , \(Y\) ，有 \(n\) 个物品，每个物品有 \(a\) ，\(b\) 两个属性，你需要选择最少的物品满足\(\sum a_i \geq X\)并且 \(\sum b_i \geq Y\)
思路解析：
\(O(n^3)\)的DP
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn=305;
int dp[maxn][maxn];
int a[maxn],b[maxn];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n,x,y;
cin>>n>>x>>y;
for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
memset(dp,0x3f,sizeof dp);
dp[0][0]=0;
for(int k=1;k<=n;k++)
for(int i=302;i>=0;i--)
for(int j=302;j>=0;j--)
dp[i][j]=min(dp[i][j],dp[max(i-a[k],0)][max(j-b[k],0)]+1);
if(dp[x][y]>=1e8)cout<<-1<<endl;
else cout<<dp[x][y]<<endl;
}
G题 Propagation
题目大意：
给出一个无向图，给出操作序列，每次操作将点 \(x_i\) 的所有邻接点上的数改为 \(x_i\) 上的数
思路解析：
首先我们观察到 \(1 \leq n \leq 2e5\) , \(1 \leq q \leq 2e5\),所以我们直接模拟的话是会 \(T\) 飞的,所以我们考虑如何优化
AC代码：