BUPT2017 wintertraining(15) #9

下面不再说明题意了请自行读题，直接放contest链接。

https://vjudge.net/contest/151607

A.考虑当火车隔k站一停时

区间长度 >= k 的纪念品一定能买到

区间长度 <k 的纪念品最多覆盖一个停靠的站点

求出 n / k 个点， 每个点上覆盖的纪念品数累加即可

k 从 1 到 m 都需要求

我们只要把纪念品按区间长度排序

然后向后扫就可以了

总复杂度 O(nlog^2n)

#include <cstdio>
#include <algorithm>

#define lowbit(x) (x&(-x))

using std::sort;

const int maxn = 300010;

int n, m, c[maxn];

struct node {
    int l, r, len;
    bool operator < (const node &a) const {
        return len < a.len;
    }
}a[maxn];

void add(int i, int x) {
    while(i <= m) c[i] += x, i += lowbit(i);
}

int ask(int i) {
    int ret = 0;
    while(i > 0) ret += c[i], i -= lowbit(i);
    return ret;
}

int main() {
    scanf("%d %d", &n, &m);
    for(int i = 1;i <= n;i ++) {
        scanf("%d %d", &a[i].l, &a[i].r);
        a[i].r ++, a[i].len = a[i].r - a[i].l;
    }
    sort(a + 1, a + n + 1);
    for(int i = 1, j = 1, ans;i <= m;i ++) {
        while(j <= n && a[j].len < i) {
            add(a[j].l, 1);
            add(a[j].r, -1);
            j ++;
        }
        ans =  n - j + 1;
        for(int k = i;k <= m;k += i)
            ans += ask(k);
        printf("%d
", ans);
    }
}

B.一个暴力理论向上约等于O(n^3)的做法:

我们把原矩阵旋转45度，再扔掉那些对当前点贡献为0的点

就能得到一个对当前点有贡献的正方形点阵

从外到里，贡献系数递增

所以我们的做法就是枚举点，然后O(k)计算它的 f 函数值...

下面代码把 scanf 改成快读卡常数就能过了...

#include <cstdio>

#define rep(i, j, k) for(int i = j;i <= k;i ++)

long long s[2100][2100], ans = -1, tmp;

int n, m, k, t, p, q, ax, ay;

int main() {
    scanf("%d %d %d", &n, &m, &k);
    rep(i, 1, n) rep(j, 1, m) {
        scanf("%d", &t);
        s[i + j - 1][i - j + m] = t;
    }
    rep(i, 1, n + m - 1) rep(j, 1, m + n - 1) 
        s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
    rep(i, k, n + 1 - k) rep(j, k, m + 1 - k) {
        tmp = 0, p = i + j - 1, q = i - j + m;
        rep(r, 0, k - 1) tmp += s[p + r][q + r] - s[p - r - 1][q + r] - s[p + r][q - r - 1] + s[p - r - 1][q - r - 1];
        if(tmp > ans) ans = tmp, ax = i, ay = j;
    }    
    printf("%d %d", ax, ay);
    return 0;
}