2024黑龙江省赛-VP

发表于 更新于 分类于 ， ， 阅读次数： Waline： 本文字数： 1.8k 阅读时长 ≈ 7 分钟

I.This is an easy problem

超级无敌简单的签到

1
2
3
4
5
6
7
void slove() {
	int x;
	cin>>x;
	int s = 0;
	while(x) x-=x&-x, s++;
	cout<<s<<endl;
}

##B.String

题意

斯诺有一串字符，现在他想用魔法缩短这串字符。每次他施法时，都可以消除三个相邻的相同字符。但斯诺觉得反复施法太费时间了，所以他希望您能帮他计算出使用任意次数魔法后字符串的最短形式。

题解

可以注意到一种典型的

1
aabcccbba

这种嵌套的字符串，与栈的特性很类似，是一种特殊的“括号匹配”，不过此处是三个为一组合法的符号序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void slove() {
	string s;
	cin>>s;
	n = s.size();
	for(int i=0;i<n;++i){
		stk[++top] = s[i];

		// for(int i=1;i<=top;i++) cout<<stk[i];
		// 	cout<<endl;

		int cc = 0;
		for(int j = top;j>=top-2&& j > 0; --j){
			cc++;
			if(stk[j-1] != stk[j]) break;
		}

		if(cc == 3){
			top-=3;
		}
	}

	if(!top) cout<<"NAN"<<endl;
	for(int i=1;i<=top;i++) cout<<stk[i];
	return;
}

J.Trade

在一个繁荣的国家，金斯诺决定从事贸易。

这个国家由 \[n*m\] 座城市组成。每个城市由一对整数 \[(x, y)\] 表示，其中 \[1\leq x\leq n\] 和 \[1\leq y\leq m\] 表示其在网格中的位置。在城市 \[(x,y)\] 中，物品的价格用 \[a[x][y]\] 表示，到达该城市的旅行费用用 \(b[x][y]\) 表示。

在踏上旅程之前，金斯诺需要你为他规划一条路线。路线必须符合以下条件：

  • 路线的起点必须是位于第一行第一列的城市，即 \[(1, 1)\] 。
  • 路线的终点必须是位于最后一行（ \[x = n\] ）或最后一列（ \(y = m\) ）的城市。
  • 金斯诺只能从城市 \[(x_i, y_i)\] 移动到 \[(x_i+1, y_i)\] 或 \[(x_i, y_i+1)\] 。因此，对于路线中的每一步 \(i\) （路线中的最后一步除外）， \[(x_{i+1}, y_{i+1})\] 必须选择在 \[(x_i, y_i)\] 的正下方或正右方。

进入路线后，Kingsnow 将在路线的第一个城市 \[(1, 1)\] 购买一件物品。然后，他将任意选择路线上的另一个城市出售该物品。此外，从他开始旅行的城市到他出售物品的城市之间，每到一个城市，他都会支付旅行费用。

也就是说，对于任何给定的路线 \[(x_1, y_1), (x_2, y_2), ..., (x_k, y_k)\] ，Kingsnow 都会从区间 \[[2, k]\] 中任意选择一个整数 \(t\) 。他在城市 \((x_t, y_t)\) 出售商品的利润计算公式为 \[ \text{Profit} = a[x_t][y_t] - a[1][1] - \sum_{i=1}^t b[x_i][y_i]\]

金斯诺寻找的路线是，无论他选择在路线上的哪个城市出售物品，他都能获得非负利润。

题解

然我们重新看一看这个式子

\[ \text{Profit} = a[x_t][y_t] - a[1][1] - \sum_{i=1}^t b[x_i][y_i]\]

我们把它简单变换一下 \[ Profit = a[x_t][y_t] - a[1][1] - \sum_{i=1}^{t} b[x_i][y_i]\ge 0\\ \rightarrow a[x_t][y_t] - \sum_{i=1}^{t} b[x_i][y_i]\ge a[1][1] \\ \rightarrow a[x_t][y_t] \ge a[1][1]+\sum_{i=1}^{t} b[x_i][y_i] \] 简单思考一下，我们似乎并不关心\[a[x_t][y_t]\]每一个的值，只关心他是否大于右边这个值

再看一看\[n,m \le 1000\]这个数据量对dp，记忆化都是可行的。显然我们可以处理出对每一个点的最小总合b值，对于满足上面条件的点我们记录一下，最后看一看起始点与最终点是否是一个连通块。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
int dfs(int x,int y){
	if(x==n && y == m) return 1;
	if(x >n || y> m || (!st[x][y])) return 0;
	st[x][y] = 0;

	if(dfs(x+1,y)) return 1;
	if(dfs(x,y+1)) return 1;

	return 0;
}

void slove() {
	memset(f,0x3f,sizeof f);
	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++)
		cin>>b[i][j];

	f[1][0] = f[0] [1] = 0; 
	for(int i = 1;i<=n;i++) for(int j=1;j<=m;j++){
		f[i][j] = min(f[i-1][j] + b[i][j], f[i][j-1] + b[i][j]);
	}

	// for(int i=1;i<=n;++i) {
	// 	for(int j=1;j<=m;++j)
	// 		cout<<f[i][j]<<'\t';
	// 	cout<<endl;
	// }

	for(int i=1;i<=n;i++) for(int j=1;j<=m;++j){
		if(f[i][j] + a[1][1] <= a[i][j]){
			st[i][j]  = 1;
		}
	}

	st[1][1] = st[n][m] = 1;

	// for(int i=1;i<=n;++i) {
	// 	for(int j=1;j<=m;++j)
	// 		cout<<st[i][j];
	// 	cout<<endl;
	// }

	if(dfs(1,1)) puts("YES");
	else puts("NO");
}

K. Puzzle

题意

24 字谜是一道经典的算术谜题，其目的是找到一种方法来处理四个整数，使最终结果为 24。

Nerifish 非常喜欢这种谜题，因此他为自己设计了一个类似的谜题。

Nerifish 有四张扑克牌，每张牌上的数字都是 \[a,b,c,d(1\leq a,b,c,d\leq 13)\] 。他可以按照任意顺序排列扑克牌，并用加号、减号和乘号将它们连接起来。请注意，不能使用括号，最终表达式应包含 4 个整数和 3 个运算符。

Nerifish 想知道他能得到多少结果。

题解

简单的计算可得\[2^8 = 256\]

暴力！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
void dfs(int u,stack<int> s,set<int>& S){
	if(u==3) {
		int ans = 0;
		while(s.size()) ans += s.top(),s.pop();
		// cout<<ans<<endl;
		S.insert(ans);
		return ;
	}
	if(u==0) s.push(a[u]);
	for(int i=0;i<3;++i){
		if(i==0) {
			s.push(a[u+1]);
			dfs(u+1,s,S);
			s.pop();
		}
		else if(i == 1) {
			s.push(-a[u+1]);
			dfs(u+1,s,S);
			s.pop();
		}
		else {
			int t = s.top();s.pop();
			s.push(t * a[u+1]);
			dfs(u+1,s,S);
			s.pop();
		}
	}
	return ;
}

void slove() {
	for(int i=0;i<4;i++) cin>>a[i];

	sort(a,a+4);

	set<int> S;
	do{
		// for(int i=0;i<4;++i) cout<<a[i] << ' ';
		// 	cout<<endl;
		stack<int> t;
		dfs(0,t, S);
	}while(next_permutation(a,a+4));

	cout<<S.size();
	return ;
}

D.Card Game

题意

甲和乙在玩纸牌游戏，游戏开始时，甲和乙各有一些健康值，分别叫做 hpa 和 hpb 。每个玩家开始时都有 n 张牌，分别叫做 \[a_1, a_2... a_n \]和 b1, \[b_1,b_2...b_n\] ，每个玩家每回合都要出一张他之前没有出过的牌。卡牌分为两种：攻击卡牌和防御卡牌。每张攻击卡都有攻击力，如果一方出了攻击卡，而另一方没有出防御卡，则另一方的健康值会减少攻击卡的攻击力；如果另一方出了防御卡，则他的健康值不会减少。如果一方出了一张防御牌，除了防御对方的攻击外，没有其他效果。

回合结束时，如果任何一方的健康值小于或等于零，游戏就结束。如果只有一方的健康值小于或等于零，则另一方获胜。如果双方的健康值都小于或等于零，则平局。如果所有回合结束后，没有一方的健康值为零或更少，则也是平局。

我们称 A 打出的牌序列为 \[p_1, p_2... p_n \]，称 B 打出的牌序列为 \[q_1, q_2... q_n\] ，它们是从 1 到 n 的排列。如果在 i - th 回合之前游戏还没有结束，那么在 i - th 回合，甲会下 api ，乙会下 bqi 。

现在你知道了 A 和 B 的牌。问题是是否存在一对A和B的出牌顺序能让A获胜。

题解