Try and Try...

October 27, 2019

算法竞赛错误集锦

本文记录了自己在算法竞赛中常犯的低级错误,将持续更新。1. 常规错误搞混Yes,No等的大小写。for (int j = x; j <= y; j++) if (p[a[i]] == a[j]) { puts("YES"); // puts("Yes"); } puts("NO&...

C++ 预处理命令

1. 概述预处理命令就是我们程序开头以#字符开头的命令。为什么叫预处理命令?因为这些命令是在编译时的第一步就执行了的,不会转为汇编码。编译器编译代码的步骤:预处理。处理#include,#define等命令并删除注释,所以无论怎么写都不会再第一步CE。编译。真编译会分析代码语法(开了O2还会改一些)并生成汇编文件。汇编。将汇编码转为机器码。链接。根据电脑情况进行重定位,链接库等,生成可执行文...
November 12, 2019

P4513 【小白逛公园】

P4513 【小白逛公园】博客广告注意不能不选,至少要选一个数。本题应该是线段树题,但是做过P2042或者P2710的人会很容易发现,这道题的动态求最大子段和只是那道题的一部分,并且区间是静态的,只涉及单点修改,不用维护懒标记,相当轻松。所以我选择FHQ Treap。维护每一个点的区间和,最大前缀和,最大后缀和,最大子段和。修改权值: 将这个点分离出来,将它的值,区间和,子段和都赋值为c,将...
November 11, 2019

P3522 【TEM-Temperature】

P3522 【TEM-Temperature】这道单调队列可不一般,只要一段区间至少有一点重叠就可以看做连续。我们维护一个队列,从左往右扫,保证队列里的左端点单调递减。对于一个新的点来说,只有他的r大于之前所有l的最大值时才有答案,而队列里的左端点是但单调递减的,所以不断弹出队列左端直到左端点降到合适位置即可接下来要把这个点加入队列,因为要满足单调递减,所以应该把左端点比我低的点全部从右弹出...
November 7, 2019

P1351 【联合权值】

P1351 【联合权值】这道题看似与树有关,但是显然每个节点周围的所有节点都是可以作为备选的,计算他们的和与最大值就可以了,但是这样做是$O(N^2)$的,需要优化到$O(N)$。现在一个节点周围所有点的权值分别是$a_1, a_2...a_n$,那么答案就是$2(a_1a_2+...+a_1a_n+a_2a_1+a_2a_n+..+a_na_n)$。有一个公式可以解决这个问题:$$(a_1...
November 5, 2019

UVA1363 【Joseph's Problem】

UVA1363 【Joseph's Problem】数论分块是一个听起来高端,却好些好打的算法。我们知道$k\%i==k - i * (k/i)$,那么就有$\sum _{i=1}^nk\%i==n*k-\sum _{i=1}^ni*(k/i)$。我们以$n=k=10$为例: i: 1 2 3 4 5 6 7 8 9 10 k/i: 10 5 3 2 2 1 1 1 1 1很容易发现相邻一...
November 5, 2019

UVA1640 【The Counting Problem】

UVA1640 【The Counting Problem】这道题不能输出多余空格,可把我害惨了。我是从多倍经验过来的,正好复习基础的数位DP。1. 预处理我们先允许前导0存在,用$f[i][j][p]$表示“长度为i,以j开头的所有数字里p的次数”。当我们考虑到第i位时,枚举最高位j和次高位k(从0到9),相同的数字方案都是可以继承的,即$f[i][j][p] = \sum _{p=0} ...
November 3, 2019

P4158 【粉刷匠】

P4158 【粉刷匠】所以说一定不能畏难,这道题拖了好久才来做,看得题解发现思路并没有那么难想,还是自己做得题不够多。$f[i][j][k][0/1/2]$表示刷到了$(i,j)$,用了T次机会,没刷/刷错/刷对这一格时一共刷对的格子数,分三类讨论:1.这一格是新一行的格子。如果我不打算填这一格,那么可以从上面结尾任意一个继承来。如果我打算刷错这一格,那么要用一次机会,从上面结尾中T-1的情...
November 2, 2019

P2466 【Sue的小球】

P2466 【Sue的小球】提高试炼场有一道P1220 关路灯和这个几乎一模一样,今天考了这道题,我才发现就是原题。显然我们应该直接把初始y值加起来,然后减去最小的损耗以使答案最大,y累加以后就没有用了,记得把点从左往右排序。我们让f0[L][R]表示从R直接走到L的最小损耗值,用f1[L][R]表示从L和R中间一个点先走到R再掉头回来的最小损耗值(肯定不会掉两次头,亏)。小区间可以推出大区...
November 2, 2019

P2556 【黑白图像压缩】

P2556 【黑白图像压缩】题目前一半都是废话,耐心读完可以发现并没有难度。我们把每一个数读进来,它的范围在$[0, 255]$之间,那么把它的后8位直接从高到低排列即可,就可以得到对应的01序列。然后从前往后遍历01序列,所有只含0或1的字段长度就是答案,注意答案占7位,不能超过127,如果是1的长度还要在或上1 << 8。#include <bits/stdc++.h&...
November 1, 2019

P1594 【护卫队】

P1594 【护卫队】本题流氓,没有给出W, S的范围,事实上要开long long才能AC,另外应该注意小时与分钟的换算。记f[i]为前i辆车全部通过的最小时间,一定会有一个以i结尾的车队通过,枚举这个车队的开头L,那么f[i]就应该是“L以前所有车的最小时间 + [L, i]里最慢的车需要的时间”。即$f[i] = f[L-1]+\frac M {min(v_i,i \in [L, i]...
October 30, 2019

P1854 【花店橱窗布置】

P1854 【花店橱窗布置】这么经典的题被我拖到现在才来做。枚举每一个花放在哪一列,同时在枚举上一列,在保证上一列在这一列的左侧的情况下,选取最大的一个继承即可,注意权值有负数,应将f初始化为负无穷。比较麻烦的就是输出序列,在继承时标记一下每一个f[i][j]由上一排哪一个数继承而来即可,然后从最后一排递归输出。#include <bits/stdc++.h> int N, M...