E和F通过人数太少，也由于个人能力问题，就不去补了。

A Strange Partition

题意

给出长度为n的数组和一个整数x，我们可以把其中任意两个数合并为一个数。数组的“美丽值”计算方法为数组中所有元素分别对x除法（向上取整）的和，求最大和最小的的“美丽值”。

题解

显而易见，元素越多，“美丽值”越大，反之越小。
分别除和加在一起除即为最大和最小值。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f 
int main(void)
{
    int _;
    cin>>_;
    while(_--){
        ll n,x;
        cin>>n>>x;
        ll s,maxsum=0,sum=0;
        for(int i=0;i<n;i++){
            cin>>s;
            sum+=s;
            if(s%x){
              maxsum+=s/x+1;
            }
            else{
              maxsum+=s/x;
            }

        }
        if(sum%x){
              sum=sum/x+1;
            }
            else{
              sum=sum/x;
            }

        cout<<sum<<" "<<maxsum<<endl;
    }
}

B Strange List

题意

还是给出一个长度n的数组和一个整数x。从头开始遍历，如果n_i%x为0则将n个n_i/x追加到数组末端，否则停止遍历，求最终数组的和。

题解

直接模拟即可，注意内存优化。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
int main(void)
{
    int _;
    cin>>_;
    while(_--){
        deque<pair<ll,ll>> m;
        ll sum=0,flag=0;
        int n,x,s;
        cin>>n>>x;
        for(int i=0;i<n;i++){
            cin>>s;
            pair<ll,ll> p;
            p.first=s;
            p.second=1;
            m.push_back(p); 
        }
        for(int i=0;i<m.size();i++){
            sum+=m[i].first*m[i].second;
            if(m[i].first%x==0&&flag==0){
                pair<ll,ll> p;
                p.first=m[i].first/x;
                p.second=m[i].second*x;
                m.push_back(p);
            }
            else{
                flag=1;
            }
        }
        cout<<sum<<endl;
    }
}

C Strange Birthday Party

题意

Petya举办生日聚会，有n个朋友和m个礼物，Petya为每位朋友分配了一个值k_i，礼物一定按照结果顺序排列（c_j）。Petya可以给朋友送礼物（必须满足条件j\leq k_i），也可以直接给他们c_{k_{i}}美元，每个礼物只能买一次，求最小花费。

题解

把朋友排个序，然后可以拿礼物或者给钱。
从后向前遍历，因为礼物是有序的，所以便宜的礼物优先给后面，前面的直接给钱就行了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
int main(void)
{
    int _;
    cin>>_;
    while(_--){
        ll n,m;
        cin>>n>>m;
        ll k[n],c[m+1];
        for(int i=0;i<n;i++) cin>>k[i];
        for(int i=1;i<=m;i++) cin>>c[i];
        sort(k,k+n);
        ll sum=0,fr=1;
        for(int i=n-1;i>=0;i--){
            if(fr<=k[i]){
                sum+=c[fr];
                fr++;
            }
            else sum+=c[k[i]];
        }
        cout<<sum<<endl;
    }
}

D Strange Definition

题意

如果x和y的\frac{lcm(x,y)}{gcd(x,y)}为完全平方数，即x,y满足关系“adjacent”。
给出长度为n的数组a，每次操作会将a_i替换为所有和它具有adjacent关系的元素（包括自身）的乘积。
d_i为与a_i具有adjacent关系的元素的个数（包括其本身），数组的优美度为d_i的最大值。
现有q次查询，每次查询给一个w，求w次操作后的优美度。

题解

已知lcm(x,y)=\frac{xy}{gcd(x,y)}
那么\frac{lcm(x,y)}{gcd(x,y)}=\frac{xy}{gcd(x,y)^2}
gcd(x,y)^2一定是完全平方数，如果xy是完全平方数，则\frac{xy}{gcd(x,y)^2}是完全平方数。
所以\frac{lcm(x,y)}{gcd(x,y)}为完全平方数等价于xy为完全平方数。
首先，数组中任何一个整数a都可以表示成a=br^2（r为大于等于1的整数），当r为1时，也就是我们把所有的完全平方数约掉，只有a_i=a_j的时候，a_i和a_j才满足adjacent关系。所以，这里可以得出，当w=0时，答案就是数组中个数最多元素的个数。
我们输入数据之后，用map<int,int> m保存，key为b，value为个数。
另外，由于平方的性质，一次变换和多次变换结果相同。当w大于等于1时，若b等于1，则该数和一一个完全平方数满足adjacent关系。当进行变换时，所有具有adjacent关系的数的b一定相等，奇数个b相乘一定不是完全平方数（b=1除外），偶数个b相乘一定是完全平方数。另外，如果x和y都是完全平方数，那么x和y具有adjacent关系。所以答案就是max(所有偶数个元素(b不为1)value的和+b=1的value,b_i的value（value奇数且value最大）)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int _;
    cin>>_;
    while(_--){
        int n,s;
        map<int,int> a;
        cin>>n;
        for(int i=0;i<n;i++){
            cin>>s;
            for(int j=2;j*j<=s;j++){//去除完全平方数
                while(s%(j*j)==0){
                    s=s/(j*j);
                }
            }
            a[s]++;
        }
        int re0=0,re1=0,re2=0;
        for(auto i:a){
        //cout<<"i"<<" "<<i.first<<" "<<i.second<<endl;
           re0=max(i.second,re0);
           if(i.second%2==0) re2+=i.second;//奇数取最大
           else re1=max(re1,i.second);//偶数就相加
        }
        if(a[1]%2==1) re2+=a[1];//如果1是奇数，加上1
        re1=max(re1,re2);//奇数和偶数的最大值
        ll q,w;
        cin>>q;
        for(ll i=0;i<q;i++){
            cin>>w;
            //scanf("%lld",&w);
            if(w==0)cout<<re0<<endl;
            else cout<<re1<<endl;
        }
    }
}

题目来源于https://codeforces.com/contest/1471