2020-2021:teams:manespace:2020_07_25-2020_07_31周报_week12
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:manespace:2020_07_25-2020_07_31周报_week12 [2020/07/31 13:16] quantumbolt |
2020-2021:teams:manespace:2020_07_25-2020_07_31周报_week12 [2020/07/31 17:04] (当前版本) iuiou |
||
|---|---|---|---|
| 行 3: | 行 3: | ||
| =====本周推荐===== | =====本周推荐===== | ||
| ====by iuiou==== | ====by iuiou==== | ||
| - | * **题源**： | + | * **题源**：[[https://codeforces.com/contest/1384/problem/B1]]&&[[https://codeforces.com/contest/1384/problem/B2]] |
| - | * **题意**： | + | * **题意**：一个人要从0号沙滩到n+1号岛屿，中间有n片海，每片海都有一个深度$d_i$，还存在潮汐的作用，潮汐在呈$[0,1,2,……,k-1,k,k-1,……,1]$的规律按照时间循环变化，在一个时刻海域的深度为潮汐高度加深度，有一个安全深度$l$，而且他移动一次需要时间$1$，它可以在任何一个海域停留任何一个时间。问他能否安全的到达目标岛屿？ |
| + | |||
| + | * **知识点**: dp,思维,构造 | ||
| + | |||
| + | * **题解**： | ||
| + | * **题解1**：对于简单的版本，考虑使用$dp$的思想，用$dp[i][j]$表示在时间为$j$时在第$i$个海域的可能性,转移时考虑，dp[i][j-1]与dp[i-1][j-1]有没有存在一个1，有就可以转移，时间总量可以开大一点，开$2*k*n$，最后遍历$dp[n][j]$存找是否存在$1$即可，至于判断单个状态是否成立，这很简单。 | ||
| + | * **题解2**：上面那种比较暴力得做法，明显过不了大样例，所以要想一个$O(n)$的想法，其实就是设计一个无论在那种情况都能占优的策略，可以发现，在降潮的时候走是有优势的，如果这时候到$i+1$，会有危险，那就等到$i+1$没有危险时再走，二长时间呆在原地，潮水只会往下跌，所以只会越来越“安全”,所以只要找可以等到涨潮的点即可，即满足$k+d_i≤l$的点，在这个点等到潮水涨到最高，然后再开始继续走，当然，一开始要判断不成立，两种情况，一种是已经涨潮，而对面已经过不去了，还有就是存在一片海域，$d_i>l$,那么也一定不成立。时间复杂度$O(N)$ | ||
| + | * **总结**：这种题目有时候还是束手无测啊，但是又学到了一种暴力方法，dp暴力，感觉很有用啊，其实看见这种一个一个状态划分的非常清楚地题，怎么会想不到dp呢，<del>爬</del> | ||
| + | |||
| + | ====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$的局面，且轮到后手先选择，上面已经证明，这种局面先选择的必输。 | ||
| + | |||
| =====团队训练===== | =====团队训练===== | ||
| - | 2020.7.25 [[牛客多校第六场]] | + | 2020.7.25 牛客多校第六场 |
| - | 2020.7.27 [[牛客多校第七场]] | + | 2020.7.27 牛客多校第七场 |
| =====范泽恒===== | =====范泽恒===== | ||
| 行 21: | 行 52: | ||
| ====比赛==== | ====比赛==== | ||
| - | * [[codeforces round 656(div3)]] | + | * [[codeforces round 659(div2)]] |
| - | * [[codeforces round 657(div2)]] | + | * [[Educational Codeforces Round 92 (Rated for Div. 2)]] |
| - | * [[codeforces round 658(div2)]] | + | * [[codeforces round 660(div2)]] |
| ====题目==== | ====题目==== | ||
| - | * **题源**：[[https://codeforces.com/contest/1385/problem/G]] | ||
| - | |||
| - | * **题意**：给定两排数，每排都有$n$个数，每次操作可以交换一列的两个数，问能否存在一个最少的交换方案，使操作之后每一行都是$1$到$n$的一个排列。 | ||
| - | | ||
| - | ***知识点**：dfs | ||
| - | * **题解**：这题有点难想，大致是一个二分图的问题。首先遍历两行数，如果一个数的出现次数超过了2次，那么肯定不成立。如果所有数出现次数都是两次，那么一定有一种方案满足。现定四个数组$r1[n],r2[n],b1[n],b2[n],b$数组用于存放列数，$r$数组用于存放行数，如果对于一个数$i$,$b_{1i}=b_{2i}$,则不考虑这个点，因为肯定不会动这个点的。接下来对点染色，如果$b_{1i}≠b_{2i}$,考虑$r$数组，如果$r_{1i}≠r_{2i}$,则在$b_{1i}$和$b_{2i}$之间连一条权为0的边表示，两点染的色必须相同。反之，连一条权为$1$的边，表示两个点颜色相反，最后从每个点开始$dfs$经行染色即可,注意每次比对将开头的那个点染成$1$还是$0$，最后的结果会最优(即最少)。 | ||
| - | |||
| - | |||
| - | |||
| =====恭天祥===== | =====恭天祥===== | ||
| 行 45: | 行 67: | ||
| * [[cf 659 div.2]] | * [[cf 659 div.2]] | ||
| + | * [[cf 658 div.2]] | ||
| ====题目==== | ====题目==== | ||
| - | |||
| - | * | ||
| - | ===== 题意 ===== | ||
| - | * **题源**：[[https://codeforces.com/contest/1384/problem/D]] | ||
| - | |||
| - | * **题意**：Koa和KoalaKoala两人玩游戏，初始分均为$0$，每次两人从一个数组中选择一个数，选择后该数字会被从数组中删除，两人的分数异或上该数字的值为新的分数，问均采取最优策略谁能赢，规定KoaKoa先手。 | ||
| - | | ||
| - | * **知识点**：博弈论 | ||
| - | |||
| - | * **题解**：这个题是博弈论的题： 分析一下： 设$p_i$表示$n$个数二进制位第$i$位为$1$的个数 若$p_i|2$那么先手和后手对$i$位的结果没有影响 从而我们需要找到$j$，使得$p_j|2=1$这样才能导致先后手的结果在第$j$位不同 现在我们的任务就是找打最大的$j$位，使结果最大化 若$\frac{P_j-1}{2}$是偶数，那么先手的就一定赢 - 先手在该位先取一个1，然后跟着后手选，那么后手会选择偶数个1，结果为：先手在该位值为1，后手为0。 若$\frac{P_j-1}{2}$是奇数，分两种情况 1. 若$n|1 = 1$先手就必输： - 先手在该位先取一个1，然后跟着后手选，那么后手会选择偶数个1，结果为：先手在该位值为1，后手为0。 2. 若$n|1$那么先手必赢 - 先手第一步选一个0，然后将状态转为$n|2=1$的局面，且轮到后手先选择，上面已经证明，这种局面先选择的必输。 | ||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| 行 68: | 行 75: | ||
| =====刘怀远===== | =====刘怀远===== | ||
| ====专题==== | ====专题==== | ||
| - | |||
| *无 | *无 | ||
| ====比赛==== | ====比赛==== | ||
| - | |||
| * [[Codeforces Round 656 (Div. 3)]] | * [[Codeforces Round 656 (Div. 3)]] | ||
| ====题目==== | ====题目==== | ||
2020-2021/teams/manespace/2020_07_25-2020_07_31周报_week12.1596172563.txt.gz · 最后更改: 2020/07/31 13:16 由 quantumbolt
