2020-2021:teams:manespace:codeforces_round_663_div2
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:manespace:codeforces_round_663_div2 [2020/08/14 15:04] iuiou 创建 |
2020-2021:teams:manespace:codeforces_round_663_div2 [2020/08/14 15:32] (当前版本) iuiou |
||
|---|---|---|---|
| 行 11: | 行 11: | ||
| 题意：描述[[https://codeforces.com/contest/1391/problem/C]] | 题意：描述[[https://codeforces.com/contest/1391/problem/C]] | ||
| - | 题解：会发现正面的情况会十分的多二杂，不好考虑，不妨从反面考虑，考虑不成立的情况，发现只要满足山峰状排列就一定不会成立，所以相当于只要寻找山峰装排列的有多少即可，考虑山峰消退阶段中数的数量，发现只要选出一定数量的数，适当排列(从大到小)后就会对应一种情况，所以答案就是$C_n^i$ | + | 题解：会发现正面的情况会十分的多二杂，不好考虑，不妨从反面考虑，考虑不成立的情况，发现只要满足山峰状排列就一定不会成立，所以相当于只要寻找山峰装排列的有多少即可，考虑山峰消退阶段中数的数量，发现只要选出一定数量的数，适当排列(从大到小)后就会对应一种情况，所以答案就是$\sum_{i=0}^{n}C_n^i$即$2^n$注意到这里其实是多算了，每种情况算了两遍所以直接除2得到不符合的情况。最后答案即为$n!-2^{n-1}$ |
| + | =====D 505===== | ||
| + | 题意：给出一个$n*m$的$01$矩阵，问如何做出最小的改变即(0变1，1变0)使这个矩阵中任意一个偶数为边长的方阵中1的数量为奇数。 | ||
| + | |||
| + | 题解：首先发现，对于一个4*4的矩阵，由4个2*2的方阵组成，若这4个2*2的方阵都满足条件，则这个4*4的矩阵中1的数量一定是偶数个。所以显然一旦$n$和$m$的边长都大于4则一定不会成立。所以现在我们只需要考虑n和m都小于4的情况，可以使用$dp$来做，状压dp，考虑每个列的2*2矩阵的状态，修改前一个的矩阵会影响到下一个矩阵，而且对于一种不满足情况的矩阵修改一次就可以改变其状态，用01串来表示状态，枚举每个列，做转移即可。 | ||
2020-2021/teams/manespace/codeforces_round_663_div2.1597388669.txt.gz · 最后更改: 2020/08/14 15:04 由 iuiou
