Personal-Traning题解(一)

布满荆棘的人生 2022-06-07 03:20 108阅读 0赞

1.Codeforces Round \#418 E (dp+组合数学)：

[https://loj.ac/problem/6094][https_loj.ac_problem_6094]  
[http://codeforces.com/contest/814/problem/E][http_codeforces.com_contest_814_problem_E]  
虽然题目是一样的，但是时限不一样，cf的时限大1s，所以在cf上这题O(n5)可以过，但是loj就不行了，  
codeforces：  
把图按照最短路分层，那么这个图需要满足每个点都向上一层有且只有一条边，并且没有更向上的边。  
我们用dp\[u\]\[i\]\[j\]\[k\]\[l\]表示前u个节点，上一层有i个读数为1的插头和 j 个度数为2的插头，  
这一层有 k 个度数为 1 的插头和 l 个度数为 2 的插头。注意我们甚至并不需要关心最短路到底是多少。  
大力讨论一下转移就可以了。当前点先和上一层的一个点连接，剩下的度数可以留下，也可以和这一层的随便连。

[http://blog.csdn.net/sdfzyhx/article/details/73003862][http_blog.csdn.net_sdfzyhx_article_details_73003862]

loj:  
O(n^3),参考一下cf上的KAN的做法。很神奇。  
[http://codeforces.com/blog/entry/52449][http_codeforces.com_blog_entry_52449].

2.二分图染色。(组合数学，递推公式)

[https://loj.ac/problem/6160][https_loj.ac_problem_6160]  
这题是美团初赛的题，在一个完全二分图上将边进行染色的问题，红色不共享端点，蓝色不共享端点，绿色随意染。

可以转化为棋盘模型，即 N×N 棋盘上放黑白棋子，每个格子至多放一个，同行同列没有相同颜色的棋子。  
令bn为只有一种颜色，那么，bn=∑ni=0Cin∗Ain。  
然后我们考虑容斥掉两个颜色在同一格，如果一个格子既放黑又放白，那么这一列和这一行不会有其他棋子，直接删掉。

an=∑ni=0(−1)i∗Cin∗Ain∗(bn−i)2。

bn=2∗n∗bn−1−(n−1)2∗bn−2，可以花点时间想想左边这个公式。  
第一项是在第 n 行或者第 n 列上放一枚棋子或者不放的方案数，由于放两枚棋子的情况会  
被统计两次，最后还需减去摆两枚棋子的方案数，即第三项。

[http://blog.csdn.net/u014609452/article/details/73744264][http_blog.csdn.net_u014609452_article_details_73744264]

3.「美团 CodeM 初赛 Round A」倒水 （二分）

[https://loj.ac/problem/6161][https_loj.ac_problem_6161]

二分温度，返回总共使用的体积。  
这道题要注意一下精度。有的人用了long double,其实double也是可以的，分类二分温度一下。  
当全部t\_i相同时，什么操作都不需要，直接输出。  
当T>max\{t\_i\},就for 200-300次二分，有可能升温，也有可能降温。  
当T< min\{t\_i\},就只能降温了，直接算能不能把其他杯水是否能降到当前min\{t\_i\}，否则就Impossible。

4.「美团 CodeM 初赛 Round A」合并回文子串 （区间dp）

注意：a,b子串中的字母是相对不变的。  
考虑c中的回文子串，既然是子串，就一定可以拆成 a, b 两串的两个子串的组合。  
不妨 设是 a\[i, j\]与 b\[k, l\]的组合，则可以考虑动态规划的状态 dp\[i\]\[j\]\[k\]\[l\] 表示  
a\[i, j\]与 b\[k, l\]的组合能否组成回文子串。 新组合的串的串头一定是S1和S2串头中的一个，  
串尾一定是S1和S2串尾中的一个，则可以匹配第一个字符和最后一个字符来转移，  
根据第一个字符和最后一个字符分别来自 a 还是 b 共有四种转移:  
(注意分别l和1)（L和一）  
dp\[i\]\[j\]\[k\]\[l\]<−−dp\[i\+1\]\[j−1\]\[k\]\[l\](i<j,a\[i\]=a\[j\])  
dp\[i\]\[j\]\[k\]\[l\]<−−dp\[i\+1\]\[j\]\[k\]\[l−1\](i<=j,k<=l,a\[i\]=b\[l\])  
dp\[i\]\[j\]\[k\]\[l\]<−−dp\[i\]\[j−1\]\[k\+1\]\[l\](i<=j,k<=l,b\[k\]=a\[j\])  
dp\[i\]\[j\]\[k\]\[l\]<−−dp\[i\]\[j\]\[k\+1\]l−1\](k<l,b\[k\]=b\[l\])

5.「美团 CodeM 初赛 Round B」模（数学题。证明题。）

[https://loj.ac/problem/6176][https_loj.ac_problem_6176]

如果没有进位，则数字和为S(a)\*n，一次进位对数字和的贡献和是1-k，而数位和需要在模b下与c相等，  
根据模方程的扩展欧几里得解法，可以发现方程有解的必要条件是gcd(a,k−1,b)|c。然后我们要证明  
这个条件是充分条件。  
证明可以通过构造完成，对于任何a,一定【存在】其某个倍数p最低非零位的前一位不为 9，  
设此时最低非零位为 t,则一定存在其倍数 q 使得最高位为 k - t，设 q 在 k 进制下有 r 位，  
考虑构造如下两个数：

u=p∗kr\+q  
v=p∗k(r−1)\+q

可以发现u,v贡献的a数量相同,而进位数恰好 v 比 u 多 1。  
在模 b 意义下，构造x∗a\+y∗(1−k) 。  
由于an可以任意大，我们在无限位中分散地摆放 x 个 a(可能有一些进位)，再摆放一共  
b 个 u 或 v ，其对 a 的数目没有贡献，但可以把进位数变成 \[0,b-1\]的任意值 即 y。  
既然任意 x∗a\+y∗(1−k) 可以被构造出来，  
所以在b剩余系下有且仅有 gcd(a,k−1,b)|c 的倍数可以被构造出来。

6.LOJ \#6165. 一道水题（线性筛）

[https://loj.ac/problem/6165][https_loj.ac_problem_6165]

先用线性筛筛出\[1,n\]的所有素数，记为p\[i\]。  
答案是对每个p\[i\]，求出最大的p\[i\]k，满足p\[i\]k<=n。把所有这些p\[i\]k乘起来就是答案。

注意：模是1e8+7。

7.「美团 CodeM 初赛 Round B」送外卖2 （状压dp）

[https://loj.ac/problem/6177][https_loj.ac_problem_6177]

三进制状压DP。dp\[i\]\[j\]表示三进制状态为 i，最终走到 j 点的最小时间花费。  
那么状态对应一个位置是0表示没有取餐，是1表示取了餐没有送，2表示送到了，  
然后分析每一位上是0还是1进行状态转移，转移之前要预处理一下最短路，  
这个点比较少直接Floyd预处理一下即可。

8.ACdream 1113 （概率dp）

[http://acdream.info/problem?pid=1113][http_acdream.info_problem_pid_1113]

设dp\[i\]表示从i丢到n才达到目标和的期望的次数。  
dp\[n\]肯定等于0，那么就从最后往前推。

不难想到掷到123456的期望都是6.00。

dp\[i\] += dp\[i+j\]。  
dp\[i\]+ = 6 ==> dp\[i\]/=(6 - tot) (tot表示当前掷到的数和之前掷到的书的和大于n的次数)

最终答案就是dp\[0\]。

9.ACdream 1124 喵喵的遗憾（Fib数模n的循环节）

[http://acdream.info/problem?pid=1124][http_acdream.info_problem_pid_1124]

输入 N 和 P ，输出 Fib\[Fib\[Fib\[n\]\]\]%P。

找循环节。  
对于一个正整数n，我们求Fib数模n的循环节的长度的方法如下：  
（1）把n素因子分解，即 n=pa11∗pa22∗pa33∗∗∗∗pakk

（2）分别计算Fib数模每个的循环节长度，假设长度分别是 x1,x2.....xk.

（3）那么Fib模n的循环节长度L=lcm(x1,x2,.....,xk)

从上面三个步骤看来，貌似最困难的是第二步，那么我们如何求Fib模pm的循环节长度呢？

这里有一个优美的定理：Fib数模 pm 的最小循环节长度等于G(p)∗p(m−1)，其中G(p)表示Fib数模素数p的最小循环节长度。  
可以看出我们现在最重要的就是求G(p).

对于求G(p)我们利用如下定理：

如果5是模p的二次剩余，那么循环节的的长度是p-1的因子，否则，循环节的长度是2(p\+1)的因子。  
顺便说一句，对于小于等于5的素数，我们直接特殊判断，loop(2)=3,loop(3)=8,loop(5)=20。  
那么我们可以先求出所有的因子，然后用矩阵快速幂来一个一个判断，这样时间复杂度不会很大。

注意：需要注意的是P可能为1，因此n==0或者1的时候，特判要输出1%P而不是1.

10.HDU 2993 （斜率优化）

链接：[http://acm.hdu.edu.cn/showproblem.php?pid=2993][http_acm.hdu.edu.cn_showproblem.php_pid_2993]  
题意i：给你一个长度为 n 的序列，找出长度 >= k 的平均值最大的连续子序列。输出其平均值。

题解：斜率优化+fread。数据后期加强了。不加fread不能过。  
复杂度：O(n)。  
斜率优化的例题。  
先求出前缀和数组sum\[\]，然后问题转化成给出n+1个点求出两点横坐标差>= k的点对所能构成的最大斜率。  
然后朴素的想法是对于每一个可能的序列末端点 i，去寻找集合 \[1,j\]（i-j+1 >= k）中与它能构成的最大斜率，不断更新最大值。复杂度 O(n^2)。  
然后斜率优化的思想，是对于不断增长的集合\[1,j\] 维护一个下凸曲线，每次找出曲线中的切线即为当前最优值。  
找切线的时候，根据下凸曲线中切点斜率递增的性质，可以删除已经找到的切点之前的点。复杂度为 O(n)。  
数据被加强过，必须加fread才能AC。

11.HDU 1500（dp）

链接：  
[http://acm.hdu.edu.cn/showproblem.php?pid=1500][http_acm.hdu.edu.cn_showproblem.php_pid_1500]

题解：  
从大到小排序，保证k对筷子都有一支最大的条件 。  
dp\[i\]\[j\]表示前 j 支筷子取 i 对筷子的最小 badness，不考虑第三根筷子 。  
dp\[i\]\[j\]=min(dp\[i\]\[j−1\],dp\[i−1\]\[j−2\]\+(L\[j−1\]−L\[j\])∗(L\[j−1\]−L\[j\]));（L为筷子的长度）

12.HDU 1511（dp+思维）

链接：[http://acm.hdu.edu.cn/showproblem.php?pid=1511][http_acm.hdu.edu.cn_showproblem.php_pid_1511]

题解：  
先从前往后dp，dp\[i\] 表示包括第i位往前，满足题目要求能得到的最小长度。  
这样就可以求出，最后一个最小的满足的数了。

求出最后一个最小的数后，从后往前dp,dp\[i\]表示从第i位开始往后，在满足题目要求的情况下，能得到的最大长度。  
这样就可以求出，按顺序依次最大的。

简而言之：  
①从前往后DP，找出最后一个数的最小值，即最后一个数尽可能的小；  
②从后往前DP，找出最前面一个数的最大值，即第一个数尽可能的大。

14.Codeforces Alpha Round \#21 D（状压dp）

链接：[http://codeforces.com/contest/21/problem/D][http_codeforces.com_contest_21_problem_D]

题意：给一个无向图，要求从1出发回到1，但是必须经过图中每一条边，并且至少经过一次。注意：这不是欧拉回路。

/***\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\****/  
判断欧拉路是否存在的方法：  
有向图：图连通，有一个顶点出度大入度1，有一个顶点入度大出度1，其余都是出度=入度。  
无向图：图连通，只有两个顶点是奇数度，其余都是偶数度的。

判断欧拉回路是否存在的方法：  
有向图：图连通，所有的顶点出度=入度。  
无向图：图连通，所有顶点都是偶数度。  
/***\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\****/

题解：状压DP。  
度数为偶数的点不需要被考虑，只需要考虑度数为奇数的情况。首先每条边必须要访问一次，所以，所有边权加起来就是答案的初值。　  
然后度数为奇数的点就需要访问之前已经走过的边。我们考虑两个度数为奇数的点可以组合一下，就变成了度数为偶数的点，  
相当于是在这两个点之间新连了一条边，我们可以floyd预处理一下两点之间的最短路。  
然后状压dp，状态表示当前哪些结点的度数为奇数，然后枚举每次连哪两条边就可以了。

now = i^(1<<(j-1))^(1<<(k-1));  
dp\[now\] = min(dp\[now\],dp\[i\]+ w\[j\]\[k\]);//取或不取 j 和 k 两条边

15.Codeforces Beta Round \#14 (Div.2) D （树形dp）

链接：[http://codeforces.com/contest/14/problem/D][http_codeforces.com_contest_14_problem_D]

题意：  
给定一个无向图，含有一定的路。从中找出两个最长的路径（每条路径有一些相通路组成）。  
这两个路径不能经过公共的点，求什么时候两条路径的乘积最大。

题解：  
把一个图沿一条边割开，分成两个树，求这两个数中最长的路的乘积。  
这里需要分别求两个树的直径。  
因为题目数据不大，直接枚举边即可。(n^2)  
DFS从当前点开始搜索，把枚举的那条边先当作删掉，DFS当前点存在的最大深度和次大深度。  
两个相加不断更新最值，便可得到其中一边树的直径。  
同样再DFS一次就可以得到另外一边树的直径。  
最后相乘即可。

复杂度就是：O(n2).

16.Codeforces Beta Round \#14 (Div.2) E （dp）

链接： [http://codeforces.com/contest/14/problem/E][http_codeforces.com_contest_14_problem_E]

题意：  
画骆驼峰，给你n步，要你求可以画t个骆驼峰的方案数。  
要求骆驼峰的高度不能超过4。  
(3≤n≤20, 1≤t≤10).

题解：  
四维dp。  
dp\[n\]\[t\]\[j\]\[s\]。  
n代表点数（步长），t代表尖峰数，j代表高度，s代表上升（1）还是下降（0）的方案数。  
初始化第一步，第一个尖峰，高度为j的是一个上升峰。  
因为初始值看成了一个上升峰，那么步数为2时会出现下降峰。比如21，32这些。但是这些不合法。  
所以要把步数为2时的置0就可以了。  
转移方程：

一.更新上升峰（1：上升峰再加一个上升，2：下降峰加一个上升）  
dp\[n\]\[t\]\[i\]\[1\]\+=(dp\[n−1\]\[t\]\[j\]\[1\]\+dp\[n−1\]\[t−1\]\[j\]\[0\]);

二.更新下降峰（1:下降峰再加一个下降，2：上升峰加一个上升）  
dp\[n\]\[t\]\[i\]\[0\]\+=(dp\[n−1\]\[t\]\[j\]\[0\]\+dp\[n−1\]\[t\]\[j\]\[1\]);

复杂度：O(n3).

[https_loj.ac_problem_6094]: https://loj.ac/problem/6094
[http_codeforces.com_contest_814_problem_E]: http://codeforces.com/contest/814/problem/E
[http_blog.csdn.net_sdfzyhx_article_details_73003862]: http://blog.csdn.net/sdfzyhx/article/details/73003862
[http_codeforces.com_blog_entry_52449]: http://codeforces.com/blog/entry/52449
[https_loj.ac_problem_6160]: https://loj.ac/problem/6160
[http_blog.csdn.net_u014609452_article_details_73744264]: http://blog.csdn.net/u014609452/article/details/73744264
[https_loj.ac_problem_6161]: https://loj.ac/problem/6161
[https_loj.ac_problem_6176]: https://loj.ac/problem/6176
[https_loj.ac_problem_6165]: https://loj.ac/problem/6165
[https_loj.ac_problem_6177]: https://loj.ac/problem/6177
[http_acdream.info_problem_pid_1113]: http://acdream.info/problem?pid=1113
[http_acdream.info_problem_pid_1124]: http://acdream.info/problem?pid=1124
[http_acm.hdu.edu.cn_showproblem.php_pid_2993]: http://acm.hdu.edu.cn/showproblem.php?pid=2993
[http_acm.hdu.edu.cn_showproblem.php_pid_1500]: http://acm.hdu.edu.cn/showproblem.php?pid=1500
[http_acm.hdu.edu.cn_showproblem.php_pid_1511]: http://acm.hdu.edu.cn/showproblem.php?pid=1511
[http_codeforces.com_contest_21_problem_D]: http://codeforces.com/contest/21/problem/D
[http_codeforces.com_contest_14_problem_D]: http://codeforces.com/contest/14/problem/D
[http_codeforces.com_contest_14_problem_E]: http://codeforces.com/contest/14/problem/E