Codeforces Round 1008 (Div. 2)

又是一次掉分，最近打CF总是好难受啊。还是实力太弱太弱导致的。感觉非常的难受啊。不过也合理，我又付出了什么呢？真正自己思考的题能有几个呢？😭😭😭

真的还是很失落的，好久没上分了，甚至一直卡在青名，好久没有体会到上分的快乐了。唉唉。

比赛链接: https://codeforces.com/contest/2078

上不了分就要加训，我一定要上分。

A

正常的 A 题，直接观察发现正好平均值等于 X 的都是 YES ，然后就猜一发直接交，后面再想想吧。

void ChatGptDeepSeek()
{
    int n,x;
    cin>>n>>x;
    vector<int>a(n+1);
    for(int i=1;i<=n;i++)
        cin>>a[i];
    int sum=0;
    for(int i=1;i<=n;i++)
        sum+=a[i];
    //如果选了一个因子 那么？
    //3？
    if(sum==n*x) cout<<"YES\n";
    else cout<<"NO\n";
}

B

肯定不可能所有人都能到 $n$ ，因为 $a_i\ne i$ ，但是我们完全可以做到只有一个不等于 $n$ 。

分下奇偶讨论一下.

$k$ 为奇数，则我们需要第一次就能直接到 $n$ ，所以就全等于 $n$ 。

$k$ 为偶数，则第一次不要到 $n$ ，那就到 $n-1$ 呗，然后 $n-1$ 到 $n$ 。

void ChatGptDeepSeek()
{
    int n,k;
    cin>>n>>k;
    //k为奇数？
    //全为 n ，除了最后一个
    //k为偶数？
    //第一次全部去n-1 ，然后n-1去n
    

    //2 2?
    //2 1
    if(k&1){
        for(int i=1;i<=n-1;i++){
            cout<<n<<' ';
        }
        cout<<n-1<<'\n';
    }else{
        for(int i=1;i<n-1;i++)
            cout<<n-1<<' ';
        cout<<n<<" "<<n-1<<'\n';
    }
}

C

其实挺 easy 的 ，但是为什么一直没看出来呢。。。

太慢了，这把打得不好的很大一部分原因就是 C 写得太慢了。虽然之后还是不一定能 AC D题。

由于每个数字都不同，所以我们通过组合，肯定可以使得那个表达式是大于0或者小于0。

那么我们如果把 $b$ 里最大的值当作 $a_1$ ，那么肯定可以使得 $a_2$ 后面减的是一个正数，这样 $a_2$ 就是我们构造出的新数字，它比原数组中每一个数字都大。

构造一个比最小值小的数字也是可以做到的，但是可能会不是一个正整数。

这个思路好像还真不是很好想。

void ChatGptDeepSeek()
{
    //+b0 -b1
    int n;
    cin >> n;
    vector<int> b(n * 2 + 1);
    for (int i = 1; i <= n * 2; i++) {
        cin >> b[i];
    }
    sort(b.begin() + 1, b.end());

    // set<int> st1, st2;
    // ll s1 = 0, s2 = 0;
    // for (int i = 1; i <= n; i++)
    //     st1.insert(b[i]), s1 += b[i];
    // for (int i = n + 1; i <= n * 2; i++)
    //     st2.insert(b[i]), s2 += b[i];

    //如果说大的n 个 减去小的 n个
    //正好等于了某一个值
    
    //- + - + -
    //选一个很大的数字，然后减了之后正好等于an?可行吗

    //4
    //1 2 3 4
    //6-1+2-3
    ll s=b[2*n];
    //s-x=a[2n]
    for(int i=1;i<2*n;i++){
        if(i&1) s+=b[i];
        else s-=b[i];
    }
    cout<<b[2*n]<<" "<<s<<' ';
    for(int i=1;i<2*n;i++)
        cout<<b[i]<<" \n"[i+1==2*n];
}

其实能写出来 C 也是有点不容易了。。。

D

不得不说这D确实不难的，但是确实是一直没想到。。。

我单想到了哪个乘的离得近就给哪个，但是我没想到如果大小相同，可以先把多出来的留着，之后再决定怎么分配。。

好牛啊。

using ll = long long;

void ChatGptDeepSeek()
{
    int n;
    cin >> n;
    ll x = 0, L = 1, R = 1;
    while (n--) {
        char o1, o2;
        int x1, x2;
        cin >> o1 >> x1 >> o2 >> x2;
        if (o1 == 'x' && o2 == 'x') {
            if (x1 > x2) {
                L += x;
                x = L * (x1 - 1) + R * (x2 - 1);
            } else if (x1 < x2) {
                R += x;
                x = L * (x1 - 1) + R * (x2 - 1);
            } else {
                x = x * x1 + L * (x1 - 1) + R * (x2 - 1);
            }
        } else if (o1 == 'x') {
            L += x;
            x = L * (x1 - 1) + x2;
        } else if (o2 == 'x') {
            R += x;
            x = R * (x2 - 1) + x1;
        } else {
            x += x1 + x2;
        }
    }
    cout << L + R + x << '\n';
}

E

本来是一点思路都没的，看了评论区有人说用 01010101 和 10101010 问，也有说拿 0 和 101010101 ，我当时没太理解第一种。

我本来自己想的是，先问一次 0 ，这样就知道 $x+y$ 的值了。第二次我想的是问一个全 $1$ 的数字来着。这样我可以知道 $x$ 和 $y$ 每一位上的 $1$ 的数量。

但是事实上并不行，因为有的地方那一位0个1，答案会是 $2$ 倍的这一位的值，也可能是 $1$ 位的高一位的值。。。并不能确定具体是那一位给的贡献。

所以我们问 0 和 1010101010 就能确定奇数或者偶数位上的 1 的数量，然后用 $x+y$ 减去这个值，就得到了 $x$ 和 $y$ 的偶数位的和，就可以知道偶数位的每一位上的 $1$ 的数量。于是就知道了每一位的情况。

其实 10101010 和 01010101 这两个一起问，也是差不多同理的。

令奇数位上全为 $1$ 的 $101010101=n$ ，那么 $(x|n)+(y|n)-2n$ 实际上就等于 $x+y$ 在奇数位上的和，就可以求出它们奇数位的异或的值。然后再另一个数字可以求出偶数位的异或的值，就达到了和另一种问法的相同的效果。

还是比较不容易想到的。。但感觉难度不太高的，起码只知道问什么数字就很容易写了。

constexpr int val = 715827882;

int ask(int n)
{
    cout << n << endl;
    int res;
    cin >> res;
    return res;
}
void ChatGptDeepSeek()
{
    // 问01010101非常有道理啊
    // 因为这一位的1，一定会比后面所有的和要大

    // 不对，，，但是怎么和10101010结合起来呢？
    // 直接问 0 和 0101010101吧
    //
    int sum = ask(0);
    int res = ask(val);
    vector<int> b(30);
    int x = res - sum, y = 0;
    for (int i = 29; i >= 0; i -= 2) {
        if (x >= (1 << (i + 1))) {
            // b[i] = 2;
            x -= 1 << (i + 1);
        } else if (x >= (1 << i)) {
            b[i] = 1;
            x -= 1 << i;
            y += 1 << i;
        } else {
            y += 1 << (i + 1);
            b[i] = 2;
        }
    }
    assert(x == 0);
    x = sum - y;
    for (int i = 28; i >= 0; i -= 2) {
        if (x >= (1 << (i + 1))) {
            x -= 1 << (i + 1);
            b[i] = 2;
        } else if (x >= (1 << i)) {
            x -= 1 << i;
            b[i] = 1;
        }
    }
    cout << "!" << endl;
    int m;
    cin >> m;
    for (int i = 29; i >= 0; i--) {
        // cerr << b[i] << " \n";
        if (m >> i & 1) {
            sum += (2 - b[i]) * (1 << i);
        }
    }
    cout << sum << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    // int sum=0;
    // for(int i=29;i>=0;i--){
    //     if(i&1) sum|=1<<i;
    // }
    // cerr<<sum<<'\n';
    int T = 1;
    cin >> T;
    while (T--)
        ChatGptDeepSeek();
    return 0;
}

这里只写了第一种，另一种同理的。