# 1005 学几何导致的

1005 学几何导致的

显然，对于 $k$ 是奇数的情况，不存在解。

现在讨论 $k$ 为偶数的情况：

如果要构成 $90°$ 需要连续的线的个数是\frac{k}

$$\frac{180°}{k} \times x=90°\Rightarrow x = \frac{k}{2}$$

即每隔$\frac{k}{2}$ 条线就会形成垂直，令d = \frac{k}

我们可以根据 $n \mod d$ 的余数，将 $n$ 分成 $n\mod d$ 组，对于每一组，其中的线应该都是相互垂直或者相互平行的

对于每组内部，我们可以看做是 $k = 2$ 的情况，假设每组内部有 $t$ 条线，即一组中会有 $\lfloor \frac{t}{2}\rfloor + 1$ 条线和 $l_0$ 平行（包含 $l_0$），以及 $\lfloor \frac{t}{2}\rfloor$ 条线和 $l_0$ 垂直，那么互相垂直的线共有

$$(\lfloor \frac{t}{2}\rfloor + 1) * \lfloor \frac{t}{2}\rfloor$$

那么每一组中有到底有多少条线呢？

我们以 $n = 11, k = 8, d = 4$ 为例

我们发现

• $i \mod d$ 余 $0, 1, 2$ 的部分，每组有 $n / d + 1$ 条线
• $i\mod d$ 余 $3$ 的部分，每组有 $n / d$ 条线

这是因为在最后一块，例如图中的第 $9, 10$ 条线，是会在 $n / d$ 之后多出来的，所以需要 $+1$

我们可以总结规律，共有 $n \mod d$ 组中线条条数是 $n / d + 1$， 剩下的$d - n\mod d$ 组中的条数是 $n / d$

实现代码如下：

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

#include <bits/stdc++.h>
#define int long long
using namespace std;
int que2(int x)
{
	return (x + 1) / 2 * (x / 2);
}
void solve()
{
	int n, k;
	cin >> n >> k;
	if(k % 2 != 0)  cout << 0 << '\n';
	else
	{
		int d = k / 2; 
    	cout << (n % d) * que2(n / d + 1) + (d - n % d) * que2(n / d) << '\n';
	}
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while(t--) solve();
	return 0;
}

# 1006 学博弈论导致的

1006 学博弈论导致的

题目关键将红宝石、蓝宝石、空盒分别看成是 1 元钱，2 元钱，4 元钱

那么对应的操作可以看成是

1. 每次能拿走 $1\sim 3$ 元钱
2. 拿走 1 元钱
3. 拿走 1 元钱或 3 元钱
4. 拿走 3 元钱
5. 拿走 2 元钱
6. 拿走 3 元钱
7. 拿走 1 元钱

对于空盒的价值，因为每次拿空盒都会变出红蓝宝石，所以相当于滞后一次拿红蓝宝石；对于其价值 4，因为一次只能拿$1\sim 3$ 元钱，所以也需要拿两次，满足其滞后性

题目转换成：共有$r + 2b + 4m$ 元钱，每次可以取$1\sim 3$ 元钱，问谁必胜

我们可以从后往前推：

如果最后拿到的钱数是 1 2 3 ，那么只要一回都拿走即可，必胜

1 2 3 只可能从 4 转移过来，到达必胜态的只能是必败态，所以 4 必败

以此类推

可得到，如果开始的总金额是 4 的倍数，那么必败；否则必胜

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include <bits/stdc++.h>
#define int long long
using namespace std;
void solve()
{
	int r, b, m;
	cin >> r >> b >> m;
	if((r + 2 * b + 4 * m) % 4 == 0) cout << "Bob" << '\n';
	else cout << "Alice" << '\n'; 
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while(t--) solve();
	return 0;
}