976——Educational Codeforces Round 43 (Rated for Div. 2)

codeforces

http://codeforces.com/contest/976

2018.6.27模拟参加（ABC）
2018.6.27整理（E）

A：

一个01字符串,可以两种操作，交换相邻的，两个相邻的11变成1
问最后二进制数最小是多少，不含前导0。

所有的1最后一定变成一个1，再把0填上即可。特判0的情况！

B：

这样走，问走k步后在哪？

模拟

C：

一堆区间，问有没有一个区间包含一个区间（L1<=L2 && R2<=R1）

其实就是求逆序对。

昨天刚学了CDQ分治，发现这是典型的二维偏序问题。

D：

E：

很多怪兽，每个怪兽有hp（生命），和dmg（伤害）两个属性。
有两个操作。
第一个操作：指定一个怪兽，hp*2
第二个操作：指定一个怪兽，dmg = hp
第一个有a个，第二个有b个，问最大伤害和。

思路：模拟参加时想的dp（预处理后，背包），然后发现dp空间开不下，换状态表示，还是不行。
正解：首先一个结论：所以的a操作只对一个怪兽进行，所以判断一下对哪个怪兽使用就好了。

代码：

A：

int main() {
    int n;cin >> n;
    scanf("%s",s+1);
    int cnt = 0;
    for (int i=1; i<=n; ++i) {
        if (s[i] == '1') cnt ++;
    }
    if (cnt) {
        printf("1");
        for (int i=1; i<=(n-cnt); ++i) printf("0");
        return 0;
    }
    for (int i=1; i<=n; ++i) printf("0");
    return 0;
}

B：

int main() {
    LL n,m,k;
    cin >> n >> m >> k;k++;
    if (k <= n) {
        cout << k << " 1";return 0;
    }
    k -= n;
    LL a = (k - 1) / (m - 1) + 1; 
    a = n - a + 1;
    LL b = k % (m - 1); 
    if (b==0) b = m - 1;
    if (a & 1) cout << a << " " << (m-1)-b+2;
    else cout << a << " " << b + 1;
    return 0;
}

C：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for (;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
const int N = 500010;
struct Edge{
    int a,b,id;
    bool operator < (const Edge &x) const {
        return a==x.a ? b>x.b : a<x.a; // 必须是b > x.b 
    }
}A[N],B[N];
int X = -1,Y = -1;
void CDQ(int L,int R) {
    if (L == R) return ;
    int M = (L + R) >> 1;
    CDQ(L,M);
    CDQ(M+1,R);
    int i = L,j = M + 1,k = L,tmp;
    while (i <= M && j <= R) {
        if (A[i].b >= A[j].b) {
            printf("%d %d",A[j].id,A[i].id);
            exit(0);
        }
        else {
            B[k++] = A[j++];
        }
    }
    while (i <= M) B[k++] = A[i++];
    while (j <= R) B[k++] = A[j++];
    for (i = L; i <= R; ++i) A[i] = B[i];
}
int main() {
    int n = read();
    for (int i=1; i<=n; ++i) {
        A[i].a = read(),A[i].b = read(),A[i].id = i;
    }
    sort(A+1,A+n+1);
    CDQ(1,n);
    printf("-1 -1");
    return 0;
}

D：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for (;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
const int N = 500100;
struct Node{ LL hp,dmg; }A[N];
int main() {
    int n = read();LL a = read(),b = read();
    LL sum = 0;
    b = min(b,(LL)n);
    for (int i=1; i<=n; ++i) {
        A[i].hp = read(),A[i].dmg = read(); 
        sum += A[i].dmg; // 初始答案值 
    } 
    if (!b) return !printf("%lld",sum);
    sort(A+1,A+n+1,[](Node x,Node y){ // 排序 
        return x.hp-x.dmg > y.hp-y.dmg;
    });
    for (int i=1; i<=b; ++i)  //初始时进行b操作后的答案值 
        sum += max(0LL,A[i].hp - A[i].dmg);
    LL Ans = sum;
    for (int i=1; i<=n; ++i) {
        LL tans = sum;
        if (i <= b) {
            tans += max(A[i].hp<<a, A[i].dmg) - A[i].dmg; // 第i个的怪兽的生命值进行a次操作，后进行b操作 
            tans -= max(0LL, A[i].hp - A[i].dmg); // 减去第i个怪兽的初始b操作。 
        }
        else {
            tans += max(A[i].hp<<a, A[i].dmg) - A[i].dmg;
            tans -= max(0LL, A[b].hp - A[b].dmg);
        }
        Ans = max(Ans,tans);
    }
    return !(cout << Ans);
}