noi模拟 矩阵 贪心

https://ly.men.ci/problem/197

我们考虑,我们必定是先搞出一行全黑,然后用它来覆盖所有不是全黑的列。我们考虑枚举这个行,然后算如何能让这个行变城全黑。我们考虑,如果这是x行,那么只要在x列有一个黑块,我们可以证明,则这行必定能变成全黑,如果x列全白,我们也可以通过一[……]

Read more

bzoj 3207: 花神的嘲讽计划Ⅰ 主席树

我们对于每个k长度的字符串求hash,然后用主席书区间查询是否存在即可。第一次写不离散化的主席树QwQ。调了好久,,QwQ。

NOI模拟 取石子 贪心

取石子(a)
【题目描述】
有n 堆石子,第i 堆有ai 个。你和你的好朋友轮流取石子,每次从一堆石子
中取若干个(不能不取),。你很绅士地让你的好朋友先手。
为了能确保胜利,趁你的好朋友不在的时候,你可以取走一些石子,再放入
一些石子(可以将一堆石子全部取走,但是不能创造新的石子堆)。[……]

Read more

bzoj 1443: [JSOI2009]游戏Game 二分图匹配

我们先明确一个事实,棋盘上alice和bob能走到的点必定是不同的,可以染成黑白相间网格,这样子我们从二分图匹配的角度考虑。

四联通建图,然后我们二分图匹配,然后我们可以发现如果可以得到完美匹配,则bob是必胜的。因为bob走一个匹配边,alice走一个非匹配边。只要还有非匹配边可以走,就必然[……]

Read more

bzoj 4300: 绝世好题 DP

按位DP即可。

f[i]表示到当前这一个数字,第i位为1,最长多长。

我们一个数假设他在2,8,12上为1,那么显然他可以把之前的2接到现在的8上,就是类似转接的作用。然后每次取一个maxn更新即可。详细看代码。

bzoj 4690: Never Wait for Weights 带权并查集

好久不写,相对关系又维护的一团糟。。QwQ。。。还是我太菜了。

不过这题倒是真真切切的裸题

bzoj 4602: [Sdoi2016]齿轮 dfs

找个起始点钦点一个速度,然后搜索,然后矛盾输出即可对吧。好吧,很简单吧。

开始忘记在搜索前钦点速度了,QwQ

bzoj 4653: [Noi2016]区间 线段树

开始我只考虑到了,我们最后选的线段在在坐标上应该有些连续性。在考虑能不能单调搞一下,但是发现处理起来十分困难。后来想想我们选的边在边权上也有一些性质,我们只管两头,中间多选就多选,够了就行。

这样子我们离散化以下,维护一个线段树。然后把区间按边权排序,每次我们都不断加入边,直到有一个点重复过m[……]

Read more