P14584 [LNCPC 2025] 点击平衡球

题目背景

Z 形管道猫推荐您来玩平衡球（Ballance）。在游戏中，玩家要操纵一个可以改变自身材质（即物理性质）的球在由路面和机关构成的庞大而复杂的迷宫建筑中穿梭，避开陷阱、运用机关并破解一个个谜题，最终到达终点。

题目描述

平衡球有 33 种材质（纸球、木球、石球）。在游戏中，平衡球需要通过 nn 个机关，每个机关各自只允许特定一些材质的平衡球通过。初始，您需要花费 11 单位的代价将平衡球选定为一种材质。在通过每个机关前，您可以花费 11 单位的代价将平衡球切换为另一种材质，也可以不花费代价保持当前材质。

现在您可以任意安排机关的通过顺序，请您求出平衡球通过这 nn 个机关所需的最小代价。

输入格式

第一行给定一个整数 n(1≤n≤100)n(1\le n\le 100)，表示机关总数。

接下来 nn 行，每行给定三个整数 ai,1,ai,2,ai,3(ai,1,ai,2,ai,3∈{0,1})a_{i,1},a_{i,2},a_{i,3}(a_{i,1},a_{i,2},a_{i,3}\in\{0,1\})，其中第 ii 行的第 jj 个整数 ai,ja_{i,j} 为 00、11 分别表示给定的第 ii 个机关不允许、允许第 jj 种材质的平衡球通过。保证 ai,1,ai,2,ai,3a_{i,1},a_{i,2},a_{i,3} 不全为 00。

输出格式

一个整数，表示经由合理安排机关的通过顺序和材质的代价花费，平衡球通过这 nn 个机关所需的最小代价。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
5
1 0 0
1 0 1
0 1 0
1 0 1
0 0 1

输出 #1

1
3

说明/提示

一种机关的通过顺序和材质的代价花费的合理安排如下：
机关的通过顺序依次为给定的第 33、11、44、55、22 个机关。
初始，花费 11 单位的代价将平衡球选定为第 22 种材质。
在通过给定的第 33 个机关前，不花费代价保持当前材质。
在通过给定的第 11 个机关前，花费 11 单位的代价将平衡球切换为第 11 种材质。
在通过给定的第 44 个机关前，花费 11 单位的代价将平衡球切换为第 33 种材质。
在通过给定的第 55 个机关前，不花费代价保持当前材质。
在通过给定的第 22 个机关前，不花费代价保持当前材质。

可以证明，经由合理安排机关的通过顺序和材质的代价花费，平衡球通过这 nn 个机关所需的最小代价是 33。

题解：

发现结果一共只有三种。

  • 如果存在某一个位置，n 个点都可以经过，那么答案是 1。
  • 如果存在某三个机关，分别只能允许 1,2,3 经过，那么必须交换三次，答案是 3。
  • 否则答案是 2。

时间复杂度线性。

代码：

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
#include <bits/stdc++.h>
using namespace std;

int n, x, y, z;

int c[4], d[4];
//c数组记录每种材质出现次数,d数组表示只有一种材质的情况是否出现
bool f = false;

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> x >> y >> z;
		c[1]+=x;
		c[2]+=y;
		c[3]+=z;	
		if (x+y+z==1)
		{
			if (x==1)d[1]=1;
			if (y==1)d[2]=1;
			if(z==1)d[3]=1;
		}
	}
	
	if (c[1]==n||c[2]==n||c[3]==n)
	{
		cout << 1 << endl;
	}
	else if (d[1]&&d[2]&&d[3])
	{
		cout << 3 << endl;
	}
	else
	{
		cout << 2 << endl;
	}
	
	return 0;
}

P14589 [LNCPC 2025] 子鼠

题目背景

Z 形管道猫正在研究如何高效发动《三国杀》中的“子鼠”。

题目描述

子鼠：技能，您可以选择一名卡牌数大于您的其他角色，然后获得其的一张卡牌。

总共有 nn 名角色，您是第 11 名角色。初始，第 ii 名角色有 aia_i 张卡牌。

请您求出只通过您发动任意次（可以零次）“子鼠”后，您的卡牌数的最大值。

输入格式

每个测试点包含多组测试数据。第一行给定一个整数 T(1≤T≤104)T(1\le T\le 10^4)，表示测试数据组数。

对于每组测试数据：
第一行给定一个整数 n(1≤n≤106)n(1\le n\le10^6)，表示角色数。
第二行给定 nn 个整数 ai(0≤ai≤109)a_i(0\le a_i\le10^9)，其中第 ii 个整数 aia_i 表示初始第 ii 名角色的卡牌数。

保证在每个测试点中所有测试数据的 nn 的总和不超过 10610^6。

输出格式

对于每组测试数据，输出一行一个整数，表示只通过您发动任意次“子鼠”后，您的卡牌数的最大值。

输入输出样例 #1

输入 #1

1
2
3
4
5
2
3
0 3 1 
4
0 2 3 0

输出 #1

1
2
2
2

说明/提示

对于样例的第一组测试数据：
您发动第一次“子鼠”：选择第 22 名角色，然后获得其的一张卡牌。各角色的卡牌数变为 1,2,1\textbf{\color{red}1},\textbf{\color{red}2},1。
您发动第二次“子鼠”：选择第 22 名角色，然后获得其的一张卡牌。各角色的卡牌数变为 2,1,1\textbf{\color{red}2},\textbf{\color{red}1},1。
因为此时没有卡牌数大于您的其他角色，所以您无法发动第三次“子鼠”。
可以证明，只通过您发动任意次“子鼠”后，您的卡牌数的最大值是 22。

对于样例的第二组测试数据：
您发动第一次“子鼠”：选择第 33 名角色，然后获得其的一张卡牌。各角色的卡牌数变为 1,2,2,0\textbf{\color{red}1},2,\textbf{\color{red}2},0。
您发动第二次“子鼠”：选择第 22 名角色，然后获得其的一张卡牌。各角色的卡牌数变为 2,1,2,0\textbf{\color{red}2},\textbf{\color{red}1},2,0。
因为此时没有卡牌数大于您的其他角色，所以您无法发动第三次“子鼠”。
可以证明，只通过您发动任意次“子鼠”后，您的卡牌数的最大值是 22。

题解：

看完题目，可以发现如果想要你的手牌最大，那你肯定先从手牌小的人的手牌开始拿。

因为当你获得一张手牌时，必定有一个人失去一张手牌，所以这道题需要排序。

然后去找第一个比自己大的，然后去发动子鼠，可以发现的是，如果你找的是第 i 个人，他有aia_i的手牌，那么你的手牌数极限情况下应该是 (a1+ai+1)/2(a_1+a_i+1)/2，注意这里不可以慢慢的自己加，别人减，回超时。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,n,a[1000005],cnt;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>T;
	while(T--){
		cin>>n;
		for(int i=1;i<=n;i++)cin>>a[i];
		sort(a+2,a+1+n);//注意是第 1 个玩家，所以不可以排第一个
		cnt=2;
		while(cnt<=n){
			while(a[cnt]<=a[1]&&cnt<=n)cnt++;
			if(cnt!=n+1)a[1]=(a[1]+a[cnt]+1)/2;//不能一个一个的加和减，会超时间
			cnt++;
		}
		cout<<a[1]<<"\n";
	}
	return 0;
}