ZROI - 2023csp七连测附加赛day2

居然忘记写这一篇了。

比赛链接：http://zhengruioi.com/contest/1459

懒了，直接放代码和官方题解。陈年老题了。

A. 时队

题目简介

定义序列 的权值为 ，现在给出一个序列 ，找出其一个子序列使得权值最大。并且一共 次单调修改，每次修改后需要找出新的最大权值。

数据范围：

AC Code

#include<bits/stdc++.h>
using namespace std;
namespace io {
	const int SIZE = (1 << 21) + 1;
	char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
	// getchar
	#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
	// print the remaining part
	inline void flush () {
		fwrite (obuf, 1, oS - obuf, stdout);
		oS = obuf;
	}
	// putchar
	inline void putc (char x) {
		*oS ++ = x;
		if (oS == oT) flush ();
	}
	// input a signed integer
	template <class I>
	inline void read (I &x) {
		for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
		for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
	}
	// print a signed integer
	template <class I>
	inline void print (I x) {
		if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
		while (x) qu[++ qr] = x % 10 + '0',  x /= 10;
		while (qr) putc (qu[qr --]);
	}
	//no need to call flush at the end manually!
	struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: print;

#define int long long
const int N=2e5+20;
int a[N],n,q,x,y,ans;
signed main()
{
	int i,j,k;
	read(n),read(q);
	for(i=1; i<=n; i++)
		read(a[i]);
	for(i=1; i<=n-1; i++)
		ans+=max(max(a[i],a[i+1]),0ll);
	print(ans),putc('\n');
	while(q--)
	{
		read(x),read(y);
		if(x<n)ans-=max(max(a[x],a[x+1]),0ll),ans+=max(max(y,a[x+1]),0ll);
		if(x>1)ans-=max(max(a[x-1],a[x]),0ll),ans+=max(max(a[x-1],y),0ll);
		a[x]=y;print(ans),putc('\n');
	}
	return 0;
}

---

B. 黄队

题目简介

给定一个有 个结点的树，定义 表示从 出发经过标号不超过 的边能够到达的点的点集。一共 次询问，每次询问给出 个点 ，求出有多少个长度为 的序列 满足 且 。对 取模。

数据范围：

AC Code

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5,mod=1e9+7;
int n,q,x,y,k,tot,a[N],fa[N],val[N],sz[N],dep[N],f[N][25],tim,dfn[N],ans;
vector<int>v[N];
int find(int x){
	return x==fa[x]?x:fa[x]=find(fa[x]);
}
void dfs(int x){
	sz[x]=x<=n,dfn[x]=++tim;
	for(int i=0;i<=19;i++) f[x][i+1]=f[f[x][i]][i];
	for(int y:v[x])
		f[y][0]=x,dep[y]=dep[x]+1,dfs(y),sz[x]+=sz[y];
}
int lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=20;i>=0;i--) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
	if(x==y) return x;
	for(int i=20;i>=0;i--)
		if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
	return f[x][0];
}
signed main(){
	scanf("%d",&n);
	iota(fa+1,fa+1+n+n,1),tot=n;
	for(int i=1;i<n;i++){
		scanf("%d%d",&x,&y),x=find(x),y=find(y);
		fa[x]=fa[y]=++tot,val[tot]=i,
		v[tot].push_back(x),v[tot].push_back(y);
	}
	dep[tot]=1,dfs(tot);
	scanf("%d",&q);
	while(q--){
		scanf("%d",&k),ans=1;
		for(int i=1;i<=k;i++) scanf("%d",&a[i]);
		sort(a+1,a+1+k,[](int x,int y){return dfn[x]<dfn[y];});
		for(int i=1;i<=k;i++){
			int mn=n-1;
			if(i>1) mn=val[lca(a[i],a[i-1])]-1;
			if(i<k) mn=min(mn,val[lca(a[i],a[i+1])]-1);
			ans=1ll*ans*(mn+1)%mod;
		}
		printf("%d\n",ans);
	}
	return 0;
}

---

C. 高爸

题目简介

给定 个序列，第 个序列长度为 。

现在对于每一个 ，你需要构造一个长度为 的序列 满足 ，且 最大。输出答案。

数据范围：

AC Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
const ll INF=1e18;
vl work(int n) {
	if(n==1) {
		int m; cin>>m;
		vl f(m); for(auto &x:f) cin>>x;
		return f;
	}
	int m=n>>1;
	auto a=work(m),b=work(n-m);
	int A=a.size(),B=b.size();
	vector<ll> c(A+B-1,-INF);
	for(int x=0;x<12;++x) for(int y=0;y<12;++y)
		for(int i=x,j=y;i<A && j<B;) {
			c[i+j]=max(c[i+j],a[i]+b[j]);
			(j+12>=B || i+12<A && a[i+12]-a[i]>b[j+12]-b[j]?i:j)+=12;
		}
	return c;
}
int main() {
	ios::sync_with_stdio(0);
	int n; cin>>n;
	for(auto x:work(n)) cout<<x<<" ";
}

---

题解

---