985——Educational Codeforces Round 44 (Rated for Div. 2)

http://codeforces.com/contest/985

codeforces

2018.6.24晚，模拟参加（完成A,B,C）
2018.6.25，整理，（完成E）

A：

一个1*n的棋盘，给n/2个棋子（n为偶数），问最少移动多少步使所有的棋子不相邻。

开始想dp，之后发现题目中说棋子总是n/2个，那么排序后，要不全放在偶数位，要不全放在奇数位，取小。

B：

n个开关，n个灯，每个开关可以控制许多灯，每个开关打开后，可以使许多灯亮起来，可能有几个开关同时使一个灯亮。问能否用n-1个开关使所有灯亮。

如果一个灯只能有第i个开关打开，那么第i个必须打开。以此类推，看是否可以有一个开关不需要必须打开即可。

C：

给n*k个木板，每个都有其高度，k个木板可以造一个桶（一共n个桶），容量是最矮的木板的高度。要求，任意两个桶的容量的差都要小于等于L。在满足上述条件的情况下，求最大的容量和。

思路1：
一开始的思路。n*k个木板，那么n个木桶的容量就是前n小的木板高度，于是加起来就是容量和，判断a[n]-a[1]>L是否满足。这样写实错误的。

思路2：
如果a[n+1]-a[1]>L那么可以用a[n+1]代替a[n]，（a[n]放在前一个木桶上，a[n+1]作为一个新的木桶。）那么可以求出最大的a[R]-a[1] > L，那么模拟一遍选木板的过程就好了，在可以的条件下，能选高的选高的。

D：

E：

给一个集合，分成几个子集合。
要求：1、每个子集合的个数必须大于等于k
2、每个子集合中最大的数-最小的数 < d。
问能否分成。

思路一：
排序，对于每个数i，那么有一个L，使L~i这些数是满足条件1，a[i]-a[L]<=d。对于条件2，这些数最多到R=i-k+1。即L~R的数可以和i组成以子集合。
dp[i]表示到i能否分成。
那么对于i查询一下i∈[L-1,R-1]中有没dp[i]=1即可。
查询方法：树状数组，前缀和等。

思路二：
尺取法。
和上面类似判断dp[i]表示到i能否分成（即i能否作为右端点）。再记一数组st[i]，能否作为左端点。
那么用st[i]去更新dp[i]，相应的更新st[i]，每次不需要从st[i]开始枚举，从上次枚举到的地方开始即可。
复杂度线性。

代码
A

//A
int main () {
    int n = read();
    for (int i=1; i<=(n/2); ++i) a[i] = read();
    sort(a+1,a+(n/2)+1);
    int x = 0,y = 0;
    for (int i=1; i<=(n/2); ++i) {
        int t = i * 2;
        x += abs(a[i] - t);
        t --;
        y += abs(a[i] - t);
    }
    cout << min(x,y);
    return 0;
}

B

//B
int main () {
    int n = read(),m = read();
    for (int i=1; i<=n; ++i)scanf("%s",s[i]+1);
    for (int i=1; i<=m; ++i) {
        int t,cnt = 0;
        for (int j=1; j<=n; ++j) {
            if (s[j][i] == '1') cnt++,t = j;
        }
        if (cnt == 1) pd[t] = true;
    }
    for (int i=1; i<=n; ++i) {
        if (!pd[i]) {puts("YES");return 0;}
    }
    puts("NO");
    return 0;
}

C

//C
int main () {
    int n = read(),k = read(),L = read();
    int m = n * k;
    for (int i=1; i<=m; ++i) a[i] = read();
    sort(a+1,a+m+1);
    if (a[n] - a[1] > L) {printf("0");return 0;}
    int R = n;
    while (a[R] - a[1] <= L) R ++;
    R --;
    LL ans = 0;
    int cnt = m - R;
    for (int i=R; i>=1; --i) { // 模拟取木板的过程
        cnt ++;
        if (cnt >= k) ans += a[i],cnt -= k;
    }
    cout << ans;
    return 0;
}

E

void update(int p,int v) {
    for (; p<=(n+1); p+=p&(-p)) sum[p] += v;
}
int query(int p) {
    int ans = 0;
    for (; p; p-=p&(-p)) ans += sum[p];
    return ans;
}
int getsum(int l,int r) {
    if (l > r) return 0;
    return query(r) - query(l-1);
}
int main () {
    n = read(),k = read(),d = read();
    if (k == 1) {printf("YES");return 0;} // 不加这一行会WA第10个点
    for (int i=1; i<=n; ++i) a[i] = read();
    sort(a+1,a+n+1);
    f[1] = 1;
    update(1,1);
    int L = 1;
    for (int i=2; i<=n; ++i) {
        while (L < i && a[i] - a[L] > d) L ++;
        int R = i - k + 1;
        f[i+1] = (getsum(L,R) >= 1);
        if (f[i+1]) update(i+1,f[i+1]);
    }
    printf(f[n+1]?"YES":"NO");
    return 0;
}