CodeForces #179(295A|295B|295C)|动态规划|最短路径|前缀和

295A - Greg and Array

题目大意

对于已经给出初始值的数组a[n]，m个操作是给区间[l,r]的所有元素+d。你又有k个询问，执行[x,y]的操作。求k个询问后的数组。

题解

显然，m个操作间没有顺序，故我们只需要统计各个操作被执行了多少次，通过前缀和简单实现。然后同样用前缀和处理m个操作。

#include <cstdio>
#define FOR(i,j,k) for(i=j;i<=k;++i)
const int N = , M = N;
typedef long long ll;
int l[M], r[M], p[M], n;
ll c[N], d[M];
void add(int i, ll x) {
    for (; i <= n; i += i & -i) c[i] += x;
}
ll sum(int i) {
    ll s = ;
    for (; i; i -= i & -i) s += c[i];
    return s;
}
int main() {
    int a, m, k, i, x, y, q = ;
    scanf("%d%d%d", &n, &m, &k);
    FOR(i,,n) scanf("%I64d", &a), c[i] += a, c[i + ] -= a;
    FOR(i,,m) scanf("%d%d%d", l + i, r + i, d + i);
    FOR(i,,k) {
        scanf("%d%d", &x, &y);
        ++p[x]; --p[y + ];
    }
    FOR(i,,m) {
        q += p[i]; c[l[i]] += d[i] * q; c[r[i] + ] -= d[i] * q;
    }
    FOR(i,,n) printf("%I64d ", c[i]);
    return ;
}
           

295B - Greg and Graph

题目大意

给出n个点的有向完全图，求每删一个点图中各点对间最短路径长度之和。

题解

只有删除操作的题目一般都离线转为添加操作

如果是添加的话，每添加一个点跑一次多源最短路径显然Floyd。

#include <cstdio>
#include <algorithm>
using namespace std;
#define FOR(i,j,k) for(i=j;i<=k;++i)
typedef long long ll;
const int N = ;
ll dis[N][N], ans[N], d[N];
bool vis[N];
int main() {
    int i, j, k, l, n;
    scanf("%d", &n);
    FOR(i,,n) FOR(j,,n) scanf("%I64d", &dis[i][j]), ans[] += dis[i][j];
    FOR(i,,n) scanf("%d", &d[i]);
    for(l=n;l;--l) {
        k = d[l]; vis[k] = ;
        FOR(i,,n) FOR(j,,n) {
            dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            if (vis[i] && vis[j]) ans[l] += dis[i][j];
        }
    }
    FOR(i,,n) printf("%I64d ", ans[i]);
    return ;
}
           

295C - Greg and Friends

#include <cstdio>
#include <queue>
#define FOR(i,j,k) for(i=j;i<=k;++i)
typedef long long ll;
const int N = , MOD = ;
using namespace std;
struct Data { int n1, n2, type;
    int id() { return n1 * N * N + n2 * N + type; }
};
ll dp[N * N * ], path[N * N * ], C[N][N];
queue<Data> q;
int main() {  
    int i, j, x, n1 = , n2 = , n, k;
    Data h, p;
    FOR(i,,) C[i][] = ;
    FOR(i,,) FOR(j,,)
        C[i][j] = (C[i - ][j - ] + C[i - ][j]) % MOD;
    FOR(i,,n) {
        scanf("%d",&x);
        if (x == ) n1++; else n2++;
    }
    h = (Data){n1, n2, };
    dp[h.id()] = path[h.id()] = ;
    q.push(h);
    while (!q.empty()) {
        u = q.front(); q.pop();
        for(j=;j<=u.n2&&j*<=k;++j) {
            for(i=;i<=u.n1&&i*+j*<=k;++i) if (j || i) {
                 v = (Data) {n1 - u.n1 + i, n2 - u.n2 + j,  - u.type};
                 if (!dp[v.id()]) {
                      dp[v.id()] = dp[u.id()] + ;
                      q.push(v);
                 }
                 if (dp[v.id()] == dp[u.id()] + ) {
                      ll t = (C[u.n1][i] * C[u.n2][j]) % MOD;
                      (t *= path[u.id()]) %= MOD;
                      (path[v.id()] += t) %= MOD;
                 }
            }
        }
    }
    printf("%I64d\n%I64d", dp[((Data){n1,n2,}).id()]-, path[((Data){n1,n2,}).id()]);
    return ;
}