首页 > 其他分享 >CSP-S模拟6

CSP-S模拟6

时间:2022-09-20 21:45:17浏览次数:63  
标签:return int ll long maxn CSP 模拟 mod

A. 玩水

一直以为这是 \(dp\) ,但是只是一个性质/结论

image

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

typedef long long ll;
typedef unsigned long long ull;

inline int read(){
	int x = 0; char c = getchar();
	while(c < '0' || c > '9')c = getchar();
	do{x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}while(c <= '9' && c >='0');
	return x;
}

const int maxn = 1005;
char mp[maxn][maxn];
bool f[maxn][maxn], p[maxn][maxn];
int n, m;
bool check(){
	for(int i = 1; i < n; ++i)
		for(int j = 1; j < m; ++j)
			p[i][j] = f[i][j] = (mp[i + 1][j] == mp[i][j + 1]);
	for(int i = n - 2; i > 0; --i)
	  for(int j = 1; j < m; ++j){
		  if(p[i][j] && p[i + 1][j])return true;
		  f[i][j] |= f[i + 1][j];
	  }
	for(int i = n - 1; i > 0; --i){
		for(int j = m - 2; j > 0; --j){
			if(p[i][j] && p[i][j + 1])return true;
			if(p[i][j] && f[i + 1][j + 1] && i + 1 < n && j + 1 < m)return true;
			f[i][j] |= f[i][j + 1];
		}
	}
	return false;
}
int main(){
	freopen("water.in","r",stdin);
	freopen("water.out","w",stdout);
	int T = read();
	for(int i = 1; i <= T; ++i){
		n = read(), m = read();
		for(int i = 1; i <= n; ++i)scanf("%s", mp[i] + 1);
		if(check())printf("1\n");
		else printf("0\n");
	}
	return 0;
}

B. AVL 树

奇妙

按照先序考虑每个点,如果能够加入就加入,不能加入则跳过该子树

可以预处理出来当深度为 \(i\) 时, \(AVL\) 最少的节点数 \(f_i = f_{i - 1} + f_{i - 2} + 1\)

顺次考虑每个点时,我们每次向上跳,如果当前点作为左子树,用 \(f\) 算出右子树至少需要加入多少点,如果加入当前点需要加入的点数小于等于剩余点数就加入

这样,我们还需要维护当前确定的 \(AVL\) 中每个点子树的最大深度, 以及每个子树至少有多少深度,这样我们在加入一个点时,就能够计算保证之前加入的点对应的那些至少加入的点数一定被计算了

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

typedef long long ll;
typedef unsigned long long ull;

inline int read(){
	int x = 0; bool f = 0;char c = getchar();
	while(c < '0' || c > '9'){if(c == '-')f = 1;c = getchar();}
	do{x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}while(c <= '9' && c >='0');
	return f ? -x : x;
}

const int maxn = 500005;
int n, k, root, l[maxn], r[maxn], fa[maxn], mx[maxn], dep[maxn];
bool flag[maxn];
int mi[maxn], ndp[maxn], f[maxn], res;
void pre(int x){
	mx[x] = dep[x] = dep[fa[x]] + 1;
	if(l[x]){
		pre(l[x]);
		mx[x] = max(mx[x], mx[l[x]]);
	}
	if(r[x]){
		pre(r[x]);
		mx[x] = max(mx[x], mx[r[x]]);
	}
}
int check(int x){
	int ndep = max(dep[x], ndp[x]);
	int ans = 1;
	while(fa[x]){
		bool left = (l[fa[x]] == x);
		x = fa[x];
		ndep = max(ndep, ndp[x]);
		if(left && r[x])ans += f[max(ndep - 1, mi[r[x]]) - dep[x]]; 
	}
	return ans;
}
void upd(int x){
	int ndep = ndp[x] = max(ndp[x], dep[x]);
	while(x){
		x = fa[x];
		ndp[x] = ndep = max(ndp[x], ndep);
		if(r[x])mi[r[x]] = max(mi[r[x]], ndep - 1);
	}
}
void dfs(int x){
	int cnt = check(x);
	if(cnt <= res){
		upd(x);
		flag[x] = 1; --res;
		if(l[x] && r[x]){
			int dt = mx[l[x]] < mi[x];
			mi[l[x]] = max(mi[l[x]], mi[x] - dt);
			mi[r[x]] = max(mi[r[x]], mi[x] + dt - 1);
			dfs(l[x]); dfs(r[x]);
			return;
		}
		if(l[x]){
			mi[l[x]] = max(mi[l[x]], mi[x]);
			dfs(l[x]);
		}
		if(r[x]){
			mi[r[x]] = max(mi[r[x]], mi[x]);
			dfs(r[x]);
		}
	}
}
int main(){
	freopen("avl.in","r",stdin);
	freopen("avl.out","w",stdout);
	n = read(); res = k = read();
	for(int i = 1; i <= n; ++i){
		int x = read(); 
		if(x == -1)root = i;
		else{
			fa[i] = x;
			if(i > x)r[x] = i;
			else l[x] = i;
		}
	}
	f[1] = 1; f[2] = 2;
	for(int i = 3; i <= n; ++i)f[i] = (f[i - 1] + f[i - 2] + 1);
	pre(root);
	dfs(root);
	for(int i = 1; i <= n; ++i)printf("%d", flag[i]);
	return 0;
}

C. 暴雨

设 \(f_{i, j, k, 1 / 0}\) 表示前 \(i\) 个,铲平了 \(k\) 块, 最大高度为 \(j\), 要求后面存在 \(>= j\) 的 积水为 奇数/偶数的方案数

同理得出后缀,然后枚举最大值的位置合并答案

因为最多铲去 \(k\) 块, 那么最大值只有 \(k + 1\) 种选法, 通过映射可以转移

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

typedef long long ll;
typedef unsigned long long ull;

inline int read(){
	int x = 0; char c = getchar();
	while(c < '0' || c > '9')c = getchar();
	do{x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}while(c <= '9' && c >='0');
	return x;
}
const int mod = 1e9 + 7;
const int maxn = 25005;
int n, k, h[maxn], pre[maxn][29], nxt[maxn][29], pn[maxn], nn[maxn];
int low[maxn][29], row[maxn][29];
multiset<int>s;
int f[maxn][27][2][27], g[maxn][27][2][27];
inline void add(int &x, int y){
	x += y; x = x >= mod ? x - mod : x;
}
inline int mul(int x, int y){return 1ll * x * y % mod;}
int main(){
	// freopen("rain.in","r",stdin);
	// freopen("rain.out","w",stdout);
	n = read(), k = read();
	if(n == 1 && k == 0){
		printf("1\n");
		return 0;
	}
	for(register int i = 1; i <= n; ++i)h[i] = read();
	s.insert(0);
	for(int i = 1; i <= n; ++i){
		s.insert(h[i]);
		while(s.size() > k + 1)s.erase(s.begin());
		for(int x : s)pre[i][++pre[i][0]] = x;
	}
	for(int i = 1; i < n; ++i){
		pn[i + 1] = lower_bound(pre[i + 1] + 1, pre[i + 1] + pre[i + 1][0] + 1, h[i + 1]) - pre[i + 1];
		for(int j = 1; j <= pre[i][0]; ++j)
			low[i][j] = lower_bound(pre[i + 1] + 1, pre[i + 1] + 1 + pre[i + 1][0], pre[i][j]) - pre[i + 1];
	}
	f[1][0][0][2] = 1;
	if(k)f[1][1][0][1] = 1;
	for(register int i = 1; i < n; ++i){
		int mk = min(i, k);
		for(register int nk = 0; nk <= mk; ++nk){
			for(register int op = 0; op <= 1; ++op)
				for(int m = 1; m <= pre[i][0]; ++m){
					if(f[i][nk][op][m]){
						int hi = pre[i][m], ct = f[i][nk][op][m], po = low[i][m];
						if(nk < k)add(f[i + 1][nk + 1][(op + hi) & 1][po], ct);
						if(h[i + 1] < hi) add(f[i + 1][nk][(op + hi - h[i + 1]) & 1][po], ct);
						else add(f[i + 1][nk][op][pn[i + 1]], ct);
					}
				}
		}
	}
	s.clear();
	s.insert(0);
	for(int i = n; i >= 1; --i){
		s.insert(h[i]);
		while(s.size() > k + 1)s.erase(s.begin());
		for(int x : s)nxt[i][++nxt[i][0]] = x;
	}
	for(int i = n; i > 1; --i){
		nn[i - 1] = lower_bound(nxt[i - 1] + 1, nxt[i - 1] + nxt[i - 1][0] + 1, h[i - 1]) - nxt[i - 1];
		for(int j = 1; j <= nxt[i][0]; ++j)
			row[i][j] = lower_bound(nxt[i - 1] + 1, nxt[i - 1] + 1 + nxt[i - 1][0], nxt[i][j]) - nxt[i - 1];
	}
	if(k)g[n][1][0][1] = 1;
	g[n][0][0][2] = 1;
	for(register int i = n; i > 1; --i){
		int mk = min(n - i + 1, k);
		for(register int nk = 0; nk <= mk; ++nk){
			for(register int op = 0; op <= 1; ++op)
			   for(int m = 1; m <= nxt[i][0]; ++m){
				   if(g[i][nk][op][m]){
					   int hi = nxt[i][m], ct = g[i][nk][op][m], po = row[i][m];
					   if(nk < k)add(g[i - 1][nk + 1][(op + hi) & 1][po], ct);
					   if(h[i - 1] < hi) add(g[i - 1][nk][(op + hi - h[i - 1]) & 1][po], ct);
					   else add(g[i - 1][nk][op][nn[i - 1]], ct);
				   }
			   }
		}
	} 
	ll ans = 0;
	for(int i = 1; i <= pre[n - 1][0]; ++i)if(pre[n - 1][i] <= h[n]) ans += f[n - 1][k][0][i]; else break;
	for(int i = 1; i <= nxt[2][0]; ++i)if(nxt[2][i] < h[1]) ans += g[2][k][0][i]; else break;
	for(register int i = 2; i < n; ++i){
		for(register int kl = 0; kl <= k; ++kl){
			int kr = k - kl;
			int sl0 = 0, sl1 = 0;
			for(int j = 1; j <= pre[i - 1][0]; ++j)
				if(pre[i - 1][j] <= h[i]){
					add(sl0, f[i - 1][kl][0][j]);
					add(sl1, f[i - 1][kl][1][j]);
				}else break;
			int sr0 = 0, sr1 = 0;
			for(int j = 1; j <= nxt[i + 1][0]; ++j)
				if(nxt[i + 1][j] < h[i]){
					add(sr0, g[i + 1][kr][0][j]);
					add(sr1, g[i + 1][kr][1][j]);
				}else break;
			ans += mul(sl0, sr0);
			ans += mul(sl1, sr1);
		}
	}
	printf("%lld\n",ans % mod);
	return 0;
}

D. 置换

有个性质就是置换可以看做一些点连成环, \(f(p)\) 就是环长度的 \(lcm\), 那么环长之和为 $$

设 \(f_{i, j}\) 表示用了 \(i\) 个数, 此时 \(lcm\) 为 \(j\) 的贡献

有很多好写的 \(60pts\) 转移,但是为了引出正解,不得不用一种我认为很恶心的转移

枚举环长 \(l\) ,从大到小考虑 \(sum\), 然后枚举放 \(k\) 个环, 那么方案数为

选择 \(C_{n - sum}^{k \times l}\)

全排转组合 $fac_{k \times l} \times facinv_{l}^k $

各个环顺序无关 \(\times facinv_{k}\)

每个组合内园排列 \(\times fac_{l - 1}^k\)

最后为 \(fac_{k \times l} \times inv_{l}^k \times facinv_{k} \times C_{n - sum}^{k \times l}\)

然后此时的瓶颈在于第二维太多,考虑根号分治

上面的 \(dp\) 可以转化成直接算贡献的,这样转移每次乘上 \(lcm\) 变化倍数的平方即可

考虑优化

对环长按照最大质因子分类,

特别的$ <= \sqrt n $ 的算作一类,正常转移

然后对于每个 \(p> \sqrt n\), 他在最终 \(lcm\) 的幂次最大为 \(1\), 我们去掉 \(p\) 转移, 然后统一算上 \(p\) 的贡献

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

typedef long long ll;
typedef unsigned long long ull;

inline int read(){
	int x = 0; char c = getchar();
	while(c < '0' || c > '9')c = getchar();
	do{x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}while(c <= '9' && c >='0');
	return x;
}

const int maxn = 205;
int n, mod;
ll gcd(ll a, ll b){return b ? gcd(b, a % b) : a;}
int qpow(int x, int y){
	int ans = 1;
	for(; y; y >>= 1, x = 1ll * x * x % mod)if(y & 1)ans = 1ll * ans * x % mod;
	return ans;
}
ll lcm(ll x, ll y){
	if(!x || !y)return x | y;
	return x * y / gcd(x, y);
}
void add(int &x, int y){
	x += y; x = x >= mod ? x - mod : x;
}
const int mx = 25000;
unordered_map<int, int>f[maxn], tmp[maxn], id;
vector<int>p[maxn];
int prime[maxn], cnt, tot, pr[maxn];
bool flag[maxn];
int fac[maxn], inv[maxn];
int C(int n, int m){return 1ll * fac[n] * inv[m] % mod * inv[n - m] % mod;}
int main(){
	freopen("perm.in","r",stdin);
	freopen("perm.out","w",stdout);
	n = read(), mod = read();
	fac[0] = inv[0] = 1; for(int i = 1; i <= n; ++i)fac[i] = 1ll * fac[i - 1] * i % mod;
	inv[n] = qpow(fac[n], mod - 2); for(int i = n - 1; i > 0; --i)inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
	for(int i = 2; i <= n; ++i){
		if(!flag[i])prime[++cnt] = i;
		for(int j = 1; j <= cnt && i * prime[j] <= n; ++j){
			flag[i * prime[j]] = 1;
			if(i % prime[j] == 0)continue;
		} 
	}
	int gn = sqrt(n);
	for(int i = 1; i <= cnt; ++i)if(prime[i] > gn)id[prime[i]] = ++tot, pr[tot] = prime[i];
	for(int i = 1; i <= n; ++i){
		bool f = 0;
		for(int j = 1; j <= tot; ++j){
			int x = pr[j];
			if(i % x == 0){
				p[j].push_back(i / x);
				f = 1;
				break;
			}
		}
		if(!f)p[0].push_back(i);
	}
	f[0][1] = 1; pr[0] = 1;
	for(int now = 0; now <= tot; ++now){
		if(p[now].empty())continue;
		for(int i = 0; i <= n; ++i)tmp[i] = f[i];
		
		for(int len : p[now]){
			int kl = len * pr[now];
			for(int sum = n; sum >= 0; --sum){
				for(int k = 1; k * kl + sum <= n; ++k){
					int ds = k * kl;
					int base = 1ll * fac[ds] * C(n - sum, ds) % mod * inv[k] % mod * qpow(qpow(kl, k), mod - 2) % mod;
					for(auto x : tmp[sum]){
							int lc = lcm(x.first, len), dt = (lc / x.first);
							add(tmp[sum + ds][lc], 1ll * dt * dt % mod * x.second % mod * base % mod);
					}

				}
			}
		}
		if(now)
			for(int sum = 0; sum <= n; ++sum){
				for(auto x : tmp[sum]){
					x.second -= f[sum][x.first]; x.second = (x.second % mod + mod) % mod;
					add(f[sum][x.first], 1ll * x.second * pr[now] % mod * pr[now] % mod);
				}
				tmp[sum].clear();
			}
		else for(int i = 0; i <= n; ++i)f[i] = tmp[i];
	}
	int ans = 0;
	for(auto x : f[n]){
		add(ans, x.second);
	}
	ans = 1ll * ans * inv[n] % mod;
	ans = (ans % mod + mod) % mod;
	printf("%d ",ans);
	return 0;
}

标签:return,int,ll,long,maxn,CSP,模拟,mod
From: https://www.cnblogs.com/Chencgy/p/16712647.html

相关文章

  • 归档 220920 | CSP-J 复习
    所以为什么要复习J组所以为什么我连J组都不会,哭唧唧A.加工零件一开始的想法是,如果点\(x\)离\(1\)的距离大于等于\(L\),且与\(L\)奇偶性相同,那么就可行。然......
  • 题目:模拟网站的登录,客户端录入账号密码,然后服务器端进行验证(TCP)
    题目:模拟网站的登录,客户端录入账号密码,然后服务器端进行验证(TCP)封装的类packagecom.gao.Project.Pro4;importjava.io.Serializable;publicclassUserimplements......
  • 题目:模拟网站的登录,客户端录入账号密码,然后服务器端进行验证(TCP)(完善)
    完善(加入完整的处理异常的方式、多线程接收用户请求)(TCP)封装的类packagecom.gao.Project.Pro5;importjava.io.Serializable;publicclassUserimplementsSerial......
  • CSP-S模拟7 序列问题 钱仓 自然数 环路
    T1:线性DP,求最长不下降子序列优化(cdp,树状数组)T2:断环为链,结论T3:序列上区间统计答案,线段树维护T4:咕了,矩阵乘法+分治优化,我就打个暴力T1:给你一个长度n的序列A(n<=5e5,ai<=......
  • 【Coel.学习笔记】随机化算法:模拟退火与爬山法
    简介模拟退火(\(\text{SimulateAnneal}\))和爬山法是随机化算法,二者的原理都在于通过随机生成答案并检查,把答案逐步缩小在一个可行的区间,尽可能地靠近正确答案。在考场......
  • CSP-S模拟7
    学校体检:内科:问,你是神经病吗;答,不是。下一个。外科:问,你做过手术吗;答,没有。下一个。基础检查:问,你身高体重是多少;答,……。下一个。此处应有乌鸦飞过*** A.序列问题我......
  • P7076 [CSP-S2020] 动物园
    [CSP-S2020]动物园题目描述动物园里饲养了很多动物,饲养员小A会根据饲养动物的情况,按照《饲养指南》购买不同种类的饲料,并将购买清单发给采购员小B。具体而言,动物世......
  • 模拟springboot自动转配原理
    packagecom.tlj.app;importorg.springframework.beans.factory.annotation.Configurable;importorg.springframework.context.annotation.Bean;importorg.springf......
  • CSPS2021回文
    [CSP-S2021]回文题目描述给定正整数\(n\)和整数序列\(a_1,a_2,\ldots,a_{2n}\),在这\(2n\)个数中,\(1,2,\ldots,n\)分别各出现恰好\(2\)次。现在进行\(......
  • 2022.08.24 模拟赛小结
    2022.08.24模拟赛小结题面链接(这个链接只是为了自己方便找,页面设置权限了,不要尝试访问)更好的阅读体验戳此进入(建议您从上方链接进入我的个人网站查看此Blog,在Luo......