T1

题意：统计取模之后出现最多的数

思路：没啥好说的

T2

题意：给n,k,t，要求构造长度为n含有k个1以及有恰好t对相邻1的01串，无法满足则返回-1

思路：可以得出，k个1最多组成k-1对相邻1（连续k个1），最少则是k-1 - (n-k)，t在这个范围之内可以通过把0依次插入连续的1之间来构造得到（每插入一个0减少一个相邻对1）

int main() {
    int n,k,t;
    cin>>n>>k>>t;
    if (t <= k-1 && k <= n && k-1-t <= n-k){
        string s = "";
        int p = k-1 - t;
        while(p--){
            s += "10";
        }
        p = k - (k-1-t);
        while(p--){s+="1";}
        p = n-k - (k-1-t);
        while(p--){s+="0";}
        cout<<s;
    }
    else cout<<-1;
}

T3

题意：给x,k和一个长度为n的数组a（输入均为正整数），每次可以选取一个元素-x，问经过k次操作之后能够得到的数组最小的最大值

思路：O(n)验证一个答案，容易想到二分+验证来找到解。需要注意的是验证答案的时候把k刚好用完不一定是最优解，应该按照剩下的k>=0算合法解来逼近最优解

typedef long long ll;
ll a[100005];
int n;
ll k, x;
bool check(ll target)
{
    ll tmp = k;
    for (int i = 0; i < n; ++i)
    {
        tmp -= max(0LL, ((a[i] - target) + x - 1) / x);
        if (tmp < 0)
            return false;
    }
    if (tmp >= 0)
        return true;
    return false;
}

int main()
{

    cin >> n >> k >> x;
    ll maxx = 0;
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
        maxx = max(a[i], maxx);
    }

    ll l = maxx - k * x, r = maxx;
    ll mid;
    while (l <= r)
    {
        mid = (l + r) >> 1;
        if (check(mid))
        {
            r = mid - 1;
        }
        else
            l = mid + 1;
    }
    cout << l;
}

T4

Hard的一题，写了1h+还是没写出来，太菜了。。。

题意：给一颗有根树，每个结点有权值。每个子树的答案定义为该子树每个结点的权值的积的因数个数，求统计所有子树的答案之和（取模1e9+7）

思路：

假设n的质因数分解为 ，
因数个数则为
又有

对于一个子树的根结点，该子树的权值乘积可以通过根结点的权值乘以每个孩子的子树权值乘积来递归地得到，因此在递归的过程中维护一个质因数列表（我用一个unordered_map实现），当前子树的质因数列表可以通过当前根结点权值的质因数列表再加上每个孩子的质因数列表得到，通过该质因数列表计算答案，便可递归地求解。

但是写完了最后只过了5%，不知道错在哪里

typedef long long ll;
int a[100005];
vector<int> E[100005];
const ll mod = 1e9 + 7;
ll total_ans = 0;
bool used_pri[100005];
bool used[100005];
vector<ll> prime;
unordered_map<int, ll> dfs(int rt)
{
    // answer of this subtree
    unordered_map<int, ll> ma;
    // prime factorize
    int tmp = a[rt];
    for (auto pri : prime)
    {
        if (!used_pri[tmp])
        {
            ma[tmp] = 1;
            break;
        }

        if (tmp % pri == 0)
        {
            ma[pri] = 0;
            while (tmp % pri == 0)
            {
                tmp /= pri;
                ++ma[pri];
            }
        }
        if (tmp < pri)
            break;
    }

    // count the answer of subtree
    used[rt] = 1;
    for (int v : E[rt])
        if (!used[v])
        {
            auto &&ans_son = dfs(v);
            for (const auto &item : ans_son)
            {
                if (ma.count(item.first))
                    ma[item.first] = (ma[item.first] + item.second) % mod;
                else
                    ma.insert(item);
            }
        }

    // count total ans
    ll tmp_ans = 1;
    for (const auto &item : ma)
    {
        tmp_ans = tmp_ans * ((item.second + 1) % mod) % mod;
    }

    total_ans = (total_ans + tmp_ans) % mod;
    return ma;
}
int main()
{
    // Linear sieve prime
    memset(used_pri, 0, sizeof used_pri);
    used_pri[0] = 1;
    used_pri[1] = 1;
    for (int i = 2; i <= 100000; ++i)
    {
        if (!used_pri[i])
            prime.push_back(i);
        for (int j = 0; i * prime[j] <= 100000LL && j < prime.size(); ++j)
        {
            used_pri[i * prime[j]] = 1;
            if (!i % prime[j])
                break;
        }
    }

    int n;
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
        used[i] = 0;
        E[i].clear();
    }
    for (int i = 0; i < n - 1; ++i)
    {
        int u, v;
        cin >> u >> v;
        E[u - 1].push_back(v - 1);
    }
    total_ans = 0;
    dfs(0);
    cout << total_ans;
}