2020-2021:teams:running_chicken:2020_summer_week3_report
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:running_chicken:2020_summer_week3_report [2020/07/30 23:52] selia [XX] |
2020-2021:teams:running_chicken:2020_summer_week3_report [2020/08/07 21:47] (当前版本) selia [todolist（补题）] |
||
|---|---|---|---|
| 行 11: | 行 11: | ||
| =====todolist（补题）===== | =====todolist（补题）===== | ||
| - | 2020牛客暑期多校训练营（第五场） | + | Codeforces Round #659 zrx A/D xx **B**/**E** cjy C/F |
| - | 2020牛客暑期多校训练营（第六场） | + | 2020牛客暑期多校训练营（第五场）zrx A/H xx **K** cjy G/J |
| + | |||
| + | 2020牛客暑期多校训练营（第六场）zrx E xx I cjy **A**/F | ||
| + | |||
| + | Codeforces Educational Round #92 xx **E** zrx F cjy G | ||
| - | Codeforces Educational Round #670 | + | Codeforces Round #660 cjy C zrx D xx E |
| =====CJY===== | =====CJY===== | ||
| ====专题==== | ====专题==== | ||
| + | 欧拉回路 | ||
| ====比赛==== | ====比赛==== | ||
| + | 本周未参加个人比赛 | ||
| ====题目==== | ====题目==== | ||
| + | 2020牛客暑期多校训练营（第六场）A | ||
| =====ZRX===== | =====ZRX===== | ||
| ====专题==== | ====专题==== | ||
| + | |||
| + | 本周暂无 | ||
| ====比赛==== | ====比赛==== | ||
| + | |||
| + | 2020牛客暑期多校训练营（第五场） | ||
| + | |||
| + | 2020牛客暑期多校训练营（第六场） | ||
| ====题目==== | ====题目==== | ||
| + | |||
| + | 2020牛客暑期多校训练营（第五场） a、h | ||
| =====XX===== | =====XX===== | ||
| 行 36: | 行 51: | ||
| ====专题==== | ====专题==== | ||
| + | 点分治 | ||
| + | |||
| + | 倍增优化DP | ||
| ====比赛==== | ====比赛==== | ||
| + | Codeforces Educational Round #92 | ||
| ====题目==== | ====题目==== | ||
| + | |||
| + | Codeforces Educational Round F | ||
| ======本周推荐====== | ======本周推荐====== | ||
| 行 44: | 行 65: | ||
| =====zrx===== | =====zrx===== | ||
| + | 2020牛客暑期多校训练营（第五场） h | ||
| + | |||
| + | 题意：最后转化问题后，得到的是有n个物品，都只有一个，每个物品对应多个互不相交的区间，给定一个区间，如果覆盖了一个物品的对应的一个区间，那么这个物品就获得了，每次给定一个区间求得到多少物品，强制在线。 | ||
| + | |||
| + | 题解：首先，这样互不相交的区间可以化成二维平面上的点，一个待求，如果覆盖一次算一个物品的话，那么求[l,r]区间的答案就等于x大于等于l，且y小于等于r的点数，但是每个物品最多被加一次。假设一个物品是[l1,r1],[l2,r2] 那就两个两个区间之间加权值为-1的点，如[l1,r2]的权值为-1，这样最后二维区间求和就行了！主席树可以很好的在线解决。 | ||
| + | |||
| + | 思考：把区间转换成点，以及去重方式很好。 | ||
| =====cjy===== | =====cjy===== | ||
| + | |||
| + | African Sort | ||
| **题意** | **题意** | ||
| + | |||
| + | 给你一个排列，你每次可以选择一个下标集合，并把这个集合的元素随机排列，代价是这个集合的大小，求把原序列变成递增序列的期望代价。 | ||
| **思路**： | **思路**： | ||
| + | |||
| + | 首先把代价转换为每一个元素被选择的次数。有一个推论对于一个n元环，随机一次后，每个元素所在环的大小等概率分散在1-n。因此最优策略应 | ||
| + | |||
| + | 该是原排列中的每一个小环分别进行操作。操作代价可以通过之前的推论进行预处理。 | ||
| + | |||
| **评论**： | **评论**： | ||
| + | 这个题的思维度大，很有意思。 | ||
| =====XX===== | =====XX===== | ||
| 行 70: | 行 108: | ||
| 一个神奇的结论： | 一个神奇的结论： | ||
| - | 如果存在这样两个大格，(x~1~, y~1~)在(x~2~, y~2~)的左上，(x~1~, y~1~)大格的左上角小格被占据，(x~2~, y~2~)大格的右下角被占据，那么不合法。因为(x~i~, y~1~)的大格只能放一枚棋子在右下角小格，相应的(x~1~ +1, y~1~)、(x~1~, y~1~ +1)、(x~1~+1, y~1~+1)这三个大格也只能放右下角……以此类推，(x~2~, y~2~)的大格也只能放右下角，但是这个位置被占据了，因此不合法。 | + | 如果存在这样两个大格，(x$_{1}$, y$_{1}$)在(x$_{2}$, y$_{2}$)的左上，(x$_{1}$, y$_{1}$)大格的左上角小格被占据，($_{2}$, y$_{2}$)大格的右下角被占据，那么不合法。因为(x$_{1}$, y$_{1}$)的大格只能放一枚棋子在右下角小格，相应的(x$_{1}$ +1, y$_{1}$)、(x$_{1}$, y$_{1}$ +1)、(x$_{1}$+1, y$_{1}$+1)这三个大格也只能放右下角……以此类推，(x$_{2}$, y$_{2}$)的大格也只能放右下角，但是这个位置被占据了，因此不合法。 |
| **实现**： | **实现**： | ||
2020-2021/teams/running_chicken/2020_summer_week3_report.1596124365.txt.gz · 最后更改: 2020/07/30 23:52 由 selia
