[題解]NOIP2017 Day1 Solution - by xyz32768

我冒了嚴寒，去到相隔二萬餘裡，二十多年不見的NOIP賽場去。——出自《或許我就是蒟蒻吧》

T1 math

作為Day1T1，這一題不是一般的坑……

首先設一個合法選擇為 x ，則必須滿足這兩個條件：

1、a∤x

2、對于所有的 0≤i 并且 x−ia≥0 ，有 b∤(x−ia) 。

可以發現，在第二個條件中，滿足 0≤i 并且 x−ia≥0 的 i 有⌊xa⌋+1個。

而由于 a,b 互質，是以 x 不斷減去a後對 b 的模數是滿足周期性變化的，并且周期長度為b。是以得到，凡是 ⌊xa⌋+1≥b 的數都是不合法的。

考慮在 ⌊xa⌋=b−1 的範圍内找答案。這種情況下如果不斷地把 x 減去a，算上 x 本身一共會得到b−1種結果。而這 b−1 種結果已經周遊了對 b 的b−1種模數，還有一個模數沒有周遊到，而這個模數就是 0 。而這時候恰好就是讓x減掉 ab−a 後是 b 的倍數。但顯然x是不能取 ab−a 的，是以 x 的最大值為ab−a−b。

代碼：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int a, b;
int main() {
    //freopen("math.in", "r", stdin);
    //freopen("math.out", "w", stdout);
    cin >> a >> b;
    cout << l * a * b - a - b << endl;
    return ;
}
           

T2 complexity

大模拟……利用一點點棧的思想……注意細節。

1、x n， O(n) 。

2、n n， O(1) 。

3、x y， x<=y 則 O(1) ，否則 O(0) （無法執行）。

4、n x， O(0) 。

代碼：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
inline int read() {
    int res = ; bool bo = ; char c;
    while (((c = getchar()) < '0' || c > '9') && c != '-');
    if (c == '-') bo = ; else res = c - ;
    while ((c = getchar()) >= '0' && c <= '9')
        res = (res << ) + (res << ) + (c - );
    return bo ? ~res +  : res;
}
const int N = , INF = ;
char s[N][N], com[N]; int L, top, stk[N], st[N], ed[N];
char var[N];
void Get(int id, int to) {
    int i, n = strlen(s[id] + ); i = ; st[to] = ed[to] = ;
    while (s[id][i] == ' ') i++; var[to] = s[id][i++];
    while (s[id][i] == ' ') i++;
    while (s[id][i] != ' ') {
        if (s[id][i] == 'n') st[to] = INF;
        else st[to] = st[to] *  + (s[id][i] - '0');
        i++;
    }
    while (s[id][i] == ' ') i++;
    while (s[id][i] != ' ' && s[id][i] != ) {
        if (s[id][i] == 'n') ed[to] = INF;
        else ed[to] = ed[to] *  + (s[id][i] - '0');
        i++;
    }
}
void work() {
    int i, j, CM = , nowCm = , stCM = ;
    L = read(); scanf("%s\n", com + ); top = ;
    for (i = ; i <= L; i++) gets(s[i] + );
    for (i = ; i <= L; i++) {
        if (s[i][] == 'F') {
            stk[++top] = i; Get(i, top); nowCm = ;
            for (j = ; j < top; j++) {
                if (var[j] == var[top])
                    return (void) puts("ERR");
            }
            for (j = ; j <= top; j++)
                if (st[j] != INF && ed[j] == INF) nowCm++;
                else if (st[j] == INF && ed[j] != INF) break;
                else if (st[j] != INF && ed[j] != INF) {
                    if (st[j] > ed[j]) break;
                }
            CM = max(CM, nowCm);
        }
        else {
            top--;
            if (top < ) return (void) puts("ERR");
        }
    }
    if (top > ) return (void) puts("ERR");
    if (com[] == '1') stCM = ;
    else {
        int w = strlen(com + );
        for (i = ; i < w; i++) stCM = stCM *  + (com[i] - '0');
    }
    puts(CM == stCM ? "Yes" : "No");
}
int main() {
    //freopen("complexity.in", "r", stdin);
    //freopen("complexity.out", "w", stdout);
    int T = read();
    while (T--) work();
    return ;
}
           

T3 park

稍有難度的題來了……在考場上Tarjan寫炸丢了30分[挫敗]

先在反圖上以 n 為起點跑最短路，記dis[i]為 i 到n的最短路。

先考慮有無數條合法路徑的條件，容易想到，有無數條合法路徑，當且僅當圖存在零環并且存在一條長度不大于 dis[1]+K 的 1 到n的路徑經過了在零環上的點。判斷一個點是否在零環上，可以用Tarjan強連通分量等技巧實作。判斷是否在 1 到n的合法路徑上，即判斷是否滿足：

1 到該節點的最短距離+該節點到n的最短距離 ≤dis[1]+K 。

然後DP，看到 K 很小，就可以想到模型：

f[i,j]表示 i 到n，距離為 dis[i]+j 的方案數。

轉移就是（ k 為與i相鄰（存在邊 <i,k <script type="math/tex" id="MathJax-Element-57"> val<i,k> 為邊 <i,k> <script type="math/tex" id="MathJax-Element-59"> </script>的邊權）：

f[i,j]=∑kf[k,dis[i]+j−val<i,k>−dis[k]] 。

剛開始發現這個方程有點兒問題（轉移時出現環），但後來發現，

由于 val<i,k>+dis[k] 一定不小于 dis[i] ，是以 dis[i]+j−val<i,k>−dis[k] 一定不大于 j ，是以不存在零環的情況下，轉移是不會出現環的。

由于j相同的情況下，隻能從 dis 較小的點轉移到 dis 較大的點，是以可以将每個點按照 dis 為關鍵字排序（蒟蒻用了記憶化搜尋）進行DP。

代碼：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
inline int read() {
    int res = ; bool bo = ; char c;
    while (((c = getchar()) < '0' || c > '9') && c != '-');
    if (c == '-') bo = ; else res = c - ;
    while ((c = getchar()) >= '0' && c <= '9')
        res = (res << ) + (res << ) + (c - );
    return bo ? ~res +  : res;
}
const int N =  + , M =  + , E = , INF = ;
int n, m, ecnt, K, nxt[M], adj[N], go[M], val[M], f[N][E], dis[N],
nxt2[M], adj2[N], go2[M], val2[M], ecnt2, que[M << ], len, PYZ,
times, sum, bel[N], stk[N], num[N], top, dfn[N], low[N], disS[N];
bool vis[N], VIS[N], ins[N];
void add_edge(int u, int v, int w) {
    nxt[++ecnt] = adj[u]; adj[u] = ecnt; go[ecnt] = v; val[ecnt] = w;
    nxt2[++ecnt2] = adj2[v]; adj2[v] = ecnt2; go2[ecnt2] = u; val2[ecnt2] = w;
}
void Tarjan(int u) {
    dfn[u] = low[u] = ++times; ins[stk[++top] = u] = ;
    for (int e = adj[u], v; e; e = nxt[e]) {
        if (val[e]) continue;
        if (!dfn[v = go[e]]) {
            Tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (ins[v]) low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        num[bel[u] = ++sum] = ; ins[u] = ; int v;
        while (v = stk[top--], v != u) num[bel[v] = sum]++, ins[v] = ;
    }
}
void spfa(int S) {
    int i; memset(dis, INF, sizeof(dis));
    dis[que[len = ] = S] = ;
    for (i = ; i <= len; i++) {
        int u = que[i]; vis[u] = ;
        for (int e = adj[u], v; e; e = nxt[e])
            if (dis[u] + val[e] < dis[v = go[e]]) {
                dis[v] = dis[u] + val[e];
                if (!vis[v]) vis[que[++len] = v] = ;
            }
    }
    for (i = ; i <= n; i++) disS[i] = dis[i];
}
void SPFA(int S) {
    int i; memset(dis, INF, sizeof(dis));
    dis[que[len = ] = S] = ;
    for (i = ; i <= len; i++) {
        int u = que[i]; vis[u] = ;
        for (int e = adj2[u], v; e; e = nxt2[e])
            if (dis[u] + val2[e] < dis[v = go2[e]]) {
                dis[v] = dis[u] + val2[e];
                if (!vis[v]) vis[que[++len] = v] = ;
            }
    }
}
bool zeroCycle() {
    times = sum = ; int i; memset(num, , sizeof(num));
    memset(dfn, , sizeof(dfn));
    for (i = ; i <= n; i++) if (!dfn[i]) Tarjan(i);
    for (i = ; i <= n; i++) if (num[bel[i]] > 
        && disS[i] + dis[i] <= dis[] + K) return ;
    return ;
}
int DP(int u, int x) {
    if (f[u][x] != -) return f[u][x];
    if (!x && u == n) return f[u][x] = ; f[u][x] = ;
    for (int e = adj[u], v; e; e = nxt[e]) {
        int d = dis[u] + x - val[e] - dis[v = go[e]];
        if (d >=  && d <= K)
            (f[u][x] += DP(v, d)) %= PYZ;
    }
    return f[u][x];
}
void work() {
    memset(bel, , sizeof(bel));
    memset(vis, , sizeof(vis));
    memset(VIS, , sizeof(VIS));
    ecnt = ecnt2 = ; memset(adj, , sizeof(adj));
    memset(adj2, , sizeof(adj2));
    memset(f, -, sizeof(f));
    int i, x, y, z; n = read(); m = read(); K = read(); PYZ = read();
    for (i = ; i <= m; i++) {
        x = read(); y = read(); z = read();
        add_edge(x, y, z);
    }
    spfa(); SPFA(n); int ans = ; if (zeroCycle()) return (void) puts("-1");
    for (i = ; i <= K; i++) (ans += DP(, i)) %= PYZ;
    printf("%d\n", ans);
}
int main() {
    //freopen("park.in", "r", stdin);
    //freopen("park.out", "w", stdout);
    int T = read();
    while (T--) work();
    return ;
}