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 13:40] lak [李元恺] |
2020-2021:teams:acm_life_from_zero:7.25-7.31 [2020/07/31 18:34] (当前版本) lak [姜维翰] |
||
|---|---|---|---|
| 行 10: | 行 10: | ||
| ====== 姜维翰 ====== | ====== 姜维翰 ====== | ||
| - | ===== 专题 ===== | ||
| ===== 比赛 ===== | ===== 比赛 ===== | ||
| - | ===== 题目 ===== | + | cf edu 92（码农专场.jpg） |
| ====== 袁熙 ====== | ====== 袁熙 ====== | ||
| 行 21: | 行 19: | ||
| 没有比赛 | 没有比赛 | ||
| ===== 题目 ===== | ===== 题目 ===== | ||
| + | 补题（板子） 牛客第五场B \\ [[https://ac.nowcoder.com/acm/contest/5670|链接]] \\ | ||
| + | 题意；给边带权的树，可以连边或删边，要求始终连通且形成的环异或和=0，求最后图的最小权值和\\ | ||
| + | 思路：对原图的树，可以把边权用所连点的权值异或和来表示，转化成异或最小生成树\\ | ||
| + | 类似的模板题：[[http://codeforces.com/problemset/problem/888/G|链接]] | ||
| ====== 本周推荐 ====== | ====== 本周推荐 ====== | ||
| ====== 李元恺 ====== | ====== 李元恺 ====== | ||
| 行 47: | 行 49: | ||
| 4、存在一个使答案等于2n-k-1的方案，给出构造：设G(V,E)最大DAG导出子图=S($V_1$,$E_1$),令序列为$V \setminus V_1$,$V_1$,$V \setminus V_1$ | 4、存在一个使答案等于2n-k-1的方案，给出构造：设G(V,E)最大DAG导出子图=S($V_1$,$E_1$),令序列为$V \setminus V_1$,$V_1$,$V \setminus V_1$ | ||
| + | |||
| + | 5、状压dp求出最大DAG导出子图 | ||
| comment:这周做的最有意思的题，推荐给大家 | comment:这周做的最有意思的题，推荐给大家 | ||
| ====== 袁熙 ====== | ====== 袁熙 ====== | ||
| + | CF1372F [[https://codeforces.com/contest/1372/problem/F|题目链接]]\\ | ||
| + | |||
| + | 标签：构造 交互\\ | ||
| + | |||
| + | 题意：一个长为$n$，不降的序列，由$k$个不同的数组成，每次可以询问$l,r$中的众数（数量相同取更小值），要求在$4k$次询问内确定原序列\\ | ||
| + | |||
| + | 思路：考虑如果已知某个数在某个位置$p$，和这个数的总出现次数$f$。那么可以用两次询问$(p,p+f-1),(p-f+1,p)$得到这个数的结果.那么如果能使所有数都出现在查询结果中，就能知道整个序列。\\ | ||
| + | 要想构造出上述的查询，我们可以从$(1,n)$开始，用当前区间的最高频率$f$为间隔，每次确认$f,2f,..$这些点的数值，这些数值两两不等，且$(1,n)$查询得到的众数一定在这些数值中。接下来递归地对两边的区间进行询问。这样对于每个数，找到它的一个出现位置+确定它的出现区间+递归时确定它作为众数的区间，共4k次询问。\\ | ||
| + | |||
| + | comment：做法比较多的构造题\\ | ||
| ====== 姜维翰 ====== | ====== 姜维翰 ====== | ||
| + | CF1292C | ||
| + | |||
| + | tag：dp | ||
| + | |||
| + | 题意：给一棵n个点的树，要求给每条边选择一个0到n-2的数，不可以重复，mex(u,v)表示点u到点v经过的数的mex，求最大化所有点对的mex和，n=3000 | ||
| + | |||
| + | 解法：可以看到，树上存在一条链，链上包含[0,l]上的所有值，答案只和这个链的位置和链上数的摆法有关 | ||
| + | 我们还可以通过贪心，看出链应该是这个样子的：10，8，6，4，2，0，1，3，5，7，9 | ||
| + | 于是链的摆法就确定了 | ||
| + | |||
| + | 那么我们就f[u][v]来表示链为u到v时的答案 | ||
| + | |||
| + | 在算答案的时候要把mex求和转化成对mex大于某个值的点对的计数 | ||
| + | |||
| + | 这样就可以n方的时间内完成了 | ||
| + | |||
| + | comment：很独特的一道dp题，答案计数方法的转换也很经典 | ||
2020-2021/teams/acm_life_from_zero/7.25-7.31.1596174026.txt.gz · 最后更改: 2020/07/31 13:40 由 lak
