首页 > 其他分享 >【2024.09.15】NOIP2024 赛前集训（2）

【2024.09.15】NOIP2024 赛前集训（2）

时间：2024-09-22 21:24:17浏览次数：11  
标签：ch 15 int 2024.09 cin num rk NOIP2024 mod

【2024.09.15】NOIP2024 赛前集训（2）

A

最大的难点戏剧性地变成了二叉搜索树是什么。

先根据已知序列把二叉树建出来，忘了二叉搜索树的移步 二叉搜索树 & 平衡树 - OI Wiki (oi-wiki.org)

根据题意， 想到dp计数，\(f[u]\) 表示 \(u\) 子树内的答案， 则有转移：

\[f[u] = f[lson] \times f[rson] \times C_{siz[lson] + siz[rson]}^{siz[lson]} \]

注意！对于只有一个儿子的那些点就老老实实写分类讨论，不要写成一坨！写一坨必错！！！

时间复杂度 \(O(TN)\)

/*think twice, code once
n, m, type 
ci
ui,vi,li
q
ai,bi
*/
#include<bits/stdc++.h>
#define F(i,l,r) for(int i(l);i<=(r);++i)
#define G(i,r,l) for(int i(r);i>=(l);--i)
#define int ll 
using namespace std;
using ll = long long;
const int N = 1e3 + 5;
const int mod = 1e9 + 7;
int n, T, rt;
int a[N], ch[N][2], siz[N], inv[N], fac[N], f[N];
int quickmod(int x,int y){
	int res = 1;
	while(y){
		if(y & 1) res = res * x % mod;
		x = (x * x) % mod;
		y >>= 1;
	} return res;
}
inline int C(int x, int y){
	return fac[x] * inv[y] % mod * inv[x-y] % mod;
}
void insert(int nw, int u){
	if(u < nw){
		if(!ch[nw][0]) ch[nw][0] = u;
		else insert(ch[nw][0],u);	
	}
	else {
		if(!ch[nw][1]) ch[nw][1] = u;
		else insert(ch[nw][1],u);	
	}
}
void dfs(int u){
	if(!u) return ;
	f[u] = 1;
	siz[u] = 1;
	dfs(ch[u][0]);
	dfs(ch[u][1]);
	siz[u] += siz[ch[u][0]] + siz[ch[u][1]];
	if(ch[u][0] && ch[u][1]) f[u] = f[ch[u][0]] * f[ch[u][1]] % mod * C(siz[ch[u][0]] + siz[ch[u][1]], siz[ch[u][0]]) % mod;	
	else if(ch[u][0]) f[u] = f[ch[u][0]];
	else if(ch[u][1])f[u] = f[ch[u][1]];
}
signed main(){
	freopen("bst.in","r",stdin);
	freopen("bst.out","w",stdout);
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	fac[0] = 1; F(i,1,1000) fac[i] = i * fac[i - 1] % mod;
	inv[1000] = quickmod(fac[1000],mod-2);
	G(i,999,1) inv[i] = inv[i + 1] * (i + 1) % mod;
	cin >> T;
	while(T --){
		memset(ch, 0, sizeof(ch));
		memset(siz, 0, sizeof(siz));
		cin >> n;
		F(i, 1, n) {
			cin >> a[i];
			if(i==1) rt = a[i];
			else insert(rt, a[i]);
		}
		dfs(rt);
		cout << (f[rt] + mod - 1) % mod << '\n';	
	}
	return 0;
}

B

参考博客

思维难度极高的一道小码量题目。

将 a 看作 1， b 看作 2， 那么 连续字母的替换 等效于 连续字母求模3意义下的和。

那么对于原串的任意合法区间（“合法”指存在相邻相同字符）， 如果区间和模 3 意义下等于 1，则该区间最后可以通过一系列操作最后变为字符 a；等于 2 最后会变为字符 b；等于 0 则说明这段区间无法缩成一个字符（充分但不必要，例如aba）。

于是我们的任务便转化为：在原串上分段，然后把每段转化成一个字符，问求能得到多少种本质不同的字符串。

并且我们还能发现，我们实际上并不需要在划分的时候保证每个划分段内有相邻相同字符，因为 不合法 的划分可以转化为合法的划分！

注意：不合法仅指区间内不存在相邻相同字符，但是区间和模 3 仍不能为 0，不然无法缩成一个字符！

对序列求mod 3 意义下的前缀和 \(S\) ，然后用 dp 计数， \(f[i]\) 表示 \(1 \sim i\) 的所有划分方式， 得到的结果包括 1 和 2。记 \(val \in {0,1,2 }\)。 \(las[val]\) 表示上一个前缀和为 val 的位置, 有转移：

\[f[i] =\sum_{val =0 且 val \ne S[i]}^{2} f[las[val]] \]

只有 \(S[i] - val \ne 0\) 的情况才能转移， 因为如果 \(= 0\) 代表 \(las[val]+1 \sim i\) 这个区间没办法合并成一个字母，即 不合法。

时间复杂度 \(O(TN)\)。

#include<bits/stdc++.h>
#define F(i,l,r) for(int i(l);i<=(r);++i)
#define G(i,r,l) for(int i(r);i>=(l);--i)
using namespace std;
using ll = long long;
const int N = 1e7 + 5;
const int mod = 1e9 + 7;
char s[N];
int a[N], las[N], f[N];
int T, n;
signed main(){
//	freopen("alpha.in","r",stdin);
//	freopen("alpha.out","w",stdout);
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >>T;
	while(T--){
		memset(f, 0, sizeof(f));
		memset(las, 0, sizeof(las));
		cin >> (s + 1);
		bool tag = 0;
		n = strlen(s + 1);
		F(i, 1, n) {
			a[i] = (a[i-1] + s[i]-'a' + 1) % 3;	
			if(i > 1 && s[i] == s[i-1]) tag = 1;
		}
		if(!tag){
			cout << 1 << '\n';
			continue;
		}
		F(i, 1, n){
			f[i] = (a[i]>=1);	
			F(j, 0, 2) if(j != a[i]) f[i] = (f[i] + f[las[j]]) % mod;
			//如果last[j] + 1 ~ i 的区间和(即 a[i] - j) 为0, 那么就会被缩成 ab 或 ba , 是不合法的
            //所以只有区间和在模意义下是1或者2才能缩成a或者b 
            las[a[i]] = i;
		}
		cout << f[n] << '\n';
	}
	return 0;
}

C

给定起点 \(a[i]\), 最大长度不超过 \(b[i]\), 也就是最小化最大长度，熟悉的话容易想到 Kruskal​ 重构树.

那么就先建树，再找到最远能向上走到的祖先节点的位置 \(u\)，答案就是以 \(u\) 为根的子树内出现最多次数的颜色编号（颜色信息都储存在叶子上）

对于这些颜色信息的合并，可以使用启发式合并保证复杂度。

一些细节：

  • 倍增往上跳的时候和求 \(lca\) 一样，不能跳到 0 位置去了。
  • 注意一下启发式合并 swap 的具体手法，很有意思。
  • 学习一下代码中的分类讨论，很清晰且不容易出错。

时间复杂度 \(O(NlogN)\)。

#include<bits/stdc++.h>
#define F(i,l,r) for(int i(l);i<=(r);++i)
#define G(i,r,l) for(int i(r);i>=(l);--i)
#define fi first
#define se second
using namespace std;
using ll = long long;
const int N = 5e5 + 105;
struct node1{
	int u, v, w;
}e[N];
struct node2{ int ls, rs, w, num, col; }tr[N << 1];
unordered_map<int, int> cnt[N << 1];
int n, m, q, idx, type;
int c[N << 1], fa[N << 1], pa[N << 1][22];
inline int get(int x){
	return (fa[x] != x) ? fa[x] = get(fa[x]) : fa[x];
}
void kruskal(){
	sort(e + 1, e + m + 1, [&](node1 p, node1 q){return p.w < q.w;});
	F(i, 1, n*2)  fa[i] = i;
	idx = n;
	F(i, 1, m){
		int fu = get(e[i].u), fv = get(e[i].v);
		if(fu == fv) continue;
//		cout << fu << ' ' << fv << '\n';
		tr[++idx] = (node2){fu, fv, e[i].w};
		fa[fu] = idx;
		fa[fv] = idx;
	}
}
void dfs(int u,int f){
	pa[u][0] = f;
	F(i,1,20) pa[u][i] = pa[pa[u][i-1]][i-1];
	if(tr[u].ls){
		int v = tr[u].ls;
		dfs(v, u);
		if(cnt[u].size() < cnt[v].size()) {
			swap(cnt[u], cnt[v]);
			//cnt 在 ask 的时候不会用到, 所以交换虽然不符合实际但是不影响答案 
			tr[u].num = tr[v].num;
			tr[u].col = tr[v].col;
		}
		for(auto p : cnt[v]){
			cnt[u][p.fi] += p.se;
			if(tr[u].num < cnt[u][p.fi]){
				tr[u].num = cnt[u][p.fi];
				tr[u].col = p.fi;
			}
			else if(tr[u].num == cnt[u][p.fi]) tr[u].col = min(tr[u].col, p.fi);
		}
		cnt[v].clear();	
	}
	if(tr[u].rs){
		int v = tr[u].rs;
		dfs(v, u);
		if(cnt[u].size() < cnt[v].size()) {
			swap(cnt[u], cnt[v]);
			tr[u].num = tr[v].num;
			tr[u].col = tr[v].col;
		}
		for(auto p : cnt[v]){
			cnt[u][p.fi] += p.se;
			if(tr[u].num < cnt[u][p.fi]){
				tr[u].num = cnt[u][p.fi];
				tr[u].col = p.fi;
			}
			else if(tr[u].num == cnt[u][p.fi]) tr[u].col = min(tr[u].col, p.fi);
		}
		cnt[v].clear();		
	}
	if(!tr[u].ls && !tr[u].rs){
		tr[u].num = 1;
		tr[u].col = c[u];
		cnt[u][c[u]] ++;
	}
}
inline int ask(int x, int lim){
	G(i,20,0) if(pa[x][i] != 0 && tr[pa[x][i]].w <= lim) x = pa[x][i];
	return tr[x].col;
}
signed main(){
	freopen("garden.in","r",stdin);
	freopen("garden.out","w",stdout);
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m >> type;
	F(i, 1, n) cin >> c[i];
	F(i, 1, m){
		int u, v, w;
		cin >> u >> v >> w;
		e[i] = {u, v, w};
	}
	kruskal();
	F(i, 1, idx) if(get(i) == i) dfs(i,0);
	cin >> q;
	int ans = 0;
	F(i, 1, q){
		int a, b;
		cin >> a >> b;
		if(type == 2) a ^= ans, b ^= ans;
		cout << (ans = ask(a, b)) << '\n';
	}
	return 0;
}

D

考场上以为考的是最短路，但最后发现又是并查集。出现很多次类似的误判了……

对于能相互到达的区间，是可以相互合并的，于是我们先用一个 vector 把区间存起来，然后在线段树上合并。

注意！合并是根据给出的位置 \(pos\) 来把所有相关区间都合并掉。这也是为什么要先合并再插入新的区间。

这样的话就只剩下单向的区间且没有 被大区间完全包含的小区间了。最后可以直接按题目所给的定义判断。

有一些细节标注在代码里了，还是很受益的。

时间复杂度 \(O(NlogN)\)。

#include<bits/stdc++.h>
#define F(i,l,r) for(int i(l);i<=(r);++i)
#define G(i,r,l) for(int i(r);i>=(l);--i)
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
using ll = long long;
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
int n, cnt = 0, num = 0;
int rk[N * 2], op[N], st[N], ed[N], fa[N * 2], lx[N], rx[N];
vector<int> cur[N];
inline int get(int x){
	return (fa[x] == x) ? x : fa[x] = get(fa[x]);
}
void modify(int u, int l, int r, int pos){
	for(auto x : cur[u]){
		lx[num] = min(lx[num], lx[x]);
		rx[num] = max(rx[num], rx[x]);
		fa[get(x)] = num;
	}
	cur[u].clear();
	if(l >= r) return ;
	int mid = (l + r) >> 1;
	if(pos <= mid) modify(u * 2, l, mid, pos);
	else modify(u * 2 + 1, mid + 1, r, pos);
}
void addedge(int u, int l, int r, int x, int y){
	if(x <= l && r <= y){
		cur[u].emplace_back(num);
		return ;
	}
	int mid = (l + r) >> 1;
	if(x <= mid) addedge(u * 2, l, mid, x, y);
	if(y > mid) addedge(u * 2 + 1, mid + 1, r, x, y);
}
void add(int l, int r){
	modify(1, 1, cnt, l);
	modify(1, 1, cnt, r);
	if(lx[num] +1 < rx[num]) addedge(1, 1, cnt , lx[num] + 1, rx[num] - 1);
	//极易出错!一定要先modify在addedge! 并且不能写成 :
	//if(l + 1 < r) addedge(1, 1, cnt , l + 1, r - 1);
	//因为在modify中有 "双向可达区间"之间 的合并 
	//所以为什么 lx[num] 要 +1 ?
}
signed main(){
	freopen("interval.in","r",stdin);
	freopen("interval.out","w",stdout);
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	F(i, 1, n){
		cin >> op[i] >> st[i] >> ed[i];
		if(op[i] == 1) rk[++cnt] = st[i], rk[++cnt] = ed[i];
	}
	sort(rk + 1, rk + cnt + 1);
	cnt = unique(rk + 1, rk + cnt + 1) - rk - 1;
	F(i, 1, n){
		if(op[i] == 1){
			++num;
			fa[num] = num;
			st[i] = lower_bound(rk + 1, rk + cnt + 1, st[i]) - rk;
			ed[i] = lower_bound(rk + 1, rk + cnt + 1, ed[i]) - rk;
			lx[num] = st[i], rx[num] = ed[i];
			add(st[i], ed[i]);
		}
		else{
			int u = get(st[i]), v = get(ed[i]);//注意st, ed在两种op值下的不同含义 
			if(u == v) cout << "YES\n";
			else {
				if((lx[v] < lx[u] && rx[v] > lx[u]) || (lx[v] < rx[u] && rx[v] > rx[u])) cout << "YES\n";//读清楚定义! 边界不能取等! 
				else cout << "NO\n";
			}
		}
	}
	return 0;
}

总结：熟悉概念，能够识别，学会运用！

标签：ch,15,int,2024.09,cin,num,rk,NOIP2024,mod
From： https://www.cnblogs.com/superl61/p/18425899

相关文章

  • [考试记录] 2027.9.15 csp-s 模拟赛29
    T1出了个大阴间题（repair）#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#definelb(x)((x)&(-x))constexprintN=(1<<19)+1,M=1e9+7;intn,k,a[20],f[N],g[N][2],h[N][2],sb,sk;intmain(){ ios::sync_with_stdi......
  • Vue(15)——组合式API②
    生命周期函数 选项式组合式beforeCreate/createdsetupbeforeMountonBeforeMount       mountedonMounedbeforeUpdateonBeforeUpdateupdatedonUpdatedbeforeUnmountonBeforeUnmountunmountedonUnmounted父子通信父传子基本思想：父组件中给子组件绑定属性子组件......
  • Tomcat CVE-2017-12615 靶场攻略
    漏洞描述当Tomcat运⾏在Windows操作系统时，且启⽤了HTTPPUT请求⽅法（例如，将readonly初始化参数由默认值设置为false），攻击者将有可能可通过精⼼构造的攻击请求数据包向服务器上传包含任意代的JSP⽂件，JSP⽂件中的恶意代码将能被服务器执⾏。导致服务器上的数据泄露或获取服务......
  • 基于Spring Boot的疫苗接种系统 计算机专业毕业设计源码32315
    摘 要预防预接种工作实行网络信息化管理，是我国免疫规划工作发展的需要。接种信息实行网络信息化不仅是预防接种工作步入了一个新的台阶，更重要的是解决了多年疫苗接种过程种，免疫接种剂次不清，难以全程有效接种的问题；同时各级政府卫生行政部门亦能通过平台可以及时了解本地区免......
  • NOIP2024模拟赛7 总结
    NOIP2024模拟赛7总结A.恰钱没啥好说的。赛场就过了。比较难蚌的是，第一遍本地测的时候没有写spj，导致我们很多人T1都直接挂零了。不过后来配上重测了。B.排序由于某种神秘原因，导致线段树build写的范围是\(1\simn+1\)，update的时候写的也是\(1\simn+1\)，然而que......
  • 打卡信奥刷题（780）用Scratch图形化工具信P6414[普及组/提高组] [COCI2014-2015#1] PROSJ
    [COCI2014-2015#1]PROSJEK题目描述有一个数列aaa，现在按照下列公式求出一个数列bb......
  • 【LeetCode Hot 100】15. 三数之和
    题目描述回忆一下之前做过的两数之和，用的是哈希表存储已经遍历过的元素。但是本题要求返回值中不能有重复元素，因此需要去重，强行用哈希表的话，去重操作会很复杂。我们可以通过哪些方法来保证返回的数组中不包含重复的三元组？先将整个数组进行排序，可以保证答案数组中有\((a,b,c)\)......
  • ORA-01558: out of transaction ID’s in rollback segment SYSTEM
    联系：手机/微信(+8617813235971)QQ(107644445)标题：ORA-01092ORA-00604ORA-01558故障处理作者：惜分飞©版权所有[未经本人同意,不得以任何形式转载,否则有进一步追究法律责任的权利.]客户一个11.2.0.1的库,在重启之前报ORA-00604和ORA-01558:outoftransactionID’sinrol......
  • 2024.09.22 力扣刷题 Z字形变换
    题目：将一个给定字符串s根据给定的行数numRows，以从上往下、从左到右进行Z字形排列。比如输入字符串为"PAYPALISHIRING"行数为3时，排列如下：PAHNAPLSIIGYIR之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。请你实......
  • 历年CSP-J初赛真题解析 | 2024年CSP-J初赛单项选择（1-15）
    学习C++从娃娃抓起！记录下CSP-J备考学习过程中的题目，记录每一个瞬间。附上汇总贴：历年CSP-J初赛真题解析|汇总_热爱编程的通信人的博客-CSDN博客第1题32位int类型的存储范围是（）A.-2147483647~+2147483647B.-2147483647~+2147483648C.-2147483648~+2147483647D......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99