• 周日. 7月 3rd, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

全程NOIP计划 题目选做

admin

11月 28, 2021

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 – b_i)^2 = sum_{i = 1} ^ n a_i^2 + sum_{i = 1} ^ n b_i^2 – 2sum_{i = 1} ^ n a_ib_i
]

不难发现(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 imes 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}(nlog{n} + q))

P2251

?滑动窗口三倍经验?

P1816

ST表双倍经验。

P2216

啊这个题有意思,我第一眼感觉是无脑二维数据结构,但是忘了二维ST表怎么写了(逊),遂想了个nt做法:
预处理每个(1 imes n)的方块的最大最小值,然后在每一行跑单调队列并更新。(mathcal{O}(abn)),啊啊啊逊死了!
(最优解貌似(mathcal{O}(ablog{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_i = max_{i – r le x le i – l} {dp_x} + A_i
]

不难发现转移的那个区间是连续的,那么单调队列优化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)

[dp_i = max_{i – k le j le i} {dp_{j – 1} + E[j + 1,i]}
]

(注意(j)是可以取到(i)的,因为(i)也可以休息)
考虑到(E[i,j])可以拆成前缀和:

[egin{aligned}
dp_i &= max_{i – k le j le i} {dp_{j – 1} + E_i – E_j}\
&= max_{i – k le j le i} {dp_{j – 1} – E_j} + E_i\
end{aligned}
]

单调队列维护(dp_{j – 1} – E_j)即可。

P2034

与P2627完全一致。

P1840

无脑线段树。tgt给我发过来说有并查集做法,不是太会。

P3957

想到了二分(g),然后设(dp_i)为在(i)前的最大得分,得:

[dp_i = max {dp_j} + A_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)。那么:

[dp_i = max_{X_i – r le X_j le X_i – l} {dp_j} + A_i
]

不难发现这个东西可以用单调队列维护,但是略微有点难写。

AT5758

tgt扔给我的。易证答案为(min {a_i} + min{b_i})和所有用券情况的最小值。随便写一写就好

tgt随手扔了一个故意写错的代码演我,嘤嘤嘤

Day 5

P2569

较有难度的单调队列优化dp题。
Solution

P3800

不难想到设(dp[i][j])为在((i,j))点的最大Power.显然,(dp[i][j])只能从(i – 1)行的某个区间内的(j)转移过来,即:

[dp[i][j] = max {dp[i – 1][k]} + val[i][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,

则:

[dp[i] = max_{a_i exttt{&} a_j
eq 0,j < i} {dp[j]} + 1
]

(mathcal{O}(n^2)),啪的一下,很快啊,90pts?

离谱。

但是没有AC怎么行!然后接下来就是重点:

(dp[i][j])为前(i)个数,二进制第(j)为为(1)的最大长度。因为我们发现,与运算不等于0即为至少有一位为1。那么只要暴力转移就行。

[dp[i][j] = max {dp[i][j],max_{a_i exttt{>>} k exttt{&} 1} {dp[i – 1][k]}}
]

这个(i)这一维显然可以滚掉。

时间复杂度(mathcal{O}(n log a_i))

P1396

似乎有好多做法。

  • spfa板子
  • 二分+并查集,先将所有边按照(w)排序,二分拥挤度最大值,然后check里面将所有(w le mid)的边的(u,v)合并,中间判断(s,t)是否在一个集合。

P1823

这个有点像前几天做的奶牛题。维护单调递减的单调栈,然后会发现每次的贡献就是一直到第一个比它高(严格)的人。

image-20210724001348755

P3958

并查集naive题。

两个球形是否相交或相切等同于(dist)是否小于等于(2r)。 如果是边界则是(r)

Day 6

P7167

很容易想到通过反向扫建一个单调栈求出对于第(i)个喷泉,它会流到它后面的哪一个喷泉,线性复杂度。(如果会流向水池则为0)

然后若将这些关系连边,则会变成一个树。

(根节点为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

具体看Atcoder Beginner Contest 211

P3188

0-1背包问题,但是考虑到(W)非常大,而且(w_i = a imes 2^b),那么就考虑将(b)相同的归为一类,做0-1背包,然后再将它们合并;
(dp[i][j])(w_i)可以表示为(a imes 2^i)形式的物品,容量为(j imes 2^i)的最大的价值。
那么

[dp[i][j] = max{dp[i – 1][j – w[i]] + val[i]}
]

裸的板子,接下来考虑合并:
我们设(g[i][j])表示(b)(0sim i)的所有物品,体积为(i imes 2^j + w exttt{&} (2^{i} – 1))的最大价值。
那么

[g[i][j] = max_{0 le k le j} {g[i][j – k] + g[i – 1][(2 * k) exttt{|} (m exttt{>>}(i – 1) exttt{&} 1)] }
]

Day 7

模拟赛1补题

全程NOIP计划 模拟赛1

CF1061C

rxz直播改题目难度,nb嗷
(dp[i][j])为考虑了(a_1 cdot a_i),且选了(j)个的方案数。
则:

[dp[i][j] =
egin{cases}
dp[i – 1][j] + dp[i – 1][j – 1] & (j mid a_i)\
dp[i][j] & exttt{otherwise}
end{cases}
]

发现可以滚掉第一维,又发现这样的话只要考虑(j mid a_i)的转移就行。可以做到(mathcal{O}(n sqrt{a_i}))

CF245H

(ispal[i][j])表示(S[i,j])是否为回文串,则:

[ispal[i][j] =
egin{cases}
[s_i = s_j] & (j – i le 3)\
ispal[i + 1][j – 1] exttt{&} [s_i = s_j] & exttt{otherwise}
end{cases}
]

然后作个二位前缀和即可。

P1385

(sum)为这个字符串的字典序和。不难发现所有字典序和(=sum)的字符串都可以通过这个字符串变形而来。那么问题转化成求长度为(n)的、字符串字典序总和为(sum)的字符串个数-1.
乱搞dp,不想讲了。

P1537

背包+二进制优化,不想讲了。

P1622

区间dp,设(dp[i][j])表示释放了(s[i sim j])的犯人的最小答案。

则考虑枚举(k(i le k le j)),考虑释放(k),则:

[dp[i][j] = min_{i le k le j} {dp[i][k – 1] + dp[k + 1][j] + length[s[i – 1],s[k]) + length(s[k],s[j + 1]]}
]

Day 8

P3385

差分约束。若(x_i – x_j le x),则作一条边权为(x)(j o i)的有向边。最后判断是否有负环(spfa)。

P3275

差分约束。把所有条件变成(ge),跑最长路。、

CF106C

显然每个面包最多做(min {a_i / b_i,n / c_i}),这里(/)包括了下取整。转换成多重背包二进制优化。

P3199

题意:给一个图,求环,使得(left(sum w_iight) / k)最小,(k)为环的点的个数。
考虑二分。若(ans)满足条件,则(left( sum w_i ight) / k le ans),变成(left(sum w_i ight) le ans cdot k o left(sum w_i ight) – ans cdot k le 0 o left(sum (w_i – ans) ight) le 0)。相当于是每条边(-ans)然后判断是否有负环。

P5837

一句话题意:
求一条(1 o n)的路径,最大化

[dfrac{min{c_i}}{sum f_i}
]

枚举(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

P5664 [CSP-S2019] Emiya 家今天的饭

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)成立的情况)

发表评论

您的电子邮箱地址不会被公开。