复健，水平下降剧烈

A. GCD vs LCM

You are given a positive integer n. You have to find 4 positive integers a,b,c,d such that

• a+b+c+d=n, and

• gcd(a,b)=lcm(c,d).

If there are several possible answers you can output any of them. It is possible to show that the answer always exists.

寻找四个正整数a, b, c, d，使a+b+c+d=n, 且gcd(a,b)=lcm(c,d).

看到题目提出“several possible answers”，就知道可以生成合法的答案。

#include<cstdio>
using namespace std;
int main(){
    int t,n;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        if(n%2){//奇数：k, k+1, 1, 1; k=(n-3)/2
            int k = (n-3)/2;
            printf("%d %d 1 1\n", k, k+1);
        }
        else if(n%4){//偶数: k+1, k-1, 1, 1; k=(n-2)/2. 这情况下必须不能被4整除。 
            int k = (n-2)/2;
            printf("%d %d 1 1\n", k+1, k-1);
        }
        else{
            printf("%d %d %d %d\n",n/4,n/4,n/4,n/4);
        }
    }
    return 0;
 } 

B. Array Cloning Technique

You are given an array a of n integers. Initially there is only one copy of the given array.

You can do operations of two types:

• Choose any array and clone it. After that there is one more copy of the chosen array.

• Swap two elements from any two copies (maybe in the same copy) on any positions.

You need to find the minimal number of operations needed to obtain a copy where all elements are equal.

初始时有一个数组，含有n个数字。每次操作可以复制任意一个数组，或者交换任意两个数组里的任意两个数字。求得到一个只含有相同数字的数组所需要的最少操作步数。

可以看出，顺序没有意义，最终具体是哪个相同的数字没有意义。

为了减少操作次数，选定原数组里最多的数字作为目标数字。该数字出现的次数设为m。因为只需要从其他数组里更换相同的数字到其他位置上，所以交换的次数固定为 n-m。

复制的次数则是m·2^ans≥n。ans=log(ceil(m/n))。【此处注意int/int需要强制转换。复健遇到的第一个卡了我半个小时的傻逼错误。】

#include<cstdio>
#include<cstring>
#include<map>
#include<cmath>
using namespace std;
const int N = 1000007;
int n,m,t,a,lg2[N];
map<int,int>mp;
int main(){
    for(int i=1,j=0;i<=N;i=i<<1,j++){
        lg2[i]=j;
    }
    int tmp=0;
    for(int i=1;i<=N;i++){
        if(lg2[i]) tmp=lg2[i]+1;
        else lg2[i]=tmp;
    }
    scanf("%d",&t);
    while(t--){
        mp.clear();
        m=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a);
            mp[a]++;
            if(mp[a]>m) m=mp[a];
        }
        int ans = lg2[int(ceil(1.0*n/m))]+n-m;
        printf("%d\n",ans);
    }
    return 0;
}

C. Tree Infection

A tree is a connected graph without cycles. A rooted tree has a special vertex called the root. The parent of a vertex v (different from root) is the previous to v vertex on the shortest path from the root to the vertex v. Children of the vertex v are all vertices for which v is the parent.

You are given a rooted tree with n vertices. The vertex 1 is the root. Initially, all vertices are healthy.

Each second you do two operations, the spreading operation and, after that, the injection operation:

1. Spreading: for each vertex v, if at least one child of v is infected, you can spread the disease by infecting at most one other child of v of your choice.

2. Injection: you can choose any healthy vertex and infect it.

This process repeats each second until the whole tree is infected. You need to find the minimal number of seconds needed to infect the whole tree.

一棵有n个结点的树，每秒可以进行以下操作：对于每个节点，如果它的儿子里有被感染的节点，那么感染可以传染给它的最多另一个儿子；同时可以选择一个健康的节点感染。求把整棵树感染的最短时间。

因为读错题卡了四天的一道题。没看到“最多另一个儿子”，因此以为感染速率和已经感染的节点数量有关。

可以把节点分组。父节点相同的所有节点是一组（根节点单独一组），如果这一组里有被感染的节点，那么每秒会新增一个被感染的节点。组和组之间不会互相影响。

设一共有m组，那么想要感染整棵树，就必须每组至少感染一次，也就是至少手动感染m个结点，也就至少需要m秒。在这m秒里，如果优先感染节点数量多的组，能给它更多的时间扩散，也就更有可能在这m秒结束之前完成本组的扩散。

如果m秒结束后，还有些节点没有完成扩散的话，就去手动补充。此处手动补充不会影响扩散速率。剩余节点最多的组只靠自己扩散来完成感染的速度最慢，所以优先补充剩余节点最多的组。此处是变化的，所以使用优先队列，感染后再塞回去。不需要每秒都操作一次，只需要记录在m秒后经过的秒数。只要某刻剩余节点最多的组小于这秒数，就意味着剩下的所有组都可以在这段时间里被自动扩散完成了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N=200007;
int t,n,a[N];
bool cmp(int x,int y){
    return x>y;
}
priority_queue<int>q;
int main()
{
    scanf("%d",&t);
    while(t--){
        memset(a,0,sizeof(a));
        scanf("%d",&n);
        int x;
        for(int i=1;i<n;i++){
            scanf("%d",&x);
            a[x]++;
        }
        int m=1;
        for(int i=1;i<=n;i++){
            if(a[i]) m++;
        }
        int ans=m;
        sort(a+1,a+1+n,cmp);
        for(int i=1;i<=n;i++){
            if(!a[i]) break;
            if(a[i]-m>0){
                a[i]-=m;q.push(a[i]);
            }
            else a[i]=0;
            m--;
        }
        int tmp=0;
        while(!q.empty()){
            x=q.top();q.pop();
            if(x>tmp){
                tmp++;x--;
                if(x) q.push(x);
            }
        }
        printf("%d\n",ans+tmp);
    }
    return 0;
}

剩余的题目连看的时间都没有。希望以后能提高吧。