GCPC-2017题解

C - Joyride

题意：

游乐园有$n$个游乐设施，$m$条路，游玩第$i$个游乐设施需要$T_i$的时间和$P_i$的金钱，走过一条路需要$t$的时间，每遇到一个游乐设施强制游玩，问从1号游乐设施开始到1号游乐设施结束，花费时间为$x$的最小金钱花费。

解析：

这道题$x$较小，可以枚举每一个$x$所对应的从$1$号设施开始的最小花费，可以直接跑最短路。

代码：

#include <bits/stdc++.h>

using namespace std;
#define fast                          \
       ios_base::sync_with_stdio(false); \
       cin.tie(NULL);
const int N = 3e3 + 10;
const int M = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-3;
int ans;
struct node{
    int u,v,w,next;
}a[M];
int f[N],cnt;
void add(int u,int v,int w){
    a[++cnt].v = v;
    a[cnt].w = w;
    a[cnt].next = f[u];
    f[u] = cnt;
}
long long T[N], P[N];
int x, n, m, t;
long long dis[N][N], vis[N][N];
void dijkstra() {
    priority_queue<pair<int,pair<int,int>>> q;
    memset(dis, 0x3f, sizeof dis);
    memset(vis, 0, sizeof vis);
    q.push({0, {1,T[1]}});
    dis[T[1]][1] = P[1];
    while(!q.empty()) {
        int u = q.top().second.first;
        int X = q.top().second.second;
        q.pop();
        if(X > x)   continue;
        if(vis[X][u])  continue;
        vis[X][u] = 1;
        for (int i = f[u]; i; i = a[i].next) {
            int v = a[i].v;
            int w = X + a[i].w + T[v];
            if(dis[w][v] > dis[X][u] + P[v]) {
                dis[w][v] = dis[X][u] + P[v];
                q.push({-dis[w][v], {v, w}});
            }
        }
    }
}

int main(){
    ans = INF;
    cin >> x >> n >> m >> t;
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v, t);
        add(v, u, t);
    }
    for (int i = 1; i <= n; i++) {
        add(i, i, 0);
        scanf("%d%d", &T[i], &P[i]);
    }
    dijkstra();
    if(dis[x][1] == LINF) puts("It is a trap.");
    else    cout << dis[x][1] << '\n';
    return 0;
}

D - Pants On Fire

题意：

给定一些逻辑判断询问的逻辑是否正确

分析：

直接暴力找是否正确即可，需要对每个string取一个ID进行优化，不然会TLE

#include <bits/stdc++.h>

using namespace std;
#define fast                          \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);
const int N = 1e5 + 10;
const int M = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-3;
map<string, int> mp;
vector<int> id[N];
bool find(int u, int tar) {
    if (u == tar) return true;
    for (auto it : id[u]) {
        int w = find(it, tar);
        if (w) return true;
    }
    return false;
}
int main() {
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    string s1, s2, s3;
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        cin >> s1 >> s3 >> s3 >> s3 >> s2;
        if(mp.find(s1) == mp.end()) mp[s1] = ++cnt;
        if(mp.find(s2) == mp.end()) mp[s2] = ++cnt;
        int id1 = mp[s1], id2 = mp[s2];
        id[id2].push_back(id1);
    }
    for (int i = 1; i <= m; i++) {
        cin >> s1 >> s3 >> s3 >> s3 >> s2;
        if (mp.find(s1) == mp.end()) mp[s1] = ++cnt;
        if (mp.find(s2) == mp.end()) mp[s2] = ++cnt;
        int id1 = mp[s1], id2 = mp[s2];
        int w1 = find(id2, id1), w2 = find(id1, id2);
        if (w1) {
            cout << "Fact\n";
        } else if (w2) {
            cout << "Alternative Fact\n";
        } else {
            cout << "Pants on Fire\n";
        }
    }
    return 0;
}

F - Plug It In

题意：

$m$个插座，需要供应$n$个电器工作，有1个转换头，可以使一个插座供应3个电器，问最多可以供应多少电器。

分析：

网络流或者二分图板子题，每次枚举一个插座，增加容量找增广路，最后把容量都为1时的答案和增广后的答案相加即可。

#include <bits/stdc++.h>

using namespace std;
#define fast                          \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);
const int N = 3e3 + 10;
const int M = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-3;
struct node {
    int u, v, w, next;
} a[M], b[M];
int f[N], cnt;
inline void add(int u, int v, int w) {
    a[++cnt].v = v;
    a[cnt].w = w;
    a[cnt].next = f[u];
    f[u] = cnt;
    a[++cnt].v = u;
    a[cnt].w = 0;
    a[cnt].next = f[v];
    f[v] = cnt;
}
int d[N], cur[N];
int n, m, s, t;
bool bfs() {
    queue<int> q;
    memset(d, -1, sizeof d);
    q.push(s);
    d[s] = 0;
    cur[s] = f[s];
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = f[u]; i; i = a[i].next) {
            int v = a[i].v;
            if (d[v] == -1 && a[i].w) {
                d[v] = d[u] + 1;
                cur[v] = f[v];
                if (v == t) return true;
                q.push(v);
            }
        }
    }
    return false;
}
int find(int u, int limit) {
    if (u == t) return limit;
    int flow = 0;
    for (int i = cur[u]; i && flow < limit; i = a[i].next) {
        cur[u] = i;
        int v = a[i].v;
        if (d[v] == d[u] + 1 && a[i].w) {
            int ff = find(v, min(a[i].w, limit - flow));
            if (!ff) d[v] = -1;
            a[i].w -= ff, a[i ^ 1].w += ff, flow += ff;
        }
    }
    return flow;
}
int dinic() {
    int flow, res = 0;
    while (bfs())
        while (flow = find(s, INF)) res += flow;
    return res;
}
int main() {
    int k;
    cnt = 1;
    cin >> m >> n >> k;
    s = 0, t = n + m + 1;
    for (int i = 1; i <= m; i++) {
        add(s, i, 1);
    }
    for (int i = 1; i <= n; i++) add(i + m, t, 1);
    for (int i = 1; i <= k; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, m + v, 1);
    }
    int ans = 0, ans1 = 0;
    ans = dinic();
    memcpy(b, a, sizeof a);
    for (int i = 1; i <= m; i++) {
        memcpy(a, b, sizeof b);
        a[i * 2].w += 2;
        ans1 = max(ans1, dinic());
    }
    cout << ans + ans1 << '\n';
    return 0;
}

G - Water Testing

题意：

给定一个多边形，问多边形里共有多少整数点。

分析：

有公式：$S=a+\frac{1}{b}-1$，其中$S$为多边形面积，$a$为多边形内部整数点数，$b$为多边形边上的整数点数。多边形面积可以每两个点与原点组成三角形，直接进行面积相加，多余面积会被抵消。由于题目给出的方式有顺时针或逆时针两种，所以最后答案需要取绝对值。两点间边的整数点数为向量的绝对值的gcd值。

#include <bits/stdc++.h>

using namespace std;
#define fast                          \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);
typedef long long LL;
const int N = 5e5 + 10;
const int M = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const LL LINF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-3;
#define x first
#define y second
LL count(pair<LL, LL> a) {
    LL gcd = __gcd(abs(a.x), abs(a.y));
    return gcd;
}
LL operator*(pair<LL, LL> a,
                    pair<LL, LL> b) {
    return a.x * b.y - a.y * b.x;
}
pair<LL, LL> operator-(pair<LL, LL> a,
                                     pair<LL, LL> b) {
    return {a.x - b.x, a.y - b.y};
}
pair<LL, LL> a[N];
int main() {
    int n;
    cin >> n;
    LL point = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%lld%lld", &a[i].x, &a[i].y);
    }
    LL sum = 0;
    a[0] = a[n];
    for (int i = 1; i <= n; i++) {
        sum += (a[i]) * (a[i - 1]);
        point += count(a[i] - a[i - 1]);
    }
    sum = abs(sum);
    printf("%lld\n", sum / 2 - point / 2 + 1);
    return 0;
}

I - Uberwatch

题意：

$n$个时间片段，每个是片段有若干敌人，间隔$m$个时间片段可以进行一次攻击，问最多可以击败多少敌人。

分析：

简单dp，$dp_i$为从第一个时间片段到第$i$个时间片段最多可以击败多少敌人。每个时间片段可以进行攻击或不进行攻击，进行攻击从$dp_{i-m}$转移，不进行攻击从$dp_{i-1}$转移。

代码：

#include <bits/stdc++.h>

using namespace std;
#define fast                          \
       ios_base::sync_with_stdio(false); \
       cin.tie(NULL);
const int N = 5e5 + 10;
const int M = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-3;
int a[N];
int dp[N];
int main(){
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = m + 1; i <= n; i++) {
        dp[i] = max(dp[i - m] + a[i], dp[i - 1]);
    }
    cout << dp[n] << '\n';
    return 0;
}