比赛-Round 2 (10 Jul)

谢谢 hzwer 学长！

1. 小奇挖矿

从右往左决策消除后效性。

#include <cstdio>
#include <algorithm>

using namespace std;

const int _N = 120000;

int type[_N], A[_N];

int main()
{
    double ans = 0, P, k1, k2, K, C;
    int N, i;
    scanf("%d%lf%lf%lf", &N, &K, &C, &P);
    k1 = 1.0-K/100.0;
    k2 = 1.0+C/100.0;
    for (i = 1; i <= N; ++i)
        scanf("%d%d", &type[i], &A[i]);
    for (i = N; i >= 1; --i) {
        if (type[i] == 1)
            ans = max(ans, ans*k1+A[i]);
        else
            ans = max(ans, ans*k2-A[i]);
    }
    printf("%.2lf
", ans*P);
    return 0;
}

2. 小奇的数列

3. 小奇回地球

二分答案，判断到终点路上时候有负环。

#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>
#include <string.h>

using namespace std;

const int _N = 120;
const int INF = 1e9;

struct edge {
    int v, w;
    edge(int v, int w):
        v(v), w(w) { }
};

queue<int> Q;
vector<edge> G[_N];
int N, M;
int dis[_N], mk[_N], cnt[_N];
bool GG[_N][_N];

void Ins(int x, int y, int w) { G[x].push_back(edge(y, w)); return; }

bool Check(int ex)
{
    int i;
    for (i = 1; i <= N; ++i)
        dis[i] = INF, mk[i] = false, cnt[i] = 0, GG[i][i] = true;
    while (!Q.empty()) Q.pop();
    Q.push(1), dis[1] = 0, cnt[1] = 1, mk[1] = true;
    while (!Q.empty()) {
        int p = Q.front();
        Q.pop(), mk[p] = false;
        for (i = G[p].size()-1; i >= 0; --i) {
            edge v = G[p][i];
            if (!GG[v.v][N] || !GG[1][v.v]) continue;
            if (dis[v.v] > dis[p] + v.w + ex) {
                dis[v.v] = dis[p] + v.w + ex;
                if (!mk[v.v]) {
                    Q.push(v.v);
                    if (++cnt[v.v] > N) return false;
                }
            }
        }
    }
    return dis[N] >= 0 && dis[N] < INF;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        //CLEAR
        int bi_r, bi_l, i, j, k, ans = -1;
        scanf("%d%d", &N, &M);
        
        for (i = 1; i <= N; ++i) G[i].clear();
        memset(GG, 0, sizeof GG);
        
        for (i = 1; i <= M; ++i) {
            int x, y, w;
            scanf("%d%d%d", &x, &y, &w);
            GG[x][y] = true;
            Ins(x, y, w);
        }
        
        for (k = 1; k <= N; ++k)
            for (i = 1; i <= N; ++i)
                for (j = 1; j <= N; ++j)
                    if (GG[i][k] && GG[k][j]) GG[i][j] = true;
                            
        bi_l = -120000, bi_r = 120000;
        while (bi_l <= bi_r) {
            int bi_mid = bi_l+bi_r >> 1;
            if (Check(bi_mid))
                ans = dis[N], bi_r = bi_mid-1;
            else
                bi_l = bi_mid+1;
        }
        
        printf("%d
", ans);
    }
    return 0;
}