Codeforces#435

比賽位址：Codeforces Round #435 (Div. 2)

  這場的題目都挺有意思的！

C. Mahmoud and Ehab and the xor

題意：

  給定n與x，求n個不同的數，使它們異或之後等于x。

題解：

1. 當n==2，x==0的時候無解
2. 構造：
   1. pp = 1<<17;
   2. 構造1、2、…、n-3，異或值為y
   3. 如果x^y==0，那麼構造pp，pp*2，pp^(pp*2)
   4. 如果x^y！=0，那麼構造0，pp，pp^(x^y)

代碼：

#include<iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stack>
using namespace std;

int main() {
    int n, x;
    cin >> n >> x;
    if (n ==  && x == ) {
        cout << "NO" << endl;
    }
    else {
        cout << "YES" << endl;
        if (n == ) {
            cout << x << endl;
        }
        else if (n == ) {
            cout <<  << " " << x << endl;
        }
        else {
            int temp = ;
            int pp =  << ;
            for (int i = ; i < n - ; i++) {
                cout << i +  << " ";
                temp ^= (i + );
            }
            if (temp == x) {
                cout << pp << " " << pp *  << " " << ((pp)^(pp * )) << endl;
            }
            else {
                cout <<  << " " << pp << " " << (pp ^ (x ^ temp)) << endl;
            }
        }
    }
    return ;
}
           

D. Mahmoud and Ehab and the binary string

題意：

  現在Evi有一個長度為n的隐藏字元串x（一定有一個1和一個0），現在你可以詢問Evi，你給一個長度為n的字元串y，那麼他會告訴你x與y有多少位不同。

  現在告訴你長度n，你必須在15次詢問之内，确定x中一個1和一個0的位置。

題解：

  那麼我們首先用一個全是0的字元串去詢問，那麼傳回值num就是字元串中1的個數。

  然後呢，因為原字元串中一定有一個1和一個0，并且又全部由1和0組成，那麼一定能找到一個相鄰位置l和r，他們是01或者10，那麼我們用二分法來找這個l和r.

  首先令l == 0 ， r == N-1

  那麼我們判斷一下[mid,r]中是否全是1或者0

  怎麼判斷呢，我們這個時候用一個0–(mid-1)全是0，mid–r全是1,r–N-1全是0的串去詢問，如果結果為num-(r-l+1)那麼[mid,r]中是否全是1，如果結果為num+(r-l+1)那麼[mid,r]中是否全是0，這種情況另r=mid。否則這中間既有1又有0，另l=mid.

  那麼二分政策就出來了。

代碼：

#include<iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stack>
using namespace std;

int N, num;

bool check(int l, int r) {
    cout << "? ";
    for (int i = ; i < l; i++) {
        cout << "0";
    }
    for (int i = l; i <= r; i++) {
        cout << "1";
    }
    for (int i = r + ; i < N; i++) {
        cout << "0";
    }
    puts("");
    fflush(stdout);
    int temp;
    cin >> temp;
    if (temp > num - (r - l + ) && temp < num + (r - l + )) {
        return true;
    }
    else {
        return false;
    }
}

int main() {

    cin >> N;
    cout << "? ";
    for (int i = ; i < N; i++) {
        cout << "0";
    }
    puts("");
    fflush(stdout);
    cin >> num;
    int l = , r = N - ;
    while (r > l + ) {
        int mid = (l + r) / ;
        if (check(mid, r)) {
            l = mid;
        }
        else {
            r = mid;
        }
    }
    cout << "? ";
    for (int i = ; i < l; i++) {
        cout << "0";
    }
    for (int i = l; i < r; i++) {
        cout << "1";
    }
    for (int i = r; i < N; i++) {
        cout << "0";
    }
    puts("");
    fflush(stdout);
    int temp;
    cin >> temp;
    if (temp > num ) {
        cout << "! " << l +  << " " << r +  << endl;
    }
    else {
        cout << "! " << r +  << " " << l +  << endl;
    }
    return ;
}
           

E. Mahmoud and Ehab and the function

題意：

  略。。。

題解：

  推推公式，每次二分找一下就是的，太簡單。

代碼：

#include<iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stack>
using namespace std;

long long a[], b[];
long long n, m, q;
long long sum[];
long long cnt1, cnt2;

long long get(int l, int r, long long val) {
    if ((r - l + ) & ) {
        if (l & ) {
            cnt1 += val;
        }
        else {
            cnt1 -= val;
        }
    }
    long long* pos = upper_bound(sum, sum + m - n + , -cnt1);
    long long ans;
    if (pos >= sum + m - n + ) {
        pos--;
        ans = abs(*pos + cnt1);
    }
    else if (pos == sum) {
        ans = abs(*pos + cnt1);
    }
    else {
        ans = abs(*pos + cnt1);
        pos--;
        ans = min(ans, abs(*pos + cnt1));
    }
    return ans;
}

int main() {
    cin >> n >> m >> q;

    cnt1 = cnt2 = ;
    int f = ;
    for (int i = ; i <= n; i++) {
        cin >> a[i];
        cnt1 += f * a[i];
        f *= -;
    }
    for (int i = ; i <= m; i++) {
        cin >> b[i];
        if (i <= n) {
            if (i & ) {
                cnt2 -= b[i];
            }
            else {
                cnt2 += b[i];
            }
        }
    }
    sum[] = cnt2;
    for (int i = n + ; i <= m; i++) {
        cnt2 += b[i - n];
        cnt2 *= -;
        if (n & ) {
            cnt2 -= b[i];
        }else{
            cnt2 += b[i];
        }
        sum[i - n] = cnt2;
    }
    sort(sum, sum + m - n + );
    cout << get(, , ) << endl;
    for (int i = ; i < q; i++) {
        int l, r, x;
        cin >> l >> r >> x;

        cout << get(l,r,x) << endl;
    }
    return ;
}