20zr普及组五连测day1

水

首先按照题意写一个n!的做法

然后你会发现答案是斐波那契

然后矩阵加速递推即可

正确思考:

考虑第n个放什么

如果第n个放n-1,那么第n-1个只能放n

$f_n+=f_{n-2}$

否则 $n-1$ 随便放

$f_n+=f_{n-1}$

code:


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=6;
const int B=2;
const int P=998244353;
ll n;
inline void add(ll &x,ll y) {
	x+=y;
	if(x>=P)x-=P;
}
struct rec {
	ll a[MAXN][MAXN];
	inline void init() {
		for(int i=0; i<B; ++i) {
			for(int j=0; j<B; ++j) {
				a[i][j]=0;
			}
		}
	}

} w,tmp;
inline rec mul(rec &x,rec &y) {
	rec c;
	c.init();
	for(int i=0; i<B; ++i) {
		for(int j=0; j<B; ++j) {
			for(int k=0; k<B; ++k) {
				add(c.a[i][j] ,1ll*x.a[k][j] * y.a[i][k]%P);
			}
		}
	}
	return c;
}
inline void ksm() {
	rec ans;
	n-=2;
	ans.init();
	for(int i=0; i<B; ++i)ans.a[i][i]=1;
	while(n) {
		if(n&1)ans=mul(tmp,ans);
		tmp=mul(tmp,tmp);
		n>>=1;
	}
	ans=mul(w,ans);
	printf("%lld\n",ans.a[0][0]);
	return ;
}

int main() {
	scanf("%lld",&n);
	w.a[0][0]=2;
	w.a[1][0]=1;
	tmp.a[0][0]=1;
	tmp.a[1][0]=1;
	tmp.a[0][1]=1;
	if(n<=2)printf("%lld\n",w.a[2-n][0]);
	else ksm();
	return 0;
}

考场写了假代码过了...

首先我们考虑路径可能长什么样子,第一想法

两个子树全部走,中间的走一次

然而这个可能是错的我们一个子树可能并不这样走

两个子树走部分中间走一次

然后也是错的我们可能不止两个子树

一条链走一次挂了其他一些部分子树

好像不能求

但是你会发现那条链只可能是从某个点到根的一部分

所以做完了

假在答案可能大于n,但是数据太水没卡

code:



#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e5+7;
int n,m;
int ccnt,home[MAXN],nxt[MAXN],to[MAXN];

inline void ct(int x,int y) {
	ccnt++;
	nxt[ccnt]=home[x];
	home[x]=ccnt;
	to[ccnt]=y;
}

int dep=0,ans;

inline void dfs(int u,int F) {
	if(m>dep) {
		ans=max(ans,(m-dep)/2+dep + 1);
	} else {
		ans=max(ans,m + 1);
	}
	++dep;
	for(int i=home[u]; i; i=nxt[i]) {
		int v=to[i];
		if(v==F)continue;
		dfs(v,u);
	}
	--dep;
	return ;
}

int main() {
	scanf("%d%d",&n,&m);
	for(int i=1,x,y; i<n; ++i) {
		scanf("%d%d",&x,&y);
		ct(x,y);
		ct(y,x);
	}
	if(m>=2*(n-1)-1) {
		printf("%d\n",n);
		return 0;
	}
	dfs(1,0);
    ans=min(ans,n);//考场没有
	printf("%d\n",ans);
	return 0;
}

考虑每种颜色的贡献,然后容斥一下

正难则反的补集转换/cy

我们只需要求出有多少路径没有经过某种关键颜色即可

答案就是把某种颜色去掉之后所有连通块内部算答案

考虑枚举每个点,然后计算他当做连通块最高的那个点的父亲的答案

那么我们只需要这个点的某个儿子减去儿子子树中和他颜色相同的点

显然可以用一个栈维护

时间复杂度 $O(n)$

code:


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e5+7;
const int MAXM=5e5+7;
int ccnt,home[MAXN],nxt[MAXM],to[MAXM],a[MAXN],n,vis[MAXN];
ll rc[MAXN],ans;

inline void ct(int x,int y) {
	ccnt++;
	nxt[ccnt]=home[x];
	home[x]=ccnt;
	to[ccnt]=y;
}

stack<int> v[MAXN];
int dfnn,dfn[MAXN],siz[MAXN];

inline void dfs(int u,int F) {
	dfn[u]=++dfnn;
	siz[u]=1;
	for(int i=home[u]; i; i=nxt[i]) {
		int T=to[i];
		if(T==F)continue;
		dfs(T,u);
		siz[u]+=siz[T];
		ll tmp=0;
		while(!v[a[u]].empty()) {
			int x=v[a[u]].top();
			if(dfn[x]>=dfn[T] && dfn[x]<=dfn[T]+siz[T]-1) {
				tmp+=siz[x];
				v[a[u]].pop();
			} else break;
		}
		rc[a[u]]+=1ll*(siz[T]-tmp)*(siz[T]-tmp-1)/2;
	}
	v[a[u]].push(u);
	return ;
}

int main() {
	scanf("%d",&n);
	for(int i=1; i<=n; ++i) {
		scanf("%d",&a[i]);
		vis[a[i]]=1;
	}
	for(int i=1,x,y; i<n; ++i) {
		scanf("%d%d",&x,&y);
		ct(x,y);
		ct(y,x);
	}
	dfs(1,0);
	for(int i=1; i<=n; ++i) {
		if(vis[i]) {
			ll tmp=0;
			while(!v[i].empty()) {
				tmp+=siz[v[i].top()];
				v[i].pop();
			}
			rc[i]+=(siz[1]-tmp)*(siz[1]-tmp-1)/2;
			ans=ans+1ll*n*(n-1)/2-rc[i];
		}
	}
	printf("%lld\n",ans);
	return 0;
}

神仙计数题

不难发现我们就是要找到一种合法的区间方案然后分配给每个人

$f_{i,j,k}$ 表示前i个容器,有j个区间已经使用,然后有k个区间我们还在延伸

然后转移的时候枚举两维

第一维是考虑我们新开多少个区间,然后他们开始延伸

第二维是考虑我们终结多少个区间,然后把他们乘上一个组合数分配给每个人

这样做复杂度是 $O(n^5)$ 难以接受

我们可以发现其实是有 $O(n^3)$ 然后 $O(n^2)$ 的转移

如果我们能拆开两步,变成 $O(n^3)$ O(n)转移给另一个 $O(n^3)$ 的点,然后再O(n)转移复杂度就只有 $O(n^4)$ 了

做法很简单,设 $g_{i,j,k}$ 表示考虑了前i个容器用了j个区间然后这j个区间还没有确定是不是i为右端点,然后k个延续

那么这样转移的时候我们只需要枚举下f向g转移即可

以i为左端点区间l个

g_{i,j+l,k+l}+=f_{i-1,j,k}*C(m-j,l)

以i为右端点区间l个

f_{i,j,k-l}+=g_{i,j,k}*C(k,l)

答案是 $f_{n,m,0}$

本题有标号的是人,无标号的是区间,所以只需要区间匹配人

code:


#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 105;
const int P = 998244353;
int c[MAXN][MAXN];
int f[MAXN][MAXN][MAXN], g[MAXN][MAXN][MAXN];
int n, m, t;

inline void add(int &x, ll y) {
	x += y;
	if(x >= P)x -= P;
}

int main() {
	scanf("%d%d%d", &n, &m, &t);
	c[0][0] = 1;
	for(int i = 1; i <= m; ++i) {
		c[i][0] = 1;
		for(int j = 1; j <= m; ++j) {
			add(c[i][j], c[i - 1][j - 1]);
			add(c[i][j], c[i - 1][j]);
		}
	}
	f[0][0][0] = 1;
	for(int i = 1; i <= n; ++i) {
		for(int j = 0; j <= m; ++j) {
			for(int k = 0; k <= min(j, t); ++k) {
				for(int l = 0; l <= min(m - j, t); ++l)
					add(g[i][j + l][k + l], 1ll * f[i - 1][j][k] * c[m - j][l] % P);
				for(int l = 0; l <= min(k, t); ++l)
					add(f[i][j][k - l], 1ll * g[i][j][k] * c[k][l] % P);
			}
		}
	}
	printf("%d\n", f[n][m][0]);
	return 0;
}

夏晓光(loveJY)的博客

ZR20秋季普转提day1