最短路＋拆点 Ａ 

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

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

#include 
     
      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
      
        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
      
     

 

DP+优化 C 

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

分析：,另一种情况同理，先对每个时间的位置排序，求i-1时间前缀最小的转移就好了。

#include 
     
      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 

读懂题，照着模拟

#include 
     
      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 

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

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

#include 
     
      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
      
        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 

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

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

#include 
     
      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
      
        ID;std::vector
       
         edge[N];int tot;#define lson l, mid, o << 1#define rson mid + 1, r, o << 1 | 1int 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