某些看了但不想写代码的题

其它

图片挂了看这里。

HDU.5977.Garden of Eden(点分治)

$Description$
给定一棵$n$个点的树，每个点有一个颜色，颜色一共有$k$种。求有多少条路径包含$k$种颜色。
$n\leq 10^5,\quad k\leq 10$。

$Solution$
点分治。状压颜色。记$cnt[s]$表示状态为$s$的路径个数。
如果当前点状态为$s$，那么就可以从$s$的补集以及$s$的补集的超集更新Ans。
但是这样复杂度当然爆炸。所以直接令$cnt[s]$表示状态为$s$及$s$的超集的路径数。
每次合并一棵子树的状态时，枚举子树的状态$s_i$，然后对于$s_i$的所有子集$s'$，$cnt[s']$++。
代码见：https://www.cnblogs.com/WABoss/p/6036216.html。
还有用FWT做的社会人：https://www.cnblogs.com/Menhera/p/9514412.html， http://www.cnblogs.com/sclbgw7/p/9508235.html。

hihoCoder.1496.寻找最大值(高维前缀和)

$Description$
给定$n$个数$a_i$，你需要找到两个数$a_i,a_j$，使得$a_i*a_j*(a_i\&a_j)$最大。输出这个最大值。
$n\leq 10^5,\quad 0\leq a_i<2^{20}$。

$Solution$
考虑枚举$t=a_i\&a_j$。那我们要对每个$t$求，满足$a_i\&a_j=t$的$a_i,a_j$中，乘积最大的一对。
但是还是不好求啊。这个条件其实可以削弱，即我们对每个$t$，求$t$为$a_i\&a_j$的子集，乘积最大的一对$a_i,a_j$。显然不会丢失最优解。
$t$为$a_i\&a_j$的子集，即$t$同时为$a_i,a_j$的子集。那么枚举$t$的超集，求最大的两个数做$a_i,a_j$就可以了。
可以用高维前缀和求，也可以对每个$a_i$直接枚举子集。是复杂度有差别吧？前者是$O(2^kk)$，后者是$O(n\log a_i)$。

北京八十中集训 12.20 例一.Triple(思路 计数)

$Description$

$Solution$
需要$O(n^2)$解决。可以令$Two[v]$表示$a_j+a_k=v,\ i-D<j\leq k<i$的二元组$(j,k)$的个数，$One[v]$表示$a_j=v,\ i-D<j<i$的$j$的个数，那么$Ans_i=\sum_jOne[a_i-a_j]+Two[a_i-2a_j]+[3a_j=a_i]$？
显然会有重复。每个$One$会被计算三次，所以给后两项带一个权值，让每个$Triple$恰好被计算三次，就可以直接去重了。

北京八十中集训 12.20 例二.Manhattan(CDQ分治)

$Description$

$Solution$

Codeforces.150E.Freezing with Style(点分治 二分答案 单调队列)

$Description$

$Solution$
二分答案$mid$，然后点分治（当然点分治过程中二分答案更好些）。
对于以每个点为根的子树，求是否存在边数$len$在$[L,R]$之间且至少存在$\frac{len}{2}$条边权$\geq mid$的路径。
把边权$\geq mid$的边的权值设为$1$，$<mid$的设为$-1$，对于每种边数只需维护权值最大的路径即可。显然可以单调队列维护。但注意要先将子树按最大深度从小到大排序以保证复杂度。
复杂度$O(n\log^2n)$。

HDU.5381.The sum of gcd(线段树/莫队 RMQ)

$Description$
给定长为$n$的序列$a_i$。$q$次询问，每次给定$l,r$，求$\sum_{i=l}^r\sum_{j=i}^r\gcd(a_i,a_{i+1},...,a_j)$。
$n,q\leq10^4,\ a_i\leq10^9$。

$Solution$
莫队+RMQ：
把要求和的区间画出来。每次移动区间左右端点的时候，观察改变的会有什么。
假如原先区间是$[4,6]$，现在左端点移动到$3$，当前答案会加上 $3,3\;\;3,4\;\;3,5\;\;3,6$的$\gcd$。也就是固定$l$，往右求$\gcd$一直到$r$。
因为固定一个左端点$l$，$a[l...n]$这个后缀中的$\gcd$只有$\log$种，所以可以枚举$g=\gcd$，假设$g$出现在区间$[l,\ r']$，然后跳到$r'$那里去，再从$r'$跳到下一个$\gcd$的位置，直到到达$r$为止。
这个过程中可以累加答案，复杂度是$\log$的
从每个位置开始的第几个$\gcd$出现在哪，还要RMQ+二分预处理一下。总复杂度$O(n\log^2n+n\sqrt{n}\log n)$。
当然能想起Magic GCD这道题，预处理可以用单调栈，虽然复杂度还是$n\log^2n$的但显然常数小许多。
线段树：
同样把要求和的区间画出来，就很明显了。
比如设当前区间为$[3,6]$（左端点为$3$右端点为$6$），要求的区间有：
$3,3\;\;3,4\;\;3,5\;\;3,6\\\;\;\;\;\;\;\;4,4\;\;4,5\;\;4,6\\\;\;\;\;\;\;\;\;\;\;\;\ \ \ \,5,5\;\;5,6\\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\ \ \ \ \ 6,6\\$
以列为下标（上面分别是$3,4,5,6$），当询问左端点$l=3$，右端点为$r$时，答案就是区间$[3,r]$的和。
而每次向左移动$l$，会在上面增加一行。而以$a[l...n]$中$\gcd$只有$\log$种，可以暴力算出这$\log$种$\gcd$以及它们对应出现的区间（还是同Magic GCD这道题），然后就可以直接区间加。
所以就是，把询问离线，按左端点从右往左处理。
复杂度$O(n\log^2n)$。

Codeforces.17E.Palisection(Manacher/回文树)

$Description$
给定一个字符串$s$。求$s$有多少对回文子串，满足这两对回文子串在$s$中的位置有交集。
$|s|\leq2\times10^6$。

$Solution$
记回文子串总数为$sum$，那$Ans=C_{sum}^2-\text{没有交集的回文子串对数}$。
而没有交集的回文子串对数，就是$\sum_{i=1}^{n-1}\text{以i结尾的回文串数}*\text{i后边的回文串数}$。
以$i$结尾的回文串数$cnt_i$可以直接回文树，或是Manacher+差分求。$i$后边的回文串数就是$\sum_{j=i+1}^ncnt'_j$。把串反过来求一遍$cnt_i$的后缀和就可以了。
因为$|s|$是$2e6$，回文树要用边表存转移。

牛客练习赛38 E.出题人的数组(贪心)

$Description$
给定两个长为$n,m$的序列$A_i,B_i$。你需要把两个序列拼成长$n+m$的序列$C_i$，要求原本同在$A_i$或$B_i$序列中的数在$C_i$中的相对顺序不变。求最小的$\sum\limits_{i=1}^{n+m}i*C_i$。
$n,m\leq10^5$。

$Solution$
先把整个$A$序列放在$B$前面。然后我们每次要找$B$的一个前缀扔到$A$里面去，且位置不能超过上一次放的那个前缀的位置。
假设选的$B$的前缀长度为$x$，和为$s_1$，放的位置离$A$的末尾距离为$y$，这一段和为$s_2$。
那么当$y*s_1>x*s_2$时，这么做会优。移一下项就是$B$这段前缀的平均值更大。
而选的这段$B$的前缀应该是平均值尽量大的。
同时$C$序列最后是一段$A$+一段$B$+一段$A$+一段$B$...要让这些段的平均值递减。
所以我们就先把$A,B$分成一些平均值递减的段，最后按平均值大小归并就可以了。。

牛客OI周赛7 提高组.C.小睿睿的方案(线段树)

$Description$
给定一棵树及$m$条路径。求有多少条路径满足不完全包含这$m$条路径中的任意一条。
$n,m\leq10^5$。

$Solution$
考虑求不合法的路径数。发现这些路径都是一个点在一段DFS序连续的区间中，另一个点在另一段DFS序连续的区间中。扫描线+矩阵求交即可。
复杂度$O(n\log n)$。

CF.464E.The Classic Problem(可持久化线段树 Hash)

$Description$
给定一张$n$个点$m$条边的无向图，边权都是形如$2^{x_i}$的形式（$0\leq x_i\leq 10^5$）。给定$s,t$，求$s$到$t$的最短路。
$n,m\leq10^5$。

$Solution$
考虑如何改进$Dijkstra$使得能做这道题。我们把$dis$数组用线段树存成$2^{a_1}+2^{a_2}...$的形式。
判断$dis$时，可以像字符串$Hash$一样，从高到低位在线段树上二分，找到第一个不同的位置，判断上面的大小关系。$Hash$可以直接用题目给的$seed=2,\ mod=10^9+7$，当然最好还是自己再写个。
每次枚举一条边修改$dis$时，一个暴力的想法是，每次只改一位，就可持久化一下，在对应位置$+1$，如果产生进位就暴力再在下一个位置$+1$。
这样复杂度是不对的，可以卡成$O(nm\log w)$（然而网上都是这种办法...出题人竟然数据造水了，ssfd）。
官方题解的做法是，初始建两棵全$0$和全$1$的线段树，进位时可以直接替换节点，这样复杂度就是真的$O((n+m)\log w)$了。
事实上那种错误的做法有人在Tutorial的comments里提到过，他也意识到是错的了。

CF.1104D.Game with modulo(交互 二分)

$Description$
要求在$60$次询问内猜出一个数$a\ (1\leq a\leq10^9)$。每次你可以询问$(x,y)\ (0\leq x,y\leq10^9)$，交互库会返回以下两个字符之一：
1. x，如果$(x\bmod a)\geq(y\bmod a)$。
2. y，如果$(x\bmod a)<(y\bmod a)$

$Solution$
考虑询问$(x,2x)$（$x\bmod a$和$2x\bmod a$），如果$2x<a$，显然结果是y；$x>a$，不好考虑；$x=a$，结果是x；$x<a\leq2x$，结果是x。（为什么此时一定有$x\bmod a<2x\bmod a$呢...令$2x=a+b=x+x$，因为$x<a$，所以$x>b$。。）。
综上，如果我们依次询问$(0,1),(1,2),...,(2^{29},2^{30})$，我们可以找到一个$(2^k,2^{k+1})$，满足$2^k<a\leq2^{k+1}$。这需要$30$次二分（最后一次不需要）。记这两个边界为$l,r$，即$l<a\leq r$。
考虑在$[l+1,r]$中二分答案$x$。如果$x<a$，显然有$l\bmod a<x\bmod a$；如果$x\geq a$，同样考虑拿$l$询问，有$l\bmod a>x\bmod a$（还是令$x=a+b$，如果$b\geq l$，那么$x>r$显然不对）。
这样需要二分$29$次，那么就OK啦。
为啥都写的那么简洁啊...还是我太菜...

CF.1039D.You Are Given a Tree(根号分治)

$Description$
给定一棵$n$个点的树。求最多可以选出多少条不相交的路径，满足这些路径含有$k$个点。对$k\in[1,n]$输出答案。
$n\leq10^5$。

$Solution$
暴力是$O(n^2)$的，即对于每个$k$，$O(n)\ DFS$一遍，能合并出一条$k$个点的路径就合并，否则向上。这样贪心显然是对的（$NOIP$...）。
注意到答案是随$k$增加递减的，且$k>\sqrt n$时，答案的取值只有$[0,\sqrt n-1]$这$\sqrt n$种，我们可以二分每个值是$k$的哪个区间的答案。
需要做$\sqrt n$次，每次复杂度$O(n\log n)$，总复杂度是$O(n\sqrt n\log n)$的。
$k\leq\sqrt n$时，可以对每个$k$暴力，复杂度$O(n\sqrt n)$。
发现两部分的复杂度并不均衡，$k\leq T$时复杂度是$O(Tn)$，另一部分是$O(\frac{n^2\log n}{T})$，所以取$T=\sqrt{n\log n}$时最优。

官方题解里有$O(n\log^2n)$的做法...（据作者本人说）很不好写...

SRM577 Board Painting(最小割)

具体看这里叭，先不细整理惹（不仅懒得写代码，思路也懒得写惹）。https://www.cnblogs.com/jefflyy/p/9679504.html
初始ans=总点数，每有一对点相邻，就可以减少1的花费，这样先算出一个答案。
然后把不合法的去掉。网络流每跑出1的流量，就表示有一对相邻的数不合法。这就是求割。要最小化去掉相邻点对的数量，使得方案合法。

SRM558 Surrounding Game(最小割)

神啊qwq。https://www.cnblogs.com/Blog-of-Eden/p/7783406.html

SRM590 Fox And City(最小割)

类似切糕的拆点qwq。https://www.cnblogs.com/zbtrs/p/8608842.html

PE512 Sums of totients of powers(欧拉函数 杜教筛)

https://www.cnblogs.com/JYYHH/p/8512709.html
$\varphi(n^2)=n^2\prod(1-\frac{1}{p_i})=n*n\prod(1-\frac{1}{p_i})=n*\varphi(n)\to \varphi(n^i)=n^{i-1}\varphi(n)$。
然后还有$n^2\%(n+1)\equiv0$。然后就能推出：$f(n)=n是奇数?\varphi(n):0$。

BZOJ.1727.[Usaco2006Open]The Milk Queue挤奶队列(贪心)

$Solution$
感觉这题应该是十分经典的叭？
套路，考虑相邻两个数$i,j$（$i$在前，$j$在后），不交换与交换的花费是：$A_i+B_j+\max(A_j,B_i),\ A_j+B_i+\max(A_i,B_j)$。
（其实还可以化简下，两个都减去两个$\max$，即$\min(A_i,B_j),\ \min(A_i,B_j)$）
所以sort的时候这么判下就可以惹。
似乎正确的做法应该是，先写出递推式，然后发现交换$i,i+1$没有影响？看这里叭。

BZOJ.4216.Pig(分块)

$Description$
给定长为$n$的序列$A_i$，多次强制在线询问区间和。
$n,Q\leq5\times10^5,\ |A_i|\leq8\times10^6$，内存限制$3MB$。
$Solution$
考虑$20$个数分一块，块之间求个前缀和，内存就够用了。

某道面试题(思路)

可以出成交互。
$Description$
有一个$n\times n$的矩阵，保证里面的数满足：同一行从左到右递增、同一列从上到下递增。给定一个数$k$，你需要在$O(n)$次询问内确定$k$是否在矩阵中出现过。
$Solution$
从右上角开始走。如果当前数$\lt k$，就往左走；如果$\gt k$，就往下走。

CF.379F.New Year Tree(思路)

$Description$
初始时有一个点。$q$次操作，每次操作给某个点加两个儿子，输出此时的直径。保证每次操作后是一棵树。
$q\leq5\times10^5$。
$Solution$
设之前的直径是$u\to v$。新加入两个点$n+1,n+2$，此时直径只可能是$u\to v,u\to n+1,v\to n+1$这三种。维护LCA求一下距离即可。

牛客编程巅峰赛S2第12场. C. 共鸣问题(思路)

$Description$
有$n$个数，$m$个限制$(x,y,z)$。每个限制为：若同时选$x,y$则获得$z$价值；只选$x,y$中一个不在当前限制中获得价值；$x,y$都不选则获得$-z$价值。求最大价值。
$n,m\leq10^6$。
$Solution$
不难，但挺好玩。
令初始答案$ans=-\sum z_i$，给每个限制的$x_i,y_i$加上$z_i$的权值，for一遍所有数取正权值就行了。

$Description$

$Solution$

$Description$

$Solution$

$Description$

$Solution$

$Description$

$Solution$