Day 1
P1314
二分答案
P2367
差分板子
P2882
找性质,然后模拟,异或差分维护。
P1719
转换成最大子段和问题。
P3017
二分,先考虑水平方向,定两个点\(l,r\),在\([l,r]\)行内,再挂两个点\(l_0,r_0\),表示当前竖直方向的区间,如果矩阵和\(\ge mid\),那么继续,否则继续延伸。最后若分的块数\(< B\),则不行。水平同理。
P1884
考虑离散化做,存在\(b\)数组里。设\(f[i][j]\)为矩形\([(b[i],b[j]),(b[i+1],b[j+1])]\)的覆盖次数,修改可以一维枚举一维差分。
注意:笛卡尔坐标系中的左上右下即为平时的左下右上。
P1638
简单题,双指针+桶维护就没了。
P3143
题意可以转化为:将\(a\)排序,则变成选择两个无交集区间,每个区间满足最大值和最小值的差\(\le k\),最大化两个区间的长度和。
设\(f_i\)为右端点\(\le i\)的满足条件的区间的最长长度。先双指针跑一遍,表面更新一波右端点\(=i\)时的\(f_i\),然后别忘了再来一波循环取max卷过去,即:
for(int i = 1; i <= n; i++) f[i] = max(f[i - 1],f[i]);
然后第二次双指针,更新答案。
P1496
简单题,离散化后用差分维护累加完事。(这数据似乎直接\(\mathcal{O}(n^2)\)也能过,离谱)
P1714
单调队列板题。
Day 2
AT4168
高维的东西,即\(f_i = \sum_{j \subseteq i} f_j\)。如何做?枚举子集,炸。
考虑枚举每一个维度,然后如果\(i\)状态中这一个维度的值是\(1\),那么可以推到这个维度是\(0\)(也就是之前)的状态,即\(i \space \operatorname{xor} 2^j\)。
for(int j = 0; j < n; j++) for(int i = 0; i < (1 << n); i++) {if(i >> j & 1) f[i] = f[i] + f[i xor (1 << j)];}
这里我们发现可以求出每个\(i | j = k\)的最大值,因为\(\max\)具有可重叠性,所以可以转化为\(i,j \subseteq k\),能保证\(i | j\)不大于\(k\)。
每个状态维护一个最大和次大。
P1966
不难发现\(\sum_{i = 1} ^ n a_i^2,\sum_{i = 1} ^ n b_i^2\)为定值,那么就变成了最大化\(\sum_{i = 1} ^ n a_ib_i\)。
有个结论是将\(a,b\)的每个第\(k\)小配对在一起,这个东西就最大。证明略。
考虑如何将两个的每个第\(k\)小配在一起,就是将\(a,b\)先排序,存以前的下标,为\(ida_i,idb_i\)。搞一个数组\(c\),让\(c[ida_i]=idb_i\)。我们发现只要将\(c\)变为\([1,2,3,\cdots,n]\),就可以了,那么即为\(c\)逆序对个数。
P2345
这题数据\(n \le 2 \times 10^4\)啊,那直接 \(\mathcal{O}(n^2)\)秒了。
哦你要加强?把\(\max\{v_i,v_j\} \cdot |x_i - x_j|\)处理一下,首先先按\(v\)排序,这样可以去掉\(\max\),然后对于每个牛(设为第\(i\)个牛),考虑\(x < x_i\)和\(x > x_i\)的情况。自然想到树状数组,一个维护和,一个维护个数,没了。
老师课上讲的cdq分治,但是没有BIT短,BIT yyds。
P3138
枚举\((a,b)\)二维前缀和\(\mathcal{O}(n^2)\)。目前不太会二分check在\(\mathcal{O}(n^2)\)以下。
P4653
一开始想的二分,但是不知道为什么WA了一堆,只有12~15分。自己感觉应该是对的,可能写错了?
然后发现有类似贪心做法的,就是首先选大的肯定优于选小的,所以从大到小排序,然后依次选,超过了就追上,一直到某一方到了\(n\)结束。
Day 3
P3658
这给的什么申必翻译,看不懂,看了一些题解的题目大意总算是看懂了。
即求二元组\((i,j)\),满足\(a_i < a_j,b_i > b_j,|i - j| > k\)的个数,化成三维偏序,CDQ分治即可。
然而我板子调大半天
UVA11572
双指针简单题,记录重复个数,一边跑一边更新即可。
AT4142
双指针,注意到\(x \operatorname{xor} y \le x + y\),所以前缀和小于等于前缀异或。对于\([l,r]\),若其和=异或和,那么\([l,r]\)的所有连续子序列一定也满足条件。
我一开始想枚举左端点然后右边可以的跳,后来发现有很多问题,然后就枚举右端点,找到符合条件的最小左端点(这个不严格递增),然后统计答案。
P2866
发现如果每个人硬算一遍\(C_i\)很麻烦,那么直接考虑每个牛对总答案的贡献。对于第\(i\)头牛,它对答案的贡献就是\(\sum_{j = 1}^{i - 1} [h_j > h_i]\),用单调栈维护即可。
P3467
一个单调栈的比较简单的题,维护一个单调递增的栈,然后如果两个东西的高度相同,且呈“凸”状,那么就可以少用一个覆盖。单调栈恰好能维护“凸”形。
P2032
滑 动 窗 口
P2880
两个ST表维护最大最小就行。\(\mathcal{O}(n\log{n} + q)\)
P2251
?滑动窗口三倍经验?
P1816
ST表双倍经验。
P2216
啊这个题有意思,我第一眼感觉是无脑二维数据结构,但是忘了二维ST表怎么写了(逊),遂想了个nt做法:
预处理每个\(1 \times n\)的方块的最大最小值,然后在每一行跑单调队列并更新。\(\mathcal{O}(abn)\),啊啊啊逊死了!
(最优解貌似\(\mathcal{O}(ab\log{n})\))
Day 4
P1725
凌晨写题严重降智。
设\(dp_i\)为到\(i\)的最大值,有 \(dp_i = \max \{dp_x\} + A_i\),考虑\(k\)的限制:
\(i \in [x + l,x + r]\),即\(i - r \le x \le i - l\)。
则有
不难发现转移的那个区间是连续的,那么单调队列优化dp即可。
式子写出来后一波乱写,都不知道写的什么,80分,然后乱改100
P1419
二分段落平均值,check中先将每个\(a_i\)减去mid(二分的平均值),然后做前缀和\(b_i\),问题变成:是否存在\(b_r - b_{l - 1} \ge 0 (S \le r - l + 1 \le T)\)。
对于每个\(r\),寻找最小的\(b_{l - 1}\),同时长度在\(S\)到\(T\)之间,不难发现即为\(\min_{r - T \le x \le r - S} \{b_x\}\)。 这样就可以单调队列了,和P1725一样。
为了保证不出奇奇怪怪错误,这里贴个板子:
head = 1,tail = 0;
for(int i = s; i <= n; i++)
{
while(head <= tail && b[i - s] <= b[q[tail]]) --tail;
q[++tail] = i - s; // 先入队才能更新。
while(head <= tail && q[head] + t < i) ++head;
if(b[i] - b[q[head]] >= 0) return 1;
}
P2627
设\(dp_i\)为\(i\)之前的最大值,设\(E[i,j] = \sum_{k = i} ^ j e_k\),那么考虑枚举休息的奶牛\(j\):
(注意\(j\)是可以取到\(i\)的,因为\(i\)也可以休息)
考虑到\(E[i,j]\)可以拆成前缀和:
单调队列维护\(dp_{j - 1} - E_j\)即可。
P2034
与P2627完全一致。
P1840
无脑线段树。tgt给我发过来说有并查集做法,不是太会。
P3957
想到了二分\(g\),然后设\(dp_i\)为在\(i\)前的最大得分,得:
考虑\(j\)的限制,设\(l = \max\{1,d - g\},r = d + g\)。则\(X_j + l \le X_i \le X_j + r\),得\(X_i - r \le X_j \le X_i - l\)。那么:
不难发现这个东西可以用单调队列维护,但是略微有点难写。
AT5758
tgt扔给我的。易证答案为\(\min \{a_i\} + \min\{b_i\}\)和所有用券情况的最小值。随便写一写就好
tgt随手扔了一个故意写错的代码演我,嘤嘤嘤
Day 5
P2569
较有难度的单调队列优化dp题。
P3800
不难想到设\(dp[i][j]\)为在\((i,j)\)点的最大Power.显然,\(dp[i][j]\)只能从\(i - 1\)行的某个区间内的\(j\)转移过来,即:
考虑\(k\)的限制。显然\(\max \{1,j - T\} \le k \le \min \{m,j + T\}\),这样的话用单调队列维护一下就好了。
P2254(未AC,后补)
断网测试,只写了\(40 \sim 60\)pts的部分分。
设\(dp[t][i][j]\)为在\(t\)时刻在\((i,j)\)的最大步数,分类:
-
使用魔法,\(dp[t][i][j] = dp[t - 1][i][j]\).
-
否则,\(dp[t][i][j] = dp[t - 1][i_0][j_0]\),其中\(i_0,j_0\)是指在\(t\)时刻经过倾斜前的点。
取 \(\max\)即可,\(t\)的那一位可以滚动。
\(\mathcal{O}(Tn^2)\)
P1944
一个简单题,设\(dp_i\)为以\(i\)结尾的最长括号匹配串长度。(若没有则\(dp_i = 0\)。)
考虑从\(dp_{i - 1}\)转移:
\([i - dp_{i - 1},i - 1]\)为合法字符串,那么若\(i,i - dp_{i - 1} - 1\)位置匹配,则\(dp_i = dp_{i - 1} + 2 + dp_{i - dp_{i - 1} - 2}\).
P4310
第一眼看上去像某经典题,设\(dp[i]\)为以\(i\)结尾的最大合法子序列长度。初始化为1,
则:
\(\mathcal{O}(n^2)\),啪的一下,很快啊,90pts?
离谱。
但是没有AC怎么行!然后接下来就是重点:
设\(dp[i][j]\)为前\(i\)个数,二进制第\(j\)为为\(1\)的最大长度。因为我们发现,与运算不等于0即为至少有一位为1。那么只要暴力转移就行。
这个\(i\)这一维显然可以滚掉。
时间复杂度\(\mathcal{O}(n \log a_i)\)
P1396
似乎有好多做法。
- spfa板子
- 二分+并查集,先将所有边按照\(w\)排序,二分拥挤度最大值,然后check里面将所有\(w \le mid\)的边的\(u,v\)合并,中间判断\(s,t\)是否在一个集合。
P1823
这个有点像前几天做的奶牛题。维护单调递减的单调栈,然后会发现每次的贡献就是一直到第一个比它高(严格)的人。
(根节点为0,每个点出度至多为1)
我们自然想到:暴力模拟一遍,但是这样子可能会被卡:
但是我们可以树上倍增!求出\(i\)向上跳\(2^j\)次的祖先\(f[i][j]\),和\(i \sim f[i][j]\)路径上的总点权(不包括\(i\)的点权)\(s[i][j]\)。然后倍增模拟一边就好了。时间复杂度\(\mathcal{O}((n + q) \log{n})\).
P1783
P3958 奶酪
+二分。
P1950
注意:这题(我的)证明应该是伪证。
subtask1,2:暴力二维前缀和,\(\mathcal{O}(n^4)\)。
单调栈随便搞搞,但是正确性不会证。
P2516
分类dp计数。
P1776
二进制优化背包问题。很快就秒了
P1855
多维背包?
ABC 211
具体看
P3188
0-1背包问题,但是考虑到\(W\)非常大,而且\(w_i = a \times 2^b\),那么就考虑将\(b\)相同的归为一类,做0-1背包,然后再将它们合并;
设\(dp[i][j]\)为\(w_i\)可以表示为\(a \times 2^i\)形式的物品,容量为\(j \times 2^i\)的最大的价值。
那么
裸的板子,接下来考虑合并:
我们设\(g[i][j]\)表示\(b\)为\(0\sim i\)的所有物品,体积为\(i \times 2^j + w \texttt{&} (2^{i} - 1)\)的最大价值。
那么
Day 7
模拟赛1补题
CF1061C
rxz直播改题目难度,nb嗷
设\(dp[i][j]\)为考虑了\(a_1 \cdot a_i\),且选了\(j\)个的方案数。
则:
发现可以滚掉第一维,又发现这样的话只要考虑\(j \mid a_i\)的转移就行。可以做到\(\mathcal{O}(n \sqrt{a_i})\)。
CF245H
设\(ispal[i][j]\)表示\(S[i,j]\)是否为回文串,则:
然后作个二位前缀和即可。
P1385
设\(sum\)为这个字符串的字典序和。不难发现所有字典序和\(=sum\)的字符串都可以通过这个字符串变形而来。那么问题转化成求长度为\(n\)的、字符串字典序总和为\(sum\)的字符串个数-1.
乱搞dp,不想讲了。
P1537
背包+二进制优化,不想讲了。
P1622
区间dp,设\(dp[i][j]\)表示释放了\(s[i \sim j]\)的犯人的最小答案。
则考虑枚举\(k(i \le k \le j)\),考虑释放\(k\),则:
Day 8
P3385
差分约束。若\(x_i - x_j \le x\),则作一条边权为\(x\)的\(j \to i\)的有向边。最后判断是否有负环(spfa)。
P3275
差分约束。把所有条件变成\(\ge\),跑最长路。、
CF106C
显然每个面包最多做\(\min \{a_i / b_i,n / c_i\}\),这里\(/\)包括了下取整。转换成多重背包二进制优化。
P3199
题意:给一个图,求环,使得\(\left(\sum w_i\right) / k\)最小,\(k\)为环的点的个数。
考虑二分。若\(ans\)满足条件,则\(\left( \sum w_i \right) / k \le ans\),变成\(\left(\sum w_i \right) \le ans \cdot k \to \left(\sum w_i \right) - ans \cdot k \le 0 \to \left(\sum (w_i - ans) \right) \le 0\)。相当于是每条边\(-ans\)然后判断是否有负环。
P5837
一句话题意:
求一条\(1 \to n\)的路径,最大化
枚举\(c\)上限\(F\),问题变为去掉\(c < F\)边后最小化\(\sum f_i\),变成最短路问题。
P3489
考虑\(p \le 13\),则我们可以通过状压表示当前有哪些剑,随后跑分层图。
P2341
以前在某oj上做过。。。发现洛谷没切赶快写了。
考虑每个scc,显每个scc内部互相喜欢,那么缩点,此时变成了一个DAG。
若DAG上存在唯一一个出度为0的节点,则其他任何节点都能到达它。
若DAG上存在大于1个出度为0的节点,则答案为0。
详细证明略,留给读者思考。
(雾)
P2837
伞兵dp题,一眼就秒了,不想讲。
Day 9
P5664
POJ1236
缩点,然后变成DAG,第一问为入读为0的点的个数,第二问为max(入度为0个数,出度为0个数)
Day ?~12
停更了几天,主要就是打打cf做做水题。
Day 13
P2471(仅80pts)
分类讨论。然后st表维护\(r\)最值。
但是细节写挂了只有80pts
P2574
以前做过这种题。就是维护一个线段树。不难发现,如果一个数被异或两次,那就异或了个寂寞。所以打个lazy_tag维护一下。
P5677
我们将序列\(a\)排序,不难发现,对于一个数,只有它左边和右边的数可能会和它组成好的配对。分类讨论即可。然后问题变成了:给一堆点对和一堆区间询问,求询问区间内包含了几个点对。煞笔题,BIT维护即可。
P5482
思维难度一般,细节巨多的题!!!
日
考虑将每个不等式变成约束\(x\)的不等式。
考虑一个不等式\(ax + b > c\):
- 若\(a > 0\),则\(x > \dfrac{c - b}{a}\)
- 若\(a = 0\),则与\(x\)无关,判断是否\(b > c\)
- 若\(a < 0\),则\(x < \dfrac{c - b}{a}\)
建两个BIT T1,T2,分别表示>和<。对于每个query,答案即为T1.q(k) + T2.q((k + 1)~N) + total_0(\(a = 0\)成立的情况)