2025.1.21——1300

A 1300

Qingshan has a string \(s\) which only contains \(\texttt{0}\) and \(\texttt{1}\).

A string \(a\) of length \(k\) is good if and only if

• \(a_i \ne a_{k-i+1}\) for all \(i=1,2,\ldots,k\).

For Div. 2 contestants, note that this condition is different from the condition in problem B.

For example, \(\texttt{10}\), \(\texttt{1010}\), \(\texttt{111000}\) are good, while \(\texttt{11}\), \(\texttt{101}\), \(\texttt{001}\), \(\texttt{001100}\) are not good.

Qingshan wants to make \(s\) good. To do this, she can do the following operation at most \(300\) times (possibly, zero):

• insert \(\texttt{01}\) to any position of \(s\) (getting a new \(s\)).

Please tell Qingshan if it is possible to make \(s\) good. If it is possible, print a sequence of operations that makes \(s\) good.
Input

The input consists of multiple test cases. The first line contains a single integer \(t\) (\(1\le t\le 100\)) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer \(n\) (\(1 \le n\le 100\)) — the length of string \(s\), respectively.

The second line of each test case contains a string \(s\) with length \(n\).

It is guaranteed that \(s\) only consists of \(\texttt{0}\) and \(\texttt{1}\).

B 1300

Tema decided to improve his ice cream making skills. He has already learned how to make ice cream in a cone using exactly two balls.

Before his ice cream obsession, Tema was interested in mathematics. Therefore, he is curious about the minimum number of balls he needs to have in order to make exactly \(n\) different types of ice cream.

There are plenty possible ice cream flavours: \(1, 2, 3, \dots\). Tema can make two-balls ice cream with any flavours (probably the same).

Two ice creams are considered different if their sets of ball flavours are different. For example, \(\{1, 2\} = \{2, 1\}\), but \(\{1, 1\} \neq \{1, 2\}\).

For example, having the following ice cream balls: \(\{1, 1, 2\}\), Tema can make only two types of ice cream: \(\{1, 1\}\) and \(\{1, 2\}\).

Note, that Tema do not need to make all the ice cream cones at the same time. This means that he making ice cream cones independently. Also in order to make a following cone \(\{x, x\}\) for some \(x\), Tema needs at least \(2\) balls of type \(x\).

Help Tema answer this question. It can be shown that answer always exist.
Input

Each test consists of multiple test cases. The first line of input contains a single integer \(t\) (\(1 \le t \le 10^4\)) — the number of test cases. Then follows the description of the test cases.

The first line of each test case contains a single integer \(n\) (\(1 \le n \le 10^{18}\)) — the number of ice cream types that Tema wants to make.

------------------------思考------------------------

• 字符串/贪心策略+思维/贪心策略/二分/数学

A

1. 首先保证 \(0/1\) 数量相等，一个方向是不动原字符串/对称轴不变，构造出一个一对一的字符串，但是做不到。
2. 只能在两边加串，贪心消除即可，操作次数至多 \(n\) 次。暴力拼接更新字符串即可，注意点就是 \(sub\) 下标要细节一下。本质是将首尾字符进行移动。

B

1. 是道好题。二分找出上界，剩余部分贪心，思想上证明一下。

------------------------代码------------------------

A

#include <bits/stdc++.h>
#define int long long //
#define endl '\n'     // attention: interactive/debug
#define el cout << endl
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
#define bugv(VEC, ST)                     \
    for (int i = ST; i < VEC.size(); i++) \
        cout << VEC[i] << ' ';            \
    el;

void _();
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(10);
    int T = 1;
    cin >> T;
    while (T--)
        _();
    return 0;
}

void _()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    int cnt[2] = {};
    for (auto v : s)
        cnt[v - '0']++;
    if (cnt[0] - cnt[1])
    {
        cout << -1;
        el;
        return;
    }
    int l = 0, r = n - 1;
    vector<int> res;
    // int t = 1e3;
    while (l < r)
    {
        // t--;
        // if (!t)
        //     break;
        if (s[l] - s[r])
        {
            l++, r--;
            continue;
        }
        if (s[l] == '1')
        {
            res.push_back(l);
            s = s.substr(0, l) + "01" + s.substr(l);
        }
        else
        {
            res.push_back(r + 1);
            // bug2(s.substr(0, r + 1), s.substr(r + 1));
            s = s.substr(0, r + 1) + "01" + s.substr(r + 1);
        }
        l++, r++;
        // bug2(l, r);
    }
    cout << res.size();
    el;
    bugv(res, 0);
}

B

#include <bits/stdc++.h>
#define int long long //
#define endl '\n'     // attention: interactive/debug
#define el cout << endl
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
#define bugv(VEC, ST)                         \
    {                                         \
        for (int I = ST; I < VEC.size(); I++) \
            cout << VEC[I] << ' ';            \
        el;                                   \
    }

void _();
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(10);
    int T = 1;
    cin >> T;
    while (T--)
        _();
    return 0;
}

void _()
{
    int n;
    cin >> n;
    int l = 1, r = 1e10;
    while (r - l - 1)
    {
        int mid = l + r >> 1;
        if (mid * (mid - 1) >> 1 > n)
            r = mid;
        else
            l = mid;
    }
    int res = l;
    res += n - (l * (l - 1) >> 1);
    cout << res << endl;
}

// void _()
// {
//     auto cal = [](int mid)
//     {
//         return mid * (mid - 1) >> 1;
//     };
//     for (int i = 2; i <= 20; i++)
//         bug2(i, cal(i));
// }