7.11暑期模拟赛

2022暑

---

预估分数：

T1	T2	T3	Sum
100	100	100	300

实际分数：

T1	T2	T3	Sum
100	100	100	300

（吐槽T3数据，要不是有人发现了数据BUG就痛失AK）

T1 Chain

第一问统计叶子树，第二问直接依题意树形DP上来，签到题。

Tips：题面提示说注意可能有必要写手写栈，然后我就用的Tuopu，结果递归的也都过了，我因为用了STL比有些小常数递归的还慢（

//The Code Is From Dawn
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 2 * 1e6 + 5, mod = 32416190071;
int n;
struct node {
    int v, nex;
    int w;
}edge[maxn];
int head[maxn], len, In[maxn], Out[maxn], f[maxn], root, Ans1;
inline void make_map(int u, int v, int w) {
    len++;
    edge[len].nex = head[u];
    edge[len].v = v;
    edge[len].w = w;
    head[u] = len;
}
inline void Tuopu() {
    queue <int> Q;
    for(register int i = 1; i <= n; ++i) {
        if(!In[i]) Ans1++, Q.push(i);
        if(!Out[i]) root = i;
    }
    while(!Q.empty()) {
        int x = Q.front(); Q.pop();
        for(register int i = head[x]; i; i = edge[i].nex) {
            int y = edge[i].v, z = edge[i].w;
            f[y] = (f[y] + f[x] * z % mod) % mod, In[y]--;
            if(!In[y]) Q.push(y);
        }
    }
}
signed main() {
//  freopen("Chain.in", "r", stdin);
//  freopen("Chain.out", "w", stdout);
    n = read();
    for(register int i = 1; i < n; ++i) {
        int u = read(), v = read(), w = read();
        make_map(v, u, w), In[u]++, Out[v]++;
    }
    for(register int i = 1; i <= n; ++i) f[i] = read() % mod;
    Tuopu();
    printf("%lld\n%lld\n", Ans1, f[root]);
    return 0;
}

T2 Prefix

算法：KMP+DP

计数题，考虑DP，子串，考虑定义状态 $f[i]$ 为 以 $i$ 结尾的合法子串数量。

朴素方程：

$$f[i] = \sum_{j = 2 , 2 \mid j}^{i} [s[1\ldots j] = s[i - j + 1 \ldots i]]$$

可以发现这个check是个前缀等于后缀的形式，考虑利用 KMP 里的 $\operatorname{next}$ 数组

那么就是：

$$f[i] = \begin{cases} f[\operatorname{next}[i]] + 1 & 2 \mid i\\ f[\operatorname{next}[i]] & 2\nmid i \end{cases}$$

//The Code Is From Dawn
#include<bits/stdc++.h>
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 2 * 1e5 + 5;
char s[maxn];
int n, Next[maxn], f[maxn], Ans;
inline void Get_Next() {
    Next[0] = -1, Next[1] = 0;
    for(register int i = 2; i <= n; ++i) {
        int j = Next[i - 1] + 1;
        while(s[j] != s[i] && j) j = Next[j - 1] + 1;
        if(j) Next[i] = j;
        else Next[i] = 0;
    }
}
int main() {
//  freopen("Prefix.in", "r", stdin);
//  freopen("Prefix.out", "w", stdout);
    scanf("%s", s + 1), n = strlen(s + 1);
    Get_Next();
    for(register int i = 1; i <= n; ++i) {
        if(i % 2 == 0) f[i] = 1;
        if(Next[i] > 0) f[i] += f[Next[i]];
        Ans += f[i];
    }
    printf("%d\n", Ans);
    return 0;
}

T3 Motor

很显然的分层图模型，这里采用二维 Dij

//The Code Is From Dawn
#include<bits/stdc++.h>
#define Pi pair< pair<int, int>, int >
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxm = 5 * 1e4 + 5, maxn = 1e4 + 5, INF = 1e9 + 7;
int n, m, k, s, t;
struct node {
    int v, nex;
    int w;
}edge[maxm << 1];
int head[maxn], len;
int Dist[maxn][15], Vst[maxn][15];
inline void make_map(int u, int v, int w) {
    len++;
    edge[len].nex = head[u];
    edge[len].v = v;
    edge[len].w = w;
    head[u] = len;
}
inline void Dijstra() {
    memset(Vst, 0, sizeof(Vst));
    for(register int i = 1; i <= n; ++i)
        for(register int j = 0; j <= k; ++j) Dist[i][j] = INF;
    priority_queue < Pi > Q;
    Q.push(make_pair(make_pair(0, 0), s)), Dist[s][0] = 0;
    while(!Q.empty()) {
        int x = Q.top().second, fr = Q.top().first.second; Q.pop();
        if(Vst[x][fr]) continue;
        for(register int i = head[x]; i; i = edge[i].nex) {
            int y = edge[i].v, z = edge[i].w;
            if(Dist[y][fr] > Dist[x][fr] + z) {
                Dist[y][fr] = Dist[x][fr] + z;
                Q.push(make_pair(make_pair(-Dist[y][fr], fr), y));
            }
            if(fr < k && Dist[y][fr + 1] > Dist[x][fr]) {
                Dist[y][fr + 1] = Dist[x][fr];
                Q.push(make_pair(make_pair(-Dist[y][fr + 1], fr + 1), y));
            }
        }
    }
}
int main() {
//  freopen("Motor.in", "r", stdin);
//  freopen("Motor.out", "w", stdout);
    n = read(), m = read(), k = read(), s = read(), t = read();
    for(register int i = 1; i <= m; ++i) {
        int u = read(), v = read(), w = read();
        make_map(u, v, w), make_map(v, u, w);
    }
    Dijstra();
    int Ans = INF;
    for(register int i = 0; i <= k; ++i) Ans = min(Ans, Dist[t][i]);
    printf("%d\n", Ans);
    return 0;
}