目录
2024.2.19
T1
题目大意
有一个排列 \(A\) ，定义其贡献为最长的连续整数段的长度，问全部的排列的贡献和
solution
设 \(f_{i,j}\) 表示长度为 \(i\) 的排列，贡献为 \(j\) 的方案数，\(g_{n,i,k}\) 表示长度为 \(n\) 的排列，分成了 \(i\) 个连续整数段，最长的整数段小于等于 \(k\)
那么有转移：
\[f_{n,k}=\sum_{i=1}^i(g_{n,i,k}-g_{n,i,k-1})f_{i,1}\\ f_{i,1}=d_i+d_{i-1}\\ g_{n,i,k}=\sum_{j=0}^{n/k}(-1)^j\binom ij\binom{n-jk-1}{i-1} \]第一条显然，\(i\) 组相互之间不能连续，那么系数就是 \(f_{i,1}\)
第二个可以有组合意义推出，或者 \(O(n^2)\) 递推
第三个直接简单容斥，钦定有几个为k
然后答案就是：
\[ans=\sum_{i=1}^nf_{n,i}\times i \]g的计数是调和级数，总时间复杂度为 \(O(n^2\ln n)\)
T2
原题gmoj6457
题目大意
给定一个序列，每次可以翻转一个前缀，给定一些前缀不能翻转，问最后形成的字典序最小的序列
solution
可以发现，我们先翻转一个小前缀，再翻转一个大前缀，若前面的操作不优，我们可以撤回，于是就考虑是直接维护当前的最小字典序。
对于一段不能翻的前缀，我们考虑直接加一段，并维护前后两个hash数组，用一些技巧实现拼接，然后用二分+hash判字典序即可
2024.2.20
T1
T2
2023.2.22
T1
题目大意
有一个 \(01\) 序列（形成一个环），每次随机选中一个位置，然后把它或它后面离他最近的 \(0\) 变成 \(1\)，贡献为移动的步数，问最后的期望步数
solution
首先断环成链，考虑区间DP，设 \(f_{i,j}\) 为把 \([i,j]\) 都变为 \(1\) 的期望，\(g_{i,j}\) 表示概率
初值，若区间本来就是全是 \(1\)，\(f=0,g=1\)，还有 \(f_{i,i-1}=0,g_{i,i-1}=1\) （这样就不用判边界）
转移：
\[mul=\binom{s_{i,j}-1}{s_{i,k-1}}(k-i+1)/n\\ g_{i,j}=\sum_{k=i}^jg_{i,k-1}g_{k+1,j}mul\\ f_{i,j}=\sum_{k=i}^jmul(f_{i,k-1}g_{k+1,j}+g_{i,k-1}f_{k+1,j})+g_{i,k-1}g_{k+1,j}\binom{s_{i,j}-1}{s_{i,k-1}}(1+...+(k-i+1))/n \]有一个小trick，如同统计答案和，方案数的dp，我们常把它相乘进行转移，计算期望和概率也是这个原理
2023.2.23
T1
题目大意
给定 \(k\) 棵有 \(n\) 个点的树。对于每个点对 \(i,j\)，求出其在每棵树上的路径经过的点（含端点）的并集大小。
solution
考虑一个 \(z\) 不在 \(x\to y\) 的路径上，那么以 \(s\) 为根的树，\(x,y\) 一定在同一颗子树，于是考虑hash（可以直接随机数分配权值），然后枚举 \(x\to y\)，判断 \(z\) 在为根的树中 \(x,y\) 是否一直在同一子树即可
T2
题目大意
有 \(n\) 个穿红衣服和 \(m\) 个穿紫衣服的人排成一列，给定 \(k\) 个五元组 \((a,b,c,d,p)\) 表示满足第c个紫衣服在第b个红衣服的左边且第a个红衣服在第d个紫衣服左边，就有p的贡献（p可能小于0），问如何排列能使贡献和最大
solution
首先可以先到朴素的 \(O(n^2)\) DP，设 \(f_{i,j}\) 表示已经安排了i个红，j个紫的最大值，然后每次放都可以算出贡献
我的优化是先取个补集，求出不满足的数量：第c个紫衣服在第b个红衣服的右边或第a个红衣服在第d个紫衣服右边，我们发现两个两个条件最多满足一个
然后转移相当于一条折线，折线下的(c,b)和折线上的(d,a) 点可以计算贡献，考虑容斥，先把(d,a)全部加上，然后把它的贡献设为负的，那么那么就是统计下方的和的最值
于是题目变成网格图有一些有点权的点，要求从 \((0,0)\) 到 \((n,m)\) 画一条折线，使得折线下的点的点权和最大
有两种设法，如图有两种状态，红色对应的是转移
我打的第二种，有前缀加，前缀max（感觉这个做法比较厉害，虽然要多两个懒标记，但好像没有什么限制）操作
记录一下code：
#include<bits/stdc++.h>
#define Fu(i,a,b) for(int i=a;i<=b;i++)
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
using namespace std;
int n,m,k,bj=1;
long long sum=0,s[1000005],f[2005];
struct s{
int a,b,c,d,p;
}x[1000005];
#define pil pair<int,long long>
map<int,long long>w[1000005];
struct tree{
struct node{
bool tag;
long long mx,lmx,lzy;
}t[1000005<<2];
void spread(int o){
if(t[o].lzy){
t[o*2].mx+=t[o].lzy,t[o*2].lzy+=t[o].lzy,t[o*2].lmx+=t[o].lzy;
t[o*2+1].mx+=t[o].lzy,t[o*2+1].lzy+=t[o].lzy,t[o*2+1].lmx+=t[o].lzy;
t[o].lzy=0;
}
if(t[o].lmx!=-1ll<<60){
t[o*2].mx=max(t[o*2].mx,t[o].lmx),t[o*2].lmx=max(t[o*2].lmx,t[o].lmx);
t[o*2+1].mx=max(t[o*2+1].mx,t[o].lmx),t[o*2+1].lmx=max(t[o*2+1].lmx,t[o].lmx);
t[o].lmx=-1ll<<60;
}
if(t[o].tag){
t[o*2+1].mx=max(t[o*2].mx,t[o*2+1].mx),t[o*2+1].lmx=max(t[o*2].mx,t[o*2+1].lmx);
t[o*2].tag=1,t[o*2+1].tag=1,t[o].tag=0;
}
}
void add(int o,int l,int r,int x,int y,long long z){
if(x<=l&&r<=y){
t[o].mx+=z,t[o].lzy+=z;
if(t[o].lmx!=-1ll<<60) t[o].lmx+=z;
return ;
}
spread(o);
int mid=l+r>>1;
if(x<=mid) add(o*2,l,mid,x,y,z);
if(mid<y) add(o*2+1,mid+1,r,x,y,z);
t[o].mx=max(t[o*2].mx,t[o*2+1].mx);
}
}T;
int main(){
fre(show);
scanf("%d%d%d",&n,&m,&k);
Fu(i,1,k) scanf("%d%d%d%d%d",&x[i].a,&x[i].b,&x[i].c,&x[i].d,&x[i].p);
Fu(i,1,k) w[x[i].c][x[i].b-1]+=x[i].p,w[x[i].d][x[i].a-1]-=x[i].p;
Fu(i,1,4*(n+1)) T.t[i].lmx=-1ll<<60;
Fu(i,1,m){
for(pil x:w[i]) T.add(1,0,n,0,x.first,x.second);
T.t[1].tag=1;
}
printf("%lld",T.t[1].mx);
return 0;
}
还有一种map做法，就是只记录关键点的值，然后大概要类似扫描线维护二维数据的方法转移
2024.2.26
T1
题目大意
给定正整数 \(n\)。对于由 \(1\) 到 \(n\) 的正整数构成的集合的所有子集，你需要把它染成红色或蓝色。
要满足限制：若 \(S1\) 和 \(S2\) 的颜色相同，则 \(S1\cup S2\) 的颜色也应与 \(S1\) 的颜色相同。
对于每个集合，把它染红和染蓝都有对应的代价。请求出总代价的最小值。
solution
考虑设 \(f_s\) 为计算完 \(s\) 的子集的答案
考虑转移，我们枚举一个 \(T\)，那么我们发现 \(T\cap s\) 的子集一定和 \(T\) 是同色，那么就是 \(f_{s\cup T}=f_{s-s\cap T}+cst_{s\cap T}\)，\(cst_s\) 表示 \(a\) 的 \(s\) 的子集的和与 \(b\) 的 \(s\) 的子集的和的较小值
考虑调整dp，使其变成sosdp形式
我们考虑枚举 \(s\cup T\)，从 \(s-s\cap T\) 转移过来，发现后者是前者的子集，于是考虑高位前缀和优化，时间复杂度 \(O(2^nn)\)
T2
题目大意
一共有 \(n\) 个点，若干条边。每条边都是形如 \(x\to y\) 的单向道路，其中 \(x<y\)。这些边满足不存在两条不同的边满足 \((x_i,y_i),(x_j,y_j)\)。现在你需要在这些边种选择两个不交的集合 \(A,B\)，\(A\) 构成了以 \(1\) 为根的外向生成树，\(B\) 构成了以 \(n\) 为根的内向生成树。求本质不同的方案数。
solution
边与边之间形成的是包含关系可以组成树，所以考虑树形DP
设 \(f_{i,0/1,0/1}\) 表示算到第 \(i\) 条边的子树，是否选择该边为 \(A\) 集合，\(B\) 集合，然后转移即可
T3
题目大意
有 \(n\) 个人，\(m\) 道题目，给出每道题目的对的人数范围 \([l_i,r_i]\) ，要求序号为 \(1\) 到 \(n\) 的每个人的A题数单调不下降，一共A了 \(S\) 道题，问每个人最多可以A几题
solution
先考虑 \(l_i=r_i\)，我们可以考虑贪心计算第 X 个人（从编号大到小，再编号 \(1\sim n\)），我们发现，如果 \(l_i\) 小于等于 \(X\) 那么可以通过循环使得都再前 \(X\) 个人，那么答案应该为 \(\lfloor\frac S X\rfloor\) ，但 \(l_i>X\)的时候，就有有浪费，要分给后面的人
对于全部情况，只用分讨 \(X,l_i,r_i\) 的关系，即可打出 \(O(n^2)\)
在数轴上扫描线即可 \(O(n)\) 处理
2024.2.27
T1
题目大意
有 \(n\) 个城市在一条数轴上，每个城市有个位置和广播半径 \(x_i,d_i\)，表示它可以把广播传到 \([x_i-d_i,x_i+d_i]\) 的城市，每次告知一个城市，它将一直传播直到没有新的城市收到广播为止
求最好情况下需要告知的城市数量，以及最坏情况下需要告知的城市数量
solution
考虑图论，我们将每个点向能广播到的点连边，那么我们发现，最好情况就是入度为 \(0\) 的点，最坏情况就是点数
于是考虑线段树优化建图
T3
题目大意
定义一个大小 \(x+1\) 的完全图是好的，当且仅当每个点连出的 \(x\) 条边颜色分别为 \(1\sim x\)
给出一个大小为 \(n\) 的完全图每条边的颜色 \(c(c\in{1,2 ...m})\)，问是否能在此基础构造出一个大小为 \(m+1\) 的好的完全图
solution
考虑充要条件，首先是每个点的边无相同颜色，其次是，设颜色 \(i\) 的边与 \(c_i(c_i\bmod2=0)\) ，\(n-c_i\le m+1-n\)。其实际意义为：还需要的点要小于等于剩下的点。该结论的必要性显然
于是考虑增量构造，一直满足第二条件合法，即可构造出方案
具体来说，每次构造一个点与前面的每个点的连边颜色。建立二分图，左边表示颜色，右边有 \(i\) 个点，\(i\) 没有颜色 \(c\) 的边，就连接一条流量为 \(1\) 的边。那么如果一条边有流量那就意味 \(i+1\) 向那个点链接了对应颜色的边
那么如何满足条件？我们考虑建立虚点，表示不用强制匹配的颜色，即 \(n-c_i> m+1-n\) ，颜色 \(i\) 向虚点连流量为 \(1\) 的边，虚点向汇点连流量为 \(m-i\) 的边
通过网络流建模，我们也可证明其结论的充分性
2024.2.28
补题2024.12.15T1
题目大意
求区间所有子区间的 子区间本质不同 \(mex\) 个数 的和
solution
先考虑处理里面一问子区间本质不同 \(mex\) 个数，有两种做法
区间极小 \(mex\) 段的个数是 \(O(n)\) 级别的
方法一
从前往后做，因为mex关于左端点将单调不升，我们考虑维护连续 \(mex\) 段，每个连续段的最右边即是一个极小 \(mex\) 段。若在右边加入一个数 \(x\)，那么只有 \(mex\) 值为 \(x\) 的段会分裂，因为上面结论，所以直接维护是正确的
具体来说，我们维护一棵权值线段树，表示 \(i\) 最后的出现位置，然后可以通过线段树上二分求出 \(mex\)
我们发现一段 \(mex=x\) 的连续段，它的左端点就是最后一次出现位置+1，右端点是线段树上 \(0\sim x-1\) 的最小值，于是就可以暴力分裂mex计算答案
方法二
从后往前做，维护连续 \(mex\) 段，发现是合并操作，大致是在后面删除一个数，那么维护上一个数的位置，进行对一个后缀取min
在处理完，极小 \(mex\) 后，我们可以用扫描线的方式维护对于一个右端点 \(r\)，每一个左端点的答案
在此基础上，维护历史版本和，那么每个点维护的就是对于一个左端点 \(l\)，右端点在 \(l\sim r\) 的答案和
那么如果要询问全部子区间的答案和，就是对版本和再进行区间求和
Tips
权值线段树维护 \(mex\)，还有极小 \(mex\) 数量
对于在区间问题上的高维问题，我们可以通过历史版本和维护，其实还可以再次离线，用多个BIT处理
标签：总结,题目,训练,省选,solution,端点,大意,考虑,mex From： https://www.cnblogs.com/zhy114514/p/18258904