巅峰赛 #16 全题解！！！

‮队团加不）ด้้童帅_者仇复

2024-12-19 21:37:16

发布于：广东

161阅读

0回复

0点赞

T4的题解有误，现已重写.

我们帅童玩家也是站起来了好吧（澄清一下，榜三不是我小号）

报一下个入难度：红橙橙/黄黑蓝绿绿.

T1

用 map 记录每个数字出现的次数，然后按题意判断.

#include <iostream>
#include <cstdio>
#include <map>
using namespace std;
int a[100005];
map <int, int> mp;
int main(){
	cin.tie(nullptr) -> sync_with_stdio(0);
	cout.tie(nullptr) -> sync_with_stdio(0);
	string s;
	cin >> s;
	for(int i = 0; i < s.length(); i++){
		mp[s[i] - '0']++;//记录
	}
	for(auto it:mp){
		if(it.first != it.second){//如果不相等就输出No
			cout << "No";
			return 0;
		}
	}
	cout << "Yes";

	return 0;
}

T2

每次取出第一个字符放到最后一个，判断是不是回文即可.

string没有pop_front有点烦……

#include <iostream>
#include <cstdio>
using namespace std;
int a[100005];
string s;
int main(){
	cin.tie(nullptr) -> sync_with_stdio(0);
	cout.tie(nullptr) -> sync_with_stdio(0);
	cin >> s;
	for(int i = 0; i < s.length(); i++){
		bool flag = 0;
		for(int j = 0; j < s.length(); j++){
			if(s[j] != s[s.length() - j - 1]){
				flag = 1;
				break;
			}
		}
		if(!flag){//如果是环形回文串就输出Yes
			cout << "Yes";
			return 0;
		}
		s = s.substr(1, s.length() - 1) + s[0];
	}
	cout << "No";

	return 0;
}

T3

我们可以用一种新型的记录方法，也可以记录到所有的子串.

例如 $abcadcb$ ：

遍历到第 $1$ 个字符， $l=1,r=1$ ：将 $a$ 加入字符串，并增加 $1$ 个子串： $a$ .

遍历到第 $2$ 个字符， $l=1,r=2$ ：将 $b$ 加入字符串，并增加 $2$ 个子串： $b,ab$ .

遍历到第 $3$ 个字符， $l=1,r=3$ ：将 $c$ 加入字符串，并增加 $3$ 个子串： $c,bc,abc$ .

遍历到第 $4$ 个字符， $r=4$ ：由于已经出现过了 $a$ ，所以第 $1$ 个字符就不能要了，令 $l=2$ . 此时可新增 $3$ 个子串： $a,ca,bca$ .

遍历到第 $5$ 个字符， $l=2,r=5$ ：将 $d$ 加入字符串，并增加 $4$ 个子串： $d,ad,cad,bcad$ .

遍历到第 $6$ 个字符， $r=6$ ：由于已经出现过了 $c$ ，所以第 $2,3$ 个字符就不能要了，令 $l=4$ . 此时可新增 $3$ 个子串： $c,dc,adc$ .

遍历到第 $7$ 个字符， $l=4,r=7$ ：将 $b$ 加入字符串，并增加 $4$ 个子串： $b,cb,dcb,adcb$ .

$\therefore$ 共有 $20$ 个不含有重复字符的子串.

翻译成代码如下：

#include <iostream>
#include <cstdio>
#include <set>
#define int long long
using namespace std;
int a[100005];
set <char> vis;
signed main(){
	cin.tie(nullptr) -> sync_with_stdio(0);
	cout.tie(nullptr) -> sync_with_stdio(0);
	string s;
	cin >> s;
	int ct = 0, l = 0;
	for(int i = 0; i < s.length(); i++){
		while(vis.find(s[i]) != vis.end()){//找到重复元素
			vis.erase(s[l++]);//前面的字符不能要了
		}
		vis.insert(s[i]);
		ct += i - l + 1;
	}
	cout << ct;

	return 0;
}

T4

为了方便表示，我将以 $x$ 开头， $y$ 结尾的子串数量称为 $\{x,y\}$ ，数组 $a$ 中大于数 $x$ 的个数称为 $a.LB(x)$ ，即lower bound.

个人认为本次巅峰赛最难的一题！

认真读题，可发现题目实际让我们找的是如下的代码：

for(int i = 0; i < n; i++){
    for(int j = i; j < n; j++){
        if(c[i] == c[j]) ct++;
    }
}

首先，我想到两个块合并只需要把左右两个块的 $\{x,y\}$ 相加再加上第一个块内 $x$ 的数量乘第二个块内 $y$ 的数量即可.

于是我轻松地打了个线段树代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#define int long long
using namespace std;
char c[100005];
int n, q;
int sum[26][262149];
int sum2[26][26][262149];
//sum[0] 记录数量 sum2块内值  
int size, depth;
void build(){//给出最后一层，O(n)建树 
	for(int i = size - 1; i; i--){
		for(int j = 0; j < 26; j++){
			sum[j][i] = sum[j][i * 2] + sum[j][i * 2 + 1];
		}
		for(int j = 0; j < 26; j++){
			for(int k = 0; k < 26; k++){
				sum2[j][k][i] = sum2[j][k][i * 2] + sum2[j][k][i * 2 + 1] + sum[j][i * 2] * sum[k][i * 2 + 1];//合并
			}
		}
	}
}

void modify(int i, int val){//O(logn)单点加 
	val -= 'a';
	sum[c[i] - 'a'][i + size] = 0;
	sum2[c[i] - 'a'][c[i] - 'a'][i + size] = 0;
	sum[val][i + size] = 1;
	sum2[val][val][i + size] = 1;
	c[i] = val + 'a';
	i += size;
	for(i >>= 1; i; i >>= 1){
		for(int j = 0; j < 26; j++){
			sum[j][i] = sum[j][i * 2] + sum[j][i * 2 + 1];
		}
		for(int j = 0; j < 26; j++){
			for(int k = 0; k < 26; k++){
				sum2[j][k][i] = sum2[j][k][i * 2] + sum2[j][k][i * 2 + 1] + sum[j][i * 2] * sum[k][i * 2 + 1];
			}
		}
	}
}

int query(char x, char y){
	return sum2[x - 'a'][y - 'a'][1];
}

signed main(){
	cin.tie(nullptr) -> sync_with_stdio(0);
	cout.tie(nullptr) -> sync_with_stdio(0);
	cin >> n >> q >> c;
	size = 1 << (depth = ceil(log2(n)) + 1e-5);
	for(int i = 0; i < n; i++){
		sum[c[i] - 'a'][i + size] = 1;
		sum2[c[i] - 'a'][c[i] - 'a'][i + size] = 1;
	}
	build();
	while(q--){
		int tmp;
		cin >> tmp;
		if(tmp == 1){
			int idx;
			char val;
			cin >> idx >> val;
			modify(idx - 1, val);
		}else{
			char c1, c2;
			cin >> c1 >> c2;
			cout << query(c1, c2) << '\n';
		}
	}

	return 0;
}

然后内存爆了.

后来我尝试用分块做，TLE了.

最后我使劲想想想，终于想出来了：

我们不需要维护整个线段树，真正需要维护的只是 $676$ 个结果.

我们可以换个角度考虑，如 $aababb$ ，将第 $5$ 个字符改成 $a$ ：

先统计负贡献：

在前四个字符与第五个字符的关系中， $\{a,b\}-=3$ ， $\{b,b\}-=1$ .
在第六个字符与第五个字符的关系中， $\{b,b\}-=1$ .

再统计正贡献：

在前四个字符与第五个字符的关系中， $\{a,a\}+=3$ ， $\{b,a\}+=1$ .
在第六个字符与第五个字符的关系中， $\{a,b\}+=1$ .

我们发现，如果把这个字符串拆开，分为 $a$ 字符串与 $b$ 字符串：

aa a
  b bb

那么贡献就与 $5$ 在 $a$ 字符串与 $b$ 字符串的相对位置，即 $\sum\limits_{i\in b} a.LB(i)$ 有关.

其它的字符串也有这个性质，自行验证.

可以亮代码了……吗？

等等，还有两件事没讲清楚.

1.如何快速求 $a.LB(x)$ :

如果按正常的数组处理的话，修改时间复杂度就得退化至 $O(n)$ ；

而 $set$ 只会给你返回迭代器，转换成数值又得花费 $O(n)$ 的时间.

怎么办呢？

机智的我想到了用树状数组模拟数组！只要每次加入元素在该元素的下标增加 $1$ ，删除元素在该元素的下标增加 $-1$ ，那么查询某个下标的结果就是 $a.LB(x)$ ！

使用这种方法也可以以 $O(n\log n)$ 的时间复杂度求得一个数组的逆序对.

struct fenwickarray{//树状“数组” 
	int a[100005];
	int size = 0;
	void insert(int idx){//加入元素 
		size++;//修改元素数量
		for(; idx <= n; a[idx]++, idx += (idx & (-idx)));
	}
	void erase(int idx){//删除元素 
		size--;
		for(; idx <= n; a[idx]--, idx += (idx & (-idx)));
	}
	int lower_bound(int idx){//获取这个的相对位置 
		int ct = 0;
		for(; idx; ct += a[idx], idx -= (idx & (-idx)));
		return ct;
	}
};

2.初始化时间复杂度问题：

确实，通过上面的办法可以让修改变为 $O(\log n)$ ，查询变为 $O(1)$ ，但是要初始化. 而如果按照上面的代码初始化，时间复杂度是 $O(n^2)$ ！

没关系，稍微推导一下，就可以推出 $\{x,y\}=\sum\limits_{i\in y} x.LB(i)+(i\in x)$ .

该题代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <vector>
#define int long long
#pragma GCC optimize(2)
using namespace std;
char c[100005];
int ans[26][26];
int n, q;
struct fenwickarray{//树状“数组” 
	int a[100005];
	int size = 0;
	void insert(int idx){//加入元素 
		size++;//修改元素数量
		for(; idx <= n; a[idx]++, idx += (idx & (-idx)));
	}
	void erase(int idx){//删除元素 
		size--;
		for(; idx <= n; a[idx]--, idx += (idx & (-idx)));
	}
	int lower_bound(int idx){//获取这个的相对位置lower_bound
		int ct = 0;
		for(; idx; ct += a[idx], idx -= (idx & (-idx)));
		return ct;
	}
}a[26];
vector <int> orgin[26];//记录初始的元素 
void modify(int idx, char val){
	val -= 'a';

	for(int i = 0; i < 26; i++) ans[i][c[idx] - 'a'] -= a[i].lower_bound(idx);//计算贡献
	for(int i = 0; i < 26; i++) ans[c[idx] - 'a'][i] -= a[i].size - a[i].lower_bound(idx);
	
	a[c[idx] - 'a'].erase(idx);//删除
	a[val].insert(idx);//加入
	
	for(int i = 0; i < 26; i++) ans[i][val] += a[i].lower_bound(idx);
	for(int i = 0; i < 26; i++) ans[val][i] += a[i].size - a[i].lower_bound(idx);
	 
	c[idx] = val + 'a';//最后别忘了修改！
}
int query(char x, char y){
	return ans[x - 'a'][y - 'a'];//直接返回答案即可
}
signed main(){
	cin.tie(nullptr) -> sync_with_stdio(0);
	cout.tie(nullptr) -> sync_with_stdio(0);
	cin >> n >> q >> c + 1;
	for(int i = 1; i <= n; i++){
		a[c[i] - 'a'].insert(i);//加入进去 
		orgin[c[i] - 'a'].push_back(i);
	}
	for(int i = 0; i < 26; i++){
		for(int j = 0; j < 26; j++){
			for(int k:orgin[i]){//直接遍历原来的，减少常数项大小
				ans[i][j] += (a[j].size - a[j].lower_bound(k) + (c[k] == j + 'a'));//初始化
			}
		}
	}
	
	while(q--){
		int tmp;
		cin >> tmp;
		if(tmp == 1){
			int idx;
			char val;
			cin >> idx >> val;
			modify(idx, val);
		}else{
			char c1, c2;
			cin >> c1 >> c2;
			cout << query(c1, c2) << '\n';
		}
	}

	return 0;
}

T5

模板题，参考区间根号题.

我们发现最多只会运算 $350$ 次，所以 $O(350n)$ 是完全可以的.

具体做法：维护一个线段树，记录区间内 $1$ 的个数，修改时如果发现有一个子树内的元素都为 $1$ 就不搜了；查询直接按普通线段树做.

由于这个算法是自顶而下的，所以就不能用重口味线段树了.

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int a[200005], sum[800005];
int n, q;
void build(int u, int l, int r){//O(n)建树
	if(l == r){
		cin >> a[l];
		sum[u] = (a[l] == 1);//判断是否为1
		return;
	}
	int mid = l + r >> 1;
	build(u * 2, l, mid), build(u * 2 + 1, mid + 1, r);
	sum[u] = sum[u * 2] + sum[u * 2 + 1];
}

void __modify(int u, int l, int r, int x, int y){
	if(l == r){
		a[l] = (a[l] & 1 ? a[l] * 3 + 1 : a[l] / 2);//暴力计算
		sum[u] = (a[l] == 1);
		return;
	}
	int mid = l + r >> 1;
	if(x <= mid && sum[u * 2] < mid - l + 1) __modify(u * 2, l, mid, x, y);//如果全是1就不遍历了
	if(y > mid && sum[u * 2 + 1] < r - mid) __modify(u * 2 + 1, mid + 1, r, x, y);
	sum[u] = sum[u * 2] + sum[u * 2 + 1];
}

int __query(int u, int l, int r, int x, int y){
	if(x <= l && y >= r) return sum[u];
	
	int mid = l + r >> 1;
	int ct = 0;
	if(x <= mid) ct += __query(u * 2, l, mid, x, y);
	if(y > mid) ct += __query(u * 2 + 1, mid + 1, r, x, y);
	
	return ct;
}
#define modify(l, r) __modify(1, 1, n, l, r)
#define query(l, r) __query(1, 1, n, l, r)
int main(){
	cin.tie(nullptr) -> sync_with_stdio(0);
	cout.tie(nullptr) -> sync_with_stdio(0);
	cin >> n >> q;
	build(1, 1, n);
	while(q--){
		int tmp, l, r;
		cin >> tmp >> l >> r;
		if(tmp == 1) modify(l, r);
		else cout << query(l, r) << '\n';
	}

	return 0;
}

T6

一开始没读题就0帧起手，写了个bfs找环+Floyd算法.

直到我看到了：不会重复经过同一个车站.

天塌了70+行的代码白写了

但是这个提示也带给我了一个好消息：消耗的时间最多也不会超过 $15$ .

这就让我想到了最短Hamilton路径的解法：状压DP.

巧了，在这题也同样适用！

我们弄个dp， $dp[i][j][k]$ 表示从 $i$ 出发，第 $k$ 个状态，最后一个点为 $j$ 是否可能实现.

然后枚举每个时间和所有点，判断当时间为 $i$ ，选取 $j$ 点作为车站是否可行.

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int a[20];
bool edge[20][20];
bool dp[15][15][32768];
vector <int> v[16];
int n, m, k;
//15？肢解暴力！ 
int main(){
	cin.tie(nullptr) -> sync_with_stdio(0);
	cout.tie(nullptr) -> sync_with_stdio(0);
	cin >> n >> m >> k;
	for(int i = 0; i < k; i++) cin >> a[i], a[i]--;//由于状压DP需要以0作为起始点，所以要-1 
	for(int i = 0; i < m; i++){
		int x, y;
		cin >> x >> y;
		edge[x - 1][y - 1] = edge[y - 1][x - 1] = 1;//同理
	}
	for(int i = 0; i < n; i++){//遍历所有点 
		dp[i][i][1 << i] = 1;
		for(int tmp = (1 << i) + 1; tmp < (1 << n); tmp++){//遍历每一个状态
			for(int j = 0; j < n; j++){
				if(tmp >> j & 1){//这个状态是否包括这个点
					for(int k = 0; k < n; k++){
						if((tmp >> k & 1) && edge[j][k]){//这个状态是否包括这个点，这两个点是否可达
							dp[i][k][tmp] = (dp[i][k][tmp] || dp[i][j][tmp - (1 << k)]);//更新，之前的经历告诉我逻辑或比按位或更快
						}
					}
				}
			}
		}
	}
	for(int i = 0; i < (1 << n); i++){
		v[__builtin_popcount(i)].push_back(i);//记录当前状态所需的时间
	}
	
	for(int times = 0; times <= n; times++){//选时间 
		for(int tmp = 0; tmp < n; tmp++){//挑车站 
			bool flag = 1;
			for(int i = 0; i < k; i++){//看看人 
				bool flag2 = 0;
				for(int j:v[times]){
					if(dp[a[i]][tmp][j]){
						flag2 = 1;
						break;
					}
				}
				if(!flag2){flag = 0; break;}
			}
			if(flag){cout << tmp + 1; return 0;}
		}
	}
	
	cout << -1;

	return 0;
}