(1条未读私信) 牛客2025秋季算法编程训练联赛2-基础组_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ

A 做游戏

image-20251031202041109

读了一遍题目发现根本没有思路， 哎，蒟蒻的oi选手啊~

为什么呢，我当时在想牛牛出石头，牛可乐出剪刀，牛牛赢了；如果说牛可乐出布赢了牛牛怎么办呢。我在考虑相互之间的博弈关系。

deepseek：你提到“牛可乐出布赢了牛牛怎么办呢”，但问题是要最大化牛牛的赢局，所以我们只关心牛牛赢的情况，而不关心牛可乐赢的情况。在计算牛牛赢局时，我们不需要考虑牛可乐赢的情况，因为赢局是独立的。

由于这三种获胜情况互不冲突，牛牛的总获胜局数即为这三种情况之和。这样计算可以确保牛牛在给定的出拳次数下获得最大获胜局数，因为每次匹配都是最优的，不会相互影响。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>

using namespace std;

long long a, b, c, x, y, z;

int main()
{
    cin >> a >> b >> c >> x >> y >> z;
    
    cout << min(a, y) + min(b, z) + min(c, x) << endl;
    
    return 0;
}

C 判正误

image-20251031204341496

这题当时没时间同时也是看到提交过了的人不多所以就没写了，但是比赛结束后我感觉是可以写出来的。

我的思路是通过快速幂 + 高精度最后限制位数来写，但是看了题解后我成小丑了！ 其实可以直接对快速幂求出来的结果进行取模运算就可以了， 不需要上高精度…

这里回顾下快速幂算法时间复杂度：O(logn)O(logn)

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
49
50
51
#include <iostream>

using namespace std;

typedef long long LL;

const LL mod = 1e9 + 10;

LL a, b, c, d, e, f, g, t;
//思考：高精度 + 快速幂 -> 取模运算 + 快速幂

LL pw(LL a, LL b)
{
	LL p = 1;
	
	a = a % mod;
	
	while (b)
	{
		if (b & 1)
			p = ((p % mod) * (a % mod)) % mod;
		a = ((a %mod) * (a % mod)) % mod;
		b >>= 1;
	}
	
	return p;
}

void solve()
{
	cin >> a >> b >> c >> d >> e >> f >> g;
	
	if (pw(a, d) % mod + pw(b, e) % mod + pw(c, f) % mod == g % mod)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> t;
	
	while (t--)
		solve();
		
	
	return 0;
}

D 数三角

image-20251031210751655

看到这个题目，我就在纠结怎样判断一个三角形是钝角三角形，我甚至想到了要做辅助线来解决；看了题解真觉得自己高中三年白上了，其实知道三角形三个顶点的坐标，用向量就可以判断是否是钝角三角形了。

向量判断方法：x1 * x2 + y1 * y2 < 0 && x1 * y2 != x2 * y1即可判断

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
#include <iostream>
#include <vector>

using namespace std;

typedef long long LL;

int n, x, y, ans;

vector<pair<int, int> > v(510);

bool judge(pair<int, int> A, pair<int, int> B, pair<int, int> C)
{
	int x1 = B.first - A.first;
	int y1 = B.second - A.second;
	int x2 = C.first - A.first;
	int y2 = C.second - A.second;
	
	return (x1 * x2 + y1 * y2 < 0 && x1 * y2 != x2 * y1);
	
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
		
	cin >> n;
	
	for (int i = 1; i <= n; i++)
	{
		cin >> x >> y;
		v[i].first = x;
		v[i].second = y;
	}
	
	for (int i = 1; i <= n; i++)
		for (int j = i + 1; j <= n; j++)
			for (int k = j + 1; k <= n; k++)
				if (judge(v[i], v[j], v[k]) || judge(v[k], v[i], v[j]) || judge(v[j], v[k], v[i]))
					ans++;
	
	cout << ans << endl;
	
	return 0;
}