首页 > 其他分享 >盖世计划--0726--B班模拟

盖世计划--0726--B班模拟

时间:2024-07-30 14:29:59浏览次数:12  
标签:std 0726 -- i64 int 开关 盖世 define mod

又写不了一点,怎么会是呢。菜。

A

为什么第一题的难度都很懵,不知道是真难还是我傻。你考虑分类讨论保留奇数位还是偶数位,然后就可以知道若干不合法的位置。感觉显然是不能动合法的位置,怎么使代价最小?

如果你把要修改的位置分为奇偶两类的话,感觉依次连可以取到最小值。然后你又不知道怎么使字典序最小了。这题到底是图论还是贪心,不知道。

赛后:好吧,是贪心。

B

感觉是离线数据结构题,我不会。先同色缩成一段,然后可以分析出,每次开关灯对答案的增减情况,然后就有 \(O(nq)\) 做法。

艹了,没有发现关键性质。

首先要描述题目的答案,表示为所有开灯位置-相邻两个亮灯对数。前者显然可以 \(O(1)\) 维护,后者单一颜色段内可以预处理,我们需要考虑的是不同颜色段相邻时的贡献。

因为所有颜色的总和为 \(n\),而数据范围提示了 \(k\le 500\),启发我们从开关数(颜色种类数)以及单个开关控制数量考虑,极有可能是根号分治。假设开关控制的位置为 \(B\),那么控制不同颜色的开关不超过 \(\frac{n}{B}\) 个。

我们按照开关控制的位置数量分别考虑,我们将控制的位置不超过 \(B\) 的开关叫做小开关,反之为大开关。

以 \(B\) 为界,假设现在操作的是小开关,那么我们直接暴力枚举每个位置计算贡献即可。否则这个暴力复杂度就不对了,需要额外考虑处理方法,此时控制数量大的开关的种类数是小于 \(B\) 的,我们预处理两两之间的贡献 \(f_{i,j}\),表示 \(i\) 开关和 \(j\) 开关开启时的贡献。

此时我们还没有考虑大开关和小开关相邻的贡献。换个角度,我们在开启小开关的时候提前计算其相邻大开关的贡献,操作大开关的时候就可以 \(O(1)\) 查询了。

看起来最暴力的地方就是预处理,实际上复杂度为 \(O(\frac{n}{B}\times \frac{n}{B}\times B)\) 的,当 \(B=\sqrt{n}\) 时取到最小值 \(\sqrt{n}\)。

这样查询时的复杂度为 \(O(q(B+\frac{n}{B}))\approx O(q\sqrt{n})\)。

C

神仙题。博弈论 + dp + 组合计数

赛时想到了一层,就是对每棵树求出先手能否必胜,但是这个在 \(m=1\) 才正确,因为游戏过程中的先后手会改变。

实际上我们缺少了对当前整个游戏的状态的描述,也就是我们不知道走完这棵树最后是能赢还是输。

设 \(SG(0/1,0/1)\) 表示如果最后走完这棵树回到大本营的这个人之后是必胜的,那么先手(指先到根节点的人)必胜(\(1\))还是必败 \(0\);如果最后走完这棵树回到大本营的这个人之后是必败的,那么先手必胜(\(1\))还是必败 \(0\)。

如果有 \(SG(1,1)\),那么无论如何这棵树都能让后手必败。

如果有 \(SG(1,0)\),那么这棵树会改变胜负状态。

如果有 \(SG(0,1)\),那么不会改变胜负状态。

如果有 \(SG(0,0)\),那么无论如何这棵树都能让先手必败。

那么这四种状态的出现次数决定了最后的结局。不难得出必胜的充要条件是 \(SG(1,0)\) 出现了奇数次,或者出现过 \(SG(1,1)\)。策略就是把树 \(SG(1,1)\) 留到最后走或者将 \(SG(1,0)\) 先走。

求出 \(SG\) 指关心这棵树的根节点能否主动走到深度为奇数为偶数的叶子结点,可以用树形 dp 得到。

然后根据充要条件用组合数计算答案即可。

#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define mk std::make_pair
#define fi first
#define se second
#define pb push_back

using i64 = long long;
using ull = unsigned long long;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
/*

*/
const int N = 1e5 + 10, mod = 998244353;
int m;
int f[N][2], g[2][2];
int dep[N];
i64 fac[N], inv[N];
i64 ans;
std::vector<int> e[N];
void dfs(int u) {
	if(!e[u].size()) {
		f[u][dep[u] & 1] = 1;
		return;
	}
	if(dep[u] & 1) f[u][1] = f[u][0] = 1;
	for(int v : e[u]) {
		dep[v] = dep[u] + 1;
		dfs(v);
		if(dep[u] & 1) {
			f[u][1] &= f[v][1];
			f[u][0] &= f[v][0];
		} else {
			f[u][1] |= f[v][1];
			f[u][0] |= f[v][0];
		}
	}
}
i64 qpow(i64 a, i64 b) {
	i64 ret = 1;
	while(b) {
		if(b & 1) ret = ret * a % mod;
		a = a * a % mod; 
		b >>= 1;
	}
	return ret;
}
void init(int n) {
	fac[0] = 1;
	for(int i = 1; i <= n; i++) {
		fac[i] = fac[i - 1] * i % mod;
	}
	inv[n] = qpow(fac[n], mod - 2);
	for(int i = n - 1; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1) % mod;
}
i64 C(int n, int m) {
	if(m > n) return 1;
	return fac[n] * inv[m] % mod * inv[n - m] % mod; 
}
int main() {
	freopen("game.in", "r", stdin);
	freopen("game.out", "w", stdout);

    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
	std::cin >> m;

	dep[1] = 1;
	for(int j = 1; j <= m; j++) {
		int n;
		std::cin >> n;
		for(int i = 2; i <= n; i++) {
			int fa;
			std::cin >> fa;
			e[fa].pb(i);
		}
		dfs(1);
		if(f[1][0]) {
			if(f[1][1]) g[1][1]++;
			else g[1][0]++;
		} else {
			if(f[1][1]) g[0][1]++;
			else g[0][0]++;
		}
		for(int i = 1; i <= n; i++) e[i].clear(), f[i][0] = f[i][1] = 0;
	}

	init(1e5);

	for(int i = 0; i <= g[1][0]; i++) {
		if(i & 1) ans = (ans + C(g[1][0], i) * qpow(2, g[1][1] + g[0][1] + g[0][0]) % mod) % mod;
		else ans = (ans + C(g[1][0], i) * (qpow(2, g[1][1]) - 1) % mod * qpow(2, g[0][1] + g[0][0]) % mod) % mod;
	}

	std::cout << ans << "\n";

	return 0;
}

D

又是神仙题。

容易想到 \(O(nk)\) 时间的 dp。然后就可以得到 \(60\) 分,不会了。

需要一个打表,发现 \(f_{i,j}=f_{i,i-j}\),从意义上看也比较显然,感觉类似 \(C_{n}^m=C_{n}^{n-m}\)。或者你改变一下状态的定义,从加入编号小的人和加入编号大的人两个状态可以得到两个相等的等式。

\[f_{i,j}\times (1-p)^{i-j+1}+f_{i,j}\times p^j=f_{i,j}\times p^{i-j+1}+f_{i,j}\times (1-p)^{j} \]

初始状态 \(f_{i,0}=1\),那么就可以从 \(f_{n,0}\) 递推了。

特殊情况是当 \(p=\frac{1}{2}\) 时是恒等式,此时的答案 \(f_{n,i}\) 是组合数 \(C_{n}^i\frac{1}{2^{i(n-i)}}\)。

复杂度 \(O(n\log n)\) 或 \(O(n)\)。

#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define mk std::make_pair
#define fi first
#define se second
#define pb push_back

using i64 = long long;
using ull = unsigned long long;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
/*

*/
const int mod = 998244353, N = 1e5 + 10;
i64 n, a, b, v, f, ans;
i64 inv[N], fac[N];
i64 gcd(i64 a, i64 b) {
	if(!b) return a;
	return gcd(b, a % b);
}
i64 qpow(i64 a, i64 b) {
	i64 ret = 1;
	while(b) {
		if(b & 1) ret = ret * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ret;
}
i64 C(i64 n, i64 m) {
	if(m > n) return 0;
	return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
int main() {
	// freopen("contest.in", "r", stdin);
	// freopen("contest.out", "w", stdout);

    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
	std::cin >> n >> a >> b;
	i64 g = gcd(a, b);
	a /= g, b /= g;	

	if(a == 1 && b == 2) {
		fac[0] = 1;
		for(int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
		inv[n] = qpow(fac[n], mod - 2);
		for(int i = n - 1; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1) % mod;

		v = f = 1;
		for(int i = 1; i < n; i++) {
			v = C(n, i) * qpow(qpow(2, i * (n - i) % (mod - 1)), mod - 2) % mod;
			ans = (ans + v * f % mod) % mod;
			f = (f * f % mod + 2) % mod;
		}

		std::cout << ans << "\n";
		return 0;
	}

	v = 1, f = 1;
	i64 p = a * qpow(b, mod - 2) % mod, q = (b - a) * qpow(b, mod - 2) % mod;
	for(int i = 1; i < n; i++) {
		v = v * (qpow(p, n - i + 1) - qpow(q, n - i + 1) + mod) % mod * qpow((qpow(p, i) - qpow(q, i) + mod) % mod, mod - 2) % mod; 
		ans = (ans + v * f % mod) % mod;
		f = (f * f % mod + 2) % mod;
	}

	std::cout << ans << "\n";


	return 0;
}
/*
499122177 499122177
62390313
*/

E

思维题。

你考虑每个数的形成过程,实际上就是从 \(1\) 开始不断 \(\times 10\) 或 \(+1\) 的过程,这像二叉树,于是你可以 bfs 找到第一个满足是 \(k\) 的倍数的数,他的数位和就是最小的。

#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define mk std::make_pair
#define fi first
#define se second
#define pb push_back

using i64 = long long;
using ull = unsigned long long;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
/*

*/
const int N = 1e5 + 10;
int k;
int vis[N];
void bfs(int s) {
	std::deque<pii> q;
	q.push_front(mk(1, 1));
	while(!q.empty()) {
		pii u = q.front();
		q.pop_front();
		if(!u.fi) {
			std::cout << u.se << "\n";
			return; 
		}
		if(!vis[u.fi * 10 % k]) {
			q.push_front(mk(u.fi * 10 % k, u.se));
			vis[u.fi * 10 % k] = 1;
		}
		if(!vis[(u.fi + 1) % k]) {
			q.push_back(mk((u.fi + 1) % k, u.se + 1));
		}
	}
	return;
}
int main() {
	freopen("min.in", "r", stdin);
	freopen("min.out", "w", stdout);
	
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
	std::cin >> k;

	bfs(1);

	return 0;
}

标签:std,0726,--,i64,int,开关,盖世,define,mod
From: https://www.cnblogs.com/FireRaku/p/18332297

相关文章

  • [OI] 珂朵莉树
    对于一个序列,它有较多重复元素,并且题目需要维护区间修改,维护区间信息,维护整块值域信息的,那么就可以考虑珂朵莉树解决.主要思想珂朵莉树将全部相同的颜色块压缩为一组,如对于下述序列:111234444珂朵莉树铺平后即可以变为这样:{1,3,1}{4,4,2}{5,5,3}{6,9,4}其中的三......
  • 对后端返回数据的格式化-日期
    解决方式:1).方式一在属性上加上注解,对日期进行格式化但这种方式,需要在每个时间属性上都要加上该注解,使用较麻烦,不能全局处理。方式二(推荐)**在WebMvcConfiguration中扩展SpringMVC的消息转换器,统一对日期类型进行格式处理点击查看代码/***扩展SpringMVC框......
  • 使用 Python + Beautiful Soup 抓取任何包含 5 个数字的字符串
    我住在德国,那里的邮政编码在大多数情况下都是5位数字。53525。我真的很想使用beautifulSoup从网站中提取该信息。我是Python/BeautifulSoup的新手,我不知道如何将“查找连续的每5个数字+“空格””翻译成Python语言。importrequestsimporturllib.re......
  • 【计算机方向】五本“三区水刊”重磅推荐!几乎不拒收,国人发文友好!
    本期将为您带来五本计算机SCI妥妥毕业神刊!AUTONOMOUSAGENTSAND MULTI-AGENT SYSTEMS InternationalJournalonDocumentAnalysis andRecognition COMPUTATIONALINTELLIGENCE   IETBiometrics   ACMTransactionsonAsianandLow-Resource......
  • S3:Rclone:非常好用的S3备份、同步工具。
    step0:配置backends step1:copy、sync、move操作我所关心的核心参数:--buffer-sizeSizeSuffixInmemorybuffersizewhenreadingfilesforeach--transfer(default16Mi)--checkersintNumberofcheckerstoruninparallel(default8)--transfersintNumberof......
  • Linux安装redis(超级详细)
    持续关注我,我将分享一个网站完整的搭建过程!序号内容链接1linux安装jdk1.8https://blog.csdn.net/weixin_43836859/article/details/1404782392linux安装mysql5.7https://blog.csdn.net/weixin_43836859/article/details/1406272333linux安装redishttps://blog.csdn.net/we......
  • 模拟退火
    模拟退火必须要单独开一个专题来讲模拟退火了。看到身边很多同学写的模退都是不标准的,步长没有随温度的降低而减小,只能叫随机爬山。系统的学习模退是跟着Acwing的yxc,他写的模退给人一看就有一种豁然开朗,神清气爽的感觉,让你惊叹天下竟然还有如此精妙的算法。是的,优雅的模退......
  • LeetCode-day30-2961. 双模幂运算
    LeetCode-day30-2961.双模幂运算题目描述示例示例1:示例2:思路代码题目描述给你一个下标从0开始的二维数组variables,其中variables[i]=[ai,bi,ci,mi],以及一个整数target。如果满足以下公式,则下标i是好下标:0<=i<variables.length((aibi%10)ci)......
  • 果宇科技与某迪公司应用布袋除尘器的管道插入式粉尘检测仪案例
    项目背景:某迪为了确保工业生产的安全、‌提高生产效率以及保护环境,‌保障工作人员的健康,该企业选购24台管道插入式粉尘检测仪,下面果宇科技小编分享管道插入式粉尘检测仪在某迪公司布袋除尘器的应用案例:技术背景与工作原理管道插入式粉尘检测仪概述:GY/VGD-100-PIL管道插入......
  • 有毒有害气体在线监测系统在大型钢铁厂的应用案例
    背景介绍钢铁产业是国民经济的重要支柱产业,涉及面广、产业关联度高、消费拉动大,在经济建设、社会发展、财政税收、国防建设以及稳定就业等方面发挥着重要作用。我国是钢铁工业大国,每年为全球供应超过一半以上的钢铁。在钢铁生产过程中,高炉、转炉和焦炉会产生大量煤气。煤气......