CF Round 918

很久很久以后我连Div4都开始做不动了……

Codeforces Round 918 (Div.4)

E Romantic Glasses

题意

给一个数列，问是否存在一个子区间，奇数位置的和等于偶数位置的和。

题解

奇数位置的和=偶数位置的和，移项后也就是 奇数位置的和-偶数位置的和=0，或者偶数位置的和-奇数位置的和=0，所以将奇数位置或者偶数位置取相反数以后问题及转化为是否存在子区间的和为0。而子区间 的和 = ，所以问是否有子区间和为0也就等同于问是否有两个前缀和相等。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fr first
#define sc second

inline int rd() {
    int x = 0; bool f = 0; char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

map<ll, bool> vis;
#define N 200007
int a[N];

inline void work() {
    int n = rd();
    ll sum = 0;
    vis.clear(); vis[0] = 1;
    for (int i = 1; i <= n; ++i) {
        a[i] = rd();
        if (i % 2) a[i] = -a[i];
    }
    for (int i = 1; i <= n; ++i) {
        sum += a[i];
        if (vis[sum]) {puts("YES"); return;}
        vis[sum] = 1;
    }
    puts("NO");
}

int main() {
    for (int t = rd(); t; --t) work();
    return 0;
}

G Bicycles

题意

给一张无向图，每个点都有一个点权 ，每个边也有一个边权 ，假设已经经过的点集合是 ，现在要经过的边边权为 ，则经过这条边的代价为 ，求从 号点到 号点的最小代价。

题解

首先，在最优方案里一个点是可能被经过多次的（比如第一个样例），所以不能仅根据点来划分最短路的阶段，观察数据范围可知，可以将经过的点集的 记在状态里，然后进行转移。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fr first
#define sc second

inline int rd() {
    int x = 0; bool f = 0; char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 1007
ll dis[N][N];
bool vis[N][N];
int s[N];
vector<pii> e[N];
priority_queue<pair<ll, pii> > q;

inline void work() {
    int n = rd(), m = rd();
    for (int i = 1; i <= n; ++i) {
        e[i].clear();
        for (int j = 1; j <= 1000; ++j) {
            dis[i][j] = 1e18;
            vis[i][j] = 0;
        }
    }
    for (int i = 1; i <= m; ++i) {
        int u = rd(), v = rd(), w = rd();
        e[u].pb(mp(v, w)); e[v].pb(mp(u, w));
    }
    for (int i = 1; i <= n; ++i) s[i] = rd();
    dis[1][s[1]] = 0;
    q.push(mp(0, mp(1, s[1])));
    while (!q.empty()) {
        int u = q.top().sc.fr, ss = q.top().sc.sc;
        q.pop();
        if (vis[u][ss]) continue;
        vis[u][ss] = 1;
        for (auto [v, w] : e[u]) {
            if (dis[u][ss] + 1ll * w * ss < dis[v][min(ss, s[v])]) {
                dis[v][min(ss, s[v])] = dis[u][ss] + 1ll * w * ss;
                q.push(mp(-dis[v][min(ss, s[v])], mp(v, min(ss, s[v]))));
            }
        }
    }
    ll ans = 1e18;
    for (int i = 1; i <= 1000; ++i) ans = min(ans, dis[n][i]);
    printf("%lld\n", ans);
}

int main() {
    for (int t = rd(); t; --t) work();
    return 0;
}