2024西安铁一中集训DAY2 ---- 模仿赛（最小天生树 + AC自动机 + 模仿 + rmq）

角逐效果

估测：60 + 100 + 100 + 0 = 260
实得：5 + 100 + 0 + 0 = 105
rk11
挂大分的一场
题解

A. 江桥的天生树（MST）

标题
分析：
           我们思量 差别颜色的点终极肯定是联通的。因此我们可以对于每一种颜色可以先拿出来一个点，跑一遍  K r u s k a l Kruskal Kruskal 算法，然后剩下的点可以选择一个代价最小的点连起来。如许肯定是最优的。必要注意的是由于 图很稠密，因此  K r u s k a l Kruskal Kruskal 算法中对边排序会导致  T L E TLE TLE，因此必要用  P r i m Prim Prim 算法。
            P r i m Prim Prim 算法头脑：思量往天生树聚集中加点，每次选 间隔天生树近来的点 参加天生树中，并用它更新别的点到天生树的间隔。
时间复杂度  O ( n 2 ) O(n^2) O(n2)。
CODE：

1. #include<bits/stdc++.h>
2. #define pb push_back
3. using namespace std;
4. typedef long long LL;
5. typedef pair< int, int > PII;
6. const int M = 1e6 + 10;
7. const int N = 5005;
8. int n, a[N], tot;
9. LL p, q, w, h;
10. LL W[N][N], Min_val[N], res, dis[N];
11. int bin[N], Min_id[N];
12. bool vis[N];
13. void prim() {
14.    
15.    
16.         memset(dis, 0x3f, sizeof dis);
17.         vis[1] = 1;
18.         for(int i = 1; i <= n; i ++ ) {
19.    
20.    
21.                 if(!vis[i]) dis[i] = min(dis[i], W[1][i]);
22.         }
23.         for(int i = 2; i <= n; i ++ ) {
24.    
25.    
26.                 int id = -1, Min = 1e18;
27.                 for(int j = 1; j <= n; j ++ ) {
28.    
29.    
30.                         if(!vis[j]) {
31.    
32.    
33.                                 if(dis[j] < Min) Min = dis[j], id = j;
34.                         }
35.                 }
36.                 res += Min;
37.                 vis[id] = 1;
38.                 for(int j = 1; j <= n; j ++ ) {
39.    
40.    
41.                         if(!vis[j]) dis[j] = min(dis[j], W[id][j]);
42.                 }
43.         }
44. }
45. int main() {
46.    
47.    
48.         memset(Min_val, 0x3f, sizeof Min_val);
49.         scanf("%d", &n);
50.         for(int i = 1; i <= n; i ++ ) {
51.    
52.    
53.             scanf("%d", &a[i]);
54.         }
55.         scanf("%lld%lld%lld%lld", &p, &q, &w, &h);
56.         LL tmp = 0;
57.         for(int i = 1; i <= n * n; i ++ ) {
58.    
59.    
60.                 tmp = (p * tmp % h + q) % h;
61.                 int x, y;
62.                 if(i % n == 0) x = (i / n), y = n;
63.                 else x = (i / n + 1), y = i % n;
64.                 if(y >= x) {
65.    
66.    
67.                         W[x][y] = W[y][x] = tmp;
68.                 }
69.         }
70.         for(int i = 1; i <= n; i ++ ) {
71.    
72.    
73.                 for(int j = 1; j <= n; j ++ ) {
74.    
75.    
76.                         if(W[i][j] < Min_val[i]) Min_id[i] = j, Min_val[i] = W[i][j];
77.                 }
78.         }
79.         for(int i = 1; i <= n; i ++ ) a[i] --;
80.         for(int i = 1; i <= n; i ++ ) {
81.    
82.    
83.                 if(a[i] > 0)
84.                         res += (1LL * a[i] * Min_val[i]);
85.         }
86.         prim();
87.         cout << res << endl;
88.         return 0;
89. }

复制代码

B. 江桥的神机暗码（AC自动机，ST表）

分析：
           套路题。起首我们可以罗列一个右端点，然后求出一个最靠前的左端点更新答案。不难发现固定右端点后长度约短越容易满足限定，具有单调性，因此可以二分。思量怎样查验：一个区间不包罗特殊字符串等价于区间内恣意一个位置为末了都不能在区间里形成特殊字符串。因此我们处置惩罚出每个位置为末了，间隔他近来的左端点，满足左端点到它的区间是一个特殊字符，这个可以在构建  A C AC AC 自动机时处置惩罚。那么查验就是区间中全部位置对应的左端点都小于区间左端点。这个可以利用  S T ST ST 表  O ( 1 ) O(1) O(1) 求出区间最小值。
时间复杂度  O ( n l o g 2 n ) O(nlog_2n) O(nlog2​n)
CODE：

1. #include<bits/stdc++.h>
2. using namespace std;
3. const int N = 1e5 + 10;
4. int T, n, m, tot, tr[N][26], fail[N], e[N], L[N], Max[21][N];
5. char t[N], str[N];
6. void Insert(char *s){
7.    
8.    //插入
9.         int p = 0, len = strlen(s + 1);
10.         for(int i = 1; i <= len; i++){
11.    
12.    
13.                 int c = (int)(s[i] - 'a');
14.                 if(!tr[p][c]) tr[p][c] = ++tot;
15.                 p = tr[p][c];
16.         }
17.         e[p] = min(e[p], len);
18. }
19. queue< int > q;
20. void build(){
21.    
22.    
23.         int p

复制代码