ABC371 个人部分题解

AtCoder Beginner Contest 371 - AtCoder

C

注意到 $N \leq 8$ 直接暴力枚举全排列判定即可。

const int N = 10;
int G[N][N],H[N][N],n,v[N][N],m1,m2,p[N];

ll calc() {
    ll ans = 0;
    for (int i = 1;i <= n;++i) {
        for (int j = i + 1;j <= n;++j) {
            if (G[i][j] != H[p[i]][p[j]]) {
                //printf("(%d,%d) (%d,%d):%d\n",i,j,p[i],p[j],v[p[i]][p[j]]);
                ans += v[min(p[i],p[j])][max(p[j],p[i])];
            }
        }
    }
    return ans;
}

signed main() {
    read(n);
    read(m1);
    for (int i = 1;i <= m1;++i) {
        int x,y;read(x,y);
        G[x][y] = G[y][x] = 1;
    }
    read(m2);
    for (int i = 1;i <= m2;++i) {
        int x,y;read(x,y);
        H[x][y] = H[y][x] = 1;
    }
    for (int i = 1;i <= n;++i) {
        for (int j = i + 1;j <= n;++j) {
            read(v[i][j]);
        }
    }
    for (int i = 1;i <= n;++i) p[i] = i;
    ll ans = 1e17;
    do {
        ans = min(ans,calc());
    }while (next_permutation(p+1,p+1+n));
    cout << ans;
    return 0;
}

D

离散化之后对下标做个前缀和就做完了。

const int N = 6e5 + 10;
int n,q;
ll p[N],x[N],qwq[N],tot,val[N];
pii qu[N];
vector <int> v;

signed main() {
    read(n);
    for (int i = 1;i <= n;++i) read(x[i]),v.push_back(x[i]);
    for (int i = 1;i <= n;++i) read(val[i]);
    read(q);
    for (int i = 1;i <= q;++i) {
        read(qu[i].first,qu[i].second);
        v.push_back(qu[i].first);v.push_back(qu[i].second);
    }
    sort(v.begin(),v.end());
    qwq[++tot] = v[0];
    for (int i = 1;i < v.size();++i) {
        if (v[i] != v[i-1]) {
            qwq[++tot] = v[i];
        }
    }
    for (int i = 1;i <= n;++i) {
        x[i] = lower_bound(qwq + 1,qwq + 1 + tot,x[i]) - qwq;
        p[x[i]] += val[i];
        //printf("%d ",x[i]);
    }
    //puts("");
    for (int i = 1;i <= q;++i) {
        qu[i].first = lower_bound(qwq + 1,qwq + 1 + tot,qu[i].first) - qwq;
        qu[i].second = lower_bound(qwq + 1,qwq + 1 + tot,qu[i].second) - qwq;
        //printf("(%d,%d)\n",qu[i].first,qu[i].second);
    }
    for (int i = 1;i <= tot;++i) {
        p[i] += p[i-1];
    }
    for (int i = 1;i <= q;++i) {
        printf("%lld\n",p[qu[i].second] - p[qu[i].first - 1]);
    }
    return 0;
}

E

这种题优先考虑每种数可能带来的贡献！我们考虑一个 $a_i$ 可能在什么样的区间内对答案有贡献。

如果 $a$ 是一个排列，那么答案显然为 $\sum\limits_{i=1}^n i \times (n-i+1)$

我们考虑右端点可能取值为 $[i+1,n]$，考虑左端点，唯一的限制是存在 $a_j = a_i(j < i)$ 这种情况会导致我们的计算出现重复，研究一下发现我们左端点的取值范围实际上是 $(lst_{a_i},i]$ 直接算一下就可以了。所以对整个数列累加一遍，时间复杂度 $O(n)$

int a[N],n,lst[N];
ll ans;

signed main() {
    read(n);
    for (int i = 1;i <= n;++i) {
        read(a[i]);
        ans += (ll)(i - lst[a[i]]) * (n - i + 1);
        lst[a[i]] = i;
    }
    cout << ans;
    return 0;
}

F

发现题目里的操作实际上等价于：

1. 找到第一个 $\geq k$ 的位置，发现这一段都需要往旁边走
2. 最小的位置显然最后是一段等差数列的形式。

所以就变成了查询第一个 $\geq k$ 的位置，区间加等差数列。感觉很难写啊！

但是这个时候我们使用一个经典 trick：把第 $i$ 个数减去 $i$，那么一个公差为 1 的等差数列就会变成一段相等的数。

这个不难理解，考虑 $a_i = k + (i-1)$ 同时减去 $i$ 就变为了 $a_{i}^‘ = k-1$ 也就变成了区间推平的一个形式！

接下来我们考虑一下答案的形式：

原答案的形式应该是一个等差数列和减去序列和，即 $\sum\limits_{i = 1} ^{len} i+k - \sum\limits_{i=1}^{len} x_i$

发现同时减去 $i$ 之后答案不变，也就是 $k\times len -\sum\limits_{i=1}^{len} x_i$

所以只需要实现一个区间推平 区间求和 线段树上二分就可以做完啦！

太久没写线段树了 这里有个坑点是：线段树在每次 pushdown 之后都要记得 pushup，即使是在看似不用的二分里面！

时间复杂度 $O(n\log n)$

const int N = 2e5 + 10;

int x[N],n,q;

struct node {
    int l,r;
    ll sum,tag,maxx;
}tree[N<<2];
//可以区间推平等差数列 但是没必要
//全部-i

void pushup(int p) {
    tree[p].sum = tree[p << 1].sum + tree[p << 1 | 1].sum;
    tree[p].maxx = max(tree[p << 1].maxx,tree[p << 1 | 1].maxx);
}

void build(int p,int l,int r) {
    tree[p].l = l,tree[p].r = r;
    if (l == r) {
        tree[p].maxx = tree[p].sum = x[l] - l;
        return ;
    }
    int mid = (l + r) >> 1;
    build(p << 1,l,mid);
    build(p << 1 | 1,mid + 1,r);
    pushup(p);
}

void pushdown(int p) {
    if (!tree[p].tag) return ;
    tree[p << 1].tag = tree[p].tag;
    tree[p << 1].sum = (ll)tree[p].tag * (tree[p << 1].r - tree[p << 1].l + 1);
    tree[p << 1].maxx = tree[p].tag;
    tree[p << 1 | 1].tag = tree[p].tag;
    tree[p << 1 | 1].sum = (ll)tree[p].tag * (tree[p << 1 | 1].r - tree[p << 1 | 1].l + 1);
    tree[p << 1 | 1].maxx = tree[p].tag;
    tree[p].tag = 0;
}

void change(int p,int x,int y,ll k) {
    if (tree[p].l >= x && tree[p].r <= y) {
        tree[p].sum = (ll)(tree[p].r - tree[p].l + 1) * k;
        tree[p].tag = k;
        tree[p].maxx = k;
        return ; 
    }
    pushdown(p);
    int mid = (tree[p].l + tree[p].r) >> 1;
    if (x <= mid) change(p << 1,x,y,k);
    if (y > mid) change(p << 1 | 1,x,y,k);
    pushup(p);
}

ll query(int p,int x,int y) {
    if (tree[p].l >= x && tree[p].r <= y) {
        return tree[p].sum;
    }
    pushdown(p);
    int mid = (tree[p].l + tree[p].r) >> 1;
    ll ans = 0;
    if (x <= mid) ans += query(p << 1,x,y);
    if (y > mid) ans += query(p << 1 | 1,x,y);
    return ans;
}

int getpos(int p,int x,int y,int k) {
    if (tree[p].l == tree[p].r) {
        return tree[p].maxx < k ? tree[p].l + 1 : tree[p].l;
    }
    pushdown(p);
    int ans = 0;
    if (tree[p << 1].maxx >= k) ans = getpos(p << 1,x,y,k);
    else ans = getpos(p << 1 | 1,x,y,k);
    pushup(p);
    return ans;//小心任何pushdown之后都一定要pushup？
}

signed main() {
    read(n);
    for (int i = 1;i <= n;++i) read(x[i]);
    build(1,1,n);
    read(q);
    ll ans = 0;
    while (q--) {
        ll x,k;read(x,k);k -= x;
        int pos = getpos(1,1,n,k);
        //第一个大于等于k的位置 然后你会发现要把这一段都改 
        if (pos > x) {
            --pos;
            ans += (ll)(pos - x + 1) * k - query(1,x,pos);
            change(1,x,pos,k);
        } else {
            ans += (ll)query(1,pos,x) - k * (x - pos + 1);
            change(1,pos,x,k);
        }
    }
    printf("%lld\n",ans);
    return 0;
}