Dispwnl

Crazy Up

[THUPC2017]天天爱射击

题目题解整体二分，对于一个时间区间$[l,r]$先把$[1,mid]$的子弹加入树状数组，然后就是区间查询是否满足条件了注意最后处理时间点$m$的时候所有前面没碎的木板都在这个点上，所以要检验是否合法（即到最后是否碎掉）代码 # include<iostream> # include<cstring> # include<cstdio> ...

Posted by Dispwnl on April 22, 2019

[GZOI2019]与或和

题目题解化简问题后就成了对$01$矩阵求最大全$0/1$子矩阵处理出来每个点往上最长延伸长度，然后单调栈解决即可代码 # include<iostream> # include<cstring> # include<cstdio> # include<algorithm> using namespace std; const ...

Posted by Dispwnl on April 22, 2019

[CF1151F]Sonya and Informatics

题目题解首先先考虑$k$较小的时候怎么做，设$f_{i,j}$表示到第$i$次操作，设$N_{0/1}$为$0/1$的个数，前$N_0$个数中有$j$个$1$的概率设$M=\frac{n(n-1)}{2}$，则有转移$f_{i,j}=\left(\frac{\frac{N_1(N_1-1)}{2}+\frac{N_0(N_0-1)}{2}+j(N_1-j)+j(N_0-j)}{M...

Posted by Dispwnl on April 22, 2019

[POI2000]条纹

题目 Description 条纹游戏是一个双人的游戏。所需要的物品有一个棋盘以及三种颜色的长方形条纹，这三种颜色分别是红色、绿色和蓝色。所有的红色条纹的尺寸是$c\times 1$，所有的绿色条纹的尺寸是$z\times 1$，所有的蓝色条纹的尺寸是$n\times 1$，这里c,z,n是正整数。每种颜色的条纹每个游戏者都拥有无限多个。一个棋盘是一个尺寸为$p\times 1$的长...

Posted by Dispwnl on April 21, 2019

[HNOI2014]江南乐

题目题解明显的$Multi-SG$游戏，可以枚举堆数然后判断各种大小堆的个数的奇偶性，这样复杂度是$O({\max(a_i)}^2)$的发现讨论各种大小的堆的个数没有意义，因为只会有两种堆的大小最小堆的大小在枚举堆数的时候是类似一个整除分块，某些堆数的最小堆大小可能一样，这样可以分最小堆个数为奇数和偶数讨论预处理跑不过……只能记忆化搜索代码 # include<...

Posted by Dispwnl on April 21, 2019

[HNOI2007]分裂游戏

题目题解最后情况肯定是所有豆子都在最后一个瓶子里如果有个瓶子里有偶数个豆子不影响最后的胜负，因为无论先手走什么后手都可以模仿先手所以可以把每个瓶子看成一个独立的游戏，处理出来$n$个瓶子时$SG$的值至于找方案，可以$O(n^3)$枚举$i,j,k$，判断去掉$SG_i$异或上$SG_j,SG_k$（即规定了第一步应该这么走）是否满足必胜即可代码 # include...

Posted by Dispwnl on April 21, 2019

[GZOI2019]逼死强迫症

题目题解先考虑没有$1\times 1$块的方案数对于第$i$列，要么是从第$i-1$列加上一块$2\times 1$的块转移过来的，要么是从第$i-2$列加上两块$1\times 2$的块转移过来的，所以前$i$列的方案数为$f_i=f_{i-1}+f_{i-2}$，即斐波那契数列当然这并不重要现在考虑加上$1\times 1$块的情况，设$g_i$表示第$i$列和之前列中...

Posted by Dispwnl on April 21, 2019

[GZOI2019]旧词

题目题解在做了这题和这题之后思路就是一眼了把$1\sim x$到根的路径上打标记，然后查询$y$到根的标记和即可既然要求的是$k$次方那么点$a$的标记打成${d_a}^k-(d_a-1)^k$即可代码 # include<iostream> # include<cstring> # include<cstdio> # include...

Posted by Dispwnl on April 21, 2019

[GZOI2019]旅行者

题目题解有一道处理思路差不多的题先处理出来感兴趣城市到其他点的最短距离以及是从哪个感兴趣城市转移过来的，在反着跑一遍用其他点更新感兴趣城市代码 # include<iostream> # include<cstring> # include<cstdio> # include<queue> # include<algor...

Posted by Dispwnl on April 21, 2019

[LOJ572]Misaka Network 与求和

题目题解发现这个式子非常莫比乌斯，设$F(x)=f(x)^k$，先化式子 $\sum_{i=1}^{n}{\left\lfloor\frac{n}{i}\right\rfloor}^2\sum_{d\vert i}F(d)\mu(\frac{i}{d})$ 后面的是个狄利克雷卷积的形式，尝试用杜教筛筛一下前缀和设$s(n)=\sum_{i=1}^{n}(F*\mu)(i)...

Posted by Dispwnl on April 19, 2019