Sciseed Programming Contest 2021（AtCoder Beginner Contest 219）个人题解

比赛链接：Sciseed Programming Contest 2021（AtCoder Beginner Contest 219）个人题解

A题 AtCoder Quiz 2

题目大意：

各个等级有一个最低分数，给出当前分数，问要加多少分才能上一个等级

思路解析：

直接判断即可

AC代码：

#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair 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< else if(x<70)cout<<70-x< else if(x<90)cout<<90-x< else cout<<"expert"<}


B题 Maritozzo

题目大意：

依次给出3个字符串，再给出一串1,2,3的序列，表示依次输出第几个字符串

思路解析：

模拟即可

AC代码：

#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair 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 cout< }
}


C题 Neo-lexicographic Ordering

题目大意：

给出 \(26\) 个字母的新字典序，给出 \(n\) 个字符串，按字符串字典序由小到大顺序输出

思路解析：

可以拿 map 把新字典序转换为原字典序，直接 sort 然后映射回来就可以

AC代码：

#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair pii;
const int maxn=1e5+5;
string s;
struct node{
int rk;
string s,val;
}a[maxn];
mapmp;
bool cmp(node x,node y){
return x.s}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>s;
for(int i=0;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].s+=mp[a[i].val[j]];
}
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++){
cout< }
}


D题 Strange Lunchbox

题目大意：

给出 \(X\) , \(Y\) ，有 \(n\) 个物品，每个物品有 \(a\) ，\(b\) 两个属性，你需要选择最少的物品满足\(\sum a_i \geq X\)并且 \(\sum b_i \geq Y\)

思路解析：

\(O(n^3)\)的DP

AC代码：

#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair 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< else cout<}


G题 Propagation

题目大意：

给出一个无向图，给出操作序列，每次操作将点 \(x_i\) 的所有邻接点上的数改为 \(x_i\) 上的数

思路解析：

首先我们观察到 \(1 \leq n \leq 2e5\) , \(1 \leq q \leq 2e5\),所以我们直接模拟的话是会 \(T\) 飞的,所以我们考虑如何优化

我们把点分为两类，一种是度数小于 \(sqrt(m)\) 的，一种是大于 \(sqrt(m)\) 的，对于第一种，我们可以直接把它的所有邻接点更新。

AC代码：

推广一波小飞龙博客：戳这里@不会飞的小飞龙