划水笔记[置顶]

沉迷于刷水题无法自拔

2017-10-18

考试

T1

十字架,模拟。

T2

搭积木,贪心,从小的开始枚举,有地方放就放,没地方放就自己单独放,最后统计答案。

T3

NOIP 原题,关押罪犯,将所有的矛盾从大到小排序,维护两个并查集,一个维护一定在一起的,一个维护一定不在一起的,然后枚举事件,若事件双方已经必须在一起,则输出答案,反之维护并查集。

2017-10-17

考试

T1

宽搜,队列要手写不然会T。

T2

哈希冲突:对于模数大于根n的直接暴力求,小于的就建一个数组存一下,d[i][j]表示在模i时j这个池子里的数字之和,修改的时候维护一下就好了。

T3

地毯:只要知道二维差分的写法这就是个水题。

笔记

洛谷 P1710 地铁涨价: 先将所有的修改存起来,然后倒着枚举,因为修改一条表相当于删除一条边,因此倒着枚举一条边相当于添加一条边,每次添加完后所有能从起点遍历到的都是满意的点,因为每次遍历时只需从新谅解的两个点开始,因此遍历的总复杂度为O(n)。
洛谷 P1220 关路灯: 区间DP,定义f[i][j][0/1]表示将区间[i,j]的灯全部关闭之后且此时在i(j)的最小代价,转移方程就很简单了,只要在预处理出来一个功率的前缀和后缀就可以了。

2017-10-16

考试

T1

队爷的新书:将所有的点离散化之后,点的个数不超过200000个,直接借助差分,去枚举每个点被覆盖的个数,乘以原先的权值,更新答案。

T2

队爷的 Au Plan:DP,方程很好想,再加上单调队列优化。

T3

队爷的讲学计划: Tarjan缩点,计算边权点权,再做一个DAGDP,做DP一定要严格按照TOPO序,避免GG。

笔记

洛谷 P2327 [SCOI2005]扫雷: 通过第一个数字去判断第一个格子的状态,如果是0,则一定没有,如果是2则一定有,如果是1就需要分开判断,如果每局当前状态是1,那么就让下一个格子减1,最后再判断和不合法。
洛谷 P1153 点和线: 首先预处理出来任意两条线是否相交,然后从1进行搜索,保证每次选到的线不与之前的相交,最后回到1,由于每一个图形都被统计两次,因此答案要除以二输出。

2017-10-15

考试

T1

一个三维状态的DP,定义f[i][j][k]表示前i行,其中有j列放了两枚棋子,k列放了一枚棋子的方案数,转移时则需要考虑第i行放了几枚,放在了什么位置,然后写六个转移方程就行了。

T2

因为题目明确要求说在棋盘上方最多的车,因此很容易此想到放最多的车的数量应该是min(n,m),不妨设n<m,因此我们只需要考虑这n个棋子分别放在了哪一列就可以了,因此答案就是C(m,n),最后再套一个高精。

T3

如果是八十分的话就是常规的n皇后搜索,在加上棋盘破损的影响,再加上最后三个点的打表就能拿到。满分的话我们就要考虑减掉一些东西。在搜索的过程中,我们就可以用二进制数来表示列以及两个对角线,还有地形的影响,然后能够得到可以在那些地方放置棋子,并对参数进行适当位运算修改进而去搜索下一轮。

笔记

Vijos P1917 艾酱最喜欢的数字: 由于内存卡的紧,于是乎不得不想一些奇技淫巧。由于题目中已知要求的数的数量超过所有数的一半,因此我们就可以记录一个数cnt,如果下面的数是它,那么计数器加一,反之计数器减一,如果计数器小于零,则让记录的数字转变为当前数字,并将计数器重置,最终标记的数字就是答案。
洛谷 P1768 天路: 最优比例环,二分答案然后将算是变形得到新权值,并判断是否存在负环。
洛谷 P1791 线段覆盖: 贪心,将线段按照右端点从小到大,左端点从大到小排序,是的每次选完线段后剩下的区域最多。

2017-10-14

考试

T1

容斥原理,最恶心的事高精加减除,写到想吐。

T2

由题意可知,不同位的二进制数之间互不影响,而且一个数的平方可以表示为多个二次方数相加的形式,再平方就是每两个数分别相乘再相加。因此我们可以枚举任意两位x,y,然后定义dp[i][j]表示第x位运算后是i第y位运算后是j的方案数,做一个DP,对答案有贡献的一定是该两位都是1的方案数,对答案的贡献为2^i2^jdp[1][1],最后求和取模;

T3

首先二分答案,对于二分出的答案枚举每一只蚂蚁的路径,且必须满足|li-X|+|ri-Y|<=mid,|li-Y|+|ri-X|<=mid。

2017-10-13

考试

T1

模拟就好。

T2

DP,因为可转移的区间是连续的,所以用前缀和维护。我用的是树状数组,在开O2的情况下也能卡过。

T3

先预处理处每一个点到途中其他点的最短路之和以及虽短路树上的所有边,接着枚举删除每一条边,如果某一点的虽短路树上没有这条边,就直接加上,否则重新对该点进行BFS。

笔记

洛谷 P1168 中位数 :先进行离散化,然后用树状数组维护所有的数的前缀,同时进行二分查找。
洛谷 P1029 最大公约数与最小公倍数问题 :将最大公约数与最小公倍数分别进行质因数分解,并找出那些最小公倍数中的个数比最大公约数中的个数多的因子,并统计不同的符合条件的质数的个数,答案就是2^sum。
洛谷 P3931 SAC E#1 - 一道难题 Tree : 最小割问题,我用网络流过的。
洛谷 P2706 巧克力: 最大子矩阵问题,用悬线法或枚举,详见我的另一篇博客奶牛浴场;

2017-10-12

考试

T1

将长度二进制分解,答案为每一个二进制位减1以后的和。

T2

二分答案,先预处理处每一个点到离他最近的怪兽的距离,然后对于二分出的答案进行宽搜,判断起点终点是否联通。

T3

长得很像图论但其实是区间覆盖问题。
首先因为数据中保证了一定存在一颗美妙的仙人掌,所以所有的(i,i+1)的边一定存在(显然),也就意味着,所有的这类边连起来就是一棵满足题意的美妙的仙人掌。剩下需要做的就是选择尽量多的边使得它们没有相交的部分,就抽象成了区间覆盖问题。贪心求解。

2017-10-11

考试

终于全场AK了好不容易啊。

T1

很水的大模拟,由于时间很长,所以不能一步一步的模拟,我们会发现每走完一遍字符串循环后,位置的变化是一样的,因此我们可以先统计能够走完几遍循环,接着再将剩余的操作模拟出来,由于一个串的长度<=5000,所以最后的模拟很容易就能跑过。

T2

类似于菲波那切数列,可以用矩阵快速幂优化,跑得飞快。

T3

题面花哨得很,由于不同的时间边权在变化,所以我们可以将一个点拆成两个点,再去建模,跑SPFA。

2017-10-10

考试

T1

问n的阶乘模p的值,n<=10^18,p<=10000000,其中两个点p=1000000007,很水的数论题,如果n>=p的话那么最终的答案一定是0,很显然。反之因为p<=10000000,所以直接暴力求就好。而对于p=1000000007的数据,可以分段打表,然后暴力求过去就好。

T2

样例给错了好坑爹,根据题面里给的代码很容易能知道是在求具有大小关系的数对,a=b<c=d,其中a,b可以是一个数,c,d可以是一个数,元素很大,但是数字很少,暗示我们可以通过离散化来降低数据规模,然后开个桶,最后暴力统计一下就可以。

T3

神奇的贪心,因为最后的答案与操作的顺序无关,所以可以将行与列分开进行预处理,处理出f[i]表示对行操作i次的最大值,g[i]表示对列操作i次的最大值,最后枚举行与列分别操作了多少次,然后加和取最大值,因为取最大值的过程中行与列多加了一些p,个数为行与列的操作次数之积,减去它们就可以。最后一定要记得所有的地方都要开 long long,因为 long long没开全丢了四十分。。不然就全场AK了。。。

笔记

Vijos P1146 宿舍里的故事之五子棋: 搜索,将棋盘转化成一排,然后加一个可行性剪枝。
Vijos P1540 月亮之眼: 随便选取一个点,将正向边赋成正边权,同时建立对应的反向边,赋成负边权,然后通过搜索求每一个点的距离,如果存在一个点先后搜到的路径长度不一样,则输出-1,最后统计一下。
洛谷 团队题目: 题目大意:有一个数列a1,a2,a3,……,an,其中n为偶数,其中有2个数再序列中只出现了一次,其他的(n-2)个数都有且只有出现了2次,找出这两个数,并从小到大输出。 解法很玄学,n<=100000,元素大小肯定无法开桶,而且最后六个点时间卡到了20ms,意味着根本没法离散化。这是就需要一个O(n)的解法,正解是这样的,首先将所有的数字异或起来,显然异或和就是要求的两个数的异或值,因为相同的两个数异或之后就抵消掉了,然后随便找一位是1,则证明两个数的二进制在这个地方一定是不同的,于是乎再将所有这一位是1的数字异或起来,很显然异或和就是我们要求的其中一个数字,再根据两个数字的异或值就能求出来另一个数字(不得不膜拜出题大佬)。

2017-10-1

QB学堂集训

2017-9-29

笔记

洛谷 P1491 集合位置: 求第二短的最短路。先将最短路求出来,然后试着将最短路上的每一条边赋一个极大值,每次都跑一遍最短路,然后取最小值。居然没有T。
洛谷 P1522 牛的旅行: 跑一遍Floyd,然后记录下每一个点所能到的最远的点,枚举每一对不能到达的点,试图将他们连接起来,然后用他俩之间的距离以及两点分别到最远的点的距离之和去更新答案。
洛谷 P1119 灾后重建: 每一次增加的点只需要用它去更新其他的点就可以,不需要每一次都跑一遍Floyed。
洛谷 P1417 烹调方案: DP背包,只是用了一个贪心的思想将物品进行排序。考虑两个物品,不同顺序下损失的美味值,可以得到a.cb.b<b.ca.b排序,然后以时间作为背包体积做一个背包。
洛谷 P2716 路障,P2865 路障: 两道同名的题,解法也很类似,第一题将最短路上的每一条路翻倍再跑最短路并更新答案,第二题因为题面说可以重复去走一些路,所以不能简单地将最短路上的每一条路变成极大值,而是先将最短路上的每条路变成三倍(来——去——来)再去跑最短路更新答案。

2017-9-28

笔记

洛谷 P1134 阶乘问题:并没有看题解的解法,先将阶乘的质因子筛出来,因为5的数量要远小于2的数量因此将同等数量的2和5删去,再去做快速幂求得个位。注意的是在快速幂中要先将x取膜后再进行快速幂。防止一上来就平方然后炸int
洛谷 P1347 排序:这题就是恶心没有别的,用拓扑排序加Floyd判断。

考试

T1

题面除了恶心就是恶心(最近总是恶心题)。先将所有的折痕记录下来,然后就将每次折叠之后后边的折痕映射到录下的那半部分,并且维护左边界和右边界。

T2

数论题,真是费脑细胞。类似于辗转相除法。 l<=sx mod m<=r –> l<=sx-my<=r –> -r<=my mod s<=-l
若求出的x满足条件就输出x,否则求出y,再计算x,要算出y,就要继续递归下去。

T3

同样令人恶心的精度,秩序将每一个人都压给两边,最终只剩下三个人的是后手玩一下就好。

2017-9-27

考试

T1

很水的贪心,先删除重复的。

T2

同花顺,程序很简单,将不同颜色的牌分开,排序,去重,然后根据牌的总数去判断以每一张牌做结尾的时候,最早能找到哪一张牌在同花顺里,然后就能知道保留下几张牌,也就知道了删去几个牌,取个极小值,详细可见我的另外一篇博客同花顺

T3

一开始想到了2-sat,后来又想到了Floyd,然后。。。人家是并查集。。。和前两道题一样,都没有办法直接用数据做下标开数组,所以只能离散化,map很慢,慢到让我崩溃,T了三组。然后用MSY大老教的离散化过掉了(说实话之前没用过离散化)。先将相同的元素并到一起,然后再去判断不同的是否合法。

笔记

洛谷 P2380 狗哥采矿:dp+前缀,向上或向左。
洛谷 P1341 无序字母对:欧拉回路,用DFS实现。
洛谷 P1537 弹珠:做背包,看能否组成总价值的一半。
洛谷 P2002 消息扩散: 缩点后统计入度为零的点.

2017-9-26

考试

T1

求完全平方数,将阶乘全部质因数分解,然后将奇数个的质因数中多余的一个抹去,然后乘起来。

T2

居然是逆序对,平均数=(ai+1,ai+2..ai+n)/n
观察发现 ai数组 记前n项和(即a1+a2+a3..+an)为 An
那么要使平均数在 [l,r]内 那么 nl<=An<=nr
于是在区间[al,ar]中同时减去l,如果[al,ar]的和小于零,
则平均数不在[al,ar]内,大于零就在范围内。
同理[al,ar]区间减去r大于零就在范围内
所以可以分别求一下ai数组减去 l和r 后前缀和,记为Si
当减去l时,如果Sb-Sa>0那么说明区间[a,b]的平均数在[l,r]内
变形可以得到Sb>Sa,因此求解逆序对的个数,当是减去r时正好相反,那么将sum反转一下就和减去l的情况一样了

用补集转化的思想
我们求得是逆序对,可以发现逆序对是不合法的情况,
那么用总的情况减去不合法的情况就是合法情况了

T3

是暴搜??!!??!!
写个半个多小时的状压DP一直在想怎么优化,然而根本不会优化。
枚举当前的葱放入每一个栅栏的情况再加上最优化剪枝,666了。

×

纯属好玩

扫码支持
扫码打赏,你说多少就多少

打开支付宝扫一扫,即可进行扫码打赏哦

文章目录
  1. 1. 2017-10-18
    1. 1.0.1. 考试
      1. 1.0.1.1. T1
      2. 1.0.1.2. T2
      3. 1.0.1.3. T3
  • 2. 2017-10-17
    1. 2.0.1. 考试
      1. 2.0.1.1. T1
      2. 2.0.1.2. T2
      3. 2.0.1.3. T3
    2. 2.0.2. 笔记
  • 3. 2017-10-16
    1. 3.0.1. 考试
      1. 3.0.1.1. T1
      2. 3.0.1.2. T2
      3. 3.0.1.3. T3
    2. 3.0.2. 笔记
  • 4. 2017-10-15
    1. 4.0.1. 考试
      1. 4.0.1.1. T1
      2. 4.0.1.2. T2
      3. 4.0.1.3. T3
    2. 4.0.2. 笔记
  • 5. 2017-10-14
    1. 5.0.1. 考试
      1. 5.0.1.1. T1
      2. 5.0.1.2. T2
      3. 5.0.1.3. T3
  • 6. 2017-10-13
    1. 6.0.1. 考试
      1. 6.0.1.1. T1
      2. 6.0.1.2. T2
      3. 6.0.1.3. T3
    2. 6.0.2. 笔记
  • 7. 2017-10-12
    1. 7.0.1. 考试
      1. 7.0.1.1. T1
      2. 7.0.1.2. T2
      3. 7.0.1.3. T3
  • 8. 2017-10-11
    1. 8.0.1. 考试
      1. 8.0.1.1. T1
      2. 8.0.1.2. T2
      3. 8.0.1.3. T3
  • 9. 2017-10-10
    1. 9.0.1. 考试
      1. 9.0.1.1. T1
      2. 9.0.1.2. T2
      3. 9.0.1.3. T3
    2. 9.0.2. 笔记
  • 10. 2017-10-1
  • 11. 2017-9-29
    1. 11.0.1. 笔记
  • 12. 2017-9-28
    1. 12.0.1. 笔记
    2. 12.0.2. 考试
      1. 12.0.2.1. T1
      2. 12.0.2.2. T2
      3. 12.0.2.3. T3
  • 13. 2017-9-27
    1. 13.0.1. 考试
      1. 13.0.1.1. T1
      2. 13.0.1.2. T2
      3. 13.0.1.3. T3
    2. 13.0.2. 笔记
  • 14. 2017-9-26
    1. 14.0.1. 考试
      1. 14.0.1.1. T1
      2. 14.0.1.2. T2
      3. 14.0.1.3. T3
  • ,