2020-2021:teams:manespace:2020_08_01-2020_08_07周报_week13
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:manespace:2020_08_01-2020_08_07周报_week13 [2020/08/07 10:21] iuiou |
2020-2021:teams:manespace:2020_08_01-2020_08_07周报_week13 [2020/08/07 15:23] (当前版本) iuiou |
||
|---|---|---|---|
| 行 3: | 行 3: | ||
| =====本周推荐===== | =====本周推荐===== | ||
| ====by iuiou==== | ====by iuiou==== | ||
| - | * **题源**： | + | * **题源**：[[https://codeforces.com/group/azDPdoF24f/contest/290092/problem/A]] |
| - | * **题意**： | + | * **题意**：给$1-n$的一串数，有$m$次操作，每次操作给一段区间，如果左数大于右数，则将这段区间从大到小排序，如果左数小于右数，则将这段区间从小到大排序。 |
| - | * **知识点**: | + | * **知识点**:线段树，二分答案 |
| - | * **题解**： | + | * **题解**：考虑二分答案（做的时候确实死也没想到），二分枚举中间的数，每次枚举后在序列中将所有大于等于枚举数的数标为1，剩余标为0，之后操作时只要对分一半$1$，分一半$0$即可。操作完之后看中间的点是否为1，是则扩大中间数，否则缩小中间数 |
| - | ====by QuantumBolt==== | ||
| - | * **题源**：[[https://codeforces.com/contest/1384/problem/D]] | ||
| - | |||
| - | * **题意**：Koa和KoalaKoala两人玩游戏，初始分均为$0$，每次两人从一个数组中选择一个数，选择后该数字会被从数组中删除，两人的分数异或上该数字的值为新的分数，问均采取最优策略谁能赢，规定KoaKoa先手。 | ||
| - | | ||
| - | * **知识点**：博弈论 | ||
| - | |||
| - | * **题解**： | ||
| - | |||
| - | |||
| - | 这个题是博弈论的题： | ||
| - | 分析一下： 设$p_i$表示$n$个数二进制位第$i$位为$1$的个数 | ||
| - | 若$2|p_i$那么先手和后手对$i$位的结果没有影响 | ||
| - | 从而我们需要找到$j$，使得$2|p_j=1$这样才能导致先后手的结果在第$j$位不同 | ||
| - | 现在我们的任务就是找打最大的$j$位，使结果最大化 | ||
| - | |||
| - | 1. 若$\frac{P_j-1}{2}$是偶数，那么先手的就一定赢 | ||
| - | 先手在该位先取一个1，然后跟着后手选，那么后手会选择偶数个1，结果为：先手在该位值为1，后手为0。 | ||
| - | |||
| - | 2. 若$\frac{P_j-1}{2}$是奇数，分两种情况 | ||
| - | |||
| - | (1). 若$2|n = 1$先手就必输： | ||
| - | 先手在该位先取一个1，然后跟着后手选，那么后手会择偶数个1，结果为：先手在该位值为1，后手为0。 | ||
| - | |||
| - | (2). 若$2|n$那么先手必赢 | ||
| - | 先手第一步选一个0，然后将状态转为$2|n=1$的局面，且轮到后手先选择，上面已经证明，这种局面先选择的必输。 | ||
| =====团队训练===== | =====团队训练===== | ||
| 行 62: | 行 36: | ||
| ====比赛==== | ====比赛==== | ||
| - | * [[cf 659 div.2]] | + | |
| * [[cf 658 div.2]] | * [[cf 658 div.2]] | ||
2020-2021/teams/manespace/2020_08_01-2020_08_07周报_week13.1596766909.txt.gz · 最后更改: 2020/08/07 10:21 由 iuiou
