给你一棵树，两个人每次只能移走一颗子树，这个子树必须是满二叉树（叶子也行），第一个人先开始，谁不能操作谁就输了，问你谁能赢。
满二叉树是奇数个节点（\(2^x-1\)），那么每次都是移走奇数个点，判奇偶性就行了。
进制转换，把给的数的10进制转化为带限制k进制，每一位都要在原本认知的基础上-1。
以k=10为例：
x = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 （十进制）
0 1 2 3 4 5 6 7 8 9 00 01 02 03 04 （十进制每一位还要-1）
如果要满足每一位-1，上面9和10是对应的，如果对每一位-1，那么10第一位-1就要把第二位退一位下来；如果先转10进制再模拟减法退位应该是可行的，代码量也应该不会很大。
还有一种做法是:
void solve(int k, int x)
{
if (!x)return;
x--;
solve(k, x / k);
ans.push_back((x % k) + 10 - k);
}
假设x=114514,k=5,我们虽然不知道x的5进制表示，但如果x的五进制表示的最后一位为0时，把x--之后它的五进制也自动进行了退位，不为0时就是最后一位-1，这样x%k得到的就是最后一位的位权，那么再把这个x/=k，相当于把x右移一位，这样递归下去直到x==0时就把x分解完了w
最后再加上题目条件10-k即可。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 10;
#define ll long long
#define pii pair<int,int>
#define fastio ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
ll mod = 1e9 + 7;
vector<int>ans;
void solve(int k, int x)
{
if (!x)return;
x--;
solve(k, x / k);
ans.push_back((x % k) + 10 - k);
}
int main()
{
fastio;
int t;
cin >> t;
while (t--)
{
ans.clear();
ll k, x;
cin >> k >> x;
solve(k, x);
for (auto i : ans)
cout << i;
cout << endl;
}
return 0;
}
给长度为n的排列，每次操作选择连续的3个数，然后删除最大的和最小的数，进行很多次最终留下一个数。问你这个排列中哪些数可以在进行某一系列操作之后留下来。
记当前的数为x，比它大的数变为1,比它小的数变为0，比较0和1的个数：
①如果0和1的个数相同，那么肯定可以让这个数最终留下来（给出一种示例操作：由于0和1的个数相同，那么每次操作最理想的就是移除一个0一个1。出现0x1和1x0时移除x两侧的0和1；剩下的情况全部枚举出来：000、111、011、100、。。。操作一个000时肯定要对应的操作一个111，不过大部分时候连续0周围都会有1，这样就可以满足移除一个0一个1，连续1同理）
②如果0和1的个数不同，那么就要把多出来的数删除。由于只存在两种删除模式（删除2个相同的数（3个连续相同的数可以这样）和各删除一个），很显然只能去寻找删除2个相同的数这种情况。
让cnt0和cnt1做差，如果为奇数就凑不出来;
否则就再里面找连续的去删，看看能不能删到0和1的数量相同的状态，再去用各减1的操作处理。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fastio ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
const int inf = 1e9 + 7;
const ll lnf = 1e18 + 7;
const int maxn = 1e6 + 10;
ll mod = 998244353;
bool ans[maxn];
int n;
int solve(int x,vector<int>&a)
{
int cnt = 0, tot = 0;
for (int i = 1; i <= n; i++)
if (a[i] > a[x])cnt++;
else if (a[i] < a[x])tot++;
if (cnt == tot)return 1;
if (abs(cnt - tot) & 1)return 0;
int flag = (cnt > tot ? 1 : -1);
int sum = 0;
for (int i = 1; i <= n; i++)
{
if (i == x)
{
sum = 0;
continue;
}
if (a[i] > a[x])
sum += flag;
else sum -= flag;
if (sum < 0)
sum = 0;
if (sum == 3)
{
if (flag == 1)
cnt -= 2;
else tot -= 2;
sum = 1;
if (cnt == tot)
return 1;
}
}
return 0;
}
int main()
{
fastio;
int t;
cin >> t;
while (t--)
{
cin >> n;
vector<int>a(n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i], ans[i] = 0;
for (int i = 1; i <= n; i++)
ans[i] = solve(i, a);
for (int i = 1; i <= n; i++)
cout << ans[i] << "";
cout << endl;
}
return 0;
}
CF gym-102452 2019-2020 ICPC Asia Hong Kong Regional Contest
原文：https://www.cnblogs.com/ruanbaiQAQ/p/14659829.html