补题链接：Dashboard - Codeforces Round 977 (Div. 2, based on COMPFEST 16 - Final Round) - Codeforces
A. Meaning Mean
思路
排个序，然后暴力跑一遍
代码
#include<bits/stdc++.h>
using namespace std;#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define int long long
#define ull unsigned long long
#define bit __builtin_popcountll
#define lowbit(x) ((x)&-(x))
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;const int N=2e5+10;
const int INF=0x3f3f3f3f3f3f3f3f;
const int inf=INT_MIN;
const int mod=998244353;
const int base=283;void solve(){int n;cin>>n;vi a(n+1);for(int i=1;i<=n;i++){cin>>a[i];}sort(a.begin()+1,a.end());int t=a[1];for(int i=2;i<=n;i++){t=(t+a[i])/2;}cout<<t<<"\n";
}
signed main() {vcoistntint _=1;cin>>_;while(_--) {solve();}return 0;
}B. Maximize Mex
思路
暴力跑从0到n，如果这个数出现过就往后跑，并把多余的传给i+x这个数，直到出现次数为0的数
代码
void solve(){int n,x;cin>>n>>x;vi a(n+10);map<int,int>mp;for(int i=1;i<=n;i++){cin>>a[i];mp[a[i]]++;}sort(a.begin()+1,a.begin()+1+n);vi p(n+10);for(int i=0;i<n;i++){if(i<x){if(!mp[i]){cout<<i<<"\n";return;}p[i]+=(mp[i]-1);}else{p[i]+=(mp[i]-1)+p[i-x];if(p[i]<0){cout<<i<<"\n";return;}}}cout<<n<<"\n";
}C1. Adjust The Presentation (Easy Version)
思路
可以发现我们只需要看b数组中第一次出现的数的顺序，如果此顺序是a的一个前缀则输出“YA”否则输出“TIDAK”
代码
#include<bits/stdc++.h>
using namespace std;#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define int long long
#define ull unsigned long long
#define bit __builtin_popcountll
#define lowbit(x) ((x)&-(x))
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;void solve(){int n,m,q;cin>>n>>m>>q;vi a(n+10);for(int i=1;i<=n;i++){cin>>a[i];}int j=1;map<int,bool> mp;bool flag=true;for(int i=1;i<=m;i++){int x;cin>>x;if(!mp[x]){if(a[j]==x){j++;mp[x]=true;}else{flag=false;}}}if(flag){cout<<"YA\n";}else{cout<<"TIDAK\n";}
}
signed main() {vcoistntint _=1;cin>>_;while(_--) solve();return 0;
}C2. Adjust The Presentation (Hard Version)
思路
此题和C1的结论一样，要看b数组中数第一次出现的位置，不同的是我们要对数组b进行更改，我们可以用set来实现进行维护
代码
#include<bits/stdc++.h>
using namespace std;#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define int long long
#define ull unsigned long long
#define bit __builtin_popcountll
#define lowbit(x) ((x)&-(x))
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;void solve(){int n,m,q;cin>>n>>m>>q;vi a(n+10),mp(n+10);for(int i=1;i<=n;i++){cin>>a[i];mp[a[i]]=i;}set<int> st[n+1];vi b(m+10);for(int i=1;i<=m;i++){cin>>b[i];st[b[i]].insert(i);}int cnt=0;vi f(n+10);for(int i=1;i<=n-1;i++){if(!st[a[i+1]].empty()&&(st[a[i]].empty()||(*st[a[i]].begin())>(*st[a[i+1]].begin()))){f[i]=1;cnt++;}}if(cnt){cout<<"TIDAK\n";}else{cout<<"YA\n";}auto updata=[&](int i)->void{if(i>=n||i<=0) return;if(!st[a[i+1]].empty()&&(st[a[i]].empty()||(*st[a[i]].begin())>(*st[a[i+1]].begin()))){cnt+=1-f[i];f[i]=1;}else{cnt-=f[i];f[i]=0;}};while(q--){int s,t;cin>>s>>t;int x=b[s];st[x].erase(s);st[t].insert(s);b[s]=t;updata(mp[t]),updata(mp[t]-1);updata(mp[x]),updata(mp[x]-1);if(cnt){cout<<"TIDAK\n";}else{cout<<"YA\n";}}
}
signed main() {vcoistntint _=1;cin>>_;while(_--) solve();return 0;
}
