第一周

1. 选择数字

第一种思路

读入所有数，并建立一个 $hash$ 表储存值域内的数字是否出现过即可。

第二种思路

因为都为 正整数，所以直接输出两个序列的 最大值 即可。

2. 最大中位数

第一种思路

二分查找 基础题，将数据排序后，二分能加在 中位数上的最大值，

如果剩下的操作能使 中位数后的值 不小于中位数本身即可。

bool check(LL x)
{
    LL sum = a[m] + x;
    LL num = 0;
    for (int i = m; i <= n; i ++ )
    {
        if (a[i] < sum) num += (sum - a[i]); 
        else break;
    }
    return num <= k;
}

第二种思路

根据题意我们可以得出，在数据排序后，只有中位数后面的数都 不小于中位数，中位数的值才能增加。

所以，我们可以将中位数后的值作一个差分，每当往后 $i$ 个索引位，就要将 $[m, i]$ 之间的值全部增加到 $i$

    int m = (n + 1) / 2;
    for (int i = m + 1; i <= n; i ++ )
    {
        q[i] = (a[i] - a[i-1]) * (i - m);
    }

3. 数字移动

第一种思路

此图可以看作由多个不相干的简单环组成

可以将每个环看成一个连通块，题意就是求每个连通块大小

用并查集实现就可以了，这里是合并的过程

int fa[N], se[N];
int find(int x) // 并查集
{
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}
...
for (int i = 1; i <= n; i ++ ) fa[i] = i, se[i] = 1;    // 每个点的祖先初始化为自己，各自为 1 个连通块
for (int i = 1; i <= n; i ++ )
{
    int j;
    scanf("%d", &j);

    int a = find(i), b = find(j);   // 查找祖先
    if (a != b)                     // 不是，所以合并
    {
        fa[b] = a;                  // b 祖先为 a
        se[a] += se[b];             // a 所在连通块加上 b 所在连通块
    }
}

或者也可以用 $Tarjan$ 实现，这个之后补齐。