一些可能用来复习的题目

cbio · 2020-08-06 23:47:47 · 个人记录

与本地版本不定期同步

• UOJ311 积劳成疾（最大值的分治性质）

• 无限之环

• 切糕

• 300iq r2 J.Jiry Matchings

• [ARC072D] Dam

• uoj549【UNR #4】序列妙妙值

• loj539「LibreOJ NOIP Round #1」旅游路线

• agc036D : Negative Cycle

• 疏散

• 划分

• AGC040C

• 【NOI2020】超现实树

• AGC033F

• 一些题目

• [ARC092D] Two Faced Edges

• [AGC030D] Inversion Sum

• [ARC083D] Collecting Balls

• BZOJ4245 OR-XOR

  • 考虑按位贪心；注意到或为零即代表前缀和序列均相等，因为n必然出现，因此可以确定可用的前缀和位置，维护可用情况即可

• CF860E

• Poping Balls

• Sightseeing（unsolved）

• 「WC2019」I 君的商店

• UOJ 217 奇怪的线段树

• [ZJOI2017]线段树

• 【AGC 024E】Sequence Growing Hard

• PA2019 Desant

• AGC023F 01 on Tree

  • 一类邻项交换有关的贪心模型
  • 考虑排序后的第一项，一定是在可以选之后第一个选，否则可以向前交换使得答案更小

• All killed

  • 比较启发式的思路
  • 显然不能dp时记录当前的序列的覆盖情况，也无法简单的优化
  • 考虑从值域（此处为写题的时间覆盖）而不是定义域入手，计算值域中合法的情况每一种对应的初始序列，最终的时间段有n+t-Σai个，每次填入一个题目；会选择当前会做的编号最小的题目写，则可以简单的计数
  • 类似的题目： [清华集训2016] 你的生命已如风中残烛]
  • 转化为圆排列，在m+1个元素中随意选择，可以证明对应唯一的一种成链的方法，再乘上系数

• 水壶（地址同下）

• [51nod 1327](D:\OIFiles\课件\syq的课件\那些年一起的培训\sjz 国庆\example.pdf)

  • 发现按行转移会有冲突，考虑按列转移；从左往右选列，假如对于左侧限制在每一列匹配，则不能记录选择情况，那么在端点处匹配；常见技巧：为之后的限制预留列

• AGC030C

  • 构造，一般来说思路不会过于复杂，而是比较隐蔽，从特殊或弱化情况有可能能得到思路
  • 从一行中的为一个数出发，注意到对角线可以进行类似操作，同时对角线个数为2n-1；对角线还可以替换为两种颜色交替的序列

• CF576D

  • 询问全局最短路，但是边的出现机会不同——考虑把最优解差分，求出必须经过每个点的最优解，此时发现经过边数≥t的一定经过t，那么求出t时刻能到达哪里，bfs
  • 在一般图上找关于环的信息，目的是为了找到绕环的方案，且时间很大，一般考虑用矩阵乘法维护（参考数据范围）

• Clique 给一个圆的n 条圆弧, 选出一个尽量大的子集使得其中的圆弧两两有交. n ≤ 3000.

  • 枚举一条必须选的圆弧x, 使得不存在其他选了的圆弧被它完全包含.

  对于与它两端都有交的圆弧, 选入不会影响答案; 对于与它不相交的圆弧, 显然不能选. 剩下只考虑与它左端点相交的圆弧和右端点相交的圆弧. 一个左边的圆弧和一个右边的圆弧可能会在x内和x外相交。于是可以转化为二维平面上的问题: 选出最多的黑点和白点使得不存在黑点严格在白点的左下方. 按照横坐标排序设DP状态f(i)为之前选过的黑点最低纵坐标为i时，不能选的白点个数减去选过的黑点个数，最小化这个值。线段树优化，当前横坐标之后的纵坐标i以上的白点个数为h(i)，则维护f(i)-h(i)，扫描到第i个黑点时f(y_i)=\min\{f(j)-h(j)+h(y_i)|j>y_i\}，再把小于yi的dp值减一，答案为白点个数减去最终的\max f(i)

• CF959F

  • 线性基的另一个应用方式

• 线性基的元素在原集中对应的元素个数相同设为k，若x不能被表出，则方案为0，否则除k个之外，剩余的可以任意选，设其xor和为p，p,x均可以表出，则p xor x也可以被表出

  • 类似题：杜老师

• 线性基的张成与原集相同的原因：相当于化为阶梯形矩阵的过程，是行变换，行变换不改变张成

  给定N 个点的图，你需要连恰好M 条边 (N,M<=2000)，不能连自环，同一对点之间至多连一条边. 给定K，求有多少种方案使得得到的图中：恰好有K 个点度数为奇数？恰好点1 ~ K 的度数为奇数？

  • 一类容斥方法；根据题目的一些特殊性质，发现当前状态的不合法情况恰好可以使用之前的状态表出，可进行递推

  IOI 河流

  给定N 个点的有根树，每条边有一个长度，你需要选择其中K + 1 点建伐木场，且保证根节点有一个伐木场.每个节点有一个权值wi，记它和最近的、建立了伐木场的祖先的距离为di，那么它需要支付的代价为w_id_i. 合理地安排伐木场的位置，使得总代价和最小. N=100,K≤50,w≤1e9

  • w的值域很大，不能从权值入手；同时n很小，考虑决策点；不能在子树根处枚举，决策集合过大，发现一个点的祖先节点集合很小，设计状态f[x][k][anc]表示以x为根的子树，建了k个，且承诺距x最近的为anc的最优代价

• [COCI2015] Divljak

  • 树上两种操作：给若干点，对于这些点到根形成的链的并加一、或单点查询值
  • 更改时，点按dfs序排序，在点处加一，dfs序相邻两点的lca处减一，查询子树和；发现对于某子树一定加了k次，减去k-1次

• [AGC028D] Chords

  • DP最终有几个连通块不可行，需要知道具体的连边情况；考虑计算贡献
  • 思路是对于每一个点计算出它为最左端的连通块个数；发现DP复杂度过高
  • 注意到连通块一定是一个连续区间，其中的点与外界无边；那么可以利用组合数计算区间[l,r]的方案数，只要满足给定的匹配即可，可以利用更短的区间的答案进行容斥，去掉l,r不在同一个连通块的情况
  • 计算贡献时枚举的元素也可以内部有组合情况，根据问题特征选择

• [AGC029F] Construction of a tree

• CF1043F Make It One

  • 注意到答案≤7，枚举答案转化为求gcd为1的个数，先计数因数，然后容斥得到gcd的情况

• ARC104F Visibility Sequence Editorial

  • 注意到在最左端添加一个极大值后序列形成了一棵树；进一步发现原序列的顺序是树的一个前序DFS遍历
  • 区间dp，以满足高度限制
  • 类似的题目：维护一个这样的序列，支持互换相邻项、求序列区间深度和
  • 发现互换相邻项会进行子树中的换根操作，直接维护区间的深度，则操作为区间加，单点赋值

• CF1166E The LCMs Must be Large

  • 必要条件：m个集合两两有交
  • 证明其也是充分条件：考虑构造方案，对第i个集合中的数乘一个质数pi，其中质数两两不同；一个集合的lcm是所有质数的乘积，而其补集至少不含pi

• AGC027E

  • 推出判定值域可行性结论+直接计算值域（方法为贪心思想）

• IOI2013 wombats

  • 宽度过大，考虑优化转移；发现边权均为非负整数，那么矩阵合并时，满足二维决策单调性（原因：若不满足，则一点出发的到另外两点的最短路径有交，不成立）

• 你一共有n张符卡，他们按照编号顺序从上到下形成一叠。每张符卡有两个属性L_i​和D_i。你每次可以执行以下任意一个操作： 1.切换：把卡堆最上方的符卡放到卡堆底。 2.施法：使用最上方的符卡，若最上方的符卡编号为i ，则你丢掉卡堆最上面的L_i张符卡（包括你使用的最上面的符卡）。你可以对敌人造成D_i伤害。如果卡堆不足L_i张你不能使用此操作。 你可以执行任意次操作，最后求你的卡堆能造成的最大伤害。

  • 轮换的次数不受限制，那么只要存在足够的卡，且当前卡存在，则可以选；转化一下条件：从前往后选，当前点被覆盖则从覆盖之后的空位向后选，只要不覆盖左侧第一个被选择的点即可。观察一下发现只要长度相加小于n即可。

• ARC105D

  • 有n堆石子，轮流选一个没有选过的放到一个位置上，可以和之前的放在一起。最终形成若干堆石子，做nim，问谁获胜

  • 若n是偶数，第二个人目标是使得xor为零。若每一种数字的出现次数都为偶数，则第二个人可以与前一个人的行动对称地做，使xor为零。否则第一个人可以每次选最大的一堆放到当前最多的位置上，使得最终这一堆>n/2

  • 若n是奇数，第二个人可以可以每次选最大的一堆放到当前最多的位置上，使得最终这一堆>n/2

• ARC106E Medals

  • n很小，求完全匹配的最少右部点，那么使用霍尔定理
  • 注意到直接求出一个子集的右部相接点很困难，但是对于特定的t，求出所有的子集的相接点可以用FMT优化，那么二分答案即可

• 一群饥饿的小鸟，要到河对岸吃东西。河的宽度为 N 米，小鸟每飞行 L 米就必须在一片荷叶上休息一下，才能够继续飞行。当然，小鸟们也可以选择没飞够 L 米就先休息一下，但不能一次飞超过 L 米。 距离小鸟们出发的河岸一侧距离为i的荷叶共有Ai 片，每片荷叶在有小鸟停于上方休息后， 就会沉入水底，不能够再供其他小鸟休息。 现在想要知道，至多有多少只小鸟能够抵达对岸。

  • 贪心结论是每次优先选最靠后的能选的；然而直接写多路增广会tle；发现每次直接从能到达的远处开始枚举j，把当前点的流量推min(rest,a[j])到j即可；因为假如点j不能把流量流完，这部分流量在点j之前的点k也不能流出更多

• 给定一棵点带权的二叉树，支持左右旋、查询一个点的子树中所有点的sum（其子树中所有点的点权和）的乘积

  • 注意到中序遍历不变，且每次sum值更改了的只有两个点；在中序上建立线段树维护sum，单点更改区间求积

• ARC107 D

  • 这题场上a了，还是可以复习一下
  • 给定n，k(\leq3000)，求出用n个 2的整数次幂的倒数 凑k的方案数；
  • 显然各个位在计数时是等价的，可以设f(i,j)为用j个凑了i个当前位的方案数；转移f(i,j)=f(i-1,j-1)+f(i,j2)，发现j的转移是逆着的；此时不能放弃这个思路，发现边界是f(i,i)=1，于是j逆着递推即可

• CF274E Mirror Room

  • 推性质的题目，利用的性质如此specific...没有性质的话可以log方树套树跑
  • 发现形成回路只有两种情况：
  • 碰到头返回
  • 只利用90°转弯，从来的反方向回到了起点
  • 同时黑白染色后发现在回路中同一个格子进入时的角度mod180相同，于是可以简单计算

• 给出一个长度为 \mathrm{n} 的序列 \mathrm{A}[1 \sim \mathrm{n}], 求其所有排列下的{1~n所有前缀和之积的倒数}之和；所有的运算均在 mod 998244353 意义下进行。

  • 考虑组合意义，假设n个盒子，分别有a[i]个球，如果从中间分别任选一个，则选定其中一种组合的概率是\dfrac{1}{\prod a[i]}，考虑每次从所有的中任意选一个，然后剔除掉这个盒子，直到选择了所有的盒子，那么最终选择每一种的概率不变，即等于题目要求的式子。

• 给出一个H 的行和W 列的网格（均≤100）。有一个出口，若干机器人，其余是空地。每次可以选择上，下，左，右之一的方向，将所有剩余的机器人向这个方向移动一个格子，如果一个机器人被移出了网格，那么这个机器人会爆炸，并立即消失。如果一个机器人移动到出口所在的格子，机器人将获救，并消失，求最多有多少机器人获救。

  • 考虑未到达出口机器人的存在情况，只和当前到达过的横纵坐标最值有关，因此可以考虑设f(i,j,k,l)表示横纵坐标最值情况下已经获救了多少个（拓展坐标的顺序会影响答案），枚举当前新增哪一维，新增权值即为新出现在范围内且不在之前的范围外的个数

• 给一段序列，求总权值最小的划分方案，每一段的长度不大于L；每一段的权值是最后一个数字减一后的这一段的最大值+1，总权值是每一段权值之和

  • 给出q个询问，求如果把某一个数修改，最终的答案
  • 1≤a_i,x,v≤n≤6×10^5,1≤q≤2×10^4,1≤L≤600

  • 可以预处理出来前后缀的dp值，中间的修改部分（以及DP）考虑使用单调队列优化，发现要维护最大值，支持两端删除，那么使用线段树维护；计算出来以后和后缀dp值拼接即可
  • 动态的DP问题，考虑能否求出从最终状态到当前状态的dp值，直接合并即可

• 有一个长度为n（n≤500）的数组，给定所有的不同数对的和，共n(n-1)/2个（无序），求出所有的可能的原数组的方案

  • 设原数组排序后是a，则前两个是a1+a2,a1+a3；枚举a2+a3所在的位置，最多有n种情况，知道了以后只要不断地把已知的元素所组成的所有的数对从集合中去掉就可以知道下一个数字

• 一个数列，每一个位置可以填一共给定数组的下标，使得数列填上的下标对应的数值之和为M，求可能的情况的奇偶性

  • 观察到如果1，2两个填入的下标不同，那么可以互换，则对答案无贡献，那么设1，2填入的相同；依此类推，最终只有log个大小是2的幂次的位置，数位dp即可

• 一棵树，点可能是白色或黑色，每次将若干个白色变为黑色，然后让所有的相邻至少有一个白色节点的黑色变为白色；求最终的颜色情况

  • 考虑维护一个可能变为白色的队列，同时维护儿子中的颜色数，当一个位置确定不能存在的时候也不需要立刻删除，懒删除即可；再维护一个儿子可能变白的队列，在父节点处维护儿子中是黑色的链表，同样懒删除

• 无向图，边权是0/1，一条路径的权值是从开头将经过的01记录下来形成的二进制数，先经过为高位，求单源最短路

  • 可以用主席树在分层图上跑，也可以利用性质：BFS，一开始队列里放入所有的从源点能不经过1边到达的点，每次取出队首的所有权值相同的点，先考虑0边，再考虑1边；设队首一定是相同位数下还没拓展过的最小的，那么一定比之后的优，则插入队尾后可以进行归纳

• 一个网格图，有若干白点能和若干黑点匹配，其中白点的匹配只能在给定方向进行，一个白点朝向的方向上不存在其他白点，黑点有权值，求最大权匹配，要求匹配路径不相交

  • 如果每个白点都先取可能达到的最大值，那么即可最小化代价，每个白点连一条从S到T的链，边权是所有的它可能匹配的点，跑最小割，那么相当于取最小值；限制只有不同方向的，那么只要不同方向的白点链的顺序相反即可连边

• n个物品，各有三档，分别花费1，2，3，其中一档和三档的价值增量为a，二档为b，求1到3n花费下的最小价格

  • 可以发现可以将物品拆分为两个：a+b和a，然后排序后凸序列max，+卷积合并即可

• 【AGC021D】一个字符串，可以选择最多k个位置换成任意的字符，要求最大化和它的reverse的LCS

  • 设最终LCS长度为k，正反的CS下标序列分别是a,b（s[a_i]=s[b_i]），那么存在一个i使得a_i<b_i,a_{i+1}\ge b_{i+1}，（两个指针相向扫），能够发现两边拼起来是两个回文串，且更大的那个长度≥k，那么LCS长度等于最长回文子序列LSP长度，区间dp设f(i,j,k)为i到j，花费k的LSP长度，枚举两边字符取不取即可

• 求n个点的竞赛图中有多少个存在至少一个大小≥k的环n,k\le 5000

  • 结论：强连通竞赛图存在哈密顿环，且竞赛图缩点后是一条链；那么条件等价于图中存在一个≥k的强连通块；容斥计算1~n个点的强连通竞赛图个数，再dp即可
  • 一个特征：全集易得，A集合是B集合的补集，同时B集合可以由不同大小的A集合组合得出

• uoj#512. 【JOISC2020】D4T3应对方案

  • 考虑最后的有可能成为最优解的方案，在任意时刻，一定满足当前所有连通块的左右端点即为最左/右端的线段去掉过去时间长度的位置；那么两个相邻点满足L_j≤R_i−∣T_i−T_j∣+1则可以接起来；且可以按照左端点排序后只向之后的转移（相同左端点不会同时选），用线段树维护即可

• bzoj1305 跳舞：

  • 考虑二分答案，如果能找到一个边集满足题目中的限制，同时每个点的度数均为k，那么可以归纳证明一定可以找到k个不交完全匹配；最大流即可

• PKUSC2018 神仙的游戏

  • 通配符匹配，考虑NTT；发现对于border长度大于n/2的会出现通配符前后代表的不一致的情况。考虑对应的周期，一定是出现了这样的情况：1,?,?,0，且这几个字符间隔为周期长度。那么先ntt，对于长度为k的周期枚举其倍数即可。

• loj6500. 「雅礼集训 2018 Day2」操作

  • 按照套路先差分，发现差分后除了开头，无论[l,r]在哪，差分结构都不变。首先要满足模k同余的所有点段内之和为偶数，可以求哈希值异或前缀和。答案也可以用前缀和求，原因是合法区间前一个点的所有奇偶性都与右端点相同，维护一个从右侧开始两两匹配的答案的前缀和即可，而求这个序列只需要维护每一个同余类的当前答案，新增一个时答案加上i-v(i)。

• PKUWC2020 给定一个 1..n的排列 p, 定义 L(p)为字典序不超过 p的所有 1..n的排列按字典序从小到大依次连接而成的序列。求 L(p)本质不同的子序列个数，对 998244353取模。 数据范围: 1≤n≤50

  • 按照在子序列自动机上匹配的方法dp。发现一般的从规模为i的排列推到规模为i+1的排列的方法无法计算答案。考虑如何连接两个串，为方便连接定义 f_S(i,j)= S的子序列中以 i 开头，选了若干个，最后当需要 j 时要跳出 S的个数，则连接就是做矩乘

  设 Ak= 前 k! 个排列依次连接得到的串的矩阵​，显然 A1(i>0,j≥0)=f_{1,2..n}(i,j)=[i≥j]2^{n−i}+[i<j]2^{j−i−1}(2^{n−j+1}−1)，为了求答案还要定义 A1(0,0)=1

  考虑如何 从 Ak 推到 Ak+1，这个过程相当于连接 1,2…n-k-1,(这一位从n-k到n-k+1...n)[剩下 k 个的排列]，那这一位从 t 到 t+1 相当于交换第 t 和 t+1 列并交换第 t 和 t+1 行。复杂度O(n^5)

• THUWC 解密运算

  • 如果存在相同字符，考虑如何区分排名。当首字母相同的时候，我们比较下一个字母。考虑两个相同字符，一个在另一个前面，那么在排序的时候它的串一定比另一个串小。于是按第二关键字是输入顺序排序就做完了。

• 给定n个数(n,a\leq 5\times10^5)，求一个最大的子集使得其异或和为0

  • 答案最多为log(a)，设f(i,j)代表不超过i个能否和为j，初始化f(1,i)后每次拿f(i-1)和f(1)FWT即可，因为只要求可达性，而在异或时最多需要出现一次，所以无需考虑重复；也可以利用异或FWT的意义每次O(N)求出单点的IFWT值

• 区间本质不同子串：

  • 离线，动态维护当前右端点时每个不同子串最靠右左端点位置；首先1~i区间+1，然后在sam上跳，遇到之前的就修改，此时发现如果把相同右端点的一些同时修改，然后再改成新颜色，那么复杂度就相当于lct的acc的复杂度。那么用lct维护链，在sgt上维护答案。

• 孩子们的玩具共有n 种，每种都有价格wi。一共只可以最多存放m种玩具，因而幼儿园会不断清理掉玩具（以后再需要时重新购买）。给定k条形如 [l,r]时段孩子们喜欢玩具i 这样的信息，问至少需要花费多少钱。n, k ≤ 1e4; m ≤ 10。

  • 显然可以跑流量为k的费用流，主轴最大流量为m，其他的流出代表卖掉下次再选；发现m很小，于是可以将主轴设为不选，流出设为选，上下界或者用-inf来满足选的要求

• 有n 个人向n 个箱子中投放物品。每人拥有物品质量ai，每个箱子承受质量上限bi 第i 个人只可以向第i个或第i mod n+1 个箱子里放物品。物品可以拆开来放，最多向箱子里放多少物品？n=1e6

  • 显然是最大流，因为数据范围，转化成最小割做，dp即可；最小割dp无需设流量为状态，只要知道是否割掉

• n个人，分别能到达的区间是 [l_i,r_i]，每一个人从中选一个点去，求最大的\sum_{i=1}^np(i)，其中p(i)是最终与i在同一个位置的人的个数

  • 结论是区间中人数最多的点满足[l,r]被区间覆盖的，且能到达它的人都会走到它，反证可证；此时区间被分成了不相关的两部分，区间dp枚举人数最多点，分治即可

• 「WC2021」表达式求值

  • 多组询问，考虑预处理一些东西，发现m阶乘过大，但是如果利用最值的性质将每一个设为0/1，则可以做到O(2^m|S|+nm\log m)

• 给一个n*m(n\leq 22,m\leq 200000)的01矩阵，每次操作可以取反任意一行或一列的所有元素，求进行任意次操作， 矩阵中的1的个数最少是多少。

  • 注意到二进制下x\otimes y可以视作x转化到y取反的位的表示，将计数数组和i各位上0和1的个数的最小值的数组异或卷积即可