巅峰赛 #26 T1,T2,T5 题解

AAA混凝土批发ppl哥

2025-10-12 22:03:11

发布于：广东

99阅读

0回复

0点赞

~~其实就是为了让我的 T5 有趣解法能进讨论区而发的（~~

T1

思维：普及-
算法：普及-（快速幂）
模拟：入门
综合：普及-

好骗兄弟，好骗。

自行模拟，可以发现无论如何摆放齿轮，结果一定是合法的。

所以总情况数为 $2^{hw}$ 。

#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
int n, m;
const int mod = 998244353;
int pow(int n, int k){
	int tmp = 1;
	while(k){
		if(k & 1) tmp = tmp * n % mod;
		n = n * n % mod, k >>= 1;
	}
	return tmp;
}
signed main(){
	cin >> n >> m;
	cout << pow(2, n % (mod - 1) * (m % (mod - 1)) % (mod - 1));

	return 0;
}

时间复杂度： $O(\log p)$ ，其中 $p=998244352$ 。

T2

思维：普及-
算法：入门/普及-（无）
模拟：入门
综合：普及-

考虑贪心，先试试能不能放第一个盒子，如果可以就放，不可以再试试能不能放第二个盒子。

如果有一个数能放第一个盒子，但你把它放了第二个盒子，显然不优。

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int a[200005];
void solve(){
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	vector <int> v1, v2;
	for(int i = 1; i <= n; i++){
		if(v1.empty() || v1.back() <= a[i]) v1.push_back(a[i]);
		else if(v2.empty() || v2.back() <= a[i]) v2.push_back(a[i]);
		else{
			cout << "NO\n";
			return;
		}
	}
	cout << "YES\n";
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while(t--) solve();

	return 0;
}

时间复杂度： $O(\sum n)$ 。

T5

思维：普及-
算法：普及+/提高（树状数组，树形 DP）
模拟：普及+/提高
综合：普及+/提高

好玩，以后多出这种题。

我们可以离线所有查询，然后搜索整棵树，在搜索完后合并所有子树的信息。

这样的话查询一定得在 $O(\log n)$ 左右，我们可以使用 map 和权值树状数组存储一个节点的信息。

map 用于记录每种颜色出现了多少次，权值树状数组用于查询出现次数小于等于 $k$ 有多少种颜色。

具体实现就是这样的：

struct node{
	map <int, int> mp;
	vector <int> fenwick;
	int cursize, realsize;
	node(){fenwick.push_back(0);}
	node(int val){
		fenwick = {0, 1};
		mp[val]++;
		cursize = 1;
		realsize = 1;
	}
	void merge(node &b){// 合并两个节点
		for(int i = 1; i <= b.cursize; i++){
			fenwick.push_back(0);// 扩大树状数组容量
			cursize++;
			for(int j = 1; j < (cursize & (-cursize)); j <<= 1){
				fenwick[cursize] += fenwick[cursize - j];// 更新新增的树状数组节点
			}
		}
		for(auto it:b.mp){
			if(mp[it.first]){// 旧的元素大小增加
				for(int i = mp[it.first]; i <= cursize; i += (i & (-i))){
					fenwick[i]--;// 先在树状数组中删除这个元素
				}
			}else realsize++;// 有新元素添加
			mp[it.first] += it.second;// 修改颜色的个数
			for(int i = mp[it.first]; i <= cursize; i += (i & (-i))){
				fenwick[i]++;// 然后在树状数组加回这个元素
			}
		}
	}
	int query(int val){
		if(val > cursize) return 0; 
		val--;// 由于树状数组是查询小于等于某个数的，所以要将值 -1 来查询小于 k，继而求出大于 k 的个数
		int ans = 0;
		for(int i = val; i; i -= (i & (-i))){
			ans += fenwick[i];
		}
		return realsize - ans;// 拿总数减去小于 k 的
	}
};

然后考虑如何合并一个点的所有子树的节点。

把子树的信息全部合并在这个点上？很显然这样子单次合并时间复杂度是 $O(size\log size)$ 的，可以构造出一条链来将这种做法卡到 $O(n^2\log n)$ 。

我们可以选定子树大小最大的子节点，然后把所有信息合并到它那。为什么这样是对的呢？我们可以假设当前节点子树大小为 $n$ ，最大子节点的子树大小为 $m$ ，则其它的树大小绝对不超过 $m$ 。则时间复杂度的函数可以如下表示：

$F(n)\le O((n-m)\log n)+\frac{n}{m}F(m)$

显然，当 $m$ 与 $n$ 是同一个数量级时，只需进行 $O(n-m)$ 次合并，而递归其它子树的时间复杂度可以忽略不计，总时间复杂度约为 $O(n\log n)$ ；

当 $n$ 与 $m$ 不是同一个数量级，经主定理可得时间复杂度为 $O(n\log_2 n\log_{\frac{n}{m}} n)$ 。

所以这个做法的时间复杂度为 $O(n\log^2 n)$ 。

接下来就是如何实现了。

我们可以用一个 vector 数组，当递归到叶子结点时，在 vector 里面加入一个节点，包含它这一种颜色，并返回下标；否则先递归子树大小最大的子节点，获取它返回的下标，然后将其它向下递归，将获取的下标合并至最大的子节点上，最后返回存储最大子节点的信息的点下标。

int dfs(int cur){
	if(cur != 1 && v[cur].size() == 1){
		nodes.push_back(node(a[cur]));
		int id = nodes.size() - 1;
		for(auto it:query[cur]){
			ans[it.second] = nodes[id].query(it.first);
		}
		return id;
	}
	int id = dfs(son[cur]);
	for(int i:v[cur]){
		if(i == father[cur] || i == son[cur]) continue;
		int tmp = dfs(i);
		nodes[id].merge(nodes[tmp]);
	}
	node curnode(a[cur]);
	nodes[id].merge(curnode);
	for(auto it:query[cur]){
		ans[it.second] = nodes[id].query(it.first);
	}
	return id;
}

最终代码如下：

#include <iostream>
#include <cstdio>
#include <map>
#include <vector>
using namespace std;
struct node{
	map <int, int> mp;
	vector <int> fenwick;
	int cursize, realsize;
	node(){fenwick.push_back(0);}
	node(int val){
		fenwick = {0, 1};
		mp[val]++;
		cursize = 1;
		realsize = 1;
	}
	void merge(node &b){
		for(int i = 1; i <= b.cursize; i++){
			fenwick.push_back(0);
			cursize++;
			for(int j = 1; j < (cursize & (-cursize)); j <<= 1){
				fenwick[cursize] += fenwick[cursize - j];
			}
		}
		for(auto it:b.mp){
			if(mp[it.first]){
				for(int i = mp[it.first]; i <= cursize; i += (i & (-i))){
					fenwick[i]--;
				}
			}else realsize++;
			mp[it.first] += it.second;
			for(int i = mp[it.first]; i <= cursize; i += (i & (-i))){
				fenwick[i]++;
			}
		}
	}
	int query(int val){
		if(val > cursize) return 0; 
		val--;
		int ans = 0;
		for(int i = val; i; i -= (i & (-i))){
			ans += fenwick[i];
		}
		return realsize - ans;
	}
};
vector <pair <int, int>> query[200005];
int a[200005];
int ans[200005];
vector <int> v[200005];
int father[200005];
int siz[200005];
int son[200005];
vector <node> nodes;
int n, m;
void dfs0(int cur, int fa){
	father[cur] = fa;
	siz[cur] = 1;
	int val = 0;
	for(int i:v[cur]){
		if(i == fa) continue;
		dfs0(i, cur);
		siz[cur] += siz[i];
		if(val < siz[i]){
			son[cur] = i;
			val = siz[i];
		}
	}
}
int dfs(int cur){
	if(cur != 1 && v[cur].size() == 1){
		nodes.push_back(node(a[cur]));
		int id = nodes.size() - 1;
		for(auto it:query[cur]){
			ans[it.second] = nodes[id].query(it.first);
		}
		return id;
	}
	int id = dfs(son[cur]);
	for(int i:v[cur]){
		if(i == father[cur] || i == son[cur]) continue;
		int tmp = dfs(i);
		nodes[id].merge(nodes[tmp]);
	}
	node curnode(a[cur]);
	nodes[id].merge(curnode);
	for(auto it:query[cur]){
		ans[it.second] = nodes[id].query(it.first);
	}
	return id;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i < n; i++){
		int x, y;
		cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	for(int i = 1; i <= m; i++){
		int idx, val;
		cin >> idx >> val;
		query[idx].push_back({val, i});
	}
	dfs0(1, 0);
	dfs(1);
	for(int i = 1; i <= m; i++){
		cout << ans[i] << '\n';
	}

	return 0;
}

时间复杂度： $O(n\log^2 n+q\log n)$ 。

还有，T4 被数据 hack 了，求条。

#include <iostream>
#include <cstdio>
#include <memory.h>
#define int long long
using namespace std;
int dp[3005];
int qzh[3005];
int pzh[3005];
string a;
const int mod = 998244353;
void solve(){
	int n;
	cin >> n;
	cin >> a;
	a = ' ' + a;
	dp[1] = 1;
	qzh[1] = pzh[1] = 1;
	for(int i = 2; i <= n; i++){
		memset(dp, 0, sizeof(qzh));
		for(int j = 1; j <= i; j++){
			if(a[i - 1] == 'P'){
				dp[j] = pzh[j];
			}else if(a[i - 1] == 'V'){
				dp[j] = qzh[j - 1];
			}else{
				if(a[i] == 'P'){
					dp[j] = qzh[j - 1];
				}else if(a[i] == 'V'){
					dp[j] = pzh[j];
				}else{
					dp[j] = qzh[i - 1]; 
				}
			}
		}
		memset(qzh, 0, sizeof(pzh));
		memset(pzh, 0, sizeof(dp));
		for(int j = 1; j <= i; j++){
			qzh[j] = qzh[j - 1] + dp[j];
			qzh[j] %= mod;
		}
		for(int j = i; j; j--){
			pzh[j] = pzh[j + 1] + dp[j];
			pzh[j] %= mod;
		}
	}
	cout << qzh[n] << '\n';
	memset(dp, 0, sizeof(qzh));
    memset(qzh, 0, sizeof(pzh));
	memset(pzh, 0, sizeof(dp));
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while(t--) solve();

	return 0;
}

有帮助，赞一个

去预览

0/2000

全部评论 10

Stars_Seeker
Orz

昨天来自重庆
1
༺ཌༀ我要上南开ༀད༻
OTL

16小时前来自天津
0
™
$\Huge$ 有T6吗

16小时前来自浙江
0
- AAA混凝土批发ppl哥
  回复™
  不会
  
  16小时前来自广东
  0
- ™
  回复AAA混凝土批发ppl哥
  
  15小时前来自浙江
  0
AAA混凝土批发ppl哥
T4 神秘变量名 %%%

16小时前来自江苏
0
༺ཌༀwonder2013ༀད༻
AI代码？

昨天来自浙江
0
- AAA混凝土批发ppl哥
  回复༺ཌༀwonder2013ༀད༻
  s b，自己写的
  
  昨天来自广东
  0
- ༺ཌༀwonder2013ༀད༻
  回复AAA混凝土批发ppl哥
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  
  昨天来自浙江
  0
- AAA混凝土批发ppl哥
  回复༺ཌༀwonder2013ༀད༻
  ？
  
  昨天来自广东
  0
Stars_Seeker
qp

昨天来自重庆
0
Stars_Seeker
%%%

昨天来自重庆
0
- Moon_Seeker
  回复Stars_Seeker
  那啥你直接把你头像发出来
  
  17小时前来自浙江
  0
AAA混凝土批发ppl哥
这里的在一个数量级就是特别接近，比如说 $n=100000,m=99801$ 就是在一个数量级，而 $n=100000,m=60000$ 则不是

2天前来自广东
0
亚洲卷王 AK IOI
orz T5启发式合并也可以

2天前来自北京
0
- 复仇者_澜（不处不加团队）
  回复亚洲卷王 AK IOI
  呜我好菜启发式合并赛时44WA
  
  昨天来自广东
  1
- AAA混凝土批发ppl哥
  回复复仇者_澜（不处不加团队）
  写暴力对拍啊
  
  昨天来自广东
  0
AAA混凝土批发ppl哥
d

2天前来自广东
0

T1

T2

T5

全部评论 10

Orz

\Huge 有T6吗

热门讨论

$\Huge$ 有T6吗