时间戳

首页 > 技术文章 > 2022/02/12 模拟赛题解

2022/02/12 模拟赛题解

Dark-Romance 2022-02-12 15:59 原文

T1

Desription

定义长度为 \(n\) 的“好”的串 \(s\) 满足：

\[|s_i-s_{i-1}|=1 ,i\in [2,n] \]

\[s_i \geq \dfrac{g_{i-1}+g_{i+1}}{2}, i\in [2,n-1] \]

给你两个长度为 \(n\) 的序列 \(a,v\) ，每次选择一段“好”的子串删掉，剩下的子串前后拼接；

若该子串长度为 \(l\) ，获得 \(v_l\) 的价值；

不一定要删完，求最大价值。

Solution

我们可以考虑设 \(f_{l,r}\) 表示完全删掉区间 \([l,r]\) 的最大贡献，可以发现转移我们可以从中间划开分两边删，我们也可以选出一个可以删的的子序列，然后把中间的都删了。

对于可以删的子序列，我们可以分别做一个单调上升子序列的dp，以及一个单调下降子序列的dp。

复杂度 \(\Theta(n^3)\)。

Code

#include <bits/stdc++.h>
using namespace std;

#define Int register int
#define int long long
#define MAXN 405

template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}
template <typename T> inline void chkmax (T &a,T b){a = max (a,b);}
template <typename T> inline void chkmin (T &a,T b){a = min (a,b);}

int n,val[MAXN],a[MAXN],dp[MAXN],f[MAXN][MAXN],pre[MAXN][MAXN],suf[MAXN][MAXN];

signed main(){
	freopen ("good.in","r",stdin);
	freopen ("good.out","w",stdout);
	read (n);
	for (Int i = 1;i <= n;++ i) read (val[i]);
	for (Int i = 1;i <= n;++ i) read (a[i]);
	memset (f,0xcf,sizeof (f)),memset (pre,0xcf,sizeof (pre)),memset (suf,0xcf,sizeof (suf));
	for (Int i = 1;i <= n + 1;++ i)
		for (Int j = 0;j < i;++ j) f[i][j] = 0;
	for (Int l = n;l >= 1;-- l){
		suf[l][l] = pre[l][l] = 0,f[l][l] = val[1];
		for (Int r = l + 1;r <= n;++ r){
			for (Int k = l;k < r;++ k) chkmax (f[l][r],f[l][k] + f[k + 1][r]);
			for (Int k = l + 1;k <= r;++ k) if (a[k] == a[l] + 1) chkmax (pre[l][r],pre[k][r] + f[l + 1][k - 1]);
			for (Int k = l;k <= r - 1;++ k) if (a[k] == a[r] + 1) chkmax (suf[l][r],suf[l][k] + f[k + 1][r - 1]);
			for (Int k = l;k <= r;++ k) if (a[k] >= a[l] && a[k] >= a[r]) chkmax (f[l][r],pre[l][k] + suf[k][r] + val[a[k] - a[l] + 1 + a[k] - a[r]]);
		}
	}
	memset (dp,0xcf,sizeof (dp)),dp[0] = 0;
	for (Int i = 1;i <= n;++ i){
		dp[i] = dp[i - 1];
		for (Int j = 1;j <= i;++ j)
			chkmax (dp[i],dp[j - 1] + f[j][i]);
	}
	write (dp[n]),putchar ('\n');
	return 0;
}

T2

Description

给定一张 \(n\) 个点，\(m\) 条边的连通无向图，图有边权，每个点有一个颜色。

有 \(q\) 次操作，每次操作可改变某一点颜色。

每次操作后求图中不同颜色点的最短距离。

保证图中点颜色至少存在两种。

Solution

不难发现，答案一定是一条边的权值，那么一定出现在最小生成树上，那么我们可以直接线段树+set直接 \(\Theta(n\log n)\) 维护。

Code

#include <bits/stdc++.h>
using namespace std;

#define Int register int
#define MAXN 200005
#define MAXM 300005

template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}
template <typename T> inline void chkmax (T &a,T b){a = max (a,b);}
template <typename T> inline void chkmin (T &a,T b){a = min (a,b);}

int n,m,c,q,fa[MAXN],col[MAXN];

struct edge{
	int u,v,w;
	bool operator < (const edge &p)const{return w < p.w;}
}e[MAXM];

int findSet (int x){return fa[x] == x ? x : fa[x] = findSet (fa[x]);}

#define pii pair<int,int>
#define se second
#define fi first
vector <pii> g[MAXN];

int ind,par[MAXN],dfn[MAXN],val[MAXN],bg[MAXN],ed[MAXN],tur[MAXN];

struct node{
	int c,id;
	node(){}
	node (int _c,int _id){c = _c,id = _id;}
	bool operator < (const node &p)const{return c != p.c ? c < p.c : id < p.id;}
};
set <node> tS[MAXN];

void dfs (int u,int fa){
	bg[u] = ind + 1,par[u] = fa;
	for (pii it : g[u]){
		int v = it.fi,w = it.se;
		if (v == fa) continue;
		val[v] = w,dfn[v] = ++ ind,tur[ind] = v,tS[u].insert (node(col[v],dfn[v]));
	}
	ed[u] = ind;
	for (pii it : g[u]){
		int v = it.fi,w = it.se;
		if (v == fa) continue;
		dfs (v,u);
	}
}

struct Segment{
	int minn[MAXN << 2],tmp[MAXN << 2],tag[MAXN << 2];
	void pushadd (int x,int t){tag[x] = t,minn[x] = (t == 1) ? tmp[x] : 1e9;}
	void pushup (int x){minn[x] = min (minn[x << 1],minn[x << 1 | 1]);}
	void pushdown (int x){if (tag[x]) pushadd (x << 1,tag[x]),pushadd (x << 1 | 1,tag[x]),tag[x] = 0;}
	void modify (int x,int l,int r,int ql,int qr,int t){
		if (l >= ql && r <= qr) return pushadd (x,t);
		int mid = l + r >> 1;pushdown (x);
		if (ql <= mid) modify (x << 1,l,mid,ql,qr,t);
		if (qr > mid) modify (x << 1 | 1,mid + 1,r,ql,qr,t);
		pushup (x);
	}
	void build (int x,int l,int r){
		if (l == r){
			int p = tur[l];
			tmp[x] = (p == 1 ? 1e9 : val[p]);
			minn[x] = (col[par[p]] == col[p] ? 1e9 : tmp[x]);
			return ;
		}
		int mid = l + r >> 1;
		build (x << 1,l,mid),build (x << 1 | 1,mid + 1,r),pushup (x),tmp[x] = min (tmp[x << 1],tmp[x << 1 | 1]);
	}
}tree;

void change (int x,int y){
	if (col[x] == y) return ;
	if (x != 1){
		if (col[par[x]] == y) tree.modify (1,1,n,dfn[x],dfn[x],-1);
		if (col[par[x]] == col[x]) tree.modify (1,1,n,dfn[x],dfn[x],1);
		tS[par[x]].erase (node(col[x],dfn[x])),tS[par[x]].insert (node(y,dfn[x]));
	}
	auto it = tS[x].lower_bound (node(col[x],0));
	if (it != tS[x].end() && it -> c == col[x]){
		auto it1 = tS[x].lower_bound (node(col[x] + 1,0));-- it1;
		tree.modify (1,1,n,it -> id,it1 -> id,1); 
	}
	it = tS[x].lower_bound (node(y,0));
	if (it != tS[x].end() && it -> c == y){
		auto it1 = tS[x].lower_bound (node(y + 1,0));-- it1;
		tree.modify (1,1,n,it -> id,it1 -> id,-1); 
	}
	col[x] = y;
}

signed main(){
	freopen ("color.in","r",stdin);
	freopen ("color.out","w",stdout);
	read (n,m,c,q);
	for (Int i = 1;i <= m;++ i) read (e[i].u,e[i].v,e[i].w);
	for (Int i = 1;i <= n;++ i) read (col[i]),fa[i] = i;
	sort (e + 1,e + m + 1);
	for (Int i = 1;i <= m;++ i){
		int u = e[i].u,v = e[i].v,w = e[i].w;
		if (findSet (u) != findSet (v)) fa[fa[u]] = fa[v],g[u].push_back ({v,w}),g[v].push_back ({u,w});
	}
	dfn[1] = ind = tur[1] = 1,dfs (1,0),tree.build (1,1,n);
	while (q --> 0){
		int x,y;read (x,y),change (x,y);
		write (tree.minn[1]),putchar ('\n');
	}
	return 0;
}

T3

Description

将一段旋律简化为一个正整数序列

给定一个序列 \(v\)，一段长度为 \(n\) 的悦耳的旋律 有如下特征：

  1. \(s_i\leq v_i\)；
  2. 序列不存在 \(\texttt{border}\).

求长度为 \(n\) 的旋律中有多少段是悦耳的，由于答案可能很大，对 \(998244353\) 取模。

Solution

不难列出 dp 式：

\[f_i=pre_i-\sum_{j=1}^{2\times j\le i} f_j\times pre_{i-j}/pre_j \]

其中 \(pre_i\) 是前缀积。

然后你发现可以很轻松地做到 \(\Theta(n\log^2n)\)，但是出题人脑子有点问题，正解就是 \(\Theta(n\log^2n)\) 的。

Code

#include <bits/stdc++.h>
using namespace std;

#define Int register int
#define mod 998244353
#define MAXN 1000005

template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}
template <typename T> inline void chkmax (T &a,T b){a = max (a,b);}
template <typename T> inline void chkmin (T &a,T b){a = min (a,b);}

int n,val[MAXN],dp[MAXN],pre[MAXN],ipre[MAXN];

int mul (int a,int b){return 1ll * a * b % mod;}
int dec (int a,int b){return a >= b ? a - b : a + mod - b;}
int add (int a,int b){return a + b >= mod ? a + b - mod : a + b;}
int qkpow (int a,int b){
	int res = 1;for (;b;b >>= 1,a = mul (a,a)) if (b & 1) res = mul (res,a);
	return res;
}
void Add (int &a,int b){a = add (a,b);}
void Sub (int &a,int b){a = dec (a,b);}

#define poly vector<int>
#define SZ(A) ((A).size())
#define MAXX 4000005

void putout (poly A){
	cout << SZ(A) << ": ";
	for (Int i = 0;i < SZ(A);++ i) cout << A[i] << " , ";cout << endl;
}

int rev[MAXX],w[MAXX];
void init_ntt (){
	int lim = 1 << 21;
	for (Int i = 0;i < lim;++ i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << 20);
	int Wn = qkpow (3,(mod - 1) / lim);w[lim >> 1] = 1;
	for (Int i = lim / 2 + 1;i < lim;++ i) w[i] = mul (w[i - 1],Wn);
	for (Int i = lim / 2 - 1;i;-- i) w[i] = w[i << 1];
}

void ntt (poly &a,int type){
#define G 3
#define Gi 332748118
	static int d[MAXX];int lim = a.size();
	for (Int i = 0,z = 21 - __builtin_ctz(lim);i < lim;++ i) d[rev[i] >> z] = a[i];
	for (Int i = 1;i < lim;i <<= 1)
		for (Int j = 0;j < lim;j += i << 1)
			for (Int k = 0;k < i;++ k){
				int x = mul (w[i + k],d[i + j + k]);
				d[i + j + k] = dec (d[j + k],x),d[j + k] = add (d[j + k],x);
			}
	for (Int i = 0;i < lim;++ i) a[i] = d[i] % mod;
	if (type == -1){
		reverse (a.begin() + 1,a.begin() + lim);
		for (Int i = 0,Inv = qkpow (lim,mod - 2);i < lim;++ i) a[i] = mul (a[i],Inv);
	}
#undef G
#undef Gi 
}

poly operator * (poly A,poly B){
	int lim = 1,l = 0,len = SZ(A) + SZ(B) - 1;
	while (lim < SZ(A) + SZ(B)) lim <<= 1,++ l;
	A.resize (lim),B.resize (lim),ntt (A,1),ntt (B,1);
	for (Int i = 0;i < lim;++ i) A[i] = mul (A[i],B[i]);
	ntt (A,-1),A.resize (len);
	return A;
}

void work (int l,int r){
	if (l == r){
		if (l * 2 <= n) Sub (dp[l * 2],dp[l]);
		return ;
	}
	int mid = l + r >> 1;
	work (l,mid);
	if (l * 2 <= n){
		poly H1,H2;H1.resize (r - mid + 1),H2.resize (mid - l + 1);
		for (Int i = mid + 1;i <= r;++ i) H1[i - mid] = pre[i];
		for (Int i = l;i <= mid;++ i) H2[i - l] = mul (dp[i],ipre[i]);
		H1 = H1 * H2;
		for (Int i = 0;i < SZ(H1);++ i) if (i + l + mid <= n) Sub (dp[i + l + mid],H1[i]);
	}
	work (mid + 1,r);
}

signed main(){
	freopen ("music.in","r",stdin);
	freopen ("music.out","w",stdout);
	read (n),pre[0] = 1,init_ntt ();
	for (Int i = 1;i <= n;++ i) read (val[i]),pre[i] = mul (pre[i - 1],val[i]),ipre[i] = qkpow (pre[i],mod - 2),dp[i] = pre[i];
	work (1,n),write (dp[n]),putchar ('\n');
	return 0;
}

推荐阅读