A题 Chip Game(签到)
给定一个 \(n\) 行 \(m\) 列的方格矩阵,左下角是 \((1,1)\),右上角是 \((m,n)\)。(采取了类似笛卡尔坐标系的表示法,不是普通的 \(x\) 行 \(y\) 列)
Burenka 和 Tonya 轮番在矩阵上进行游戏,Burenka 先手。初始状态下,在起点 \((1,1)\) 处有一个棋子,轮到某个人时,它可以选择将棋子向上或者向右移动奇数格(但是不可以超出边界),无法移动者判负(也就是先到达右上角终点者胜利)。
试求出在采取最优策略的情况下,获胜者会是谁。
\(T\leq 10^4,1\leq n,m\leq 10^9\)
如果 \(m\) 是偶数,\(n\) 是奇数,那么 Burenka 先手必胜:他只要直接走到 \((m,1)\) 处,然后 Tonya 就尴尬了:因为 \(n\) 是奇数,所以他不可能一步走到 \((m,n)\),只能走到 \((m,y)\) 处(\(y<n\) 且 \(y\) 是偶数),那么 Burenka 就再向上走 \(n-y\) 步即可。\(m\) 奇 \(n\) 偶时候同理(由对称性可得)。
如果 \(m,n\) 奇偶性相同,那么 Burenka 不可能一部走到终点,而其走完一部之后,必然使得对方进入了奇偶不同的状态(即先手必胜态),故 Burenka 先手必败。(采取了 SG 博弈的思想,虽然出题人可能只是想让我们模拟一下)。
综上,得到结论:\(n,m\) 奇偶性相同时先手必败,否则先手必胜。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int T;
cin >> T;
while (T--) {
int n, m;
cin >> n >> m;
puts((n + m) % 2 ? "Burenka" : "Tonya");
}
return 0;
}
B题 Mathematical Circus(数学)
给定 \(n\) 个整数 \((1,2,\cdots,n)\)(保证 \(n\) 是偶数)和整数 \(k\),问我们能否将这些整数分成 \(\frac{n}{2}\) 对,每一对都类似 \((a,b)\),并使得 \((a+k)b\) 是 4 的倍数?
\(T\leq 10^4,n,\sum n\leq 2*10^5,0\leq k\leq 10^9\)
我们直接让 \(k\) 对 4 先取一下模,方便后面分类讨论。
如果 \(k=1,3\),那就让 \(a\) 是奇数,\(b\) 是偶数就行了,类似 \((1,2),(3,4),\cdots,(n-1,n)\) 这样就行(观察样例也能看出来)。
如果 \(k=2\),也就是让 \((a+2)b\) 是 4 的倍数,我们将 \([1,n]\) 内整数也按照对 4 的取模值划分,分成 \((1,2,3,0)\) 四类,那么我们发现(也可以通过观察样例得到),可以构造 \((3,0)\) 和 \((2,1)\) 这两种配对,使得 \(a+2,b\) 里面至少有一个是 4 的倍数。
\(k=0\) 时,也就是让 \(ab\) 是 4 的倍数,因为至少有一半奇数,不可能让两个奇数进一个组,所以每个组都得有一个奇数(就让他们是 \(a\))吧,那么就得要求 \(b\)(也就是剩下的每一个偶数)都是 4 的倍数,显然不可能。
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n, k;
cin >> n >> k, k %= 4;
if (k == 0) {
puts("NO");
return;
}
puts("YES");
if (k == 2) {
for (int i = 1; i <= n; i += 2) {
if (i % 4 == 1) printf("%d %d\n", i + 1, i);
else printf("%d %d\n", i, i + 1);
}
}
else {
for (int i = 1; i <= n; i += 2)
printf("%d %d\n", i, i + 1);
}
}
int main()
{
int T;
cin >> T;
while (T--) solve();
return 0;
}
C题 Fighting Tournament(模拟优化)
给定一个长度为 \(n\) 的排列 \(\{a_n\}\),初始状态下,将该排列按照下标顺序放入一个队列中。
接着,进行无穷次操作,每次操作都会取出队头两个元素并进行“战斗”,胜者还放在队头,反之放入队尾(显然,两个元素相互“战斗”,肯定是大的那个赢)。
接下来有 \(q\) 次询问,每次询问给定 \(i,k\),问 \(a_i\) 这个数在 \(k\) 轮操作后,一共胜了多少局?
\(2\leq n\leq 10^5,1\leq q\leq 10^5,1\leq a_i\leq n,1\leq i \leq n,1\leq k\leq 10^9\),多组数据不影响数据范围
手玩几组样例后,发现:当最大的那个元素 \(n\) 到达队头时,后面的每一个操作都是它赢(没有人比它大,所以就一直呆在队头)。类似的,我们发现:如果原序列中 \(x\) 前面有比 \(x\) 大的,那么 \(x\) 的赢的次数就一定为 0(等 \(x\) 到队头的时候,前面那个数比它大,\(x\) 去队尾,然后发现队头直接变成 \(n\) 了);相反,如果 \(x\) 前面的数都小于 \(x\),那么直接看看后面 \(x\) 还能赢多少次,输了后放到队尾,下一次也就碰到 \(n\) 而赢不了了。
那么,我们分类讨论,得到结果:
-
\(a_i=n\),判断 \(n\) 还要几轮到队头,之后就一直赢
-
\(\exist j<i,a_j>a_i\),那么赢的次数就是 0
-
\(\max\limits_{1\leq j\leq i}a_j=a_i\),判断 \(a_i\) 还要几轮到队头,然后赢一局(如果 \(i=1\) 就跳过这个赢的一局),随后看后面还有连续多少数是小于 \(a_i\) 的。这东西可以二分或者线段树或者啥的,但是作为 Div2C,我们还是用一些相对简单的方法:构造前缀最大值 \(s_i=\max\limits_{1\leq j\leq i}a_i\),那么对于 \(a_i\),找出最大的 \(d\),使得 \(s_d=a_i\) 即可,而这可以用另外一个方式代替:
for (int i = 1; i <= n; ++i) farPos[s[i]] = i;
那么
d=farPos[a[i]]
。(也就是针对记录一下每个数的最右端点)
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, q, a[N], s[N], pos[N];
void solve()
{
cin >> n >> q;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
s[i] = max(s[i - 1], a[i]);
pos[s[i]] = i;
}
while (q--) {
int i, k, ans;
cin >> i >> k;
if (s[i] > a[i]) ans = 0;
else if (a[i] == n) {
int d = max(i - 2, 0);
ans = max(k - d, 0);
}
else {
int d = max(i - 2, 0);
if (k <= d) ans = 0;
else ans = min(k - d, pos[a[i]] - i + (i > 1));
}
cout << ans << endl;
}
}
int main() {
int T;
cin >> T;
while (T--) solve();
return 0;
}
D1题 Burenka and Traditions (easy version)(贪心,DP)
给定一个长度为 \(n\) 的序列 \(\{a_i\}\)。
现在,你可以执行若干次操作,每次操作都自行指定 \(l,r,x\),然后消耗 \(\lceil\frac{r-l+1}{2}\rceil\) 的能量,来将区间 \([l,r]\) 内所有元素都和 \(x\) 异或一下。
问,至少需要多少能量,才能将所有元素变为 0?
\(1\leq n,\sum n\leq 5*10^3,0\leq n\leq 5*10^3\)
发现了一个贪心的性质:反正操作需要消耗的能量和区间长度相关,那么我们只进行长度为 1 或者 2 的操作即可(大区间操作不如拆成若干个小区间,还更灵活),这使得序列操作整体上变得有序了(从前往后即可,不会出现明显的无序性)。
我们考虑 \(dp_i\) 为将前 \(i\) 个数全部变成 0 所花的能量,但是这显然不够,因为有时候我们对 \(i\) 进行操作时候,需要 \(a_{i-1}\) 是其他的数(这点可以看样例)。那么,我们加上一个维度 \(j\),用 \(dp_{i,j}\) 表示将前 \(i-1\) 个数变为 0,最后一个数变为 \(j\) 的所需代价。
那么,只进行长度为 1 的区间操作,有 \(dp_{i,j}=dp_{i-1,0}+(a_i\not=j)\),进行长度为 2 的区间操作,则有 \(dp_{i,j\oplus x}=dp_{i-1,j}+1\)。处理一下边界条件后跑一次线性 DP 即可,最后答案就是 \(dp_{n,0}\)。
注意一下,\(j\) 的范围是 \([0,8191]\),因为要考虑一下异或后会大于 \(n\) 的状态。
#include<bits/stdc++.h>
using namespace std;
const int N = 5010;
int n, a[N];
int dp[N][8192];
int solve()
{
//read
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> a[i];
//solve
for (int i = 0; i < 8192; ++i)
dp[1][i] = 1;
dp[1][a[1]] = 0;
for (int i = 2; i <= n; ++i) {
//do opt len 1
for (int j = 0; j < 8192; ++j)
dp[i][j] = dp[i - 1][0] + (a[i] != j);
//do opt len 2
for (int j = 0; j < 8192; ++j)
dp[i][a[i] ^ j] = min(dp[i][a[i] ^ j], dp[i - 1][j] + 1);
}
return dp[n][0];
}
int main() {
int T;
cin >> T;
while (T--) cout << solve() << endl;
return 0;
}
标签:10,Burenka,int,题解,队头,CF,leq,814,dp
From: https://www.cnblogs.com/cyhforlight/p/16596670.html