这场比赛是晚上vp的,太逆天了自己,给我自己都菜笑了,第二题当时差了一个那个循序渐进的点没想到,关键细节都想到了,当时以为是错的就没写,第二题没做出来确实好久没遇到过了,裂开
话不多说,直接开始看题目
A. Meaning Mean
这题不需要看了,很水的一道题,就从小到大排序,然后累加除2即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n;
int a[200005];
void solve()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+1+n);int ans=a[1];for(int i=2;i<=n;i++){ans=(ans+a[i])/2;}cout<<ans<<"\n";
}
signed main()
{cin>>t;while(t--){solve();}return 0;
}
B. Maximize Mex
题意:就是说给你一个数组,然后每个元素都可以选择0次或者有限次的去累加值x,然后判断最小的没有出现的整数是多少
思路:用map去存储每个数出现的次数,但是我们知道有n个数,所以不会出现的最小数只会存在于0~n这个区间内,因此我们去遍历这个区间,去判断当前i这个地方是否存在值,如果不存在就判断能否通过累加获得,我们用另一个map容器去存储被x取模后的结果,也就是可以变换的数量,然后去判断是否到了一个结点此时既没有出现,也没有多余的数可以累加出来即可
#include<bits/stdc++.h>
using namespace std;
#define int long longint t;
int n,x;
int a[200005];void solve()
{cin>>n>>x;map<int,int> mp;map<int,int> num;for(int i=1;i<=n;i++){cin>>a[i];mp[a[i]]++;}for(int i=0;i<=n;i++){if(mp[i]>1){num[i%x]+=mp[i]-1;mp[i]=1;}else if(mp[i]==0&&num[i%x]!=0){mp[i]=1;num[i%x]--;}else if(mp[i]==0){cout<<i<<"\n";return ;}}
}signed main()
{cin>>t;while(t--){solve();}return 0;
}
C1. Adjust The Presentation (Easy Version)
这题感觉没什么好说的,纸上写一写就发现,如果你想要满足那个b数组那个序列,你的初始序列就要去满足他那个顺序,我们遍历一遍去查看是否符合那个顺序即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n,m,q;
int a[200005];
int b[200005];
void solve()
{int vis[200005];memset(vis,0,sizeof(vis));cin>>n>>m>>q;for(int i=1;i<=n;i++){cin>>a[i];}for(int j=1;j<=m;j++){cin>>b[j];}int len=1;for(int i=1;i<=m;i++){if(vis[b[i]]!=0){continue;}if(a[len]!=b[i]){cout<<"TIDAK\n";return ;}vis[b[i]]=1;len++;}cout<<"YA\n";return ;
}
signed main()
{cin>>t;while(t--){solve();}return 0;
}