2020-2021:teams:wangzai_milk:weekly2
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:weekly2 [2020/05/17 22:00] zars19 [比赛] |
2020-2021:teams:wangzai_milk:weekly2 [2020/05/24 13:27] (当前版本) zars19 [团队训练] |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| ====== 2020.05.11-2020.05.17 周报 ====== | ====== 2020.05.11-2020.05.17 周报 ====== | ||
| ===== 团队训练 ===== | ===== 团队训练 ===== | ||
| - | 2020.05.13 [[https://vjudge.net/contest/373595#rank|2019 Multi-University Training Contest 1]] ''prob: 3:5:13'' ''rnk：141/?'' | + | 2020.05.13 [[https://vjudge.net/contest/373595#rank|2019 Multi-University Training Contest 1]] ''prob: 3:7:13'' ''rnk：141/?'' |
| [[20200513比赛记录]] | [[20200513比赛记录]] | ||
| 行 54: | 行 54: | ||
| [[20200513比赛记录#D-Vacation]] | [[20200513比赛记录#D-Vacation]] | ||
| + | |||
| + | [[20200513比赛记录#A-Blank]] | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| 行 77: | 行 79: | ||
| $N$个炸弹处在坐标轴上，给出每个炸弹的坐标和状态$A_i,B_i$，状态为$1$表示激活$0$表示非激活。$M$项可选操作，每项操作$l_i,r_i$表示将坐标处在这个区间的炸弹状态反转。问有没有没有一个操作集可以使得所有炸弹状态为$0$。 | $N$个炸弹处在坐标轴上，给出每个炸弹的坐标和状态$A_i,B_i$，状态为$1$表示激活$0$表示非激活。$M$项可选操作，每项操作$l_i,r_i$表示将坐标处在这个区间的炸弹状态反转。问有没有没有一个操作集可以使得所有炸弹状态为$0$。 | ||
| - | 题解：操作可以分解成对$l_i-1$和$r_i$反转其之前全部，将这两点之间连边，由于反转时一次要同时改变两个端点的状态，故图中每一连通块中状态为$1$的点需要是偶数个，如不是则没有可能。若符合则必有可能的方案，用任意生成树，由叶子节点到根判断是否需要反转即可。 | + | 题解：定义操作$O_i$为反转坐标在$i$及以前所有炸弹的状态，将炸弹状态$w$数组进行异或差分，操作$O_i$相当于仅改变$w_{i+1}$。题中操作可以分解成$O_{l_i-1}$和$O{r_i}$，将$l_i$和$r_i+1$两点之间连边（lower_bound查找后），反转时一次要同时改变两个端点的状态，故图中每一连通块中状态为$1$的点需要是偶数个，如不是则没有可能。若符合则必有可能的方案，用任意生成树，由叶子节点到根判断是否需要反转即可。 |
| ===== 本周推荐 ===== | ===== 本周推荐 ===== | ||
2020-2021/teams/wangzai_milk/weekly2.1589724006.txt.gz · 最后更改: 2020/05/17 22:00 由 zars19
