2020-2021:teams:acm_life_from_zero:7.25-7.31
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:acm_life_from_zero:7.25-7.31 [2020/07/31 15:43] holmium [姜维翰] |
2020-2021:teams:acm_life_from_zero:7.25-7.31 [2020/07/31 18:34] (当前版本) lak [姜维翰] |
||
|---|---|---|---|
| 行 10: | 行 10: | ||
| ====== 姜维翰 ====== | ====== 姜维翰 ====== | ||
| - | ===== 专题 ===== | ||
| ===== 比赛 ===== | ===== 比赛 ===== | ||
| - | ===== 题目 ===== | + | cf edu 92（码农专场.jpg） |
| ====== 袁熙 ====== | ====== 袁熙 ====== | ||
| 行 69: | 行 67: | ||
| CF1292C | CF1292C | ||
| - | DP题 | + | tag：dp |
| 题意：给一棵n个点的树，要求给每条边选择一个0到n-2的数，不可以重复，mex(u,v)表示点u到点v经过的数的mex，求最大化所有点对的mex和，n=3000 | 题意：给一棵n个点的树，要求给每条边选择一个0到n-2的数，不可以重复，mex(u,v)表示点u到点v经过的数的mex，求最大化所有点对的mex和，n=3000 | ||
| 解法：可以看到，树上存在一条链，链上包含[0,l]上的所有值，答案只和这个链的位置和链上数的摆法有关 | 解法：可以看到，树上存在一条链，链上包含[0,l]上的所有值，答案只和这个链的位置和链上数的摆法有关 | ||
| - | |||
| 我们还可以通过贪心，看出链应该是这个样子的：10，8，6，4，2，0，1，3，5，7，9 | 我们还可以通过贪心，看出链应该是这个样子的：10，8，6，4，2，0，1，3，5，7，9 | ||
| - | |||
| 于是链的摆法就确定了 | 于是链的摆法就确定了 | ||
2020-2021/teams/acm_life_from_zero/7.25-7.31.1596181417.txt.gz · 最后更改: 2020/07/31 15:43 由 holmium
