前言
- 比赛链接。
状态不太好，又犯了老毛病死磕 T1，但 T1 是个很典的套路题我根本没听说过，T2 做过原题但没打。
T1 九次九日久重色
详细记录一下这个经典套路。
求最长上升子序列
\(O(n^2)\) 的就不写了，但是记录路径或方案书必须用 \(O(n^2)\)，这里说如何 \(O(n\log n)\) 求。
因为这里只关注序列长度不关注具体元素，记录当前最长上升子序列的长度 \(len\) 与元素 \(f_i\)，添加新的 \(a_i\) 时，若 \(a_i>f_{len}\) 则直接加入，否则二分找到第一个大于等于 \(a_i\) 的位置将其替换为 \(a_i\)，从贪心的角度，在序列长度不变且满足单调的同时使其内部元素尽可能小从而方便填入后续元素。
对于两个排列求最长公共子序列
\(O(n^2)\) 的就不写了，但是记录路径或方案数必须用 \(O(n^2)\)。
最长公共子序列是可以转换为最长上升子序列的，对于数组 \(b\) 中元素在数组 \(a\) 中有对应位置，记录其为 \(c\) 数组，因为最长公共子序列是一个满足数组 \(a,b\) 下标均递增的二维偏序，所以 \(c\) 的最长上升子序列即为所求。
对于任意数量元素的两个序列求最长公共子序列
总体处理依然与上面类似，但是发现 \(b\) 数组中一个元素对应多个 \(a\) 数组元素，这几个是不能重复计算的，依然是一个二维偏序，考虑前面求的是最长上升子序列，那么只需要讲一个 \(b_i\) 对应 \(a\) 数组的几个位置递减排序放到 \(c\) 数组里，然后直接求就可以了，依然直接二分即可，不需要树状数组。
对于本题
等同于对于任意数量元素的两个序列求最长公共子序列，只是这里相等变成了整除，依然是对应若干个位置，预处理时对于 \(b_i\) 是从 \(1\) 循环到 \(\sqrt{b_i}\) 的，鉴于学习莫反时推的结论，\(\sqrt 1+\sqrt 2+\sqrt 3+…+\sqrt{n}≈\dfrac{2}{3}n\sqrt n\)，再通过调和级数，\(c\) 数组的长度约为 \(n\log n\)，所以最终复杂度为 \(O(\dfrac{2}{3}n\sqrt n+n\log^2 n)\)。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=2e5+10,M=4e6+10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);}
int n,a[N],b[N],pos[N],c[M],tot,top,sta[N],f[N],len;
signed main()
{
read(n);
for(int i=1;i<=n;i++)
{
read(a[i]);
pos[a[i]]=i;
}
for(int i=1;i<=n;i++)
{
read(b[i]);
top=0;
for(int j=1;j*j<=b[i];j++)
if(b[i]%j==0)
{
if(j*j==b[i]) sta[++top]=pos[j];
else
{
sta[++top]=pos[j];
sta[++top]=pos[b[i]/j];
}
}
sort(sta+1,sta+1+top);
while(top)
{
c[++tot]=sta[top];
top--;
}
}
f[1]=c[1],len=1;
for(int i=2;i<=tot;i++)
{
if(c[i]>f[len]) f[++len]=c[i];
else
{
int k=lower_bound(f+1,f+1+len,c[i])-f;
f[k]=min(f[k],c[i]);
}
}
write(len);
}
T2 天色天歌天籁音
- 原题：P3709 大爷的字符串题。
把题读明白就做完了，贪心角度每次放入一个尽可能长的递增序列前产生 \(-1\) 的贡献，所以最终答案就是区间众数出现的次数 \(\times -1\)。
对此有很多写法，P4168 [Violet] 蒲公英 这题的在线分块做法复杂度在此题是错误的，因为没有要求在线，考虑使用莫队。
- 回滚莫队，这个很显然直接写不删除莫队即可，与下面算法比优势是能够同时处理众数是谁，缺点是常数巨大。
- 普通莫队，因为只询问次数不询问具体是谁，考虑删除一个元素时答案最多 \(-1\)，所以先开一个桶，再给桶开一个桶就可以了。
复杂度均为 \(O(m\sqrt n)\)。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=2e5+10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);}
int n,m,t,ans,a[N],b[N],pos[N],anss[N],cnt[N],sum[N];
struct aa {int l,r,id;}e[N];
bool cmp(aa a,aa b) {return pos[a.l]==pos[b.l]?((pos[a.l]&1)?a.r<b.r:a.r>b.r):a.l<b.l;}
void add(int x)
{
sum[cnt[x]]--; cnt[x]++; sum[cnt[x]]++;
ans=max(ans,cnt[x]);
}
void del(int x)
{
sum[cnt[x]]--;
ans-=(ans==cnt[x]&&sum[cnt[x]]==0);
cnt[x]--; sum[cnt[x]]++;
}
signed main()
{
read(n,m);
t=sqrt(n);
for(int i=1;i<=n;i++)
{
read(a[i]); b[i]=a[i];
pos[i]=(i-1)/t+1;
}
sort(b+1,b+1+n);
b[0]=unique(b+1,b+1+n)-(b+1);
for(int i=1;i<=n;i++)
a[i]=lower_bound(b+1,b+1+b[0],a[i])-b;
for(int i=1,l,r;i<=m;i++)
{
read(l,r);
e[i]={l,r,i};
}
sort(e+1,e+1+m,cmp);
for(int i=1,l=1,r=0;i<=m;i++)
{
while(l<e[i].l) {del(a[l]);l++;}
while(l>e[i].l) {l--;add(a[l]);}
while(r<e[i].r) {r++,add(a[r]);}
while(r>e[i].r) {del(a[r]),r--;}
anss[e[i].id]=ans;
}
for(int i=1;i<=m;i++) write(-anss[i]),puts("");
}
T3 春色春恋春熙风
据说是树上启发式合并发明者专门出的题，为此还专门学了一下树上启发式合并。
具体操作就是先遍历所有轻儿子，记录答案但不统计贡献；再遍历重儿子，记录答案饼统计贡献；最后遍历所有轻儿子，记录答案并统计贡献；当然别忘了自身节点贡献。
这么做正确性是显然的，复杂度分析详见 oi-wiki。
因为只有 \(22\) 个边权，考虑状压，发现其为合法需满足二进制状态中重最多存在一个 \(1\)，由此发现可以用路径异或和维护，利用边权的树上差分，\(dis(x,y)=dis(x,1)\bigoplus dis(lca,1)\bigoplus dis(y,1)\bigoplus dis(lca,1)=dis(x,1)\bigoplus dis(y,1)\)。
目标找到最长的一条链满足 \(dis(x,y)\) 合法，\(f_i\) 表示满足 \(dis(x,1)=i\) 中最大的 \(dep_x\)；设 \(s\) 表示一种合法状态，有 \(dis(x,1)\bigoplus dis(y,1)=s\)，即 \(dis(x,1)\bigoplus s=dis(y,1)\)，再通过上面维护的 \(f\) 数组，用 \(len(x,y)=dep_x+dep_y-2dep_{lca}\) 求解即可。
复杂度 \(O(22n\log n)\)。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=5e5+10,M=5e6+10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);}
int n,tot,a[N],sz[N],son[N],in[N],out[N],pos[N],f[M],ans[N],sum[N],dep[N];
vector<int>e[N];
void add1(int x,int y)
{
ans[x]=max(ans[x],dep[y]+f[sum[y]]-(dep[x]<<1));
for(int i=0;i<=21;i++)
ans[x]=max(ans[x],dep[y]+f[sum[y]^(1<<i)]-(dep[x]<<1));
}
void add2(int x) {f[sum[x]]=max(f[sum[x]],dep[x]);}
void dfs1(int x,int fa)
{
in[x]=++tot; pos[tot]=x; sz[x]=1; dep[x]=dep[fa]+1;
sum[x]=(x!=1)*(sum[fa]^(1<<a[x]));
for(int y:e[x])
{
dfs1(y,x);
sz[x]+=sz[y];
son[x]=sz[son[x]]<sz[y]?y:son[x];
}
out[x]=tot;
}
void dfs2(int x,int fa,bool flag)
{
for(int y:e[x]) if(y!=son[x]) dfs2(y,x,0);
if(son[x]) dfs2(son[x],x,1);
for(int y:e[x])
if(y!=son[x])
{
for(int i=in[y];i<=out[y];i++) add1(x,pos[i]);
for(int i=in[y];i<=out[y];i++) add2(pos[i]);
}
add1(x,x),add2(x);
for(int y:e[x]) ans[x]=max(ans[x],ans[y]);
if(!flag)
for(int i=in[x];i<=out[x];i++) f[sum[pos[i]]]=-0x3f3f3f3f;
}
signed main()
{
read(n);
char s;
for(int i=2,x;i<=n;i++)
{
read(x); cin>>s;
a[i]=s-'a';
e[x].push_back(i);
}
memset(f,-0x3f,sizeof(f));
dfs1(1,0); dfs2(1,0,1);
for(int i=1;i<=n;i++) write(ans[i]),putchar(' ');
}
T4 雪色雪花雪余痕
不会。
总结
有的东西积蓄依旧早晚要写，不然会憋坏的，本想找个最不开心的一天，打得这么唐正是好时候吧，但昨天忙着改题没时间，今天好不容易没有模拟赛不想扰了好心情，也许 hz 最好的抑制情绪的手段就是让人忙得没时间沮丧吧……
标签：write,20,int,void,Tp,2024,inline,集训,dis From： https://www.cnblogs.com/Charlieljk/p/18350891