# 小苯的石子游戏

# 题目大意

现在有 $n$ 堆石子，每堆石子里有 $a_i$ 个石子，两个人轮流从石堆里取石子，谁先无法取谁输，取石子的规则如下：

如果所有位于奇数位置的石子堆里都有石子，则从所有奇数位置的石子堆里都各拿走一颗
如果所有位于偶数位置的石子堆里都有石子，则从所有偶数位置的石子堆里都各拿走一颗
现在，小苯先手，小格后手，谁会赢呢？

# 数据范围

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 10^9$

# 题解

能取的总次数是奇数堆中 $Min(a_i)$ 加上偶数堆的 $Min(a_i)$ ，那么如果和为奇数，则先手赢，否则后手

C++

void solve () {
    cin >> n;
    int jmin = 1e18, omin = 1e18;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (i & 1)
            jmin = min(jmin, a[i]);
        else
            omin = min(omin, a[i]);
    }

    cout << ((jmin + omin) & 1 ? "BEN" : "GEGE") << endl;
}

# 小苯的木棍切割

# 题目大意

现在有 $n$ 根木棍，第 $i$ 根木棍的长度为 $a_i$ ，你现在有一台切割机可以进行以下操作

如果木棍数量为 $0$ ，停止工作
将所有木棍切去最短木棍的长度，长度变为 $0$ 则木棍不存在
问，在所有的切割中，切的最多的那一次切去了总长度为多少的木棍？

# 数据范围

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 10^9$

# 题解

切割顺序显然是，先把小木棍按长度升序排列，每次切当前遍历到的最短的那个， $O(N)$ 扫一遍就是答案

C++

void solve () {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + n + 1);

    int res = 0, sub = 0;
    for (int i = 1; i <= n; i++) {
        a[i] -= sub;
        
        if (a[i] <= 0)
            continue;

        sub += a[i];

        res = max(a[i] * (n - i + 1), res);
    }

    cout << res << endl;
}

# 大苯营

# 题目描述

给你一个正整数 $x$ ，你现在要找到一个 $y~(x != y, 1 \le y < {2^{31}})$ ，使得：

$x | y$
$x \oplus y$
$gcd(x, y)$
三个数字可以构成一个任意两边之和大于第三边的三角形

# 数据范围

$1 \le t \le 10^4$
$x$ 的范围是 $1$ 到 $2$ 的 $31$ 次方

# 题解

打表找规律

C++

void solve () {
    for (int i = 1; i <= 10; i++) {
        int j = 1;
        while (true) {
            int a = (i | j), b = (i ^ j), c = gcd(i, j);
            if ((a + b) > c && (a + c) > b && (b + c) > a && i != j)
                break;
            j++;
        }

        cout << j << endl;
    }
}

观察输出为：

Data

得出猜想

$x$ 是偶数时， $1$ 是答案
$x$ 是奇数时， $2^{i}$ 是答案
注意： $x != y$ 并且 $1 < y < {2^{31}}$

从而写出下面的代码

C++

void solve () {
    int x, y = 1;
    cin >> x;

    while (true) {
        int a = (x | y), b = (x ^ y), c = __gcd(x, y);

        if ((a + b) > c && (a + c) > b && (b + c) > a && y != x) {
            cout << y << endl;
            return;
        }

        y <<= 1;

        if (y >= pow(2, 31))
            break;
    }

    cout << -1 << endl;
}

# 小苯的排列数

# 题目大意

给你一个 $L, R$ ，请问， $[L,R]$ 之间，是否存在有趣的数，若存在，输出任意一个，否则输出 $-1$

有趣的数：这个数的每一位，单抽出来组成一个数组，这个数组是一个 $1$ 到 $n$ （ $n$ 是这个数的数位个数）的排列

# 数据范围

$1 \le T \le 2 \times 10^5$
$1 \le l,r \le 10^9$

# 题解

# 错解

在赛时，死脑筋一直想着，每一个 $t$ 组数据都跑一遍 next_permutation

记 $t(x)$ 为 $x$ 的位数

显然，这样的时间复杂度会是 $O(T · t(l)! · t(r)!)$ ，暴毙的时间复杂度，应该考虑预处理的

# 正解

next_permutation 生成所有排列的时间复杂度为 $O(n! \times n)$

显然，这些排列数是可以被预处理出来的，也只需要 $O(\sum\limits_{i=1}^{9}(i! · i))$ 的时间（记 $S=\sum\limits_{i=1}^9 i!$ ）
那么，用什么方式存储呢？
一开始我用了 $set$ ，但是交的时候 $TLE$ 了

C++

void solve () {
    int l, r;
    cin >> l >> r;
    auto t = lower_bound(res.begin(), res.end(), l);
    if (t != res.end() && (*t) <= r)
        cout << *t << endl;
    else
        cout << -1 << endl;
}
 
signed main () {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    vector<int> num;
    for (int i = 1; i <= 9; i++) {
        num.push_back(i);
 
        do {
            int t = 0;
            for (int n : num)
                t = t * 10 + n;
            res.insert(t);
        } while (next_permutation(num.begin(), num.end()));
    }
 
    int _ = 1;
    cin >> _;
 
    while(_--)
       solve();
 
    return 0;
}

改用

vector

存储，最后再

sort

一遍，时间复杂度更优

c++

vector<int> res;
 
void solve () {
    int l, r;
    cin >> l >> r;
    auto t = lower_bound(res.begin(), res.end(), l);
    if (t != res.end() && (*t) <= r)
        cout << *t << endl;
    else
        cout << -1 << endl;
}
 
signed main () {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    vector<int> num;
    for (int i = 1; i <= 9; i++) {
        num.push_back(i);
 
        do {
            int t = 0;
            for (int n : num)
                t = t * 10 + n;
            res.push_back(t);
        } while (next_permutation(num.begin(), num.end()));
    }
     
    sort(res.begin(), res.end());
 
    int _ = 1;
    cin >> _;
 
    while(_--)
       solve();
 
    return 0;
}

# 小苯的字符串染色

# 题目大意

你有一个长度为 $n$ 的字符串 $s$ ，其中有一些字符是白色的，其余的全部都是黑色
你现在要进行 $k$ 次染色，具体的染色操作定义如下：

选择一个没有选过的下标，将 $s_i$ 染成反色

染完色后，请问字符串中，最长的纯色子串长度是？

# 数据范围

$1 \le t \le 1000$
$1 \le n \le 10^6$
$0 \le k \le n$

# 题解

将反转后求纯色连续子串最大长度问题 $\to$ 转换为，求反转后 $0/1$ 字串最大连续长度问题
由同一时刻考虑 $0$ 和 $1$ ，转变为一次只要考虑一种，只需要跑两次即可

C++

int getRes(char t, int k) {
    int x = 0, y = 0, ans = 0;
    for (int i = 1; i <= n; i++)
        x += (s[i] == t), y += (s[i] != t);
    
    if (k > y) {
        k -= y, x -= k;
        int cnt = 0;
        for (int i = 1, j = 1; i <= n; i++) {
            cnt += (s[i] == t);
            while (cnt > x && j <= i) {
                if (s[j] == t)
                    cnt--;
                j++;
            }

            if (cnt == x && j <= i)
                ans = max(ans, i - j + 1);
        }
    }
    else {
        y = 0;
        for (int i = 1, j = 1; i <= n; i++) {
            y += (s[i] != t);
            while (y > k && j <= i) {
                if (s[j] != t)
                    y--;
                j++;
            }

            if (y == k && j <= i)
                ans = max(ans, i - j + 1);
        }
    }

    return ans;
}

现在我有一个 getRes(t, k) 函数，其实现的功能是：

在一个字符串中，进行 $k$ 次染色后，能在染色后的字符串中，找到最长的连续的 $t$ 字符的串

$x$ ： $s$ 字符串中 $t$ 的个数
$y$ ： $s$ 字符串中 $!t$ 的个数

初始化后，分类讨论

k > y 时：
- 考虑把所有的 $!t$ 修改为 $t$ ，再考虑多余的部分
- 也就是说，现在需要消耗 $y$ 次，将 $!t$ 变为 $t$ ，还剩下 k = k - y 次，只能将原本的 $t$ 变为 $!t$
- 那么原本的 $t$ 操作后只会剩下 x = x - k 个
- 利用双指针，检查任意 $[i, j]$ 范围中，满足 $[i,j]$ 内，有 $x$ 个 $t$ 的即可
k = y 时：
- 恰好可以把所有 $!t$ 修改为 $t$ ，那么答案显然就是 $n$
k < y 时：
- 双指针考虑能修改的最大范围（不超过 $k$ 个）

C++

void solve () {
    cin >> n >> k;
    cin >> s, s = " " + s;

    cout << max(getRes('1', k), getRes('0', k)) << endl;
}

二分双指针预处理排序打表找规律博弈论

# 小苯的石子游戏

# 题目大意

# 数据范围

# 题解

# 小苯的木棍切割

# 题目大意

# 数据范围

# 题解

# 大苯营

# 题目描述

# 数据范围

# 题解

# 小苯的排列数

# 题目大意

# 数据范围

# 题解

# 错解

# 正解

# 小苯的字符串染色

# 题目大意

# 数据范围

# 题解

CF-1022

伽马函数与伽马分布