【算法竞赛】AtCoder - ABC - VP

简要记录补的abc的思路，正式参加的就不记了。 不排除我咕咕的情况。 题号靠前，没有记录，基本就是模拟。 代码实现都在账号 Livinfly 中，可在AtCoder所有提交中查看。

abc042

• b，sort。
• c，从小到大枚举 i >= n，判断有没有不喜欢的数字。
  • 贪心的去选应该不太成立，后面可能比所有可用的都大。
• d，前n-a+b-1有i步向下走，剩余的步数，有n-1-i步向下走。ans = \sum_{0}^{n-a-1}C(n-a+b-1, i)*C(n+m-2-(n-a+b-1), n-1-i)求阶乘记得加LL。

abc043

• a，模拟/等差数列的和。
• b，模拟。
• c，枚举最后变成的值，取花费最小的。
• d，枚举unbalanced的字母，然后枚举找到长度为3的区间内有两个以上这个字母的地方，特判下n = 2的情况。
  • 因为长度为3的区间不多于两个，那前面的就对后面更长的没有贡献，也就不会对unbalanced有改变。

abc292

• c，统计a*b == x (1 <= x <= n)的方案数，答案就是cnt[i]*cnt[n-i]。
• d，并查集，记录一个集合的点数和边数。
• e，直接dfs搜索，扩展每个点最多能扩展出来的边，然后减去原有的边数。
• f，二分log，数学结论O(1)。
  • 二分，正三角形的边长，通过角度的转变，可以找出三角形的横向宽度。
  • Luogu第一篇题解有说明。
• g，区间DP。定义f[l, r, k, c]为，第 l 个到第 r 个字符串的从左到右的第k位大于等于c的方案数，最终答案为，f[0, n-1, 0, 0]。状态设计的来源为字典序大小的比较的递归定义，s1 < s2，要么当前位的大小关系，相等就是去掉当前位的大小关系。可以得到转移方程

同时，有几个边界条件：

1. l > r，在右半部分会出现，这时，方案数等于左半边，所以返回 1 ；
2. k == m，位数结束了，因为是严格递增，所以只有当区间大小为 1 时，才合法，返回 1， 否则返回 0 ；
3. c == 10，位数超出，显然不合法。

abc293

• d，并查集，不在同一集合里ans2 --， 在同一集合里ans1 ++
• e，分治/矩阵快速幂。分治：类似于(1+a^n/2)(1+a+...+a^n/2)的形式。
  • 用公式法的话因为不一定有逆元，会错。
• f，有两种思考方式：
  1. 枚举base，check01
  2. 枚举01，check 枚举base大小 前一种是O(n)的，后一种如果位数少，配合二分，复杂度较低。 所以就诞生了，前1000采用第一种，后面采用第二种的缝合。。
• g，普通莫队板子题，每次加进来和移出去的代价。

abc294

• d，set模拟。
• e，两行可以哪行短了放哪行，然后就可以保证多出来部分的只有一种颜色，累加多出来的部分和新加的长度取min
• f，二分浓度，通过判断浓度大于等于mid来缩小区间，这里进行等价移项，0/1分数规划。
• g，一棵树上的两点距离dist

+dist

-dist

*2可以求出，时间复杂度符合；维护dist，因为修改边权对dist的影响只有深度深的点的子树，所以可以考虑树状数组维护连续dfn序，来维护一个子树的dist的修改。

abc295

• d，状态压缩。类似前缀和，记录整体的状态，然后能和以当前位为结尾的就是前面的相同的状态。
  • 由于没想到状态压缩，转移认为时间不够，然后就寄了。

• f，枚举/数位DP，可以直接枚举在哪个位置，然后把前面和后面的稍做处理就可以得出答案。用string的库函数stoll会很方便。
• g，一开始因为都是连向比自己序号大的点，答案都是自己；因为连接u和v保证v能到u，那么u和v在连边后一定在同一个强连通分量，那么最小的点也就是v了，用并查集维护即可。

abc296

• c，sort，二分找存不存在。
• d，a，b（a \le b）两个因子，容易知道a在1e6的范围内，所以枚举a，找满足条件最小的b，其实就是b= \lceil{m/a}\rceil，枚举过程中判下a与b的大小关系和b \le n，最后判无解。对这种暴力枚举复杂度还是估不好。
• e，实际上是每个点出度都为1的内向基环树森林，跑拓扑排序，把不在环外的点去掉，然后留下的入度之和就是环的总长度。
  • 想到找环了，但不清晰。
• f，分类讨论：1. 含有的元素不同，No；2. 同个集合内有相同的元素，可以利用相同元素，别的自由交换； 3. 保持A不动的话，两次交换逆序对的奇偶性不变。
• g，计算几何板子题，凸多边形和点的关系，二分logn做法。

abc298

• b，模拟，注意是a=1的地方b为1。
• c，模拟，虽然感觉时间复杂度挺怪的。（？）
• d，类字符串哈希。
• e，概率dp或者记忆化搜索，注意不是等概率的事件，不能win/tot来求概率，多选择的，所以每一次都需要求概率。
• f，看得出是比较典的题，但是确实就不会做，想到假O(n^2)，但是不太能想。容易看出，离散化后是不大于n*n的区域，然后从大到小枚举行，从大到小枚举列，到遇到相交的点为空值时退出，显然这样包含最优解，后面需要想时间复杂度。不难发现要访问的点数最多是总点数+n，实际是O(n)的复杂度。
• g，算是特殊的区间dp，不可能分割可以优化直接返回。（浮点数有点问题，把浮点数当作INF，还是早转类型好一点。）
  • NOI1999 棋盘分割