B1. Palindrome Game (easy version)
题意
给定一个长度为$n$的01
序列,初始为回文串,Alive 和 Bob 轮流做以下操作之一:
- 将0变成1,花费1。
- 翻转(reverse)整个串,花费0。(只能在当前不是回文串,且上次操作不是翻转时做)
Alive先手,花费少的赢,相同的话平局,求结局。
思路
设 0
的个数为x
。且初始为回文串,串对称
$x$为偶数时:
串是对称的,则Alice初始不能翻转,只能操作1,此时串为非回文。
轮到Bob,就对称着Alice的那个位置变,使得变完之后串还为回文。此时两边花费相同
到Alive,又回到了和刚才一样的情况,这样一直到还剩下两个0
,Alice变完,串不回文,bob翻转,Alice不能翻转 只能变最后一个,则Bob胜
。
$x$为奇数时:
因为串对称,x要为奇数,那么多出的1个0
,一定在中间,此时n也为奇数。
Alice先手变中间的0之后,串为回文,就回到了之前的偶数情况,Alive做对应操作,Alive胜
。
特殊情况x = 1
:bob胜
平局:只有x=0
时为平局。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
#define x first
#define y second
const int N = 100010;
int a[N];
int n, m;
char s[N];
void solve()
{
cin >> n >> s + 1;
int x = 0;
for(int i = 1; i <= n; i ++)
if(s[i] == '0') x ++;
if(x == 0) cout << "DRAW" << endl;
else if(n % 2 == 0 || (n & 1) && s[(n + 1) / 2] == '1' || x == 1) cout << "BOB" << endl;
else cout << "ALICE" << endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int t;
cin >> t;
while(t --)
solve();
return 0;
}
B2. Palindrome Game (hard version)
题意
和b1的区别是,初始不一定为回文。
思路
只看串中的0,判断对称位置i
和(n - i + 1)
是否都为0,分为两种。
设x
为 对称位置的0
的个数,y
为不对称位置的0
的个数。
平局:
x = y = 0
时平局。- n为奇数,有两个不对称的0,且其中一个在中间时,平局。
比上面多了一种情况.
y <= 1 时:
特殊情况y = 1,x = 0
, 若n为奇数,且0在中间 Bob胜
,否则Alice胜
。
其他和b1一样
y > 1时:
只要y不等于0,串就不为回文,alice先手可以翻转,bob只能变,y诺不为0,alice还能翻转......
则bob的目标是先把串变成回文。这样一直到 y = 1
的情况,同上。
Alice必胜
。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
#define x first
#define y second
const int N = 100010;
int a[N];
int n, m;
char s[N];
void solve()
{
cin >> n >> s + 1;
int x = 0, y = 0;
for(int i = 1; i <= (n + 1) / 2; i ++)
{
int cnt = 0;
if(s[i] == '0') cnt ++;
if(s[n - i + 1] == '0') cnt ++;
if(cnt == 1 || cnt && i == (n + 1) / 2 && n & 1) y ++;
else if(cnt == 2) x ++;
}
if(x == 0 && y == 0 || n & 1 && s[(n + 1) / 2] == '0' && y == 2 && x == 0) cout << "DRAW" << endl;
else if(y == 1 && n & 1 && s[(n + 1) / 2] == '0' && x == 0) cout << "BOB" << endl;
else if(y) cout << "ALICE" << endl;
else cout << "BOB" << endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int t;
cin >> t;
while(t --)
solve();
return 0;
}
C. Sequence Pair Weight
题意
一个序列的权重定义为相同值的无序索引对,也就是区间内相同的数选两个,权值为选法的数量。
给n个数,求所有子段的权值。
思路
好累不想打字了(
感谢 @影无痕
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
#define x first
#define y second
const int N = 100010;
int a[N];
map<int, LL> m;
void solve()
{
m.clear();
int n;
cin >> n;
LL ans = 0;
for(int i = 1; i <= n; i ++)
{
int x;
cin >> x;
if(m[x]) ans += m[x] * (n - i + 1ll);
m[x] += i;
}
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int t;
cin >> t;
while(t --)
solve();
return 0;
}
已经点踩