全程NOIP计划题目选做

日期：2022-07-02 分类：技术分享浏览：98次评论：0条

Day 1

P1314

二分答案

P2367

差分板子

全程NOIP计划题目选做

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 - 2\sum_{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 \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_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]\)可以拆成前缀和：

\[\begin{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题。

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 \texttt{&} a_j \neq 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 \texttt{>>} k \texttt{&} 1} \{dp[i - 1][k]\}\} \]

这个\(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\)的最大的价值。
那么

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

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

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

Day 7

模拟赛1补题

CF1061C

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

\[dp[i][j] = \begin{cases} dp[i - 1][j] + dp[i - 1][j - 1] & (j \mid a_i)\\ dp[i][j] & \texttt{otherwise} \end{cases} \]

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

CF245H

设\(ispal[i][j]\)表示\(S[i,j]\)是否为回文串，则：

\[ispal[i][j] = \begin{cases} [s_i = s_j] & (j - i \le 3)\\ ispal[i + 1][j - 1] \texttt{&} [s_i = s_j] & \texttt{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 \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\)的路径，最大化

\[\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

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

转载注明出处：http://js.xxbyc.cn/post/214627.html

上一篇：微信小程序音频播放

下一篇：微信小程序之背景音频

全程NOIP计划 题目选做

Day 1

P1314

P2367

P2882

P1719

P3017

P1884

P1638

P3143

P1496

P1714

Day 2

AT4168

P1966

P2345

P3138

P4653

Day 3

P3658

UVA11572

AT4142

P2866

P3467

P2032

P2880

P2251

P1816

P2216

Day 4

P1725

P1419

P2627

P2034

P1840

P3957

AT5758

Day 5

P2569

P3800

P2254（未AC，后补）

P1944

P4310

P1396

P1823

P1783

P1950

P2516

P1776

P1855

ABC 211

P3188

Day 7

模拟赛1补题

CF1061C

CF245H

P1385

P1537

P1622

Day 8

P3385

P3275

CF106C

P3199

P5837

P3489

P2341

P2837

Day 9

P5664

POJ1236

Day ?~12

Day 13

P2471（仅80pts）

P2574

P5677

P5482

全程NOIP计划题目选做