2012 Multi-University #7

最短路＋拆点Ａ As long as Binbin loves Sangsang

题意：从１走到ｎ，每次都是LOVE，问到ｎ时路径是连续多个＂LOVE＂的最短距离．秀恩爱不想吐槽．

分析：在普通的最短路上有寻路的限制，把一个点看成４个点，表示通过某一个字符到该点的最短距离．注意自环的处理，还有距离会爆int。

#include <bits/stdc++.h>

const int N = 1314 + 5;

const int M = 13520 + 5;

const long long INF = 200000000000LL;

struct Edge {

    int v, w, ch, nex;

};

Edge edge[M<<1];

int head[N];

int n, m, etot;

void init_edge() {

    etot = 0;

    memset (head, -1, sizeof (head));

}

void add_edge(int u, int v, int w, char ch) {

    edge[etot].v = v; edge[etot].w = w;

    edge[etot].nex = head[u];

    if (ch == 'L') {

        edge[etot].ch = 0;

    } else if (ch == 'O') {

        edge[etot].ch = 1;

    } else if (ch == 'V') {

        edge[etot].ch = 2;

    } else if (ch == 'E') {

        edge[etot].ch = 3;

    }

    head[u] = etot++;

}

struct Node {

    int u, id;

};

long long dis[N][4];

int cnt[N][4];

bool vis[N][4];

void SPFA(int s) {

    for (int i=1; i<=n; ++i) {

        for (int j=0; j<4; ++j) {

            vis[i][j] = false;

            dis[i][j] = INF;

            cnt[i][j] = 0;

        }

    }

    dis[s][3] = 0; vis[s][3] = true;

    std::queue<Node> que;

    que.push ((Node) {s, 3});

    while (!que.empty ()) {

        Node now = que.front (); que.pop ();

        int u = now.u, id = now.id;

        vis[u][id] = false;

        for (int i=head[u]; ~i; i=edge[i].nex) {

            Edge &e = edge[i];

            if (e.ch != (id + 1) % 4) {

                continue;

            }

            if (dis[e.v][e.ch] > dis[u][id] + e.w || dis[e.v][e.ch] == 0) {

                dis[e.v][e.ch] = dis[u][id] + e.w;

                cnt[e.v][e.ch] = cnt[u][id];

                if (e.ch == 3) {

                    cnt[e.v][e.ch]++;

                }

                if (!vis[e.v][e.ch]) {

                    vis[e.v][e.ch] = true;

                    que.push ((Node) {e.v, e.ch});

                }

            } else if ((dis[e.v][e.ch] == dis[u][id] + e.w || dis[e.v][e.ch] == 0) && cnt[e.v][e.ch] <= cnt[u][id]) {

                cnt[e.v][e.ch] = cnt[u][id];

                if (e.ch == 3) {

                    cnt[e.v][e.ch]++;

                }

                if (!vis[e.v][e.ch]) {

                    vis[e.v][e.ch] = true;

                    que.push ((Node) {e.v, e.ch});

                }

            }

        }

    }

}

int main() {

    int T;

    scanf ("%d", &T);

    for (int cas=1; cas<=T; ++cas) {

        init_edge ();

        scanf ("%d%d", &n, &m);

        char ch[2];

        for (int i=0; i<m; ++i) {

            int u, v, l;

            scanf ("%d%d%d%s", &u, &v, &l, ch);

            add_edge (u, v, l, ch[0]);

            add_edge (v, u, l, ch[0]);

        }

        SPFA (1);

        if (dis[n][3] == INF || cnt[n][3] == 0) {

            printf ("Case %d: Binbin you disappoint Sangsang again, damn it!\n", cas);

        } else {

            printf ("Case %d: Cute Sangsang, Binbin will come with a donkey after travelling %I64d meters and finding %d LOVE strings at last.\n", cas, dis[n][3], cnt[n][3]);

        }

    }

    return 0;

}

DP+优化 C Dragon Ball

题意：m个时间，每个时间去取一个龙珠，代价是距离|x-ball[i].pos|，此时人移动到龙珠的位置，还有该龙珠的代价ball[i].cost，问最小代价。

分析： $dp[i][j]=min(dp[i-1][k]+|ball[i-1][k]-ball[i][j]|+ball[i][j].cost)$ $=min(dp[i-1][k]+ball[i-1][k])-ball[i][j]+ball[i][j].cost$ $(ball[i-1][k].pos>ball[i][j].pos)$ ,另一种情况同理，先对每个时间的位置排序，求i-1时间前缀最小的 $min(dp[i-1][k]+ball[i-1][k])$ 转移就好了。

#include <bits/stdc++.h>

const int N = 50 + 5;

const int M = 1000 + 5;

const int INF = 0x3f3f3f3f;

struct Ball {

    int pos, cost;

    bool operator < (const Ball &rhs) const {

        return pos < rhs.pos;

    }

};

Ball ball[N][M];

int dp[N][M];

int m, n, x;

int main() {

    int T;

    scanf ("%d", &T);

    while (T--) {

        scanf ("%d%d%d", &m, &n, &x);

        for (int i=1; i<=m; ++i) {

            for (int j=1; j<=n; ++j) {

                scanf ("%d", &ball[i][j].pos);

            }

        }

        for (int i=1; i<=m; ++i) {

            for (int j=1; j<=n; ++j) {

                scanf ("%d", &ball[i][j].cost);

            }

            std::sort (ball[i]+1, ball[i]+1+n);

        }

        memset (dp, INF, sizeof (dp));

        for (int i=1; i<=n; ++i) {

            dp[1][i] = abs (ball[1][i].pos - x) + ball[1][i].cost;

        }

        for (int i=2; i<=m; ++i) {

            int k = 1, mn = INF;

            for (int j=1; j<=n; ++j) {

                for (; k<=n && ball[i-1][k].pos <= ball[i][j].pos; ++k) {

                    mn = std::min (mn, dp[i-1][k] - ball[i-1][k].pos);

                }

                dp[i][j] = mn + ball[i][j].pos + ball[i][j].cost;

            }

            k = n; mn = INF;

            for (int j=n; j>=1; --j) {

                for (; k>=1 && ball[i-1][k].pos > ball[i][j].pos; --k) {

                    mn = std::min (mn, dp[i-1][k] + ball[i-1][k].pos);

                }

                dp[i][j] = std::min (dp[i][j], mn - ball[i][j].pos + ball[i][j].cost);

            }

        }

        int ans = INF;

        for (int i=1; i<=n; ++i) {

            ans = std::min (ans, dp[m][i]);

        }

        printf ("%d\n", ans);

    }

    return 0;

}

模拟 E Matrix operation

读懂题，照着模拟

#include <bits/stdc++.h>

int mat[4][4] = {2, 3, 1, 1,

                 1, 2, 3, 1,

                 1, 1, 2, 3,

                 3, 1, 1, 2};

int a[4][4], tmp[4];

void run() {

    int ans[4][4];

    for (int i=0; i<4; ++i) {

        for (int j=0; j<4; ++j) {

            for (int k=0; k<4; ++k) {

                int t;

                if (mat[i][k] == 2) {

                    t = a[k][j] << 1;

                    if (t > 0xFF) {

                        t ^= 0x1B;

                    }

                    if (t > 0xFF) {

                        t %= (0xFF + 1);

                    }

                } else if (mat[i][k] == 3) {

                    t = a[k][j] << 1;

                    if (t > 0xFF) {

                        t ^= 0x1B;

                    }

                    t ^= a[k][j];

                    if (t > 0xFF) {

                        t %= (0xFF + 1);

                    }

                } else {

                    t = a[k][j];

                }

                tmp[k] = t;

            }

            int t = tmp[0];

            for (int i=1; i<4; ++i) {

                t ^= tmp[i];

            }

            ans[i][j] = t;

        }

    }

    for (int i=0; i<4; ++i) {

        for (int j=0; j<3; ++j) {

            printf ("%02X ", ans[i][j]);

        }

        printf ("%02X\n", ans[i][3]);

    }

}

int main() {

    int T;

    scanf ("%d", &T);

    while (T--) {

        for (int i=0; i<4; ++i) {

            for (int j=0; j<4; ++j) {

                scanf ("%X", &a[i][j]);

            }

        }

        run ();

        if (T) {

            puts ("");

        }

    }

    return 0;

}

数学+快速幂 F Palindrome graph

题意：一个n*n的图填充颜色使得图如何反转或旋转都不会变化。

分析：考虑到是中心对称的，只要考虑1/8的图（三角形）就行了，假设总和x个。填充过的颜色的位置转移到1/8的图中（假设y个），其他的地方能涂k种颜色，答案是k^(x-y)。

#include <bits/stdc++.h>

const int MOD = 100000007;

int pow_mod(int x, int n) {

    int ret = 1;

    while (n) {

        if (n & 1) {

            ret = (long long) ret * x % MOD;

        }

        x = (long long) x * x % MOD;

        n >>= 1;

    }

    return ret;

}

const int N = 10005;

bool vis[N/2][N/2];

int n, m, k;

int main() {

    while (scanf ("%d%d%d", &n, &m, &k) == 3) {

        memset (vis, false, sizeof (vis));

        int mid = n / 2;

        if (n & 1) {

            mid++;

        }

        for (int i=0; i<m; ++i) {

            int x, y;

            scanf ("%d%d", &x, &y);

            x++; y++;

            if (x > mid) {

                x = n + 1 - x;

            }

            if (y > mid) {

                y = n + 1 - y;

            }

            if (x < y) {

                std::swap (x, y);

            }

            vis[x][y] = true;

        }

        int c = 0;

        for (int i=1; i<=mid; ++i) {

            for (int j=1; j<=i; ++j) {

                if (!vis[i][j]) {

                    c++;

                }

            }

        }

        printf ("%d\n", pow_mod (k, c));

    }

    return 0;

}

DFS序+线段树 G Successor

题意：给了n个人的上下级关系，每个人有能力和忠诚度，问如果上级被炒了，下属里能力比他强，忠诚度最高的是谁。

分析：其实就是给了一棵树，DFS序转换为线性序列，每一个上级管辖一段区间，按照能力从大到小排序，每次插入能力比上级强的，相同的也同时插入，询问忠诚度最高的对应人的id即是答案。

#include <bits/stdc++.h>

const int N = 5e4 + 5;

struct Person {

    int sup, loy, ab, id;

    bool operator < (const Person &rhs) const {

        return ab > rhs.ab;

    }

}p[N];

int n, m;

int left[N], right[N];

std::map<int, int> ID;

std::vector<int> edge[N];

int tot;

#define lson l, mid, o << 1

#define rson mid + 1, r, o << 1 | 1

int mx[(N<<1)<<2];

void push_up(int o) {

    mx[o] = std::max (mx[o<<1], mx[o<<1|1]);

}

void updata(int p, int v, int l, int r, int o) {

    if (l == r) {

        mx[o] = v;

        return ;

    }

    int mid = l + r >> 1;

    if (p <= mid) {

        updata (p, v, lson);

    } else {

        updata (p, v, rson);

    }

    push_up (o);

}

int query(int ql, int qr, int l, int r, int o) {

    if (ql <= l && r <= qr) {

        return mx[o];

    }

    int mid = l + r >> 1, ret = -1;

    if (ql <= mid) {

        ret = std::max (ret, query (ql, qr, lson));

    }

    if (qr > mid) {

        ret = std::max (ret, query (ql, qr, rson));

    }

    return ret;

}

void DFS(int u) {

    left[u] = tot++;

    for (auto v: edge[u]) {

        DFS (v);

    }

    right[u] = tot;

}

int ans[N];

void solve() {

    tot = 1;

    DFS (0);

    //build (1, tot-1, 1);

    memset (mx, -1, sizeof (mx));

    std::sort (p+1, p+n);

    ans[0] = -1;

    for (int j, i=1; i<n; i=j) {

        j = i;

        while (j < n && p[j].ab == p[i].ab) {

            int id = p[j].id;

            ans[id] = ID[query (left[id]+1, right[id]-1, 1, tot-1, 1)];

            j++;

        }

        j = i;

        while (j < n && p[j].ab == p[i].ab) {

            int id = p[j].id;

            updata (left[id], p[j].loy, 1, tot-1, 1);

            j++;

        }

    }

}

int main() {

    int T;

    scanf ("%d", &T);

    while (T--) {

        scanf ("%d%d", &n, &m);

        for (int i=0; i<n; ++i) {

            edge[i].clear ();

        }

        ID.clear ();

        ID[-1] = -1;

        for (int i=1; i<n; ++i) {

            scanf ("%d%d%d", &p[i].sup, &p[i].loy, &p[i].ab);

            p[i].id = i;

            edge[p[i].sup].push_back (i);

            ID[p[i].loy] = i;

        }

        solve ();

        for (int i=0; i<m; ++i) {

            int j;

            scanf ("%d", &j);

            printf ("%d\n", ans[j]);

        }

    }

    return 0;

}

巴特西

2012 Multi-University #7

最新文章

热门文章