B0831 模拟赛题解
原题链接
前言
先说点闲话。
本来是 8.15~8.19 放假的，由于我是借读，分校这边 23 号军训，之前军训的时候我又去复习中考了，所以得参加。我家住在外地，考虑到折腾一番去学校只会待 20，21，22 号 3 天左右，所以卡了个 bug 没去。
于是 8.15~8.29 号 10 多天基本没碰 oi（放假你还碰？卷狗！），除了 26 号晚上打了场 cf 还 TM 只做出 2 道，直接破防了，真要退役了。
这场比赛于我而言还是很好的康复赛，暴力和部分分给的很足，不至于破防。
差距基本在 T1，后三道很有难度，但勉强能补。
另外插一嘴，出题人文采很好。
T1 二维线段树优秀做法跑了 20 s，没想出怎么优化复杂度，36 pts。
T2 简单暴力，32 pts。
T3 简单暴力，20 pts。
T4 简单暴力，10 pts。
T1 月华
卡常题。
有两种思路，先说不带脑的。
线段树套猫树。
猫树教程
考虑用猫树维护每一排的信息，再用线段树维护列，线段树的每个节点都是一棵猫树。
时间复杂度 \(O(q \log n)\)，空间复杂度 \(O(n^2 \log n)\)，常数极大。
原 oj 是比较友好的，开到了 4 s，但校 oj 只给到 2 s，需要卡常+取模优化。
由于是隔天模拟赛时间太紧，这里直接套用模板，先鸽一下再学吧。
#include<bits/stdc++.h>
using namespace std;
const int N=1005,mod=147744151;
int n,m,p,ans,q,len=1,a[N][N],lg[N*4],pos[N],cat[N*4][13][N*2];
char buf[(1<<21)+5],*p1,*p2;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
int rd()
{
int f=0,x=0;
char ch=getchar();
while(!isdigit(ch)){f|=(ch=='-');ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return f?-x:x;
}
//直接套 _Cyan_ 的模板
#define ull unsigned long long
#define ui128 __uint128_t
struct Barrett{
ull d; ui128 m;
void init(ull _d){
d=_d,m=(((ui128)(1)<<64)/d);
}
ull operator()(ull a){
ull w=(m*a)>>64;w=a-w*d;
if(w>=d)w-=d;return w;
}
}MOD;
void build(int k,int id,int l,int r,int dep)//建猫树
{
if(l==r) {cat[k][dep][l]=a[id][l];return;}
int mid=l+r>>1;
cat[k][dep][mid]=a[id][mid],cat[k][dep][mid+1]=a[id][mid+1];
for(int i=mid-1;i>=l;i--) cat[k][dep][i]=MOD(1ll*a[id][i]*cat[k][dep][i+1]);
for(int i=mid+2;i<=r;i++) cat[k][dep][i]=MOD(1ll*a[id][i]*cat[k][dep][i-1]);
build(k,id,l,mid,dep+1),build(k,id,mid+1,r,dep+1);
}
void build_tr(int k=1,int l=1,int r=n)//建线段树
{
if(l==r) {build(k,l,1,len,1);return;}
int mid=l+r>>1;
build_tr(k<<1,l,mid),build_tr(k<<1|1,mid+1,r);
for(int i=1;i<=12;i++) for(int j=1;j<=len;j++) cat[k][i][j]=MOD(1ll*cat[k<<1][i][j]*cat[k<<1|1][i][j]);
}
int query(int x,int y,int ll,int rr,int dep,int k=1,int l=1,int r=n)
{
if(l>=x&&r<=y) return MOD(1ll*cat[k][dep][ll]*(ll==rr?1ll:cat[k][dep][rr]));
int mid=l+r>>1,ans=1;
if(x<=mid) ans=MOD(1ll*ans*query(x,y,ll,rr,dep,k<<1,l,mid));
if(mid<y) ans=MOD(1ll*ans*query(x,y,ll,rr,dep,k<<1|1,mid+1,r));
return ans;
}
signed main()
{
n=rd(),m=rd(),p=rd();
MOD.init(p);
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]=rd();
while(len<m) len<<=1;
for(int i=1;i<=len<<1;i++) lg[i]=lg[i>>1]+1;
for(int i=1;i<=m;i++) pos[i]=i+len-1;
build_tr();
q=rd();
for(int i=1;i<=q;i++)
{
int x1=rd(),y1=rd(),x2=rd(),y2=rd();
ans=(ans+(i^query(x1,x2,y1,y2,lg[pos[y1]]-lg[pos[y1]^pos[y2]])))%mod;
}
cout<<ans<<'\n';
return 0;
}
题解做法
考虑 \(x\) 在模 \(p\) 意义下存在逆元，当且仅当 \(\gcd(x,p)=1\)。
考虑让 \(a\) 数组里所有元素都存在逆元，就可以用前缀积来做。
先把 \(p\) 质因数分解，只需要把和 \(p\) 具有相同质因子的元素的质因子除掉，再用二维前缀和统计每个质因子出现次数，计算答案时乘上即可。
T2 光与影
咕咕咕
T3 夏虫
好像是我写过最长的代码？没压长度之前得有 5 kb。
设 \(f_x\) 表示以 \(x\) 为起点，需要 \(3\) 操作的最少次数。
不难发现答案为 \(f_x+n-1\)。
那么 \([l,r]\) 的答案为 \((r-l+1)\cdot (n-1)+\sum\limits_{i=l}^{r} f_i\)。
先考虑如何 \(O(n)\) 求 \(f_x\)。
设 \(l_x\) 为从 \(x\) 往左第一个大于 \(a_x\) 的位置， \(r_x\) 为从 \(x\) 往右第一个大于 \(a_x\) 的位置。
则有:
\(\begin{cases} f_x=f_{l_x}+1 \ \ \ \ (a_{l_x}<a_{r_x}) \\ f_x=f_{r_x}+1 \ \ \ \ (a_{l_x}>a_{r_x}) \\ f_x=\min(f_{l_x},f_{r_x})+1 \ \ \ \ (a_{l_x}=a_{r_x}) \end{cases}\)
直接记忆话搜索即可。 \(l_x,r_x\) 显然用单调栈求。由于每个 \(f\) 值至多算一次，复杂度 \(O(n)。\)
然后考虑每次交换的影响。
如果没有重复元素，可以发现 \(f_x\) 值为到 \(x\) 时两个单调栈元素之和。
设 \(A_x\) 为 \(a_1,a_2,...,a_x\) 的后缀最大值集合，\(B_x\) 为 \(a_x,a_{x+1},...,a_n\) 的前缀最大值集合，则 \(f_x=|A_x \cup\ B_x|\)。
现在转化为考虑交换对两个集合的影响。
先假设 \(a_x<a_{x+1}\)。
对于 \(i<x\)，若 \(\max\limits_{j=i}^{x-1} a_j < a_x\)，说明之前 \(B_i\) 中有 \(a_x\)，交换后显然 \(a_x\) 会从 \(B_i\) 中删去。可以通过线段树上查找受影响的区间 \([l,x-1]\)，但如果 \(a_{l-1}=a_x\)，说明 \(A_i,i\in[l,x-1]\) 中已经有 \(a_x\)，删去后不影响。
对于 \(i=x\) 或 \(i=x+1\)，\(i=x+1\) 的答案显然不变，\(i=x\) 则由 \(f_{x+1}\) 和 \(f_{r_x}\) 更新。注意线段树上二分求 \(r_x\) 时要忽略 \(a_{x+1}\)。
对于 \(i>x\) 和 \(i<x\) 类似，不再赘述，\(a_x>a_{x+1}\) 的情况也不再赘述。
时间复杂度 \(O(n\log n)\)，由于我写的二分套线段树，所以复杂度是 \(O(n\log^2 n)\)，开 O(fast) 可过 （时间有限，就不改写法了，嗯）。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
int n,k,q,a[N],l[N],r[N],f[N];
//维护 f 数组的线段树
struct SegmentTree{
#define lc (k<<1)
#define rc (k<<1|1)
#define mid (l+r>>1)
ll sum[N<<2],tag[N<<2];
void pushdown(int k,int l,int r)
{
if(!tag[k]) return;
tag[lc]+=tag[k],tag[rc]+=tag[k];
sum[lc]+=(mid-l+1)*tag[k],sum[rc]+=(r-mid)*tag[k];
tag[k]=0;
}
void build(int k=1,int l=1,int r=n)
{
if(l==r) {sum[k]=f[l];return;}
build(lc,l,mid),build(rc,mid+1,r);
sum[k]=sum[lc]+sum[rc];
}
void upd(int x,int y,int v,int k=1,int l=1,int r=n)
{
if(l>=x&&r<=y) {sum[k]+=1ll*(r-l+1)*v,tag[k]+=v;return;}
pushdown(k,l,r);
if(x<=mid) upd(x,y,v,lc,l,mid);
if(mid<y) upd(x,y,v,rc,mid+1,r);
sum[k]=sum[lc]+sum[rc];
}
ll qsum(int x,int y,int k=1,int l=1,int r=n)
{
if(l>=x&&r<=y) return sum[k];
pushdown(k,l,r);
ll res=0;
if(x<=mid) res=qsum(x,y,lc,l,mid);
if(mid<y) res+=qsum(x,y,rc,mid+1,r);
return res;
}
}Tf;
//二分的线段树
//其实可以和在一起写。。。
struct SegmentTree_mx{
int mx[N<<2];
void build(int k=1,int l=1,int r=n)
{
if(l==r) {mx[k]=a[l];return;}
build(lc,l,mid),build(rc,mid+1,r);
mx[k]=max(mx[lc],mx[rc]);
}
void upd(int x,int v,int k=1,int l=1,int r=n)
{
if(l==r) {mx[k]=v;return;}
x<=mid?upd(x,v,lc,l,mid):upd(x,v,rc,mid+1,r);
mx[k]=max(mx[lc],mx[rc]);
}
int qmax(int x,int y,int k=1,int l=1,int r=n)
{
if(l>=x&&r<=y) return mx[k];
int res=0;
if(x<=mid) res=qmax(x,y,lc,l,mid);
if(mid<y) res=max(res,qmax(x,y,rc,mid+1,r));
return res;
}
int findL(int r,int v)
{
int L=1,R=r-1,ans=r;
while(L<=R)
{
int m=L+R>>1;
//r-1 忽略 a[x]
if(qmax(m,r-1)<v) ans=m,R=m-1;
else L=m+1;
}
return ans;
}
int findR(int l,int v)
{
int L=l+1,R=n,ans=l;
while(L<=R)
{
int m=L+R>>1;
//l+1 忽略 a[x+1]
if(qmax(l+1,m)<v) ans=m,L=m+1;
else R=m-1;
}
return ans;
}
}Tmx;
char buf[(1<<21)+5],*p1,*p2;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
int rd()
{
int x=0;char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x;
}
// O(n) 求 f 数组
void dp(int i)
{
if(i==0||i==n+1) return;
if(l[i]==0&&r[i]==n+1) {f[i]=0;return;}
if(f[l[i]]==-1) dp(l[i]);
if(f[r[i]]==-1) dp(r[i]);
if(a[l[i]]<a[r[i]]) f[i]=f[l[i]]+1;
else if(a[l[i]]>a[r[i]]) f[i]=f[r[i]]+1;
else f[i]=min(f[l[i]],f[r[i]])+1;
}
// 单调栈求 $l,r$ 数组
void work()
{
stack<int> stk;stk.push(0);
for(int i=1;i<=n;i++)
{
while(a[i]>=a[stk.top()]) stk.pop();
l[i]=stk.top(),stk.push(i);
}
while(!stk.empty()) stk.pop();
stk.push(n+1);
for(int i=n;i>=1;i--)
{
while(a[i]>=a[stk.top()]) stk.pop();
r[i]=stk.top(),stk.push(i);
}
memset(f,-1,sizeof(f));
for(int i=1;i<=n;i++) if(f[i]==-1) dp(i);
}
int main()
{
n=rd(),k=rd();
for(int i=1;i<=n;i++) a[i]=rd();
a[0]=a[n+1]=2e9;
work();
Tf.build(),Tmx.build();
q=rd();
while(q--)
{
int x=rd(),l=rd(),r=rd();
if(a[x]<a[x+1])
{
//i<x 的影响
int L=Tmx.findL(x,a[x]);
if(L!=x&&a[L-1]!=a[x]) Tf.upd(L,x-1,-1);
//i>x 的影响
int R=Tmx.findR(x+1,a[x]);
if(R!=x+1&&a[R+1]!=a[x]) Tf.upd(x+2,R,1);
//i=x 或 i=x+1 的影响
int fx=Tf.qsum(x,x),fy=Tf.qsum(x+1,x+1);
Tf.upd(x,x,fy-fx);
R=Tmx.findR(x+1,a[x]+1);//注意这里 R 是最右 <=a[x] 的位置
if(a[x+1]<a[R+1]) fx=fy+1;
else if(a[R+1]<a[x+1]) fx=Tf.qsum(R+1,R+1)+1;
else fx=min(Tf.qsum(R+1,R+1),1ll*fy)+1;
Tf.upd(x+1,x+1,fx-fy);
Tmx.upd(x,a[x+1]),Tmx.upd(x+1,a[x]);
swap(a[x],a[x+1]);
}
else if(a[x]>a[x+1])
{
int L=Tmx.findL(x,a[x+1]);
if(L!=x&&a[L-1]!=a[x+1]) Tf.upd(L,x-1,1);
int R=Tmx.findR(x+1,a[x+1]);
if(R!=x+1&&a[R+1]!=a[x+1]) Tf.upd(x+2,R,-1);
int fx=Tf.qsum(x,x),fy=Tf.qsum(x+1,x+1);
Tf.upd(x+1,x+1,fx-fy);
L=Tmx.findL(x,a[x+1]+1);
if(a[x]<a[L-1]) fy=fx+1;
else if(a[L-1]<a[x]) fy=Tf.qsum(L-1,L-1)+1;
else fy=min(Tf.qsum(L-1,L-1),1ll*fx)+1;
Tf.upd(x,x,fy-fx);
Tmx.upd(x,a[x+1]),Tmx.upd(x+1,a[x]);
swap(a[x],a[x+1]);
}
printf("%lld\n",1ll*Tf.qsum(l,r)*k+1ll*(r-l+1)*(n-1));
}
}
T4 万分之一的光
题意可转化为给树上每条边定向，第 \(i\) 个点贡献为 \(a_i \times\) 从 \(i\) 出发能到达的点的个数，其中 \(a_i\) 为给定的点权，可能为负数。
长着一副 dp 的样子捏。
考虑点 \(u\) 到达的点分两类，子树内和子树外。
不难想出。定义 \(f(u,i)\) 表示 \(u\) 子树内能到达 \(i\) 个点的最大贡献，\(g(u,i)\) 表示 \(u\) 子树外能到达 \(i\) 个点的最大贡献。
但这样还不够，思考一下发现上面没法转移。但数据范围是 \(400\)，可以大胆猜想是 \(O(n^3)\) 的，然后上面是一副树上背包的样子，已经有 \(O(n^2)\) 的复杂度了，也就是说还差一维。不妨钦定一个点总共能到达的点的个数。
于是定义 \(h(u,i,j)\) 表示 \(u\) 总共能到达 \(i\) 个点，其中 \(j\) 个点在子树内的贡献。
初值 \(h(u,i,1)=a_u \cdot i\)。
然后考虑转移。设 \(v\) 为 \(u\) 的儿子。
若边为 \(u \rightarrow v\)，则有 \(h(u,i,j)'=\max \{h(u,i,j-k),f(v,k)\}\)。
若边为 \(v\rightarrow u\)，则有 \(h(u,i,j)'=\max \{h(u,i,j)',h(u,i,j)+g(v,i)\}\)。
显然是二者选一的转移，再解释下 \(g(v,i)\) : 由于钦定 \(u\) 能到达 \(i\) 个点，所以若 \(v\rightarrow u\)，则 \(v\) 向子树外能到达 \(i\) 个点。
最后 \(f(u,i)=h(u,i,i),g(u,i)=\max\limits_{i<j\leq n} h(u,i,i-j)\)。
树上背包+枚举总共能到达的点的个数，复杂度 \(O(n^3)\)。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=405;
int n,sz[N],a[N],f[N][N],g[N][N],h1[N],h2[N];
vector<int> G[N];
void dp(int u,int fa)
{
sz[u]=1;
for(int v:G[u]) if(v!=fa) dp(v,u),sz[u]+=sz[v];
for(int k=1;k<=n;k++) // 枚举 u 总共能到达的点的个数
{
//事实上 h 可以省略前两维，h2 是 h 的滚动数组
memset(h1,-0x3f,sizeof(h1));
memset(h2,-0x3f,sizeof(h2));
h1[1]=a[u]*k;
int now=1;
//注意树上背包不要写假了
for(int v:G[u])
{
if(v==fa) continue;
for(int i=1;i<=now;i++)
{
for(int j=1;j<=sz[v];j++)
h2[i+j]=max(h2[i+j],h1[i]+f[v][j]);
h2[i]=max(h2[i],h1[i]+g[v][k]);
}
now+=sz[v];
for(int i=1;i<=now;i++) h1[i]=h2[i],h2[i]=-1e18;
}
f[u][k]=h1[k];
for(int i=1;i<k;i++) g[u][k-i]=max(g[u][k-i],h1[i]);
}
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
memset(f,-0x3f,sizeof(f)),memset(g,-0x7f,sizeof(g));
for(int i=1;i<n;i++)
{
int u,v;cin>>u>>v;
G[u].push_back(v),G[v].push_back(u);
}
dp(1,0);
int ans=-1e18;
for(int i=1;i<=n;i++) ans=max(ans,f[1][i]);
cout<<ans;
}