部分题解集合

__vector__ · 2023-01-14 14:25:10 · 个人记录

CF1353E

• Difficulty: \color{purple}\text{1900}
• sol1:
  可以枚举最后一个灯的所在位置，进行 dp。
  设 dp_i 表示最后一个灯在位置 i，且只考虑前 i 个位置的最优解。
  显然，对于转移，一种情况是前面全是 0，只有这一位是 1；另一种情况，是位置 i-k 为 1，i-k+1 到 i-1 都是 0，从dp_{i-k} 转移过来。
  复杂度 O(n)
  提交记录
• sol2
  这些灯可以存在的位置模 k 同余。
  所以可以用 O(k) 的时间枚举灯可选的位置。
  由题目可知，除了选出了的一些相邻的模 k 同余的位置是 1，其余位置都得是 0。
  也就是说选出了一个位置使其为 1，如果原来就是 1，可以少改变一次，如果原来是 0，就要多变一次。
  现在就是选出一些连续的模 k 同余的位置使得最终改变的次数最小。
  成经典贪心题了。
  复杂度 O(k \cdot \frac{n}{k}) = O(n)
  提交记录
  然后发现和第一份做法都是 93ms，复杂度一样常数也一样。。。。。

CF1403C

• Difficulty: \color{black}\text{3}\color{red}\text{200}
• sol:

CF3A

• Difficulty: \color{gray}\text{1000}
• sol:
  本质上就是可以一次操作中可以改变单个坐标一次，也可以横纵坐标一起改一次。
  贪心是很显然的。
  提交记录

CF1396C

• Difficulty: \color{orange}\text{2300}
• sol:
  设 dp_i 表示解决完前 i 关的最小代价。
  对于每一关，显然都分两种情况：一次解决所有怪；解决所有的小怪后，逃跑，再回来打死 Boss。
  想一下，移动路线必然是从 1 到 n（最后一步可能还有个 n 到 n-1）。
  对于一次解决所有怪（即不逃跑再回来打）的情况，从 dp_{i-1} 转移。
  对于需要逃跑一次的情况，最优的方法是移动到相邻的关卡，相邻两关互相横跳再继续往后走（总体上是向后走的，一些关卡因为要打两遍，为了减少时间消耗只往前走一个关卡，然后回来继续向后走）。
  所以这种情况也从 dp_{i-1} 转移。
  注意走到了 i-1 再回来， i-1 和 i 这样下来都能打两遍，也就是说还可以从 dp_{i-2} 转移过来，计算 i-1 和 i 打两遍的代价。
  总体说完了，一些细节要处理。
  注意如果是 n-1 和 n 互相横跳的话，由于不存在没访问过的点了，n 可以直接解决所有怪然后跳到 n-1，不再回去，这个要特判。
  复杂度 O(n)。
  提交记录

ABC176F

• Difficulty: \color{red}\text{2912}
• sol:

ZOJ2113

• Difficulty: Unknown
• sol:

CF498E

• Difficulty: \color{red}\text{2700}
• hint: 矩阵乘法
• sol:

ABC144F

• Difficulty: \color{orange}\text{2189}
• sol:

CF8E

• Difficulty: \color{red}\text{2600}
• sol:

CF1140E

• Difficulty: \color{orange}\text{2200}
• sol:
  显然只需要分别计算每段连续 -1 的方案数，然后乘起来就行了。
  进行一些模拟发现，每段连续 -1 的方案数和左右两边的值没有关系，有关系的是左右两边的值是否相等。
  可以 dp 预处理长度为 i 的连续 -1 段的方案数。 $dp_{i,1}$ 表示长度为 $i$ 且左右两边的定值相等的 $-1$ 连续段。 把 dp 状态对应的图画出来（如 $dp_{i,0}$ 对应 $a,-1,-1,\cdots,-1,b$），就能列出转移方程，即： $dp_{i,1} = dp_{i-1,0} \cdot (k-1) dp_{i,0} = dp_{i-1,0} \cdot (k-2) + dp_{i-1,1}

  复杂度 O(n)。
  提交记录

CF1782E

• Difficulty: \color{orange}\text{2300}
• sol:

vjudge Kattis-tetris

• Difficulty: unknown
• sol:

CF1699E

• Difficulty: \color{red}\text{2600}
• sol:

acmicpc.net 12610

• Difficulty: unknown
• translation：
  题意：
  一年有 N 天，其中有 T 场比赛。
  每一场比赛分为很多轮，且每一轮都分布在比赛开始后的第 \cdots （不知道）天。
  这些比赛的开始时间随机分布在一年中的一些天。
  设一年中一天同时有 S 轮，那么这一天所带来的快乐值贡献为 S^2。
  求这一年快乐值期望总和（如果某些轮到了下一年，不算）
  输入格式：
  第一行有一个整数 C，代表有 C 组数据。
  每组数据第一行是两个整数 N,T。
  接下来 T 行，第 i 行描述第 i 场比赛。
  每行第一个整数 m，代表这场比赛有 m 轮，接下来是 d_2,d_3,d_4,\cdots,d_m，d_i 代表第 i 轮在比赛开始之后的第 d_i 天进行（第一轮都是在比赛开始的第一天进行，所以没给出）
  输出格式：
  每组数据输出一行，每行输出一个最简形式的带分数，代表答案（具体看原文）。
• sol:

POJ3623

• Difficulty：unknown
• hint: 贪心利用后缀数组优化
• sol:

CF295D

• Difficulty: \color{red}\text{2400}
• sol:

CF533D

• Difficulty: \color{black}\text{3}\color{red}\text{000}
• sol:

CF1418D

• Difficulty: \color{orange}\text{2100}
• sol:
  首先，如果点数小于等于 2，不用进行操作。
  否则，画图可知，答案为最大坐标减最小坐标，再减去（相邻两个点位置差的最大值）。
  加上了括号方便断句。
  最大坐标和最小坐标用 set 维护就行了，接下来要想的是如何维护相邻两个点位置差的最大值。
• sol.1
  用 multiset 维护相邻两个点位置差的最大值。
  考虑插入删除操作的影响到底是什么。
  对于插入，设插入在位置 x，x 左边最近的点为 l，x 右边最近的点为 r，相当于删除区间 [l,r] 的影响，加入区间 [l,x],[x,r] 的影响。那只需要在 multiset 里面删掉一个 r-l，加入一个 x-l 和一个 r-x。
  对于删除，和插入差不多，只不过反过来了。
  一个技巧：如果不想分类讨论，可以先插入两个点，分别是 + \infty 和 - \infty。
  复杂度 O((n+q) \log n)。
  提交记录
• sol.2
  用线段树维护相邻两个点位置差的最大值。 合并区间的时候，就是左子区间的答案，右子区间的答案，和（右子区间最靠左的点的坐标）减去（左子区间最靠右的点的坐标） 取 max 作为当前区间的答案。 所以线段树需要维护三个值，即当前区间答案，当前区间最靠左的点的坐标，当前区间最靠右的点的坐标。 复杂度 $O((n+q) \log n)$。 [提交记录](https://codeforces.com/contest/1418/submission/189812049)

Luogu P4066

• Difficulty: \color{purple}\text{省选/NOI}
• sol:

CF1520G

• Difficulty: \color{orange}\text{2200}
• sol:
  一定只使用一次传送门。
  证明：设使用两次或以上的传送门能达最优效果，第一次使用传送门的起点为 s，最后一次使用传送门的终点为 t，显然直接从 s 到 t 更优。
  现在分两种情况统计答案，第一种是不使用传送门，第二种使用一次传送门。
  第一种很简单，第二种也只需要找出走的距离和跳的代价总和最小的两个点就行了。
  复杂度 O(nm)。
  我不知道开了 Ofast 为啥还跑这么慢，提交记录。

POJ1151

• Difficulty: unknown
• sol:

CF845E

• Difficulty: \color{red}\text{2400}
• sol:
  二分答案，然后离散化所有矩形，看空隙之间距离就行了。
  离散化的时候要把矩阵四个顶点旁边的点也加入离散化，否则空隙可能会被离散化凭空消失掉。
  Codeforces 提交记录
  这样复杂度 O(k^2 log_{n})，是最劣解。
  为了优化复杂度，可以采用扫描线。
  扫描线题解

  CF1635F

• Difficulty: \color{red}\text{2800}
• sol:

CF1284D

• Difficulty: \color{orange}\text{2100}
• sol:
  本质上是问是否不存在两个会议，使得在一个会议场不发生冲突，另一个发生冲突。
  一个简单的套路就是对每个会议分配一个随机权值，然后对每个会议，在两个会场分别记录与其不发生冲突的会议的权值的异或和，看两个会场所得结果是否一样就行了。
  计算不发生冲突的会议的权值的异或和，前后缀异或和预处理就行了。
  这样是复杂度是 O(值域) 的，过不去。
  考虑实际上只关心区间端点的相对大小，可以离散化。
  复杂度是离散化的 O(n \log n)。
  提交记录

CF1132F

• Difficulty: \color{purple}\text{2000}
• sol:
  我不会比洛谷题解说得清楚。

  acmicpc8081

• Difficulty: unknown
• sol:

CF ACM sguru442

• Difficulty: unknown
• sol:

CF482C

• Difficulty: \color{red}\text{2600}
• sol:

https://coursera.cs.princeton.edu/algs4/assignments/baseball/specification.php

• Difficulty: unknown
• sol:

UVA1086

• Difficulty: unknown
• sol:

ABC210F

• Difficulty: \color{orange}\text{2632}
• sol:

HDU-3062

• Difficulty: unknown
• sol:

POJ-3281

• Difficulty: unknown
• sol:

POJ-1149

• Difficulty: unknown
• sol:

POJ-2391

• Difficulty: unknown
• sol:

CF1009G

• Difficulty: \color{red}\text{2400}
• sol:
  贪心思想。
  从前到后枚举每一位的字母。
  优先保证前面的小。
  当一位枚举了一个字母之后，可以通过网络流判断后面位是否存在合法方案。
  关于网络流：
  搞成二分图的形式，左部点是位置，右部点是 6 个字母。
  右部点向超级汇点连权值为该点在原串中出现次数的边。
  当然这不是真正的二分图，可以这样转化成二分图：把每种字母拆成该字母在原串中出现次数个点。
  然后枚举右部点 6 个字母的子集，hall 定理判定即可。
  提交记录

ARC076F

• Difficulty: \color{red}\text{2819}
• sol:
  只考虑一个段点限制，然后贪心得计算右端点。

  CF808F

• Difficulty: \color{red}\text{2400}
• sol:
  二分等级。
  质数除了 2 都是一奇一偶组成的，而 2 = 1+1，也就是说只能有一个 1。
  把 1 处理掉之后形成了一个以奇偶分类的二分图，超级源点向左部点连权值为能量的边，右部点向超级汇点连权值为能量的边，然后求最小割。
  CF 提交记录

loj3379 【CSP-S2020 儒略日】

• Difficulty: \color{green}\text{普及+/提高}
• sol:

  CF Gym100722

  这个 gym 比较特殊，可以查看他人代码，只有看数据需要 Coach Mode。
  在 UVA/SPOJ/BZOJ 有原题。

• Difficulty: unknown
• B:
  把集合编上号，模拟。
• D:
  最小斯坦纳树。
• E:
  排序，然后 dp。