1. 2024 ICPC Kunming Invitational Contest
\(\text{J. The Quest for El Dorado}\)
还是普通 dij，但是重写 dis 的形式为 \((r,w)\)，其中 \(r\) 表示最早第几张票到这个点，\(w\) 表示此时这张票已经用掉的里程的最小值。dis 之间的比较就是先比 \(r\) 再比 \(w\)。
在转移一条边 \((u,v,c,w)\) 的时候，如果能够直接从 \(dis_u\) 的同一张票走且里程不爆，那就直接走，否则去找最近的能满足 \((c,w)\) 的票。
题解说每个颜色预处理 rmq，但是实现有点烦。我直接动态开点权值主席树，每个颜色从后面最近的同颜色根转移过来，树上点权表示落在这个值域内的票最小的编号。
然后就是先找到 \(dis[u].r\) 后面最近的颜色 \(c\) 在哪（set + 二分），然后上主席树查，复杂度 \(O(\log m)\)。
然后就是每条边最多扩展一次，复杂度就对了。
爆点：没想到重新定义边权；\(n\) 和 \(k\) 傻傻分不清导致调了 3h。
\(\text{L. Trails}\)
妙。
没有特殊边就是 \(\sum_{i=0}^p \sum_{j=0}^q i+j\)，傻子都会做。
容易发现走一条斜边会使路径长度减一，因此对于单个点，应该尽量多走特殊边。而特殊边数量最大值是这个点左下角所有 \((x_i+1,y_i+1)\) 的 LIS。
做 LIS 有一个贪心做法，是遍历序列，维护一个钦定当前点在 LIS 中的序列，每次能往后加就加，不能加就二分出第一个能加的位置并加进去。
容易发现其实我们维护的是在此之前长度为 \(i\) 的 LIS，最后一个数的最小值。
对于原题，我们一列一列处理，按照 \(y\) 值从大到小做 LIS 并维护上述序列 \(f_1,f_2,...f_m\)。
处理完 \(x=x_0\) 这列以后，由 \(f_i\) 的意义，我们发现 \((x_0,0), (x_0,1), ...(x_0,f_1-1)\) 这些点都只能经过 0 条特殊边，\((x_0,f_1), (x_0,f_1+1), ...(x_0,f_2-1)\) 这些点能经过 1 条特殊边。以此类推。\((x_0,f_m), (x_0,f_m+1), ...(x_0,q)\) 这些点能经过 \(m\) 条特殊边。
那么这一列对答案的影响就是减去
\[m*(q-f_m+1)+\sum_{i=1}^{m-1}(f_{i+1}-f_i)\times i \]\[=m*(q+1)-\sum_{i=1}^{m}f_i \]所以我们只需要维护 序列长度 和 序列和即可。对于空的列可以并到最近的前面一列处理。
爆点：对 LIS 该做法的理解不够深。
\(\text{H. Subarray}\)
我草我竟然会这题。
考虑分治，每次处理跨过 \(mid\) 的区间。从 \(mid\) 开始，往两边分别预处理目前为止的最大值与该最大值出现了几次。
然后枚举区间内最大值，你能获得左半边的选择中最大值是这个数且出现 \(x\) 次的有几个左端点，右边同理（0 个可能需要特殊处理）。然后这两个序列卷起来即可。
显然这些序列的总长是 \(O(\text{区间长度})\) 的。
复杂度 \(O(n\log^2n)\)。
但是题解少一只分治的 \(\log\)。做法如下：
设最大值是 \(v\)，单调栈出极长的最大值是 \(v\) 的区间，区间内部是 \(\{ t_0 个其它数，v，t_1 个其它数，v，t_2 个其它数，...，t_p 个其它数 \}\)，对某个 \(k\)，答案就是
\(t_0t_k + t_1t_{k+1}\dots + t_{p−k}t_p\)。
显然这玩意也可以卷。而且对同一个 \(v\)，序列长度就是 \(v\) 出现次数。所以总复杂度是对的。\(O(n\log n)\)。
没写，我认为分治更加优美。
爆点：没取模！爆！没取模！爆！没取模！爆！没取模！爆！没取模！爆！
\(\text{K. Permutation}\)
我草我竟然差点会这题。
考虑分治。在已知这个区间 \([l,r]\) 中出现的元素的集合的时候，考虑如何确定左右两边的集合。
设 \(mid=\lfloor\dfrac{l+r}{2}\rfloor\)。
我们随便掏出两个还未确定的数 \(x,y\)，让询问序列 \(a\) 为 \(a_1,a_2,\dots,a_{mid}=x,a_{mid+1},a_{mid+2},\dots,a_{n}=y\)。这时候有三种返回值：
- 返回 0 或 2，此时都能确定哪个在哪边，未知量减少两个
- 返回 1，此时我们知道这俩一定在同一边，未知量减少 1 个。
这样期望询问次数是 \(\dfrac{2}{3}n\log n\)，差不多是 6000，看起来很能过，但是可能被卡，怎么办呢？
于是我们随机掏出 \(x,y\) 即可。这等价于原排列随机，这样就根本卡不掉了！
具体的实现还没写，感觉在每个区间处理的时候，可以使用并查集。万一最后真的只能确定集合不能确定哪边是哪边，那就多问一次吧。
爆点：没想到返回 1 的时候的意义
代码一遍过，我是天才。
2. The 3rd Universal Cup. Stage 7: Warsaw
\(\text{F. Fibonacci Fusion}\)
唐
考虑 \(a_i\le a_j\)，那么 \(a_j<a_i+a_j \le 2a_j\)。这个区间里最多只有两个斐波那契数。
于是我们把 \(a\) 排序，然后从前往后做。遇到一个 \(a_j\) 后，估算它附近的 \(fib\) 是第几项 ：
\(fib_n \sim \dfrac{\phi^n}{\sqrt5} \to n\sim\log_{\phi}(\sqrt 5a_j)=\log_{\phi}\sqrt 5+\dfrac{\log_{10}(a_j)}{\log_{10}\phi}\)
对于 \(\log_{10}{a_j}\)，我们可以通过前若干位（比如取前 20 位）算 \(\log\) 加上剩下的位数，这样的误差十分小。
（顺便排序也可以基于这个第几项来排）
然后就能找到一个 \(a_j\) 的那两个 \(fib\) 是啥。接下来检查 \(fib-a_j\) 在前面的数组里有几个就行了。这一步可以 hash + map。
K. Routing K-Codes
我草我差点完全自己做出来。（要不是看 F 题解的时候瞟到了换根）
如果合法，一定可以把这个图塞到一个二叉树上，该二叉树以 0 位根，0 有唯一右儿子 1，从 1 开始往下每个点连 \(2x\) 与 \(2x+1\)。
所以原图一定得是每个点度都不大于 3 的树。
现在我们需要确定一个根（显然这个根的度 \(\le 2\)），然后从底往上计算答案。可以发现任意一棵子树的权值和都可以写作 \(ax+b\) 的形式，其中 \(x\) 是这棵子树的根的权值。
合并两棵子树 \(ax+b, cx+d\) 时，会有哪棵子树放左边的问题。 \(ax+b\) 放左边就是 \(a(2x)+b+c(2x+1)+d+x=(2a+2c+1)x+b+d+c\)，右边就是 \(a(2x+1)+b+c(2x)+d+x=(2a+2c+1)x+b+d+a\)。
所以对 \(a,c\) 取 \(\min\) 即可得到合并完的新权值 \((2a+2c+1)x+b+d+\min\{a,c\}\)。
当然度为 1 的点做根时要特判一下，毕竟 0 只有右子树。
好的，现在你已经会求一个根的权值了，接下来只需要写个换根就可以了！
虽然我更愿意把他理解为枚举根，把往父节点去的那部分当作参数传下来然后算。
然后就做完了。一个细节是要注意某个点作为根时树的深度问题，是不能超过 32 的（如果根度为 1 那么可以放在 0，因此此时深度不超过 33）。这可能需要写一个树上每个点为根时的最大深度，当然这可以轻松换根。
爆点：每个点为根时的最大深度写错了。并不轻松。。。
E. Express Eviction
这个喷不了，这是我真的菜。
考虑不合法的时候是什么样的：是存在一条从左下边缘到右上边缘的一条仅经过有房子的格子的路径，其中房子之间是 24-联通（即横纵坐标均差均不超过 2）。
然后就是把每个房子拆成一个入点 \(a_u\) 一个出点 \(b_u\) 连 \((a_u,b_u,1)\)，和左下边界相邻的连 \((S,a_u,\inf)\)，和右上边界相邻的连 \((b_u,T,\inf)\)，24 联通的格子之间连 \((b_u,a_v,\inf)\)，然后最小割就是答案。
显然只会割到流量为 1 的边，割这些边的意义就是把这个房子拆了。
注意左上角和右下角有房子时是必拆的，因此特判一下就好了。
奇了怪了，这题明明不难啊？
A. Bus Analysis
难。dp of dp 是一点不会的。
首先花费除以 2。这样价格就是 1 或者 3。
首先内层状态就不一般。\(dp_{i,x}\) 表示过完了站点 \(i\)，一共花了 \(x\) 块钱时手里的票最多还能撑多久。
一个观察是，如果到 \(i\) 时的最小花费是 \(w\)，那么只有 \(dp_{i,w},dp_{i,w+1},dp_{i,w+2}\) 这几个值有用，因为 \(dp_{i,w+3}\) 显然不如用 \(w\) 的花费走到 \(i\) 然后在下一站买一张 3 块钱的票优。
（解释一下，因为我们其实只关心 \(w\) 的值，所以没用的状态的意思就是对 \(w\) 的更新没有影响）
发现 \(dp_{i,w},dp_{i,w+1},dp_{i,w+2}\) 只会有 \(75^3\) 种状态，所以塞到外层 \(f_{i,a,b,c}\) 表示前 \(i\) 个站，\(dp_{i,w}=a,dp_{i,w+1}=b,dp_{i,w+2}=c\) 的方案数。
然后在转移的时候算一下至少加多少钱才能过这一站，把这个增量乘上 \(f_{i,a,b,c}\) 并加起来即可。
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
// #define mp make_pair
#define pb push_back
#define f(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
ll rd(){
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
#define d rd()
ll n,t[6];
ll tim[1010];
ll dp[2][80][80][80];
ll pw[1010],res;
const ll mod=1000000007;
int main(){
n=d;pw[0]=1;
f(i,1,n)tim[i]=d,pw[i]=pw[i-1]*2%mod;
dp[0][0][0][0]=1;
f(i,1,n){res=(res*2)%mod;
memset(dp[i&1],0,sizeof(dp[i&1]));
f(A,0,75)f(B,0,75)f(C,0,75)if(dp[i&1^1][A][B][C]){
t[0]=max(0ll,A-(tim[i]-tim[i-1]));
t[1]=max(0ll,B-(tim[i]-tim[i-1]));
t[2]=max(0ll,C-(tim[i]-tim[i-1]));
dp[i&1][t[0]][t[1]][t[2]]=(dp[i&1][t[0]][t[1]][t[2]]+dp[i&1^1][A][B][C])%mod;
t[3]=t[4]=t[5]=0;
f(j,1,5){
t[j]=max(t[j],t[j-1]+20);
if(j>=3)t[j]=max(t[j],t[j-3]+75);
}ll nw=0;while(t[nw]==0)nw++;
ll x=t[nw],y=t[nw+1],z=t[nw+2];
if(nw)res=(res+nw*dp[i&1^1][A][B][C])%mod;
dp[i&1][x][y][z]=(dp[i&1][x][y][z]+dp[i&1^1][A][B][C])%mod;
}
}cout<<res*2%mod;
return 0;
}
3. The 3rd Universal Cup. Stage 14: Harbin
L. A Game On Tree
我竟然会这题。
先把期望换成统计所有方案权值和。
考虑对于每条链，计算路径交是这条链的方案数。这看起来很点分，但是你会发现逃不掉卷积，还有两只 \(\log\)， 看起来就不是很行。
现在假设我们在考虑路径 \(P\)。
考虑把 \(X^2\) 写作 \((\sum_{(u,v)\in E}[(u,v)\in P])^2=\sum_{(u_1,v_1)\in E}\sum_{(u_2,v_2)\in E}[(u_1,v_1)\in P][(u_2,v_2)\in P]\)，因此答案可以记作：
\[\sum_{(u_1,v_1)\in E}\sum_{(u_2,v_2)\in E}\sum_{P}[(u_1,v_1)\in P,(u_2,v_2)\in P] \text{P的方案数} \]这个东西可以枚举这两条边的 \(\text{lca}\)，然后再子树内预处理一车类似 size 和 \(\sum size^2\) 并直接计算。复杂度 \(O(n)\)。
标签：log,记录,text,sum,ACM,序列,dp,nw From： https://www.cnblogs.com/jimmywang/p/18530494