T1 笨小猴

模拟 + 数学

solution

根据题意模拟即可

code

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

const int N = 200;

int to[N] , mx , mi = N;
string s;

bool check(int k){
	if(k == 0 || k == 1) return false;
	for(int i = 2 ; i * i <= k ; i ++){
		if(k % i == 0) return false;
	}
	return true;
}

int main(){
	cin >> s;
	
	for(int i = 0 ; i < s.size() ; i ++){
		to[s[i]] ++;
	}
	for(int i = 0 ; i < 120 ; i ++){
		mx = max(mx , to[i]);
		if(to[i]) mi = min(mi , to[i]);
	}
	if(check(mx - mi)) cout << "Lucky Word" << endl << mx - mi;
	else cout << "No Answer" << endl << 0;
	return 0;
}

T2 火柴棒等式

枚举

solution

直接枚举，容易得出枚举上界为 $1111$

在枚举时只用枚举 $i , j$ 即可，随后判断 $i , j , i + j$ 是否构成合法的火柴棒等式

code

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

const int N = 1111;

int to[10] = {6 , 2 , 5 , 5 , 4 , 5 , 6 , 3 , 7 , 6};

int n , ans;

int get(int s){
	int cnt = 0;
	if(s == 0) return 6;
	while(s){
		cnt += to[s % 10];
		s /= 10;
	}
	return cnt;
}

int main(){
	cin >> n;
	
	for(int i = 0 ; i <= N ; i ++){
		for(int j = 0 ; j <= N ; j ++){
			int k = i + j;
			if(get(i) + get(j) + get(k) == n - 4) ans ++;
		}
	}
	cout << ans;
	return 0;
}

T3 传纸条

dp

solution

翻译下题面

找到两条 $(1 , 1) -> (m , n)$ 无公共点的路径，使得路径权值和最大

设 $dp_{i , j , x , y}$ 为第一条路径走到 $(i , j)$，第二条路径走到 $(x , y)$ 的权值和最大值，有如下转移

$$dp_{i , j , x , y} = \max(dp_{i - 1 , j , x - 1 , y} , dp_{i - 1 , j , x , y - 1} , dp_{i , j - 1, x - 1 , y} , dp_{i , j - 1, x , y - 1}) + a_{x , y} + a_{i , j}$$

注意当 $(i , j) = (x , y)$ 时 dp 的值为 $0$ （非终点）

最后的 $ans$ 即为 $dp_{n , m , n , m}$

ps : 这里还有复杂度更为优秀的费用流做法，请读者自行查阅 qwq

code

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

const int N = 55;

int n , m , a[N][N] , dp[N][N][N][N];

int main(){	
	cin >> n >> m;
	
	for(int i = 1 ; i <= n ; i ++){
		for(int j = 1 ; j <= m ; j ++){
			cin >> a[i][j];
		}
	}
	for(int i = 1 ; i <= n ; i ++){
		for(int j = 1 ; j <= m ; j ++){
			for(int x = 1 ; x <= n ; x ++){
				for(int y = 1 ; y <= m ; y ++){
					dp[i][j][x][y] = max(max(dp[i - 1][j][x - 1][y] , dp[i - 1][j][x][y - 1]) , 
										max(dp[i][j - 1][x - 1][y] , dp[i][j - 1][x][y - 1])) + a[i][j] + a[x][y];
					if(x == i && y == j) dp[i][j][x][y] = 0;
				}
			}
		}
	}
	cout << dp[n][m][n][m];
	return 0;
}

T4 双栈排序

模拟 + 栈 + 二分图

solution

首先我们考虑如何判断一个数列为“可双栈排序序列”

注意到在双栈排序中，有这样子的一个性质：

对于 $(i , j)$ 如果 $\exist i < j < k$ ，$p_k < p_i < p_j$ 则在任意时刻 $i , j$ 不能在同一个栈中

证明如下：

$$\because p_k < p_i < p_j \text{ \& } i < j < k\\$$

所以 $k$ 要在 $i$ 和 $j$ 前出栈，$i$ 要在 $j$ 前出栈但是 $k$ 比 $i$ 和 $j$ 后入栈，所以根据栈的性质产生矛盾，故 $i , j$ 不能在同一个栈中

考虑如何求出所有 $(i , j)$ 点对， $i , j$ 不在同一个栈中

设 $f_i$ 为 $[i , n]$ 的最小值，显然 $f_i = \min(f_i + 1 , p_i)$ 所以我们可以枚举 $(i , j)$ 判断 $f_{j + 1} < p_i < p_j$ 即可

随后将所有的 $(i , j)$ 连边，此时形成了一张图，我们可以用 dfs 染色判断图是否为二分图

• 如果不为，则根据二分图定义必有 $(i , j)$ 要在同一个栈中，与题意矛盾，故此时不可以双栈排序
• 如果为，可以双栈排序，记录每个点颜色，根据颜色将点放入对应栈中

注意此时图可能不连通，要对每个连通块 dfs

随后我们根据染色结果模拟即可，具体地：

• 遍历序列，将元素根据颜色放入栈中
• 如果栈顶元素是下一个值，出栈，重复此操作直到没有为止

最后根据贪心调整字典序，就是可以先入栈再出栈，这样字典序更优

时间复杂度： $O(n^2)$

code

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

const int N = 1e3 + 5;

char b[N];
int n , a[N] , c[N] , f[N] , flag , id = 1;
vector<int> g[N];
stack<int> st1 , st2 , out;

void dfs(int u , int p){
	c[u] = p;
	for(int i = 0 ; i < g[u].size() ; i ++){
		int v = g[u][i];
		
		if(!c[v]) dfs(v , 3 - p);
		if(c[u] == c[v]){
			flag = 1;
			break;
		}
	}
}

void pu(int x , int i){
	if(i == 1){
		st1.push(x); b[id ++] = 'a';
	}
	else{
		st2.push(x); b[id ++] = 'c';
	}
}

int main(){
	cin >> n;
	
	for(int i = 1 ; i <= n ; i ++){
		cin >> a[i];
	}
	memset(f , 0x3f3f3f3f , sizeof f);
	for(int i = n ; i >= 1 ; i --){
		f[i] = min(f[i + 1] , a[i]);
	}
	for(int i = 1 ; i <= n ; i ++){
		for(int j = i + 1 ; j <= n ; j ++){
			if(f[j + 1] < a[i] && a[i] < a[j]){
				g[a[i]].push_back(a[j]);
				g[a[j]].push_back(a[i]);
			}
		}
	}
	for(int i = 1 ; i <= n ; i ++){
		if(!c[a[i]]) dfs(a[i] , 1);
	}
	if(flag){
		cout << 0;
		return 0;
	}
	out.push(0);
	
	for(int i = 1 ; i <= n ; i ++){
		pu(a[i] , c[a[i]]);
		
		if(!st1.empty() && st1.top() == out.top() + 1 || !st2.empty() && st2.top() == out.top() + 1){
			while(1){
				if(!st1.empty() && st1.top() == out.top() + 1){
					b[id ++] = 'b';
					out.push(st1.top());
					st1.pop();
				}
				else if(!st2.empty() && st2.top() == out.top() + 1){
					b[id ++] = 'd';
					out.push(st2.top());
					st2.pop();
				}else break;
			}
		}
	}
	for(int i = 1 ; i <= 2 * n ; i ++){
		if(b[i] == 'd' && b[i + 1] == 'a') swap(b[i] , b[i + 1]);
		if(b[i] == 'c' && b[i + 1] == 'b') swap(b[i] , b[i + 1]);
	}
	for(int i = 1 ; i <= 2 * n ; i ++){
		cout << b[i] << " ";
	}
	return 0;
}