T1 统计数字

模拟

solution

用 map 标记每个数出现次数即可

map 内部有序，遍历时元素为 pair 类型，第一维下标，第二维值

code

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

map<int , int> ma;
int n , x;

int main(){
	cin >> n;
	
	for(int i = 1 ; i <= n ; i ++){
		cin >> x;
		ma[x] ++;
	}
	for(auto &it : ma){
		cout << it.first << " " << it.second << endl;
	}
	return 0;
}

T2 字符串的展开

模拟 + 字符串

solution

直接模拟即可，没什么好讲的。。。

注意：小写字母 = 大写字母 + 空格 （ASCII 码中）

code

屎山代码

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

int p1 , p2 , p3;
string s , ns;

bool check1(char a , char b){
	return (a >= '0' && a <= '9' && b >= '0' && b <= '9' && a < b);
}

bool check2(char a , char b){
	return (a >= 'a' && a <= 'z' && b >= 'a' && b <= 'z' && a < b);
}

void solve(char ch){
	for(int i = 1 ; i <= p2 ; i ++) ns += ch;
}

int main(){
	cin >> p1 >> p2 >> p3;
	cin >> s;
	
	s = " " + s;
	
	for(int i = 1 ; i < s.size() ; i ++){
		if(s[i] != '-') ns += s[i];
		else{
			if(check1(s[i - 1] , s[i + 1]) || check2(s[i - 1] , s[i + 1])){
				if(s[i - 1] + 1 == s[i + 1]) continue;
				if(p3 == 1){
					if(p1 == 1){
						char ch = s[i - 1] + 1;
						while(ch < s[i + 1]){
							solve(ch); ch ++;
						}
					}
					else if(p1 == 2){
						if(check1(s[i - 1] , s[i + 1])){
							char ch = s[i - 1] + 1;
							while(ch < s[i + 1]){
								solve(ch); ch ++;
							}
						}
						else{
							char ch = s[i - 1] - ' ' + 1;
							while(ch < s[i + 1] - ' '){
								solve(ch); ch ++;
							}
						}
					}
					else{
						char ch = s[i - 1] + 1;
						while(ch < s[i + 1]){
							solve('*'); ch ++;
						}
					}
				}
				else{
					if(p1 == 1){
						char ch = s[i + 1] - 1;
						while(ch > s[i - 1]){
							solve(ch); ch --;
						}
					}
					else if(p1 == 2){
						if(check1(s[i - 1] , s[i + 1])){
							char ch = s[i + 1] - 1;
							while(ch > s[i - 1]){
								solve(ch); ch --;
							}
						}
						else{
							char ch = s[i + 1] - 1 - ' ';
							while(ch > s[i - 1] - ' '){
								solve(ch); ch --;
							}
						}
					}
					else{
						char ch = s[i + 1] - 1;
						while(ch > s[i - 1]){
							solve('*'); ch --;
						}
					}
				}
			}
			else ns += s[i];
		}
	}
	cout << ns;
	return 0;
}

T3 矩阵取数游戏

区间 dp + 高精度 + 进制

solution

首先可以将每一行分开来考虑，最后将所有行取数后的最大得分加起来即可

分别考虑每行，设 $dp_{l , r}$ 表示 $[l , r]$ 区间取数后的最大得分，有如下转移：

$$dp_{l , r} = \max(dp_{l + 1 , r} + a_l \times 2^{m - r + l} , dp_{l , r - 1} + a_r \times 2^{m - r + l})$$

注意这里是先取外围的数，再取里面的数，所以是取了 $m - r + l$ 次

注意初始化：$dp_{i , i} = 2^m$ 每个 $i$ 都要初始化

最后行取数后的最大得分即为 $dp_{1 , m}$，将所有的 dp 值取和就是 $ans$

这里 long long 会爆掉，所以要用高精度

code

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

const int N = 105;

struct hp {
	int a[200] = {0} , len = 0;

	hp operator +(hp b){
		hp ans;
		ans.len = max(len , b.len);
		for(int i = 0 ; i <= ans.len ; i ++){
			ans.a[i] += a[i] + b.a[i];
			ans.a[i + 1] += ans.a[i] / 10;
			ans.a[i] %= 10;
		}
		if(ans.a[ans.len + 1] > 0) ans.len ++;
		return ans;
	}

	hp operator *(int b){
		hp ans;
		ans.len = len;
		for(int i = 0 ; i <= ans.len ; i ++){
			ans.a[i] += b * a[i];
			ans.a[i + 1] += ans.a[i] / 10;
			ans.a[i] %= 10;
		}
		while(ans.a[ans.len + 1] > 0){
			ans.a[ans.len + 2] += ans.a[ans.len + 1] / 10;
			ans.a[ans.len + 1] %= 10;
			ans.len ++;
		}
		while(ans.a[ans.len] == 0 && ans.len > 0) ans.len --;
		return ans;
	}
	void clear(){
		memset(a , 0 , sizeof a); len = 0;
	}
};

hp Max(const hp &a , const hp &b) {
	for(int i = max(a.len , b.len) ; i >= 0 ; i --){
		if(a.a[i] > b.a[i]) return a;
		if(a.a[i] < b.a[i]) return b;
	}
	return a;
}

void print(hp ans){
	for(int i = ans.len ; i >= 0 ; i --) cout << ans.a[i];
}

int n , m , a[N][N];
hp dp[N][N] , base[N] , ans;

int main(){
	cin >> n >> m;
	
	for(int i = 1 ; i <= n ; i ++){
		for(int j = 1 ; j <= m ; j ++){
			cin >> a[i][j];
		}
	}
	
	base[0].a[0] = 1;
	for(int i = 1 ; i <= m ; i ++){
		base[i] = base[i - 1] * 2;
	}
	for(int i = 1 ; i <= n ; i ++){
		for(int j = 1 ; j <= m ; j ++){
			for(int k = 1 ; k <= m ; k ++){
				dp[j][k].clear();
			}
		}
		for(int j = 1 ; j <= m ; j ++){
			dp[j][j] = base[m] * a[i][j];
		}
		for(int l = m ; l >= 1 ; l --){
			for(int r = l + 1 ; r <= m ; r ++){
				dp[l][r] = Max(dp[l + 1][r] + base[m - r + l] * a[i][l] , dp[l][r - 1] + base[m - r + l] * a[i][r]);
			}
		}
		ans = ans + dp[1][m];
	}
	print(ans);
	return 0;
}

T4 树网的核

树的直径 + 贪心 + 二分 + 双指针

solution

先翻译一下题面：

有一颗树，求一段长度不超过 $s$ 的路径，使得树上离这个路径最远的点到这条路径的距离的最小，输出最小值

首先给出一个结论：

设在所有满足长度限制的路径中，取得最小偏心距的路径得到的偏心距为 $minECC$，则对于任意一条直径，都存在一条长度不超过 $s$ 的路径 F，使得 $ECC(F)=minECC$

证明详见 偏心距性质的证明 作者太懒了 qwq

其中偏心距以及 $ECC()$ 的定义见原题，这里不再赘述

有了这个结论，我们就可以随便求一条直径，再到直径上找核即可。具体地，用两遍 dfs 求出直径以及直径上的点，此时 $O(n^3)$ 的算法即暴力求核再统计最小的就可以了

下面考虑 $O(n\log n)$ 的算法，设 $b_u$ 为 $u$ 点到树上除直径以外最远点的距离，求 $b$ 数组时考虑以一直径端点 $p1$ 为根的有根树，先求出 $mx_u$ （表示 $u$ 点的子树中到 $u$ 最远点的距离）有：

$$mx_u = \max_{v \in son_u}(mx_u , mx_v + w(u , v))$$

所以：

$$b_u = \max(b_u , mx_v + w(u , v))$$

其中 $(u , v)$ 有边且 $v$ 不是直径上的点

随后二分最小偏心距 $k$，将最小值问题转化为存在性问题，于是我们就可以判断所求的核是否满足条件即可，设 $(p1 , p2)$ 表示直径，$(l , r)$ 表示所求的核。则可以先用双指针求最大 $l$ 满足 $d_l - d_{p1} \leqslant k$ 和最小 $r$ 满足 $d_{p2} - d_r \leqslant r$

然后对于 $\forall p \in [l , r]$ 若都有 $b_p \leqslant k$ 则有 $k$ 存在，否则不存在

code

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

const int N = 3e5 + 5;

struct edge{
	int to , w;
};

int n , s , p1 , p2 , D , idx;
int dis[N] , fa[N] , isd[N] , ld[N] , mx[N] , b[N];
vector<edge> g[N];

void dfs1(int x , int f){
	for(auto u : g[x]){
		if(u.to == f) continue;
		dis[u.to] = u.w + dis[x];
		if(dis[u.to] > dis[p1]) p1 = u.to;
		fa[u.to] = x;
		
		dfs1(u.to , x);
	}
}

void dfs2(int x , int f){
	for(auto u : g[x]){
		if(u.to == f) continue;
		dfs2(u.to , x);
		
		mx[x] = max(mx[x] , u.w + mx[u.to]);
	}
}

bool check(int res){
	int i = 1 , j = idx;
	
	while(i + 1 <= idx && dis[ld[1]] - dis[ld[i + 1]] <= res){
		i ++;
	}
	while(j - 1 >= 1 && dis[ld[j - 1]] - dis[ld[idx]] <= res){
		j --;
	}
	if(dis[ld[i]] - dis[ld[j]] > s) return false;
	for(int p = i ; p <= j ; p ++){
		if(b[ld[p]] > res) return false;
	}
	return true;
}

int main(){
	cin >> n >> s;
	
	for(int i = 1 ; i < n ; i ++){
		int x , y , w;
		cin >> x >> y >> w;
		g[x].push_back({y , w});
		g[y].push_back({x , w});
	}
	dfs1(1 , 0);
	p2 = p1 , dis[p1] = 0;
	dfs1(p1 , 0);
	fa[p2] = 0 , D = dis[p1];
	
	int x = p1;
	while(x != fa[x]){
		isd[x] = 1 , ld[++ idx] = x;
		x = fa[x];
	}
	dfs2(p1 , 0);
	
	for(int i = 1 ; i <= n ; i ++){
		for(auto u : g[i]){
			if(isd[u.to]) continue;
			b[i] = max(b[i] , mx[u.to] + u.w);
		}
	}
	int l = 1 , r = D;
	while(l < r){
		int mid = (l + r) >> 1;
		if(check(mid)) r = mid;
		else l = mid + 1;
	}
	cout << l;
	return 0;
}