devbox
笔触狂放9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

2020牛客暑期多校训练营（第五场）题解_2020牛客暑期多校训练营(第五场

作者：笔触狂放9 | 2024-08-16 03:51:18

赞

踩

2020牛客暑期多校训练营(第五场

文章目录

A. Portal

给一张 n n n 个点 m m m 条边的无向图，边有长度，有 k k k 个任务，每个任务要去 a i a_i ai​ 捡一个物品送到 b i b_i bi​，你可以开传送门，每个时刻最多只能有两个传送门，你可以随时在脚下开个传送门，也可以随时关闭图中任意一个传送门，假如你脚下有一个传送门，你可以从这个传送门无代价地走到另一个传送门，求按顺序完成所有任务的最小代价（即距离）。

将每个任务需要走到的点记为关键点，考虑暴力 dp \text{dp} dp 的话，设 f [ i ] [ j ] [ k ] f[i][j][k] f[i][j][k] 表示走到第 i i i 个关键点，两个传送门分别在 j , k j,k j,k 的最小代价。

容易发现，每次使用传送门时，总有一个传送门在脚下，这等价于我们手里总有一个传送门，用的时候就放在脚下。所以只需要记录另外一个传送门的位置在哪里就好，状态就只有两维 f [ i ] [ j ] f[i][j] f[i][j]。为了方便，记第 i i i 个关键点为 c [ i ] c[i] c[i]。

f [ i ] [ j ] f[i][j] f[i][j] 的 dp \text{dp} dp 转移：

  1. 直接从 c [ i ] c[i] c[i] 走到 c [ i + 1 ] c[i+1] c[i+1]。
  2. 传送到 j j j，再走到 c [ i + 1 ] c[i+1] c[i+1]。
  3. 将传送门放到 k k k 点，再走到 c [ i + 1 ] c[i+1] c[i+1]。
  4. 将传送门放在 k k k，传送到 j j j，再去 c [ i + 1 ] c[i+1] c[i+1]。
  5. 传送到 j j j，将传送门放在 k k k，再去 c [ i + 1 ] c[i+1] c[i+1]。

总之就是大力分类讨论一下就做完了。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 610
#define ll long long

int n,m,q,c[maxn];
ll dis[maxn][maxn],f[maxn][maxn];
void chkmin(ll &x,ll y){if(y<x)x=y;}

int main()
{
	scanf("%d %d %d",&n,&m,&q);
	memset(dis,63,sizeof(dis));
	for(int i=1;i<=n;i++)dis[i][i]=0;
	for(int i=1,x,y,z;i<=m;i++){
		scanf("%d %d %d",&x,&y,&z);
		chkmin(dis[x][y],z);
		chkmin(dis[y][x],z);
	}
	for(int k=1;k<=n;k++)//floyd
	for(int i=1;i<=n;i++)if(i!=k)
	for(int j=1;j<=n;j++)if(j!=i&&j!=k)
	if(dis[i][j]>dis[i][k]+dis[k][j])dis[i][j]=dis[i][k]+dis[k][j];
	for(int i=1,x,y;i<=q;i++)scanf("%d %d",&x,&y),c[i*2-1]=x,c[i*2]=y;
	memset(f,63,sizeof(f));c[0]=1;f[0][1]=0;
	for(int i=0;i<2*q;i++){
		int x=c[i],y=c[i+1];
		for(int j=1;j<=n;j++){
			chkmin(f[i+1][j],f[i][j]+dis[x][y]);
			chkmin(f[i+1][j],f[i][j]+dis[j][y]);
			for(int k=1;k<=n;k++){
				chkmin(f[i+1][k],f[i][j]+dis[x][k]+dis[k][y]);
				chkmin(f[i+1][k],f[i][j]+dis[x][k]+dis[j][y]);
				chkmin(f[i+1][k],f[i][j]+dis[j][k]+dis[k][y]);
			}
		}
	}
	ll ans=1e18;
	for(int i=1;i<=n;i++)chkmin(ans,f[2*q][i]);
	printf("%lld",ans);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43

B. Graph

给出一棵树，边有边权，你可以增加或减少边，增加边时，增加的边形成的环需要保证异或和为 0 0 0，减少边时，需要保证减少了边后图依然连通，求若干次操作后形成的图的最小边权和。

容易发现，增加一条边的代价，其实就是这条边连接的两点间路径的异或和，而不管如何改变树的结构，两点间的路径异或和是不会改变的，所以可以给每个点一个权值，然后就变成了这题。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 100010
#define ll long long
#define inf 999999999

int n,val[maxn];
struct edge{int y,z,next;}e[maxn<<1];
int first[maxn],len=0;
void buildroad(int x,int y,int z){e[++len]=(edge){y,z,first[x]};first[x]=len;}
void dfs(int x,int fa){
	for(int i=first[x],y;i;i=e[i].next)
	if((y=e[i].y)!=fa)val[y]=(val[x]^e[i].z),dfs(y,x);
}
struct node{
	int l,r,dep;
	node *ch[2];
	node(int Dep):l(inf),r(0),dep(Dep){ch[0]=ch[1]=NULL;}
}*root=new node(29);
void insert(int x){
	node *now=root;
	for(int i=29;i>=0;i--){
		int c=val[x]>>i&1;
		if(!now->ch[c])now->ch[c]=new node(i-1);
		now=now->ch[c];
		now->l=min(now->l,x);
		now->r=max(now->r,x);
	}
}
int ask(node *now,int x){
	if(now->dep<0)return 0;
	int c=x>>(now->dep)&1;
	if(now->ch[c])return ask(now->ch[c],x);
	else return ask(now->ch[c^1],x)+(1<<(now->dep));
}
ll solve(node *now){
	if(now->ch[0]&&now->ch[1]){
		int mi=inf;
		for(int i=now->ch[0]->l;i<=now->ch[0]->r;i++)mi=min(mi,ask(now->ch[1],val[i]));
		return solve(now->ch[0])+solve(now->ch[1])+mi+(1<<(now->dep));
	}
	if(now->ch[0])return solve(now->ch[0]);
	if(now->ch[1])return solve(now->ch[1]);
	return 0;
}

int main()
{
	scanf("%d",&n);for(int i=1,x,y,z;i<n;i++)
	scanf("%d %d %d",&x,&y,&z),x++,y++,buildroad(x,y,z),buildroad(y,x,z);
	dfs(1,0);sort(val+1,val+n+1);
	for(int i=1;i<=n;i++)insert(i);
	printf("%lld\n",solve(root));
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56

C. Easy

构造两个序列 a , b a,b a,b，满足 ∑ i = 1 k a i = n , ∑ i = 1 k b i = m \sum_{i=1}^k a_i=n,\sum_{i=1}^k b_i=m ∑i=1k​ai​=n,∑i=1k​bi​=m，其贡献是 ∏ i = 1 k min ⁡ ( a i , b i ) \prod_{i=1}^k \min(a_i,b_i) ∏i=1k​min(ai​,bi​)，求所有构造方案的总贡献和。

一开始想 dp \text{dp} dp，一通操作只能将 O ( k n 2 m 2 ) O(kn^2m^2) O(kn2m2) 的暴力优化成 O ( k n m ) O(knm) O(knm)，然后就自闭了。

正解考虑生成函数，令 n < m n<m n<m，先不管贡献，先求出总方案数，就是：
( x + x 2 + . . . + x n ) k ( y + y 2 + . . . + y m ) k (x+x^2+...+x^n)^k(y+y^2+...+y^m)^k (x+x2+...+xn)k(y+y2+...+ym)k

那么展开后 x n x^n xn 的系数就是 a a a 的方案， b b b 类似。但是现在要求出每种方案的贡献，先拎一位的生成函数出来看：
( x + x 2 + . . . + x n ) ( y + y 2 + . . . + y m ) (x+x^2+...+x^n)(y+y^2+...+y^m) (x+x2+...+xn)(y+y2+...+ym)

此时 x i y j x^iy^j xiyj 的系数是 1 1 1，而我们希望是 min ⁡ ( i , j ) \min(i,j) min(i,j)。有一个有用的性质，如果手玩过 dp \text{dp} dp 的话比较容易发现：满足 i − d > 0 , j − d > 0 i-d>0,j-d>0 i−d>0,j−d>0 的 d d d 的个数恰好有 min ⁡ ( i , j ) \min(i,j) min(i,j) 个。

那么只需要乘上 ( 1 + x y + x 2 y 2 + . . . + x n − k y n − k ) (1+xy+x^2y^2+...+x^{n-k}y^{n-k}) (1+xy+x2y2+...+xn−kyn−k)，这样 x i y j x^iy^j xiyj 的系数就会是 min ⁡ ( i , j ) \min(i,j) min(i,j) 了，因为每一个 x i − d y j − d x^{i-d}y^{j-d} xi−dyj−d 都可以通过乘上 x d y d x^dy^d xdyd 来对 x i y j x^iy^j xiyj 的系数产生贡献。

这是一位的， k k k 位的类似，就是：
( x + x 2 + . . . + x n ) k ( y + y 2 + . . . + y m ) k ( 1 + x y + x 2 y 2 + . . . + x n − k y n − k ) k (x+x^2+...+x^n)^k(y+y^2+...+y^m)^k(1+xy+x^2y^2+...+x^{n-k}y^{n-k})^k (x+x2+...+xn)k(y+y2+...+ym)k(1+xy+x2y2+...+xn−kyn−k)k

最后就是要求这个东西展开后 x n y m x^ny^m xnym 的系数，通过枚举 ( x y ) i (xy)^i (xy)i 的指数 i i i 表示第三项对指数的贡献，然后剩下的 x n − i y m − i x^{n-i}y^{m-i} xn−iym−i 要从前两项中拿，这个可以用插板法来求，答案就是：
∑ i = 0 n − k C i + k − 1 i C k + n − k − i − 1 n − k − i C k + m − k − i − 1 m − k − i \sum_{i=0}^{n-k} C_{i+k-1}^i C_{k+n-k-i-1}^{n-k-i} C_{k+m-k-i-1}^{m-k-i} i=0∑n−k​Ci+k−1i​Ck+n−k−i−1n−k−i​Ck+m−k−i−1m−k−i​
代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 2000010
#define mod 998244353

int T,n,m,k,ans;
int ksm(int x,int y){int re=1;for(;(y&1?re=1ll*re*x%mod:0),y;y>>=1,x=1ll*x*x%mod);return re;}
int fac[maxn],inv_fac[maxn];
void work(){
	fac[0]=inv_fac[0]=1;for(int i=1;i<=maxn-10;i++)fac[i]=1ll*fac[i-1]*i%mod;
	inv_fac[maxn-10]=ksm(fac[maxn-10],mod-2);
	for(int i=maxn-11;i>=1;i--)inv_fac[i]=1ll*inv_fac[i+1]*(i+1)%mod;
}
int C(int x,int y){return 1ll*fac[x]*inv_fac[y]%mod*inv_fac[x-y]%mod;}
void add(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);}

int main()
{
	work();
	scanf("%d",&T);while(T--)
	{
		scanf("%d %d %d",&n,&m,&k);
		if(n>m)swap(n,m);ans=0;
		for(int i=0;i<=n-k;i++)
		add(ans,1ll*C(k+i-1,i)*C(k+n-k-i-1,n-k-i)%mod*C(k+m-k-i-1,m-k-i)%mod);
		printf("%d\n",ans);
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

D. Drop Voicing

有一个序列，有两种操作：1、将倒数第二位的数放到第一位；2、将第一位的数放到最后一位。一段连续的 1 1 1 操作我们称为 multi-drops \text{multi-drops} multi-drops，问你最少进行几次 multi-drops \text{multi-drops} multi-drops 可以使的序列有序。

注意到一段任意长度的 1 1 1 操作相当于对 1 1 1 ~ n − 1 n-1 n−1 位的数进行旋转，一段 2 2 2 操作相当于对 1 1 1 ~ n n n 位的数进行旋转。

先进行若干次 1 1 1 ~ n n n 的旋转，再进行若干次 1 1 1 ~ n − 1 n-1 n−1 的旋转，可以使原序列中任意一个数的位置改变到任意位置。所以我们找出这个环内的最长上升子序列，然后将其他数插入到这个序列内就好了。

如果用 O ( n log ⁡ n ) O(n\log n) O(nlogn) 的做法求最长上升子序列，那么总时间复杂度是 O ( n 2 log ⁡ n ) O(n^2\log n) O(n2logn) 的，但是 n n n 只有 500 500 500，所以大可暴力搞。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 100010

int n,a[maxn],ans=1e9;
int f[maxn];
int work(){
	int re=0;
	for(int i=1;i<=n;i++){
		f[i]=1;
		for(int j=1;j<i;j++)
		if(a[i]>a[j])f[i]=max(f[i],f[j]+1);
		re=max(re,f[i]);
	}
	return re;
}
void move(){
	int p=a[1];
	for(int i=1;i<n;i++)a[i]=a[i+1];
	a[n]=p;
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)ans=min(ans,n-work()),move();
	printf("%d",ans);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31

E. Bogo Sort

有一个Tonnnny_sort函数，内容是：while(序列未有序)shuffle(该序列)。shuffle的规则是，给定一个 1 1 1 ~ n n n 的排列 p p p，将序列中第 i i i 位的数放到 p i p_i pi​ 位置，问有多少个序列可以通过Tonnnny_sort变得有序。

将 1 1 1 ~ n n n 当成原始序列，能shuffle出的所有序列就是答案。容易发现答案就是置换 p p p 中所有循环的长度的 l c m \mathrm{lcm} lcm，套个高精度就做完了。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 100010

int n,p[maxn],ma[maxn];
struct GJD{
	int a[maxn],len;
	GJD():len(1){memset(a,0,sizeof(a));}
	void jinwei(){
		for(int i=1;i<=len;i++){
			if(i>maxn-10){len=maxn-10;break;}
			if(a[i]>9){
				a[i+1]+=a[i]/10;
				a[i]%=10;
				if(i==len)len++;
			}
		}
	}
	void operator *=(int B){
		for(int i=1;i<=len;i++)a[i]*=B;
		jinwei();
	}
	void print(){for(int i=min(len,n);i>=1;i--)printf("%d",a[i]);}
}ans;
int go(int x){
	int tot=1;
	for(int i=p[x],j;i!=x;j=p[i],p[i]=0,i=j)tot++;
	p[x]=0;return tot;
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&p[i]);
	ans.a[1]=1;
	for(int i=1;i<=n;i++)if(p[i]){
		int c=go(i);
		for(int j=2;j<=c;j++){
			if(c%j==0){
				int tot=0;
				while(c%j==0)c/=j,tot++;
				ma[j]=max(ma[j],tot);
			}
		}
		if(c>1)ma[c]=max(ma[c],1);
	}
	for(int i=2;i<=n;i++)while(ma[i]--)ans*=i;
	ans.print();
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51

F. DPS

给出每个人的分数，按照某个规则画出所有人的分数柱状图。

大模拟，代码如下：

#include <cstdio>
#include <cmath>
#define maxn 110

int n,d[maxn],ma=0;

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&d[i]);
		if(d[i]>ma)ma=d[i];
	}
	for(int i=1;i<=n;i++){
		int s=ceil(50.0*d[i]/ma);
		printf("+");for(int j=1;j<=s;j++)printf("-");printf("+\n");
		printf("|");for(int j=1;j<s;j++)printf(" ");if(s)printf("%c",d[i]==ma?'*':' ');printf("|%d\n",d[i]);
		printf("+");for(int j=1;j<=s;j++)printf("-");printf("+\n");
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

G. Greetings Souvenir

给出一棵树，每个点有一个颜色 c i c_i ci​，现在要为每个点选一个数 b i b_i bi​，令 d i d_i di​ 表示 i i i 子树内有多少个点的颜色等于 b i b_i bi​，那么这个点的贡献 v a l [ i ] = d i × b i val[i]=d_i\times b_i val[i]=di​×bi​，求 max ⁡ { mex { v a l [ i ] ∣ i ∈ [ 1 , n ] } } \max\{\text{mex}\{val[i]|i\in[1,n]\}\} max{mex{val[i]∣i∈[1,n]}}。

显然答案不可能超过 n n n，所以大于 n n n 的 v a l val val 是不需要统计的，那么就可以用 b i t s e t bitset bitset 加类似 dsu on tree \text{dsu on tree} dsu on tree 的搞法就可以求出每个点能给出的贡献集合，也可以对每种颜色建虚树来搞，代码中选择了后者，原因往下看就懂了。

这样我们就可以得到一张二分图，左边 n n n 个点对应树上的点，右边 n + 1 n+1 n+1 个点表示贡献 0 0 0 ~ n n n，如果点 i i i 可以得到贡献 j j j，那么就连一条边，然后二分跑最大流就可以得到答案。

但事实上边数可以被卡到 n 2 n^2 n2，所以上面的搞法并不能过。

注意到颜色 c c c 的虚树上对于一条父子边 ( f a , x ) (fa,x) (fa,x)，令 s z sz sz 表示 x x x 子树内颜色为 c c c 的点数，那么对于原树中 x x x 到 f a fa fa（不包括 f a fa fa）这一条链上所有点，当他们选的数为 c c c 时，他们的贡献都是 c × s z c\times sz c×sz，由于这些点在树上时连续的，所以这里可以用倍增的思想优化一下，每 2 k 2^k 2k 个点压成一个新点，那么 f a fa fa 到 x x x 这一串点就不需要依次连边，只需要找到两个对应的新点连两条边就够了。

细节都说出来就太冗长了，具体看代码吧：

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

namespace K{//网络流
	#define maxn 500010
	int S,T;
	struct edge{int y,z,next;}e[maxn<<2];
	int first[maxn],len=1;
	void buildroad(int x,int y,int z){e[++len]=(edge){y,z,first[x]};first[x]=len;}
	void ins(int x,int y,int z){buildroad(x,y,z);buildroad(y,x,0);}
	int h[maxn],q[maxn],st,ed,cur[maxn];
	bool bfs(){
		memset(h,0,sizeof(h));
		h[q[st=ed=1]=S]=1;
		while(st<=ed){
			int x=q[st++];cur[x]=first[x];
			for(int i=first[x];i;i=e[i].next)
			if(!h[e[i].y]&&e[i].z)h[q[++ed]=e[i].y]=h[x]+1;
		}
		return h[T];
	}
	int dfs(int x,int flow){
		if(x==T)return flow;int tt=0;
		for(int i=cur[x];i;i=e[i].next){
			int y=e[i].y;cur[x]=i;
			if(h[y]==h[x]+1&&e[i].z){
				int p=dfs(y,min(e[i].z,flow-tt));tt+=p;
				e[i].z-=p;e[i^1].z+=p;
			}
			if(tt==flow)break;
		}
		if(!tt)h[x]=0;
		return tt;
	}
	edge E[maxn<<2];
	int First[maxn],Len;
	void save_graph(){//存图
		for(int i=1;i<=T;i++)First[i]=first[i];
		Len=len;for(int i=2;i<=Len;i++)E[i]=e[i];
	}
	void get_graph(){//获取存档
		for(int i=1;i<=T;i++)first[i]=First[i];
		len=Len;for(int i=2;i<=len;i++)e[i]=E[i];
	}
	int max_flow(){int re=0;while(bfs())re+=dfs(S,999999999);return re;}
	#undef maxn
};
#define maxn 40010
#define pb push_back
const int D=15;
int n,col[maxn];
vector<int>e[maxn],c[maxn];
int dfn[maxn],dfnnow=0,f[maxn][D+1],dep[maxn];
void dfs(int x,int fa){
	dfn[x]=++dfnnow;f[x][0]=fa;dep[x]=dep[fa]+1;
	for(int y:e[x])if(y!=fa)dfs(y,x);
}
void init_lca(){
	for(int j=1;j<=D;j++)
	for(int i=1;i<=n;i++)
	f[i][j]=f[f[i][j-1]][j-1];
}
int lca(int x,int y){
	if(dep[x]>dep[y])swap(x,y);
	for(int i=D;i>=0;i--)if(dep[f[y][i]]>=dep[x])y=f[y][i];
	if(x!=y){for(int i=D;i>=0;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];x=f[x][0];}
	return x;
}
int id[maxn][D+1],bin[D+1];
void net_init(){
	bin[0]=1;for(int i=1;i<=D;i++)bin[i]=2*bin[i-1];
	int tot=2*n+1;//1~n是树上的点，n+1~2*n+1对应0~n每种颜色
	for(int j=0;j<=D;j++)//建新点，id[i][j]表示i往上2^j个点（包括i不包括f[i][j]）压成的新点
	for(int i=1;i<=n;i++)
	if(dep[i]>=bin[j])id[i][j]=++tot;
	K::S=tot+1,K::T=tot+2;
	
	//起点与树点连边，树点与颜色0连边（显然每个点都有办法做到贡献为0），树点再与包含自己的新点连边
	for(int i=1;i<=n;i++)K::ins(K::S,i,1),K::ins(i,n+0+1,1),K::ins(i,id[i][0],1);
	for(int j=1;j<=D;j++)for(int i=1;i<=n;i++)if(id[i][j]){
		K::ins(id[i][j-1],id[i][j],bin[j-1]);
		K::ins(id[f[i][j-1]][j-1],id[i][j],bin[j-1]);
	}
}
bool cmp(int x,int y){return dfn[x]<dfn[y];}
namespace VT{//虚树
	struct edge{int x,y,next;}e[maxn<<1];
	int first[maxn],len=0;
	void buildroad(int x,int y){e[++len]=(edge){x,y,first[x]};first[x]=len;}
	int zhan[maxn],t;
	void clear(){
		zhan[t=1]=1;
		while(len)first[e[len--].x]=0;
	}
	void add(int x){
		if(x==1)return;
		int p=lca(zhan[t],x);if(p==zhan[t])return (void)(zhan[++t]=x);
		while(t>1&&dep[zhan[t-1]]>=dep[p])buildroad(zhan[t-1],zhan[t]),t--;
		if(zhan[t]!=p)buildroad(p,zhan[t]),zhan[t]=p; zhan[++t]=x;
	}
	void work(){while(t>1)buildroad(zhan[t-1],zhan[t]),t--;}
	void addchain(int x,int y,int to){
		int k=dep[y]-dep[x],p=0;
		while(bin[p+1]<=k)p++;
		K::ins(id[y][p],to,1);
		for(int i=0;i<p;i++)if(k>>i&1)y=f[y][i];
		K::ins(id[y][p],to,1);
	}
	int dfs(int x,int fa,int C){
		int sz=(col[x]==C);
		for(int i=first[x];i;i=e[i].next)
		sz+=dfs(e[i].y,x,C);
		if(C*sz<=n)addchain(fa,x,n+C*sz+1);
		return sz;
	}
};

int main()
{
	scanf("%d",&n);
	for(int i=2,fa;i<=n;i++)scanf("%d",&fa),e[fa].pb(i);
	for(int i=1;i<=n;i++)scanf("%d",&col[i]),c[col[i]].pb(i);
	dep[1]=1;dfs(1,0);init_lca();net_init();
	for(int i=1;i<=n;i++)if(c[i].size()){
		sort(c[i].begin(),c[i].end(),cmp);
		VT::clear();for(int j:c[i])VT::add(j);VT::work();//建这种颜色的虚树
		VT::dfs(1,0,i);
	}
	int l=1,r=n,mid,ans=-1;
	K::save_graph();
	while(l<=r){
		mid=l+r>>1;
		for(int i=ans+1;i<=mid;i++)K::ins(n+i+1,K::T,1);
		if(K::max_flow()==mid-ans){
			K::save_graph();//假如合法，就把图存下来，接下来只需要在这个残余网络上继续跑即可
			l=mid+1;ans=mid;
		}else{
			K::get_graph();//否则丢掉这张图找回存档
			r=mid-1;
		}
	}
	printf("%d",ans+1);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146

H. Interval

令 F ( l , r ) = a l & a l + 1 & . . . & a r F(l,r)=a_l\&a_{l+1}\&...\&a_r F(l,r)=al​&al+1​&...&ar​， S ( l , r ) = { F ( x , y ) ∣ l ≤ x ≤ y ≤ r } S(l,r)=\{F(x,y)|l\leq x\leq y\leq r\} S(l,r)={F(x,y)∣l≤x≤y≤r}，现在给出 a a a 序列，每次询问 ∣ S ( l , r ) ∣ |S(l,r)| ∣S(l,r)∣，强制在线。

容易发现，当 l , r l,r l,r 其中一者固定时，不同的 F ( l , r ) F(l,r) F(l,r) 只有 log ⁡ \log log 个。考虑枚举 l l l，对于一个 l l l，记录一个 n o w = a l now=a_l now=al​，从左到右使 n o w now now 依次 & a l + 1 , . . . , a n \& a_{l+1},...,a_n &al+1​,...,an​，当 n o w & a x ≠ n o w now\& a_x\neq now now&ax​​=now 时，记录一个贡献是 1 1 1 的二元组 ( l , x ) (l,x) (l,x)，那么最后的询问就变成一个二维数点问题了，这个过程容易优化成 O ( n log ⁡ n ) O(n\log n) O(nlogn) 的。

但是有一个问题，有一些二元组代表的数是相同的，我们要将它去掉。对于一堆代表相同数的二元组，先将其排序，如果 x x x 包含了 y y y，那么就去掉 x x x 这个二元组。对于剩下的二元组，设 x , y x,y x,y 为两个相邻的二元组，我们再加入一个新的二元组 ( x . l , y . r ) (x.l,y.r) (x.l,y.r)，贡献是 − 1 -1 −1，这样就可以去掉多余的贡献了。

代码如下：

#include <cstdio>
#include <cstring>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
#define maxn 100010
#define pb push_back

int n,m,a[maxn];
struct point{
	int x,y,z;
	point(int xx=0,int yy=0,int zz=0):x(xx),y(yy),z(zz){}
	bool operator <(const point &B)const{return x==B.x?y<B.y:x<B.x;}
	bool in(const point &B)const{return x>=B.x&&y<=B.y;}
};
int last[30];
vector<int>la;
vector<point>cp,b,c;
map< int,vector<point> >mp;
void work(){
	for(pair< int,vector<point> > d:mp){
		cp=d.second;c.clear();
		sort(cp.begin(),cp.end());
		for(point i:cp){
			while(c.size()&&i.in(c.back()))c.pop_back(),b.pop_back();//c.back()包含i,就去掉c.back()
			c.pb(i),b.pb(i);
		}
		for(int i=1;i<c.size();i++)b.pb(point(c[i-1].x,c[i].y,-1));
	}
}
struct node *null=NULL,*root[maxn];
#define zuo ch[0]
#define you ch[1]
struct node{
	int z;node *ch[2];
	node(int x=0):z(x){zuo=you=null;}
};
void add(node *from,node *to,int l,int r,int x,int z){
	to->z+=z;if(l==r)return;
	int mid=l+r>>1,c=(x>=mid+1);
	if(to->ch[c]==null)to->ch[c]=new node(from->ch[c]->z);
	add(from->ch[c],to->ch[c],c?mid+1:l,c?r:mid,x,z);
}
void inherit(node *from,node *to,int l,int r){
	if(l==r)return;int mid=l+r>>1;
	if(to->zuo==null)to->zuo=from->zuo;else inherit(from->zuo,to->zuo,l,mid);
	if(to->you==null)to->you=from->you;else inherit(from->you,to->you,mid+1,r);
	to->z=to->zuo->z + to->you->z;
}
int ask(node *now,int l,int r,int x,int y){
	if(now==null)return 0;
	if(l==x&&r==y)return now->z;
	int mid=l+r>>1;
	if(y<=mid)return ask(now->zuo,l,mid,x,y);
	else if(x>=mid+1)return ask(now->you,mid+1,r,x,y);
	else return ask(now->zuo,l,mid,x,mid)+ask(now->you,mid+1,r,mid+1,y);
}
void build(){
	null=new node();null->zuo=null->you=null;
	root[0]=null;
	sort(b.begin(),b.end());
	for(int i=1,now=0;i<=n;i++){
		root[i]=new node();
		while(now<b.size()&&b[now].x==i)add(root[i-1],root[i],1,n,b[now].y,b[now].z),now++;
		inherit(root[i-1],root[i],1,n);
	}
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=0;i<30;i++)last[i]=n+1;
	for(int i=n;i>=1;i--){//last[i]表示第i位最早变成0的位置
		la.clear();for(int j=0;j<30;j++){
			if(!(a[i]>>j&1))last[j]=i;
			la.pb(last[j]);
		}
		sort(la.begin(),la.end());
		int sz=(int)(unique(la.begin(),la.end())-la.begin());
		la.resize(sz);
		int now=a[i];
		for(int j=0;j<sz&&la[j]<=n;j++){
			now&=a[la[j]];
			mp[now].pb(point(i,la[j],1));
		}
	}
	work();build();
	scanf("%d",&m);
	for(int i=1,x,y,lastans=0;i<=m;i++){
		scanf("%d %d",&x,&y);
		x=(x^lastans)%n+1;y=(y^lastans)%n+1;
		if(x>y)swap(x,y);
		printf("%d\n",lastans=(ask(root[y],1,n,x,y)-ask(root[x-1],1,n,x,y)));
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97

I. Hard Math Problem

在一个无限大的网格图上放 0 , 1 , 2 0,1,2 0,1,2 三种数字，要求每个 0 0 0 必须和至少一个 1 1 1 以及至少一个 2 2 2 相邻，求 0 0 0 占的比例。

以右上到左下为一行来看，每三斜行就是一个周期，一个周期内，前两行放 0 0 0，第三行交替放 1 , 2 1,2 1,2，像这样：
001001 020020 100100 002001 010020 200100 001001\\ 020020\\ 100100\\ 002001\\ 010020\\ 200100\\ 001001020020100100002001010020200100

有一个小瑕疵，一个周期内第一行最旁边的两个是不合法的，减掉就好了，由于最后算的是比例，减掉的这一点所占的比例容易发现趋近于 0 0 0，可以忽略不计，而一个周期内 0 0 0 占了两行，即 2 3 \dfrac 2 3 32​，所以这就是答案。

代码如下：

#include <cstdio>

int main()
{
	printf("0.666667");
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

K. Git Merge

给一份代码，将一些git标记的代码用#define,#else,#endif改成一份可以编译的代码，并且长度最短。

考虑 dp \text{dp} dp，只需要讨论一下公共部分的代码是否需要分别放到branch1和branch2中，以及branch1和branch2中相同的代码是不是可以放在一起。实现起来用一点技巧可以做到更简单。

代码如下：

#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 4010
#define mod 998244353

int n=0,m=0;
string s[2][maxn];
int h[2][maxn];
int Hash(string c){
	int re=0,len=c.length();
	for(int i=0;i<len;i++)re=(37ll*re+c[i])%mod;
	return re;
}
void input(){
	string c;int type=0;
	while(getline(cin,c)){
		if(c=="<<<<<<< branch1")type=1;
		else if(c=="=======")type=2;
		else if(c==">>>>>>> branch2")type=0;
		else{
			if(type!=2)s[0][++n]+=c;
			if(type!=1)s[1][++m]+=c;
		}
	}
	for(int i=1;i<=n;i++)h[0][i]=Hash(s[0][i]);
	for(int i=1;i<=m;i++)h[1][i]=Hash(s[1][i]);
}
short f[maxn][maxn][3],fa[maxn][maxn][3];
void dp(){
	memset(f,63,sizeof(f));f[0][0][0]=0;
	memset(fa,-1,sizeof(fa));
	for(int i=0;i<=n;i++)
	for(int j=0;j<=m;j++)
	for(int k=0;k<=2;k++){
		if(f[i][j][k]+1+(k!=1)<f[i+1][j][1]){//放到branch1
			f[i+1][j][1]=f[i][j][k]+1+(k!=1);
			fa[i+1][j][1]=k;
		}
		if(f[i][j][k]+1+(k!=2)<f[i][j+1][2]){//放到branch2
			f[i][j+1][2]=f[i][j][k]+1+(k!=2);
			fa[i][j+1][2]=k;
		}
		if(h[0][i+1]==h[1][j+1]&&f[i][j][k]+1+(k!=0)<f[i+1][j+1][0]){
		//相同的代码可以选择放到公共部分
			f[i+1][j+1][0]=f[i][j][k]+1+(k!=0);
			fa[i+1][j+1][0]=k;
		}
	}
}
vector<int>op;
void output(){
	int x=n+1,y=m+1,z=0;
	while(x||y){
		if(z==-1)printf("wulala"),exit(-1);
		short p=fa[x][y][z];
		if(z==0)x--,y--;
		if(z==1)x--;
		if(z==2)y--;
		z=p;op.push_back(z);
	}
	op.pop_back();
	reverse(op.begin(),op.end());
	for(int i:op){
		if(i==0){
			if(z!=0)cout<<"#endif"<<endl;
			cout<<s[0][++x]<<endl;y++;
		}
		if(i==1){
			if(z==0)cout<<"#ifdef branch1"<<endl;
			if(z==2)cout<<"#else"<<endl;
			cout<<s[0][++x]<<endl;
		}
		if(i==2){
			if(z==0)cout<<"#ifdef branch2"<<endl;
			if(z==1)cout<<"#else"<<endl;
			cout<<s[1][++y]<<endl;
		}
		z=i;
	}
	if(z!=0)cout<<"#endif"<<endl;//注意这个
}

int main()
{
	input();
	dp();
	output();
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/986551
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号