A - Dawid and Bags of Candies

Problem - A - Codeforces

题意

四个数分给两个人，必须分完，每个数只能给一个人，一个人可以拿到多个数，数字不可以被拆分。问能否有一种分配方式使得每个人获得数字的和相等。

题解

分类讨论：

  1. 三个小的 = 一个大的
  2. 最大最小 = 次大次小

B - Ania and Minimizing

Problem - B - Codeforces

题意

给出一个不含前导零的数字，你可以修改至多 $k$ 次，问修改后结果的最小值是什么

题解

第一位优先改成一，其余位改成零

C - Anadi and Domino

Problem - C - Codeforces

题意

在一个有向图上，摆放多米诺骨牌，要求每个牌朝向同一个点的点数相同，每个牌只能用一次。

题解

注意到 $n$ 的数据范围极小。

  1. 当 $n\le 6$ 时，最多只有 $15$ 条边，除去（1，1），（2，2）…六条边，每个节点对应一个数，给的边数 $m$ 即为可放置的骨牌数。
  2. 当 $n=7$ 时，因为每个顶点出发都只能为 $1\sim 6$，那么，必然第七个顶点会和前面一个顶点重复，所以两层 for 循环遍历一下找 $i$ 和 $j$ 顶点（假设 $i,j$ 相同顶点），并记录到其它点都存在边的情况（无重边），最后用m减掉不能放骨牌的边即可；

D - Marcin and Training Camp

Problem - D - Codeforces

题意

给出两个序列 $\{a_n\},\{b_n\}$，其中 $a_i$ 表示第 $i$ 个人会的算法编号（用二进制表示，权值为 $2^{j}$ 的二进制位为 $1$ 时代表该人会编号为 $j+1$ 的算法）、$b_i$ 表示这个学生的能力值。现在我们需要选出大于等于 $2$ 的学生，让他们在可以和平共处的情况下能力值之和最大。和平共处的条件为对于所有的学生都不会有会其他学生都不会的算法的情况。

题解

注意到对于两个学生，只要会的知识点二进制不一样，就会存在鄙视关系。所以直接大力统计每一个 $a_i$ 的出现次数，如果相同 $a_i$ 的数量大于等于 $2$，那么就可以以这两个人为基础，寻找符合条件的所有同学即可。

1
2
3
4
5
6
7
8
9
for(auto it : ma)
    if(it.second > 1)
        for(int i = 1; i <= n; ++i)
            if((it.first|a[i])==it.first)
                se.insert(i);
LL ans = 0;
for(auto it : se)
    ans += b[it];
cout << ans << endl;

E - Kamil and Making a Stream

Problem - E - Codeforces

题意

给定一棵树，树上每一个点有点权。定义一个路径的美丽值是路径上所有点的 $\gcd$，特别的，对于单个节点 $u$，其美丽值为 $u$ 。求树上所有路径的美丽值之和。

题解

看到树上路径的题大概率都会往点分治的方向去想。但是很可惜这道题显然不是点分治，因为 CF 大都倾向于考思维题而不是算法题。

考虑 $\gcd$ 的性质，我们会发现对于一串数字的前缀的 $\gcd$，其答案一定单调不增。而实际上不同的 $\gcd$ 的数量级很显然是 $\log$ 级别的。

所以说对于正解，我们大可以用 map 大力存下所有不同的 $\gcd$ 在大力得出答案即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void dfs(int x,int fa,map<int,int>fm){
    map<int,int>mp;
    mp[w[x]]=1;
    ans+=w[x];
    for(auto [a,cnt]:fm){
        mp[gcd(a,w[x])]+=cnt;
        ans+=cnt*gcd(a,w[x]);
        ans%=Mod;
    }
    for(auto y:g[x]){
        if(y==fa)continue;
        dfs(y,x,mp);
    }
}