杂题选做（2023.10.26-2023.10.30）

杂七杂八的题目。

CF444C DZY Loves Colors

题目描述：

有一个 $n$ 个元素组成的序列，每个元素有两个属性：颜色 $c_i$ 和权值 $w_i$。$c_i$ 初始为 $i$，$w_i$ 初始为 $0$。$m$ 次操作，操作有两种：

1. 1 l r x：对 $i\in [l,r]$ 的所有 $i$ 进行如下操作：设第 $i$ 个元素 原来 的颜色为 $y$，您要把第 $i$ 个元素的颜色改为 $x$，权值 增加 $|y-x|$。
2. 2 l r：求 $\displaystyle\sum_{i=l}^r w_i$。

$1\le n,m\le 10^5$，$1\le x\le 10^8$。

题目分析：

首先有如下的观察：

既然是对区间进行操作，所以显然可以使用线段树维护；根据颜色段均摊的经典结论，我们总颜色段数为 $O(n+m)$。

其实对于操作 $1$ 如果我们是对于一个颜色均相等的区间做，那么就是简单的，所以我们就考虑在线段树上暴力走，直到走到一个区间满足颜色均相等再进行更改。

因为每一个颜色段最多贡献到线段树上 $O(\log n)$ 个区间，而一个颜色段被访问一次之后就没用了，所以总时间复杂度为 $O((n+m) \log n)$。

代码：

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5+5;
int tag[4*N],col[4*N],sum[4*N];
void pushup(int now){
	if(col[now<<1] == col[now<<1|1])	col[now] = col[now<<1];
	else	col[now] = 0;
	sum[now] = sum[now<<1] + sum[now<<1|1];
}
void pushdown(int now,int now_l,int now_r){
	if(tag[now]){
		int mid = (now_l + now_r)>>1;
		sum[now<<1] += (mid - now_l + 1) * tag[now];
		sum[now<<1|1] += (now_r - mid) * tag[now];
		col[now<<1] = col[now<<1|1] = col[now];
		tag[now<<1] += tag[now];tag[now<<1|1] += tag[now];
		tag[now] = 0; 
	}
}
void build(int now,int now_l,int now_r){
	if(now_l == now_r){
		col[now] = now_l;
		return;
	}
	int mid = (now_l + now_r)>>1;
	build(now<<1,now_l,mid);build(now<<1|1,mid+1,now_r);
	pushup(now);
}
void modify(int now,int now_l,int now_r,int l,int r,int x){
	if(l <= now_l && r >= now_r && col[now]){
		sum[now] += (now_r - now_l + 1) * abs(x - col[now]);
		tag[now] += abs(x - col[now]);col[now] = x;
		return;
	}
	int mid = (now_l + now_r)>>1;
	pushdown(now,now_l,now_r);
	if(l <= mid)	modify(now<<1,now_l,mid,l,r,x);
	if(r > mid)		modify(now<<1|1,mid+1,now_r,l,r,x);
	pushup(now);
}
int query(int now,int now_l,int now_r,int l,int r){
	if(l <= now_l && r >= now_r)	return sum[now];
	pushdown(now,now_l,now_r);
	int mid = (now_l + now_r)>>1,ans = 0;
	if(l <= mid)	ans += query(now<<1,now_l,mid,l,r);
	if(r > mid)		ans += query(now<<1|1,mid+1,now_r,l,r);
	return ans;
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int n,m;scanf("%lld%lld",&n,&m);
	build(1,1,n);
	for(int i=1; i<=m; i++){
		int opt,l,r,x;
		scanf("%lld",&opt);
		if(opt == 1){
			scanf("%lld%lld%lld",&l,&r,&x);
			modify(1,1,n,l,r,x);
		}
		else{
			scanf("%lld%lld",&l,&r);
			printf("%lld\n",query(1,1,n,l,r));
		}
	}
	return 0;
}

CF253D Table with Letters - 2

题目描述：

给一个 $n \times m$ 的字符矩阵和一个限制 $k$，求有多少个长、宽大于 1 的子矩阵满足四个角的字母相等且包含不超过 $k$ 个 a。

$2 \leq n,m \leq 400, 0 \leq k \leq n \times m$。

题目分析：

一个想法就是直接枚举这个矩形的上下左右四个边界，然后包含不超过 $k$ 个 a 的限制就直接二维前缀和就能搞定。

但这样的复杂度是 $O(n^4)$，我们要求做到 $O(n^3)$，所以不妨只枚举上、下、左边界，这样的话在只考虑不超过 $k$ 个 a 的限制的情况下，右边界是一个连续的区间，而字符相等的限制可以开桶维护。

这个东西显然可以双指针做到 $O(n^3)$ 就可以通过了。

注意：这个题原题的提交格式要求文件输入输出。

代码：

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 505;
int sum[N][N],ans[N];
char s[N][N];
int get(int x1,int x2,int y1,int y2){
	return sum[x2][y2] - sum[x2][y1-1] - sum[x1-1][y2] + sum[x1-1][y1-1];
}
signed main(){
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	int n,m,k;scanf("%lld%lld%lld",&n,&m,&k);
	for(int i=1; i<=n; i++)	scanf("%s",s[i]+1);
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + (s[i][j] == 'a');
		}
	}
	int tmp = 0;
	for(int u=1; u<=n; u++){
		for(int d=u+1; d<=n; d++){
			int r=1;
			if(s[u][1] == s[d][1] && get(u,d,1,1) <= k)	ans[s[u][1]-'a']++;
			for(int l=1; l<=m; l++){
				if(s[u][l] == s[d][l] && get(u,d,l,l) <= k)	ans[s[u][l]-'a']--;
				while(r+1 <= m && get(u,d,l,r+1) <= k){
					++r;
					if(s[u][r] == s[d][r] && r >= l)	ans[s[u][r]-'a']++;
				}
				if(s[u][l] == s[d][l])	tmp += ans[s[u][l]-'a'];
			}
			for(int i=0; i<=30; i++)	ans[i] = 0;
		}
	}
	printf("%lld\n",tmp);
	return 0;
}

CF698C LRU

题目描述：

有 $n$ 种物品和一个大小为 $k$ 的队列，有 $p_i$ 的概率会选择第 $i$ 种物品放入队列，如果队列已经有 $i$ 则将队列中的 $i$ 移到队尾。

如果队列中元素个数超过 $k$ 则弹出队首。

求 $10^{100}$ 次操作后每种物品留在队列的概率。

$1 \le k \le n \le 20$

题目分析：

首先 $10^{100}$ 这个数我们可以认为是无限次操作，所以经过无限次操作队列中的元素小于 $k$ 个的概率就无限趋近于 $0$ 所以就不用管了，只需要在一队列中的元素恰好等于 $k$ 个的情况。

我们只在意最后 $k$ 个入队的是哪些，在他们之前的操作可以认为没有任何作用，也就是说可以设 $dp[S]$ 表示确定集合 $S$ 内的数在最后的 $k$ 个中的概率，然后转移就是确定下一个是什么。

注意在选择的过程中，如果我们选择到了集合 $S$ 内的数可以认为这个数没有任何作用，也就是说我们可以直接把集合 $S$ 内的数去掉，然后将其他的数的概率等比例扩大，这样下一个数选择 $i$ 的概率就是等比例扩大之后的 $p_i$。

这样的话转移就直接乘以概率就行了。

代码：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+5;
double p[N],dp[N],f[N];
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);   //注意特判 p_i = 1 的情况 
	int n,k;scanf("%d%d",&n,&k);
	int tot = 0;
	for(int i=1; i<=n; i++){
		scanf("%lf",&p[i]);
		if(p[i] != 0)	++tot;
	}
	if(tot <= k){
		for(int i=1; i<=n; i++){
			if(p[i] != 0)	printf("1 ");
			else	printf("0 ");
		}
		return 0;
	}
	dp[0] = 1;
	for(int i=1; i<(1<<n); i++){
		double tmp = 0;
		for(int j=1; j<=n; j++){
			if((i >> (j-1)) & 1)
				tmp += p[j];
		}
		for(int j=1; j<=n; j++){
			if(!((i >> (j-1)) & 1))	continue;
			dp[i] += dp[i ^ (1<<(j-1))] * p[j] / (1-(tmp-p[j]));
		}
	}
	for(int i=0; i<(1<<n); i++){
		if(__builtin_popcount(i) != k)	continue;
		for(int j=1; j<=n; j++){
			if((i >> (j-1)) & 1)	f[j] += dp[i];
		}
	}
	for(int i=1; i<=n; i++)	printf("%.7lf ",f[i]);
	return 0;
}

CF441E Valera and Number

题目描述：

给出一个数 $x$，对它进行 $k$ 次操作，每次操作：

• 以 $p \%$ 的概率对它乘以 $2$。
• 以 $(100 - p) \%$ 的概率对它加上 $1$。

求该数最终二进制下末尾 $0$ 个数的期望。

$1 \le x \le 10^9$，$1 \le k \le 200$，$0 \le p \le 100$

题目分析：

显然要将数看作二进制讨论，比较困难的一点就是加 $1$ 操作会导致一些连环的进位，但是注意到 $k \le 200$，也就是说我们加 $1$ 操作最多会对第 $8$ 位进 $1$ 之后就不可能对第 $8$ 位包括更高的位产生影响了。

所以我们可以直接暴力记录前 $8$ 位是什么，以及第 $8$ 位之后连续的 $0/1$ 的个数，转移就是分两种情况讨论一下即可。

这里分类讨论的时候就是注意：乘 $2$ 相当于对于前 $8$ 位也整体地平移了一位，加 $1$ 可以理解为前 $8$ 位加 $1$ 之后加到后面几位上。

代码的话就放两种，一种是我自己写的各种分讨，另一种就是 CF 官方题解更好写的写法。

代码：

My_code：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const double eps = 1e-9;
double dp[2][305][1030][2];
int get(int flag,int x){
	if(flag && x == 0)	return 10;
	int tmp = x & 1,res = 0;
	while((x & 1) == tmp && x > 0){
		++res;
		x >>= 1;
	}
	return res;
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int x,k,p;scanf("%d%d%d",&x,&k,&p);
	double p1 = 1.0*p/100;
	double p2 = 1.0-p1;
	int y = x & ((1<<10)-1);
	x = (x - y) >> 10;
	int tmp = 0;
	if(x)	tmp = get(0,x);
	dp[0][tmp][y][x&1] = 1;
	for(int i=0; i<=k; i++){
		int lst = i & 1,now = lst ^ 1;
		memset(dp[now],0,sizeof(dp[now]));
		for(int j=0; j<=300; j++){
			for(int S=0; S<(1<<10); S++){
				for(int p=0; p<=1; p++){
					if(dp[lst][j][S][p] == 0)	continue;
					int T = S + 1;
					if(T & (1<<10)){
						if(p == 0)	dp[now][1][T&((1<<10)-1)][1] += dp[lst][j][S][p]*p2;
						else		dp[now][j][T&((1<<10)-1)][0] += dp[lst][j][S][p]*p2;
					}
					else{
						if(p == 0 && j)	dp[now][j][T][0] += dp[lst][j][S][p] * p2;
						else if(p == 1 && j)	dp[now][j][T][1] += dp[lst][j][S][p] * p2;
						else	dp[now][j][T][p] += dp[lst][j][S][p]*p2;
					}
					
					T = S << 1;
					if(T & (1<<10)){
						if(j && p == 1)	dp[now][j+1][T&((1<<10)-1)][1] += dp[lst][j][S][p] * p1;
						else	dp[now][1][T&((1<<10)-1)][1] += dp[lst][j][S][p] * p1;
					}	
					else{
						if(j && p == 1)	dp[now][1][T][0] += dp[lst][j][S][p] * p1;
						else if(j && p == 0)	dp[now][j+1][T][0] += dp[lst][j][S][p] * p1;
						else	dp[now][0][T][0] += dp[lst][j][S][p] * p1;
					}
				}
			}
		}
	}
	double ans = 0;
	int now = (k & 1);
	for(int j=0; j<=300; j++){
		for(int S=0; S<(1<<10); S++){
			for(int p=0; p<=1; p++){
				ans += dp[now][j][S][p] * get(j,S) * (S % 2 == 0);
				if(S == 0 && p == 0)
					ans += dp[now][j][S][p] * j;
			}
		}
	}
	printf("%.8f\n",ans);
	return 0;
}

CF_code：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const double eps = 1e-9;
double dp[2][1030][2][305];
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int x,k,p;scanf("%d%d%d",&x,&k,&p);
	double p1 = 1.0*p/100;
	double p2 = 1.0-p1;
	int S = 10,T = (1<<S)-1;
	int pmask = 0,plast = 0,pcnt = 0;
	pmask = x & T;
	plast = (x & (1<<S)) > 0;
	x >>= S;
	if(x != 0){
		while(x % 2 == plast){
			++pcnt;x /= 2;
		}
	}
	else	pcnt = 0;
	dp[0][pmask][plast][pcnt] = 1;
	for(int i=0; i<k; i++){
		int pre = i & 1,now = pre ^ 1;
		memset(dp[now],0,sizeof(dp[now]));
		for(int mask=0; mask<=T; mask++){
			for(int lst=0; lst<=1; lst++){
				for(int cnt=0; cnt<=300; cnt++){
					{
						int nmask = (mask<<1) & T;
						int nlast = ((mask<<1) & (1<<S)) > 0;
						int ncnt = cnt;
						if(nlast == lst)	ncnt++;
						else	ncnt = 1;
						dp[now][nmask][nlast][ncnt] += dp[pre][mask][lst][cnt] * p1;
					}
					
					{
						int nmask = mask + 1;
						if(nmask == (1<<S)){
							if(lst == 1)	dp[now][0][0][cnt] += dp[pre][mask][lst][cnt] * p2;
							else	dp[now][0][1][1] += dp[pre][mask][lst][cnt] * p2;
						}
						else	dp[now][nmask][lst][cnt] += dp[pre][mask][lst][cnt] * p2;
					}
				}
			}
		}
	}
	
	int now = k & 1;
	double ans = 0;
	for(int mask=0; mask<=T; mask++){
		for(int lst=0; lst<=1; lst++){
			for(int cnt=0; cnt<=300; cnt++){
				int res = 0;
				int nmask = mask;
				if(nmask != 0){
					while(nmask % 2 == 0)	++res,nmask/=2;
				}
				else{
					res = S;
					if(lst == 0)	res += cnt;
				}
				ans += dp[now][mask][lst][cnt] * res;
			}
		}
	}
	printf("%.8f\n",ans);
	return 0;
}

CF743E Vladik and cards

题目描述：

给定序列 $A$，$A$ 中元素均为 $[1,8]$ 中的整数，求一个 $A$ 的最长子序列且满足以下 $2$ 个条件，并输出其长度。

1. $[1,8]$ 中每 $2$ 个整数的出现次数之差不超过 $1$，若没有出现则认为出现次数为 $0$。

2. 每种数字的全部元素必须连续，即 $222333$ 是合法的，$223322$ 不合法

$1 \le n \le 1000$

题目分析：

首先 $n \le 1000$，所以看上去就支持 $n^2$，所以可以直接枚举 $[1,8]$ 中数的出现次数 $p$，这样每个数就只能出现 $p$ 或 $p+1$ 次。

但是注意到一点，因为若存在一种出现次数均大于等于 $p$ 的方案，则必然存在一种出现次数为 $p-1,p-2,\cdots$ 的方案，也就是合法的出现次数满足单调性，可以直接二分，这里的复杂度就是 $O(\log n)$。

下面就是考虑怎么判定，我们的决策显然就是这个点选择或者不选择，也就是可以设 $dp[i][S][j][k]$ 表示考虑了前 $i$ 个位置，位置 $i$ 必选，当前集合 $S$ 内的数满足了数量限制，最后一个要选择的数为 $j$ 且已经选择了 $k$ 个的最长子序列长度，这样显然过不去。

因为我们选择的是一个子序列，所以一个显然的贪心就是能选则选，所以只需要我们确定了下一段要选择哪个数，最优方案就一定确定了，也就是前 $p$ 次出现或前 $p+1$ 次出现的时候。

所以就可以直接设 $dp[i][S]$ 表示考虑了前 $i$ 个位置，位置 $i$ 必选，当前集合 $S$ 内的数满足了数量限制的最长子序列长度，假设我们下一个要选择的为 $j$，可以预处理出来从 $i$ 开始第 $p$ 或 $p+1$ 次 $j$ 的出现位置，直接从 $dp[i][S]$ 转移到对应位置即可。

代码：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3+5;
void chkmax(int &a,int b){
	a = max(a,b);
}
int n,a[N],val[N],r1[10][N],r2[10][N],dp[N][500];
void get(int *r,int x,int y){
	for(int i=1; i<=n; i++){
		if(a[i] == x)	val[i] = 1;
		else	val[i] = 0;
	}
	int sum = 0,R = 1;
	for(int l=0; l<=n; l++){
		r[l] = n + 1;
		if(l != 0)	sum -= val[l];
		while(R <= n && sum < y)	sum += val[R],++R;
		if(sum == y)	r[l] = R-1;
	}
}
int chk(int val){
	for(int i=1; i<=8; i++){
		get(r1[i],i,val);
		get(r2[i],i,val+1);
	}
	memset(dp,-0x3f,sizeof(dp));
	dp[0][0] = 0;
	for(int i=0; i<=n; i++){
		for(int S=0; S<(1<<8); S++){
			for(int j=1; j<=8; j++){
				if(((S >> (j-1)) & 1))	continue;
				chkmax(dp[r1[j][i]][S|(1<<(j-1))],dp[i][S]+val);
				chkmax(dp[r2[j][i]][S|(1<<(j-1))],dp[i][S]+val+1);
			}
		}
	}
	int ans = -1;
	for(int i=1; i<=n; i++)	ans = max(ans,dp[i][(1<<8)-1]);
	return ans;
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	scanf("%d",&n);
	for(int i=1; i<=n; i++)	scanf("%d",&a[i]);
	int ans = 0;
	int l = 0,r = 1000;
	while(l <= r){
		int mid = (l + r) >> 1;
		int res = chk(mid);
		if(res > 0)	ans = max(ans,res),l = mid + 1;
		else	r = mid - 1;
	}
	printf("%d\n",ans);
	return 0;
}

CF1789F Serval and Brain Power

题目描述：

定义一个字符串 $T$ 是好的，当且仅当存在字符串 $T'$ 和整数 $k(k\geq2)$，使得 $T$ 可以由 $k$ 个 $T'$ 首尾相接得到。

例如，字符串 $\texttt{gogogo}$ 就是好的，因为它可以由 $3$ 个字符串 $\texttt{go}$ 首尾相接得到；而 $\texttt{power}$ 就不是好的。

给定仅包含小写英文字母的字符串 $S$。

你需要求出 $S$ 最长的好的子序列（不一定连续）的长度，特别的如果 $S$ 没有好的子序列，答案为 $0$。

$1 \le |S| \le 80$

题目分析：

看到 $|S| \le 80$ 就很想暴力，一点观察就是我们只需要在意 $k$ 为素数的情况，因为如果不是则其字符串必然可以表示为对应的素数个字符串的拼接。

对于 $k$ 比较大的情况，感觉上就是合法的 $T'$ 的长度不会很长，进一步观察就是必然存在一个 $T'$ 使得其第一个字母出现的位置与最后一个字母出现的位置的距离不超过 $\frac{n}{k}$，因为如果所有的都超过，那么总长度就超过 $n$ 了不合法。

所以我们此时就可以直接枚举所有长度为 $\frac{n}{k}$ 的区间，这样合法的 $T'$ 必然是这些区间的子序列，知道了 $T'$ 那么最优的个数就是直接贪心匹配即可。而当我们枚举所有长度为 $len$ 的区间的子序列的时候，必然已经包含了所有长度小于 $len$ 的区间的最序列，所以我们只需要挑选一个尽可能小的 $k$ 枚举即可，复杂度 $O(n^22^{\frac{n}{k}})$，大概取 $k = 5$ 枚举长度为 $16$ 的区间即可。

对于 $k$ 比较小的情况我们就不可能知道 $T'$ 究竟是什么，所以要求枚举一些信息之后能算出来最优的 $T'$ 是什么，最优的 $T'$ 就是一个类似 $LCS$ 的东西，所以我们就可以直接枚举这 $k$ 段的分界线是什么，然后对于这 $k$ 段求 $LCS$ 即可，复杂度 $O(n^{2k-1})$，因为在枚举的过程中有各种各样的除以 $2$ 所以大概会带接近 $\frac{1}{100}$ 的常数，可以通过 $k \le 3$ 的部分。

直接这样做的话对于 $k \ge 5$ 的部分会比较卡，可以钦定如果我们当前枚举的区间为 $[l,r]$ 则 $T'$ 必须包含点 $l$ 就可以砍掉一半的时间就可以通过了。

代码：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int N = 85;
int n,ans = 0;
char s[N];
void chkmax(int &a,int b){
	a = max(a,b);
}
namespace sub1{   //k=2
	int dp[N][N];
	void work(){
		for(int mid=1; mid<n; mid++){
			for(int L=1; L<=mid; L++){
				for(int R=mid+1; R<=n; R++){
					dp[L][R] = 0;
					if(s[L] == s[R])	dp[L][R] = dp[L-1][R-1] + 1;
					chkmax(dp[L][R],max(dp[L-1][R],dp[L][R-1]));
				}
			}
			chkmax(ans,dp[mid][n]*2);
			for(int L=1; L<=mid; L++){
				for(int R=mid+1; R<=n; R++){
					dp[L][R] = 0;
				}
			}
		}
	}
}
namespace sub2{   //k=3
	int dp[N][N][N];
	void work(){
		for(int l=1; l<=n; l++){
			for(int r=l+1; r<n; r++){
				for(int L=1; L<=l; L++){
					for(int M=l+1; M<=r; M++){
						for(int R=r+1; R<=n; R++){
							dp[L][M][R] = 0;
							if(s[L] == s[M] && s[M] == s[R])	dp[L][M][R] = dp[L-1][M-1][R-1]+1;
							chkmax(dp[L][M][R],max(dp[L-1][M][R],max(dp[L][M-1][R],dp[L][M][R-1])));
						}
					}
				}
				chkmax(ans,dp[l][r][n]*3);
				for(int L=1; L<=l; L++){
					for(int M=l+1; M<=r; M++){
						for(int R=r+1; R<=n; R++){
							dp[L][M][R] = 0;
						}
					}
				}
			}
		}
	}
}
namespace sub3{  //k >= 5
	void solve(int l,int r){
		int len = (r - l + 1);
		for(int S=1; S<(1<<len); S+=2){
			int sz = __builtin_popcount(S);
			vector<char> v;
			for(int i=1; i<=len; i++){
				if((S >> (i-1)) & 1)
					v.push_back(s[l+i-1]);
			}
			int now = 0,res = 0;
			for(int i=1; i<=n; i++){
				if(v[now] == s[i])	++now;
				if(now == sz){
					++res;now = 0;
				}
			}
			if(res >= 5)	chkmax(ans,res*sz);
		}
	}
	void work(){
		for(int i=1; i<=n; i++){
			solve(i,min(i+15,n));
		}
	}
}
int main(){
	scanf("%s",s+1);
	n = strlen(s+1);
	sub1::work();
	sub2::work();
	sub3::work();
	printf("%d\n",ans);
	return 0;
}

CF1799H Tree Cutting

题目描述：

你有一棵 $n$ 个节点的树。英雄需要进行 $k$ 次以下操作：选择其中一条边，删除它，并选择剩下的两个部分中的其中一个进行删除，输出剩余部分中的节点数。

你将会得到一颗初始的树和一个序列。你需要找到一种使得序列与所给序列相等的操作方案数量。

答案可能较大，请对 $998244353$ 取模。如果边或者剩余部分的选择不同，则将其视为不同的方案。

$2 \le n \le 5000$，$1 \le k \le \min(6,n-1)$

题目分析：

直接观察好像没啥性质，最多就是在任意时刻我们留下的树都是原树的一个连通块，而这个题恶心的一个地方就是在于切掉一条边的时候我们无法确定保留的是什么，也就是根本没办法进行 $dp$ 转移。

所以想想有什么办法可以解决这个问题，注意到 $n \le 5000$ 所以感觉可以直接枚举一个点 $i$ 钦定这个点在最后的点集 $V_k$ 中，然后将 $i$ 理解为树的根，这样我们每次切一条边保留的都是靠上的部分看上去就能做了。

注意到我们删边顺序也是有讲究的，一条边在不同的时刻删是不一样的，并且对于点 $u$ 的子树来说，如果要删除边 $(u,fa_u)$ 则必然是在这棵子树内部所有的边都删完的情况下才删除的。

那么我们该如何满足任意时刻树的大小等于序列对应数的大小呢，其实只需要在任意时刻变化量与对应的变化量大小相等即可，所以如果子树 $u$ 内部删除的边为 $S$ 那么边 $(u,fa_u)$ 在 $S$ 里面且合法就是要求除了这一条边之外的 $S$ 合法并且 $\sum_{i \in S} s_i - s_{i-1} = sz_u$，就是经过这些次切割之后正好没了，就是变化量是正确的。

所以我们最终的状态就是 $dp[i][S]$ 表示在 $i$ 的子树内，选择了集合 $S$ 内的边的方案数，这里的 $S$ 是指的 $1 \sim k$ 这些边的下标，而非树边对应的下标 $1 \sim n-1$。

添加一棵子树是简单的，如果是选择 $(i,fa_i)$ 这条边的话由上述分析可得这条边必然是第 $\max(S)$ 条被选择边，所以根据这个转移即可。

然后我们需要换根得到以每个点为根的答案，这里的换根写法就是我们维护出 $dp2_u$ 代表 $u$ 的父亲这棵子树的信息，然后就直接把这棵子树当成正常的子树合并即可，维护这颗子树的信息也是简单的。

注意到对于任意一个方案都会被计算 $s_k$ 次，所以就是对于以每个点为根的答案加和之后除以 $s_k$ 即可。

代码：

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5005;
const int MOD = 998244353;
struct node{
	int f[70];
	node(){
		memset(f,0,sizeof(f));
	}
}dp1[N],dp2[N],dp3[N],pre[N],suf[N];
struct edge{
	int nxt,to;
	edge(){}
	edge(int _nxt,int _to){
		nxt = _nxt,to = _to;
	}
}e[2*N];
int n,mask,cnt,head[N],sz[N],sum[N],s[N];
vector<int> v[N];
void add_edge(int from,int to){
	e[++cnt] = edge(head[from],to);
	head[from] = cnt;
}
int power(int a,int b){
	int res = 1;
	while(b){
		if(b & 1)	res = res * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return res;
}
void add(int &a,int b){
	a = (a + b)%MOD;
}
int highbit(int x){
	int now = 0;
	while(x){
		x >>= 1;
		++now;
	}
	return now - 1;
}
node merge(node a,node b){
	node ans;
	for(int i=0; i<=mask; i++){
		for(int j=i; ; j = (j-1) & i){
			add(ans.f[i],a.f[j]*b.f[i^j]%MOD);
			if(j == 0)	break;
		}
	}
	return ans;
}
node cut_fath(node a,int sz){
	node ans;
	for(int i=0; i<=mask; i++){
		add(ans.f[i],a.f[i]);
		if(sum[i] == sz)	add(ans.f[i],a.f[i^(1<<highbit(i))]);
	}
	return ans;
}
void dfs1(int now,int fath){
	sz[now] = 1;
	for(int i=head[now]; i; i=e[i].nxt){
		int to = e[i].to;
		if(to == fath)	continue;
		v[now].push_back(to);
		dfs1(to,now);
	}
	dp1[now].f[0] = 1;
	for(auto to : v[now]){
		dp1[now] = merge(dp1[now],dp1[to]);
		sz[now] += sz[to]; 
	}
	dp1[now] = cut_fath(dp1[now],sz[now]);
}
void dfs2(int now){
	int size = v[now].size();
	for(int i=0; i<size; i++){
		pre[i] = dp1[v[now][i]];
		if(i > 0)	pre[i] = merge(pre[i],pre[i-1]);
	}
	for(int i=size-1; i>=0; i--){
		suf[i] = dp1[v[now][i]];
		if(i < size-1)	suf[i] = merge(suf[i],suf[i+1]);
	}
	dp3[now] = dp2[now];
	if(size>0)	dp3[now] = merge(dp3[now],pre[size-1]);
	for(int i=0; i<size; i++){
		int to = v[now][i];
		dp2[to] = dp2[now];
		if(i > 0)	dp2[to] = merge(dp2[to],pre[i-1]);
		if(i < size-1)	dp2[to] = merge(dp2[to],suf[i+1]);
		dp2[to] = cut_fath(dp2[to],n-sz[to]);
	}
	for(auto to : v[now])	dfs2(to);
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	scanf("%lld",&n);
	for(int i=1; i<n; i++){
		int from,to;scanf("%lld%lld",&from,&to);
		add_edge(from,to);add_edge(to,from);
	}
	int k;scanf("%lld",&k);
	mask = (1<<k)-1;
	s[0] = n;
	for(int i=1; i<=k; i++)	scanf("%lld",&s[i]);
	for(int i=1; i<=mask; i++){
		int high = highbit(i)+1;
		sum[i] = sum[i^(1<<(high-1))] + (s[high-1] - s[high]); 
	}
	dfs1(1,0);
	dp2[1].f[0] = 1;
	dfs2(1);
	int ans = 0;
	for(int i=1; i<=n; i++)	add(ans,dp3[i].f[mask]);
	printf("%lld\n",ans * power(s[k],MOD-2) % MOD);
	return 0;
}

Atcoder ARC078F Mole and Abandoned Mine

题目描述：

给一个 $n$ 个点 $m$ 条边的无向连通图（不存在自环或重边），每条边有一个边权，要求割掉若干条边，使 $1$ 到 $n$ 只有 $1$ 条路径（不经过重复点），问割掉的边权和最小是多少。

$2 \le n \le 15$

题目分析：

首先为了方便计算，可以将最小化割边权值改为最大化保留边权值。

考虑最后形成的图是什么样子的，就是一条链，链上的点 $i$ 挂着点集 $S$ 要求保留的边中只有 $S$ 内部的边和 $S,i$ 之间的边。

而我们只在意之前已经选中了哪些点以及链的最后一个点是什么，也就是可以设 $dp[i][S]$ 表示链上最后一个点为 $i$ 选择了集合 $S$ 内的点的保留的最大权值。

转移就是可以分步进行，先考虑转移下一个加入的点，再考虑在最后一个点上挂着的 $S$。

为了转移方便我们要预处理出来 $f[S]$ 表示点集 $S$ 内部的边的权值和。

这样的话复杂度就是 $O(n3^n + n^22^n)$。

代码：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int N = 16;
int G[N][N],f[1<<N],dp[1<<N][N];
bool flag[1<<N][N];
vector<int> to[N];
void chkmax(int &a,int b){
	a = max(a,b);
}
int main(){
	int n,m;scanf("%d%d",&n,&m);
	int sum = 0;
	for(int i=1; i<=m; i++){
		int u,v,w;scanf("%d%d%d",&u,&v,&w);
		G[u][v] = G[v][u] = w;sum += w;
		to[u].push_back(v);
		to[v].push_back(u);
	}
	for(int S=0; S<(1<<n); S++){
		vector<int> p;p.clear();
		for(int i=1; i<=n; i++){
			if((S >> (i-1)) & 1)
				p.push_back(i);
		}
		for(auto i : p){
			for(auto j : p){
				f[S] += G[i][j];
			}
		}
		f[S] /= 2;
	} 
	int mask = (1<<n) - 1;
	memset(dp,-0x3f,sizeof(dp));
	dp[1][1] = 0;
	for(int S=1; S<(1<<n); S++){
		vector<int> p;p.clear();
		for(int i=1; i<=n; i++){
			if((S >> (i-1)) & 1)
				p.push_back(i);
		}
		for(int last : p){
			for(auto nlast : to[last]){  //加入一个点 
				if((S>>(nlast-1)) & 1)	continue;
				chkmax(dp[S|(1<<(nlast-1))][nlast],dp[S][last] + G[last][nlast]);
			}
			for(int T=(mask^S); T; T=(T-1)&(mask^S)){   //加入一个挂在最后一个点的集合 
				chkmax(dp[S|T][last],dp[S][last] + f[T|(1<<(last-1))]);
			} 
		}
	}
	printf("%d\n",sum - dp[(1<<n)-1][n]);
	return 0;
}

CF1523F Favorite Game

题目描述：

考虑一个在二维平面上的游戏，玩家选择一个整点并在 $0$ 时刻到达，接下来每秒玩家可以不动或向上或下或左或右走一步。

有 $n$ 个传送门第 $i$ 个在 $(xa_i,ya_i)$，初始时传送门都未被激活，当玩家到达一个未激活传送门时此传送门被激活，之后玩家在任意时刻任意位置都可以立刻瞬移到这个传送门。有 $m$ 个任务第 $i$ 个任务要求玩家在 $t_i$ 时刻时恰好在 $(xb_i,yb_i)$ 位置。

求玩家最多可以完成几个任务。

$n\le 14,m\le 100$。

题目分析：

首先我们合法的逗留点一定是只有这 $n+m$ 个有用的点，因为在其他的点的逗留都可以转化为在这些点的逗留，而 $n \le 14$ 看上去就可以直接状压放到 $dp$ 状态中。

所以也就是可以设 $dp[i][j][S]$ 代表当前在点 $i$ 完成了 $j$ 个任务，已经激活的传送门集合为 $S$ 的最小花费时间。

但是这个东西状态数就已经达到了 $O(m \times (n+m) \times 2^n)$ 就比较爆炸。

我们不妨考虑将传送门的点与任务点分开考虑。

因为如果我们当前在传送门上，我们就不用在意到底在哪个传送门上，也就是可以直接设 $f[S][i]$ 表示激活的传送门集合为 $S$ 当前完成了 $i$ 个任务的最小花费时间。

如果我们当前在某个任务点上，我们就不用在意时间，因为时间必然等于 $t_i$，也就是可以直接设 $g[S][i]$ 表示激活的传送门集合为 $S$ 当前恰好完成了任务 $i$ 最多完成多少个任务。

转移就是考虑下一步是走到某个传送门还是走到某个任务点，就是 $f,g$ 互相转移即可。

为了方便我们也应预处理出 $dis_a[S][i]$ 和 $dis_b[S][i]$ 分别表示已激活的传送门集合为 $S$ 我们当前站在某个传送门上到达第 $i$ 个传送门/任务点的最小花费时间是多少。

这样的话复杂度就是 $O(2^n \times (m^2+n^2+nm))$，可以通过。

转移的时候就是要注意我们传送到传送门不需要花费时间，以及我们也可以不用传送门直接赶路。

代码：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int N = 105;
const int INF = 1e9+5;
struct node{
	int x,y,t;
}a[N],b[N];
int dis_a[1<<16][N],dis_b[1<<16][N],f[1<<16][N],g[1<<16][N];
void chkmin(int &a,int b){a = min(a,b);}
void chkmax(int &a,int b){a = max(a,b);}
bool cmp(node a,node b){return a.t < b.t;}
int dis(node a,node b){return abs(a.x-b.x)+abs(a.y-b.y);}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("ans.txt","w",stdout);
	int n,m;scanf("%d%d",&n,&m);
	for(int i=1; i<=n; i++)	scanf("%d%d",&a[i].x,&a[i].y);
	for(int i=1; i<=m; i++)	scanf("%d%d%d",&b[i].x,&b[i].y,&b[i].t);
	sort(b+1,b+m+1,cmp);
	for(int S=0; S<(1<<n); S++){
		for(int i=1; i<=n; i++){
			dis_a[S][i] = INF;
			for(int j=1; j<=n; j++){
				if((S>>(j-1)) & 1)	chkmin(dis_a[S][i],dis(a[i],a[j]));
			}
		}
		f[S][0] = INF;
		for(int i=1; i<=m; i++){
			dis_b[S][i] = INF;
			f[S][i] = INF;g[S][i] = -INF;
			for(int j=1; j<=n; j++){
				if((S>>(j-1)) & 1)	chkmin(dis_b[S][i],dis(a[j],b[i]));
			}
		}
	}
	//f[S][i] 代表传送门集合为 S，当前在某个传送门上，完成了 i 个任务的最小花费时间
	//g[S][i] 代表传送门集合为 T，当前恰好完成了第 i 个任务，最多完成多少个任务 
	for(int i=1; i<=n; i++)	f[(1<<(i-1))][0] = 0;
	for(int i=1; i<=m; i++)	g[0][i] = 1;
	for(int S=0; S<(1<<n); S++){   //注意一下四种分类讨论的顺序即可 
		//f -> f
		for(int i=0; i<=m; i++){
			if(f[S][i] == INF)	continue;
			for(int j=1; j<=n; j++){
				if((S>>(j-1)) & 1)	continue;
				chkmin(f[S|(1<<(j-1))][i],f[S][i]+dis_a[S][j]);
			}
		}
		//f -> g
		for(int i=0; i<=m; i++){
			if(f[S][i] == INF)	continue;
			for(int j=1; j<=m; j++){
				if(f[S][i]+dis_b[S][j] <= b[j].t){
					chkmax(g[S][j],i+1);
				}
			}
		}
		//g -> g
		for(int i=1; i<=m; i++){
			if(g[S][i] == -INF)	continue;
			for(int j=i+1; j<=m; j++){
				if(b[i].t+min(dis_b[S][j],dis(b[i],b[j]))<=b[j].t){
					chkmax(g[S][j],g[S][i]+1);
				}
			}
		}
		//g -> f
		for(int i=1; i<=m; i++){
			if(g[S][i] == -INF)	continue;
			for(int j=1; j<=n; j++){
				chkmin(f[S|(1<<(j-1))][g[S][i]],b[i].t+min(dis_a[S][j],dis(b[i],a[j])));
				//两种走法：走到传送门 -> 走过去；直接走过去
			}
		}
	}
	int ans = 0;
	for(int S=0; S<(1<<n); S++){
		for(int i=1; i<=m; i++){
			chkmax(ans,g[S][i]);
//			printf("g[%d][%d] = %d\n",S,i,g[S][i]);
//			printf("f[%d][%d] = %d\n",S,i,f[S][i]);
		}
	}	
	printf("%d\n",ans);
	return 0;
}

Atcoder ABC326F Robot Rotation

题目描述：

一个机器人位于坐标平面的原点，坐标平面的正 $x$ 轴指向右侧，正 $y$ 轴指向上方。最初，机器人面向 $x$ 轴正方向。

您将依次对 $i=1,\ldots,N$ 执行以下操作。

• 将机器人顺时针或逆时针旋转 $90$ 度。然后，机器人沿着它所面对的方向向前移动 $A_i$ 个单位。

能否选择旋转方向，使机器人在进行 $N$ 操作后位于坐标 $(X,Y)$ 处？

如果可以，请确定每次操作应选择顺时针还是逆时针方向。

$1\le N \le 80$，$1 \le A_i \le 10^7$，$-10^9 \le X,Y \le 10^9$

题目分析：

手摸一下就会发现：对于第奇数次操作必然是 $y$ 轴方向上的，对于第偶数次操作必然是 $x$ 轴方向上的，而且对于每一个操作我们都可以自由决定是朝向正方向还是反方向。

所以就是两个相同的问题，先只考虑 $x$ 轴方向的问题。

这样的话就满足 $N \le 40$ 感觉上就可以折半搜索，发现折半之后的合并是很简单的，因为我们只需要对于前一半搜出来的每一个数 $p$ 判断后一半是否存在 $X-p$ 即可，这样的话使用 map 就可以做到 $O(2^{\frac{n}{4}} \times \log 2^{\frac{n}{4}}) = O(\frac{n}{4} \times 2^{\frac{n}{4}})$ 的复杂度，可以通过本题。

也可以通过一些优化做到 $O(2^{\frac{n}{4}})$ 的复杂度。

代码：

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100;
unordered_map<int,int> mp1,mp2;
int sz_x,sz_y,x[N],y[N],a[N];
void dfs1(int *p,int l,int r,int val1,int val2){
	if(l == r + 1){
		mp1[val2] = val1;
		return;
	}
	dfs1(p,l+1,r,val1<<1,val2-p[l]);
	dfs1(p,l+1,r,val1<<1|1,val2+p[l]);
}
void dfs2(int *p,int l,int r,int val1,int val2){
	if(l == r + 1){
		mp2[val2] = val1;
		return;
	}
	dfs2(p,l+1,r,val1<<1,val2-p[l]);
	dfs2(p,l+1,r,val1<<1|1,val2+p[l]);
}
int solve(int *p,int n,int X){
	if(n == 0){
		if(X == 0)	return 0;
		return -1;
	}
	if(n == 1){
		if(p[1] == X)	return 1;
		if(p[1] == -X)	return 0;
		return -1;
	}
	mp1.clear();mp2.clear();
	int mid = (n / 2);
	reverse(p+1,p+mid+1);   //reverse 是因为二进制下第一个访问到的在最高位，我们要让他在最低位。 
	reverse(p+mid+1,p+n+1);
	dfs1(p,1,mid,0,0);
	dfs2(p,mid+1,n,0,0);
	for(auto p : mp1){
		if(mp2.count(X-p.first)){
			return p.second | (mp2[X-p.first] << mid);
		}
	}
	return -1;
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int n,X,Y;scanf("%lld%lld%lld",&n,&X,&Y);
	for(int i=1; i<=n; i++)	scanf("%lld",&a[i]);
	for(int i=1; i<=n; i+=2)	y[++sz_y] = a[i];
	for(int i=2; i<=n; i+=2)	x[++sz_x] = a[i];
	int ans_y = solve(y,sz_y,Y);
	int ans_x = solve(x,sz_x,X);
	if(ans_x == -1 || ans_y == -1){
		printf("No\n");
		return 0;
	}
	printf("Yes\n");
	int now = 1;
	for(int i=1; i<=n; i++){
		if(i & 1){
			if(ans_y % 2 == now % 2)	printf("L");
			else	printf("R");
			now = ans_y % 2;ans_y >>= 1;
		}
		else{
			if(ans_x % 2 == now % 2)	printf("R");
			else	printf("L");
			now = ans_x % 2;ans_x >>= 1;
		}
	}
	return 0;
}

Topcoder YamanoteLine

题目描述：

有一个 $n$ 个点的环，任意两个点之间的距离为某个正整数，但不给定。

有如下两种限制：

• $S$ 到 $T$ 的顺时针距离不超过 $l$。
• $S$ 到 $T$ 的顺时针距离不小于 $l$。

要求可能的总环长的数量。

$1 \le n \le 50$

题目分析：

首先这两种限制就很差分约束，我们可以断环为链，设 $dis_i$ 表示前 $i$ 个点的长度，环长为 $X$，这样若 $l < r$ 则 $l$ 到 $r$ 的顺时针距离为 $dis_r - dis_l$ 否则为 $dis_r - dis_l + X$，这样的话根据上面的限制也很好写成差分约束的 $dis_a \le dis_b + C$ 的形式。

但是我们并不能直接枚举 $X$，那么也就是说合法的 $X$ 必然满足某些性质，大胆猜测 $X$ 必然是一段连续的区间。

证明的话就是考虑：给定 $X$ 如果差分约束有解当且仅当不存在负环，所以可以将所有的环拿出来，其权值和必然为 $kX + b$ 的形式，因为 $k$ 可以为正数、负数、零，所以每一个环的限制都形如 $X \le h$ 或者 $X \ge h$ 所有的限制合并在一起就是 $l \le X \le r$，直接模拟这个过程就能得到一种复杂度很劣的做法。

那么我们考虑用类似二分的方式找到这个合法的区间，关键其实就是找到某一个点是合法的，那么就是我们要能判断如果当前点不合法，那么合法的区间在其左边还是右边。

如果当前的 $X$ 不合法，那么必然存在一个环满足 $kX + b < 0$，此时如果 $k < 0$ 那么只有减小 $X$ 才能使得这个值变大，如果 $k > 0$ 那么只有增大 $X$ 才能使得这个值变大，如果 $k = 0$ 那么无解。

所以我们只需要找到一个负环就可以直接判断合法的区间在左边还是右边，这样就可以直接二分得到一个合法点，找到了合法点区间的左右端点就很好二分了。

代码：

咕咕咕