Educational Codeforces Round 108 (Rated for Div. 2) C

#include <bits/stdc++.h>
#define priority_queue < ll, std::vector<ll>, std::greater<ll> > mnheap;
#define REP(i,a,b) for (auto i = a; i != b; i++)
#define ll long long int
#define vi vector<int>
#define vll vector<ll>
#define vvi vector < vi >
#define all(c) c.begin(),c.end()
#define rall(c) c.rbegin(),c.rend()
#define eb emplace_back
#define f first
#define s second
#define pb push_back
using namespace std;
void read(int n,vector<int>& x)
{
    x.clear();
    x.resize(n);
    for(int i = 0;i<n;i++)
    {
        cin>>x[i];
    }

}
void read(int n,int m,vector<vector<int>>& x)
{
    x.clear();
    x.resize(n,vector<int>(m));
    for(int i = 0;i<n;i++)
    {
        for(int j = 0 ;j<m;j++)
            cin>>x[i][j];
    }
}
void read(int n,vector<vector<int>>& x)
{
    x.clear();
    x.resize(n+1);
    for(int i = 0;i<n-1;i++)
    {
         int a,b;
         cin>>a>>b;
         x[a].pb(b);
         x[b].pb(a);
    }
}
void read(int n,vector<vector<int>>& x,int m)
{
    x.clear();
    x.resize(n+1);
    for(int i = 0;i<m;i++)
    {
         int a,b;
         cin>>a>>b;
         x[a].pb(b);
         x[b].pb(a);
    }
}
void read(int n,vector<ll>& x)
{
    x.clear();
    x.resize(n);
    for(int i = 0;i<n;i++)
    {
        cin>>x[i];
    }
}
bool comp(vector<ll>& a,vector<ll>& b){
    return a.size() > b.size();
}
int main()
{
    std::ios::sync_with_stdio(false);
    int T = 1;
    cin>>T;
    for(int t = 1;t<=T;t++)
    {
        // cout<<"Case #"<<t<<": ";
        int n;
        cin>>n;
        vector<ll> u;
        read(n,u);
        vector<vector<ll>> skills(n);
        vector<ll> sizes(n);
        vector<vector<ll>> pref(n);
        for(int i = 0;i<n;i++){
            ll x;
            cin>>x;
            skills[u[i]-1].pb(x);
            sizes[u[i]-1]++;
        }
        sort(all(skills),comp);
        sort(rall(sizes));
        for(int i =0;i<n;i++){
            sort(rall(skills[i]));
        }
        for(int i = 0;i<n;i++){
            for(int j=0;j<skills[i].size();j++){
                if(j == 0){
                    pref[i].pb(skills[i][j]);
                }
                else{
                    pref[i].pb(pref[i].back() + skills[i][j]);
                }
            }
        }
        for(int i = 1;i<=n;i++){
            ll sum = 0;
            for(int j = 0;j<n;j++){
                if(sizes[j] < i){
                    break;
                }
                else{
                    ll x = sizes[j] / i;
                    sum += pref[j][x*i-1];
                }
            }
            cout<<sum<<" ";
        }

        cout<<endl;

    }

    return 0;
}

 

上一篇:因为未启用行移动功能 不能闪回表


下一篇:关于 FWT 的一些理解