在我的Github博客上看

Codeforces Round #755 div.1 AB

第一次打div1，头被锤烂了（

A. Two Arrays

题意：有两个 \(1-n\) 的排列 \(a,b\)，可以对 \(a\) 序列进行如下操作：

1. 将一些位置上的数+1
2. 任意改变 \(a\) 的顺序

问能否一次操作将 \(a\) 变成 \(b\)

排序后依次判断每一位上的 \(a\) 能否变成 \(b\) 即可

int n, m;
int a[maxn], b[maxn];
void solve(){
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=n;i++) cin >> b[i];
    sort(a+1, a+n+1);
    sort(b+1, b+n+1);
    for(int i=1;i<=n;i++){
        if(a[i] > b[i]){
            cout << "NO\n";
            return;
        }
        if(a[i] < b[i] - 1){
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
}

7分钟签完这题，剩下时间都在坐牢了（（

B. Guess the Permutation

考场上剩下时间全在搞这个题的玄学二分优化、三分

赛后一看代码，发现核心思维压根就没想到，很服气

题意：交互题，有一个 \(1-n\) 的排列 \(a\)，初始时 \(a_i = i\)，电脑对这个序列进行了一次更改：将 \([i,j-1]\)，\([j,k]\) 两个区间翻转了，你可以询问：\([l,r]\) 上有多少个逆序对？询问至多40次，要猜出 \(i,j,k\)

先二分找到 \(i\)，用至多30次，然后可以根据 \([i,n]\) 的结果减去 \([i+1,n]\) 直接得出第一个逆序串的长度。。同理第二个也很好弄了。

ll n;
 
ll query(ll l, ll r){
    cout << "? " << l << ' ' << r << endl;
    cout.flush();
    ll x;
    cin >> x;
    return x;
}
 
void solve(){
 
    cin >> n;
    ll l = 1, r = n;
    while(l < r){
        ll mid = (l + r + 1) / 2;
        ll x = query(1, mid);
        if(x == 0){
            l = mid;
        }else{
            r = mid - 1;
        }
    }
    ll s1 = 1 + query(l, n) - query(l + 1, n);
    ll j = l + s1;
    ll s2 = 1 + query(j, n) - query(j + 1, n);
    cout << "! " << l << ' ' << l + s1 << ' ' << l + s1 + s2 - 1 << '\n';
 
    cout.flush();
}