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$ 飞的,所以我们考虑如何优化
我们把点分为两类,一种是度数小于 $sqrt(m)$ 的,一种是大于 $sqrt(m)$ 的,对于第一种,我们可以直接把它的所有邻接点更新。对于第二种,我们只需要在它上面设置一个标志,表示这个点周围的点被当前点更新。
查询时对于度数小于 $sqrt(m)$ 的点,我们O(1)直接查询,对于度数大于 $sqrt(m)$ 的,我们只需查询邻接的最后更新它的标志就可以。
AC代码:
//假装这里有代码
巨巨 这个D题转移方程 为什么会这样写?
为什么dp里边 要取max?????