米哈游笔试

T1 #include <bits/stdc++.h>using namespace std;#define int long longvoid solve(){int n,k;cin>>n>>k;vector<int> a(n+1);for(int i=1;i<=n;i++)cin>>a[i];sort(a.begin(),a.end());int r2=n+1,r1=n+1;int ans=0;for(int i=1;i<=n;i++){r1--;ans+=a[r1];if(i%k==0){r2--;ans+=a[r2];}cout<<ans<<" ";}cout<<endl;}signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T=1;cin>>T;while(T--)solve();return 0;}T2#include <bits/stdc++.h>using namespace std;#define int long longvoid solve(){int n;cin>>n;vector<int> a(n+2),b(n+2),c(n+2);for(int i=1;i<=n;i++){char c;cin>>c;if(c=='A')a[i]++;else b[i]++;a[i]+=a[i-1];b[i]+=b[i-1];}int ans=0;for(int i=n;i>=1;i--)c[i]=max(c[i+1],b[i]+a[n]-a[i]);for(int i=0;i<=n;i++){// cout<<a[i]+c[i+1]<<" ";ans=max(ans,a[i]+c[i+1]-b[i]);}cout<<n-ans<<endl;}signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T=1;cin>>T;while(T--)solve();return 0;}T3#include <bits/stdc++.h>using namespace std;int seg[800005];void build(int id,int l,int r,vector<int>& a){if(l==r){seg[id]=a[l];return;}int mid=(l+r)/2;build(id*2,l,mid,a);build(id*2+1,mid+1,r,a);seg[id]=__gcd(seg[id*2],seg[id*2+1]);}int find(int id,int l,int r,int q,int num){// cout<<l<<" "<<r<<" "<<seg[id]<<endl;if(r<=q){int g=__gcd(seg[id],num);// cout<<g<<endl;if(num==g)return -1;if(l==r)return l;int mid=(l+r)/2;int f=find(id*2+1,mid+1,r,q,num);// cout<<f<<endl;if(f!=-1)return f;return find(id*2,l,mid,q,num);}int mid=(l+r)/2;int f=-1;if(q>=mid+1)f=find(id*2+1,mid+1,r,q,num);if(f!=-1)return f;return find(id*2,l,mid,q,num);}void solve(){int n;cin>>n;vector<vector<int>> r(n+2),o(n+2);vector<int> a(n+1);for(int i=1;i<=n;i++)cin>>a[i];build(1,1,n,a);int cur=a[1];// cout<<find(1,1,5,3,4);for(int i=2;i<=n;i++){cur=__gcd(cur,a[i]);int q=i-1,g=a[i];vector<pair<int,int>> jl;// cout<<find(1,1,n,i-1,g)<<" ";// int cnt=0;while(g!=cur){int re=find(1,1,n,q,g);if(re==-1)break;g=__gcd(g,a[re]);// cout<<g<<" "<<cur<<" ";// cnt++;// if(cnt==100)break;jl.push_back({re,g});}// cout<<cnt<<" ";// cout<<endl;jl.push_back({0,1});for(int j=0;j<jl.size()-1;j++){o[jl[j].first].push_back(a[i]-jl[j].second);r[jl[j+1].first+1].push_back(a[i]-jl[j].second);// cout<<jl[j+1].first+1<<" "<<jl[j].first<<" "<<a[i]-jl[j].second<<endl;}}map<int,int> mp;long long ans=0;for(int i=1;i<n;i++){for(auto num:r[i]){mp[num]++;// cout<<num<<" ";}// cout<<endl;ans+=mp[a[i]];for(auto num:o[i]){mp[num]--;// cout<<num<<" ";}// cout<<endl;}cout<<ans<<endl;}signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T=1;cin>>T;while(T--)solve();return 0;}