Codeforces Round #768 (Div. 2) A ~ E

Codeforces Round #768 (Div. 2) A ~ E

C题及以后有详细的解释，AB略过；

A

思路

不难想到，最大的放一边，最小的放另一边；

Code

#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;
int a[N],b[N];
void solve(){
    int n;
    cin >> n;
    for(int i=1;i<=n;++i) cin >> a[i];
    for(int i=1;i<=n;++i) cin >> b[i];
    for(int i=1;i<=n;++i)
        if(a[i] > b[i]) swap(a[i],b[i]);
    int mx1 = 0,mx2 = 0;
    for(int i=1;i<=n;++i){
        mx1 = max(mx1,a[i]);
        mx2 = max(mx2,b[i]);
    }
    cout << mx1 * mx2 << 'n';
}

signed main(){
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t;
    cin >> t;
    while(t--)
        solve();
    return 0;
}

B

思路

不断的翻倍即可；

因为除法是整数除法，不如乘二来的直接；

因此我们可以倒过来存数；

Code

#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 2e5 + 10;

int a[N];

void solve(){
    int n;
    cin >> n;
    for(int i=n;i>=1;--i)
        cin >> a[i];
    set st;
    int idx = 0;
    for(int i=1;i<=n;++i){
        if(a[1] == a[i]) ++idx;
        else break;
    }
    int mx = 0;
    for(int i=1;i<=n;++i){
        if(a[i] != a[1]) mx = max(mx,i);
    }
    if(idx == n){
        cout << 0 << 'n';
        return;
    }
    int ans = 0;
    while(idx < mx){
        idx *= 2;
        for(int i=idx+1;i<=n;++i){
            if(a[1] == a[i]) ++idx;
            else break;
        }
        ++ans;
    }
    cout << ans << 'n';
}

signed main(){
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t;
    cin >> t;
    while(t--)
        solve();
    return 0;
}

C

思路

构造题；

首先我们要想如何凑出0；

比如 n = 8 n=8 n=8；
那么我们让 111 & 000 111 & 000 111&000， 110 & 001 110 & 001 110&001， 101 & 010 101 & 010 101&010以此类推；

不难发现，其实就是从两边配对到中间即可；

又因为我们 n − 1 n-1 n−1这个数字，它的二进制表示是全1；

那么如果我们想凑出一个 x , 0 ＜ x ＜ n − 1 x,0＜x＜n-1 x,0＜x＜n−1；

我们直接拿 n − 1 & x n-1 & x n−1&x是不是就可以了；

其他数凑 0 0 0，怎么凑呢；

我们前面提到， 0 & n − 1 0 & n-1 0&n−1， 1 & n − 2 1 & n-2 1&n−2以此类推即可；

现在我们的 n − 1 n-1 n−1与 x x x用掉了；那么假设与 x x x匹配的是 a [ x ] a[x] a[x]；

我们发现，其他数没影响，还是正常匹配，即 i & a [ i ] = 0 , i ≠ x i&a[i] = 0,i ≠ x i&a[i]=0,i​=x

同时 a [ n − 1 ] = 0 ， 0 a[n-1] = 0，0 a[n−1]=0，0也是落单的；

那么我们只需要拿 0 0 0去干掉 a [ x ] a[x] a[x]即可；

---

现在考虑 x = n − 1 x=n-1 x=n−1的情况；

首先我们拿 n − 1 & n − 2 n-1 & n-2 n−1&n−2来凑出 n − 2 n-2 n−2；

再拿 1 1 1和 n − 3 n-3 n−3来凑出 1 1 1，因为 n n n是偶数， n − 3 n-3 n−3必然是奇数；

我们发现此时只有 a [ n − 1 ] , a [ n − 3 ] a[n-1],a[n-3] a[n−1],a[n−3]落单了，其他都是正常匹配出 0 0 0；

又因为 a [ n − 1 ] = 0 a[n-1]=0 a[n−1]=0，那么同理 a [ n − 1 ] & a [ n − 3 ] a[n-1] & a[n-3] a[n−1]&a[n−3]即可；

---

最后考虑-1的情况；

因为 0 ≤ k ≤ n − 1 0≤k≤n−1 0≤k≤n−1，我们与运算能凑出 0 & 1 0 & 1 0&1， 2 & 3 2 & 3 2&3 以此类推；

不难发现，只有当 n = 4 n=4 n=4的时候，所能表示的最大值为 2 2 2，即只有此刻 s u m m a x ＜ n − 1 sum_{max} ＜ n-1 summax​＜n−1，其他都是满足的；

那么特判if(n == 4 && k == 3) output(-1)即可；

Code

#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 1e6 + 10;
int a[N];
void solve(){
    int n,k;
    cin >> n >> k;
    if(n == 4 && k == 3){
        cout << -1 << 'n';
        return;
    }
    for(int i=0;i> t;
    while(t--)
        solve();
    return 0;
}

D

思路

假设所有在范围 [ x , y ] [x,y] [x,y]中的数为 i n in in，其他数为 o u t out out；

肯定有 i n + o u t = n in + out = n in+out=n；

对于划分出来的第 i i i个子数组，

有 i n i − o u t i ≥ 1 in_i - out_i≥1 ini​−outi​≥1；

我们一共有 k k k个这样的子数组，那么有 ∑ i = 1 k i n i − ∑ i = 1 k o u t i ≥ 1 sum_{i=1}^kin_i - sum_{i=1}^kout_i ≥1 ∑i=1k​ini​−∑i=1k​outi​≥1

化简一下有 i n − o u t ≥ k in - out ≥ k in−out≥k；

再和式子 i n + o u t = n in + out = n in+out=n一起搞一下；

得到 i n ≥ ⌈ k + n 2 ⌉ in ≥ lceil frac{k+n}{2}rceil in≥⌈2k+n​⌉

因为我们想使得 y − x y-x y−x最小，那么我们期望在 [ x , y ] [x,y] [x,y]中的元素最好恰好满足题目限制;

最理想的情况有 i n = ⌈ k + n 2 ⌉ in = lceil frac{k+n}{2}rceil in=⌈2k+n​⌉；

因为每个在数组 a a a中的元素，至少出现了一次；

因此在排好序以后，我们只需要去遍历长度为 ⌈ k + n 2 ⌉ lceil frac{k+n}{2}rceil ⌈2k+n​⌉的区间从中取一个 y − x y-x y−x最小的即可；

这样我们就已经得到了取值区间 [ x , y ] [x,y] [x,y]；

---

接着考虑如何构造出 k k k个子数组；

因为我们之前已经保证了合法的下界；

对于前 k − 1 k-1 k−1个子数组，

如果它们恰好 i n i − o u t i = 1 , 0 ＜ i ＜ k in_i - out_i = 1,0＜i＜k ini​−outi​=1,0＜i＜k；

那么最后一个子数组肯定能满足 i n k − o u t k ≥ 1 in_k - out_k ≥ 1 ink​−outk​≥1

Code

#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 2e5 + 10;

int a[N],l,r;
int in_range(int x){
    if(x <= r && x >= l) return 1;
    return -1;
}
void solve(){
    int n,k;
    cin >> n >> k;
    vector ve;
    for(int i=1;i<=n;++i){
        cin >> a[i];
        ve.push_back(a[i]);
    }
    sort(ve.begin(),ve.end());
    int mn = 1e9;
    int len = (n+k+1)/2;//(n+k)/2 向上取整
    for(int i=0;i+len-1> t;
    while(t--)
        solve();
    return 0;
}

E 题面

思路

假设只有一个连续的区间，比如 [ 1 , 2 , 3 , 1 , 5 , 1 ] [1,2,3,1,5,1] [1,2,3,1,5,1]，不难发现，我们只需要关注首尾的 1 1 1，中间的 1 1 1是无用的；
这样的一个连续区间，可以产生的贡献为区间长度减去首尾两个点；

如果有2个区间相交，比如 [ 1 , 2 , 3 , 1 , 2 ] [1,2,3,1,2] [1,2,3,1,2]，可以产生的贡献为区间长度减去三个点；

以此类推，有 k k k个区间相交，那么可以产生的贡献为区间长度减去 k + 1 k + 1 k+1

---

设 l a s t ( i ) last(i) last(i)表示数字 i i i最后出现的位置；

假设当前连续的区间为 [ i , j ] [i,j] [i,j]，那么产生贡献的点在 ( i , j ) (i,j) (i,j)

因为可能有相交的区间，因此我们需要扩展右端点；

也就是寻找 m a x k = i + 1 j − 1 l a s t [ a k ] max_{k=i+1}^{j-1}last[a_k] maxk=i+1j−1​last[ak​]；

直接去做是一个 O ( n 2 ) O(n^2) O(n2)的级别，我们可以用线段树来优化；

线段树的每个节点表示位置， t r [ i ] . i d x tr[i].idx tr[i].idx表示以 i i i为根子树能够映射最远的距离；

这样执行一次查询就是 O ( l o g n ) O(logn) O(logn)级别的；

Code

#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 2e5 + 10;

int first[N],last[N],f[N];

struct Node{
    int l,r,idx;
}tr[N<<2];

#define lc (p<<1)
#define rc (p<<1|1)
void push_up(int p){
    tr[p].idx = max(tr[lc].idx,tr[rc].idx);
}
void build(int p,int l,int r){
    tr[p] = {l,r,0};
    if(l == r){
        tr[p].idx = f[l];
        return;
    }
    int mid = l + r >> 1;
    build(lc,l,mid);
    build(rc,mid+1,r);
    push_up(p);
}
//查询区间[l,r]上的索引 -> 最远的索引
int query(int p,int l,int r){
    if(tr[p].l >= l && tr[p].r <= r){
        return tr[p].idx; 
    }
    int mid = tr[p].l + tr[p].r >> 1;
    if(r <= mid) return query(lc,l,r);
    else if(l > mid) return query(rc,l,r);
    else return max(query(lc,l,mid),query(rc,mid+1,r));
}
void solve(){
    int n;
    cin >> n;
    for(int i=1,x;i<=n;++i){
        cin >> x;
        if(!first[x]) first[x] = i;
        last[x] = i;
    }
    //1≤x≤n
    for(int i=1;i<=n;++i)
        if(first[i] != last[i])
            //最早的位置 -> 最晚的位置
            f[first[i]] = last[i];
    build(1,1,n);
    int L = 1,ans = 0;
    for(;L<=n;++L){
        int R = f[L];
        if(L <= R){
           //扩展区间
           while(1){
               int qr = query(1,L,R);
               if(qr == R) break;
               R = qr;
               --ans;//i个连续区间i+1个点剩余,每扩展一次减一次即可
            }
            //区间长度 - 2,中间节点在上面已经减去了,这里只需要减去首尾节点
            ans += R - L + 1 - 2;
            L = R;
        }
    }
    cout << ans << 'n';
}

signed main(){
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t--)
        solve();
    return 0;
}