【题目记录】——2021“MINIEYE杯”中国大学生算法设计超级联赛（8）

绝地灬酷狼 2022-09-04 13:46 75阅读 0赞

### 文章目录 ###

*  1003 Ink on paper 最小生成树
 *  1006 GCD Game 博弈论sg函数
 *  1009 Singing Superstar AC自动机

题目集地址 [2021“MINIEYE杯”中国大学生算法设计超级联赛（8）][2021_MINIEYE_8]  
题目集原地址 [2021“MINIEYE杯”中国大学生算法设计超级联赛（8）][2021_MINIEYE_8 1]

# 1003 Ink on paper 最小生成树 #

题目地址[1003 Ink on paper][]  
题意：在一个纸上给出坐标系，给出n个点坐标，每个点每过一秒就像四周扩散0.5（类似于墨水在纸上散开），问多久后所有的点会连接到一起？输出时间的平方。  
思路：求最小生成树，但是我们用的是kruskal算法，超时了，想换用prim算法，发现时间不够了，关键是我们都不太熟悉prim算法。。。不说了，补一篇最小生成树算法。[【算法与数据结构】——Dijkstra算法，最小生成树  
][Dijkstra_]  
AC代码：

/* **Author:skj **Time: **Function: */
    #include <bits/stdc++.h>
    #define ll long long
    #define INF 0x3f3f3f3f
    using namespace std;
    const int N = 5e3+5;
    const ll W = 2e18;//最大边权值
    ll lowcost[N];//表示生成树上以i为终点的边的最小权值,当lowcost[i]=0说明以i为终点的边的最小权值=0,也就是表示i点加入了MST
    int mst[N];//表示对应lowcost[i]的起点，即说明边<mst[i],i>是MST的一条边，当mst[i]=0表示起点i加入MST
    ll graph[N][N];
    pair<int,int> p[N];//点坐标
    
    ll weight(int a,int b)//计算a点和b点的距离当做权值
    { 
        return (1LL*p[a].first-p[b].first)*(1LL*p[a].first-p[b].first)+
        (p[a].second-1LL*p[b].second)*(p[a].second-1LL*p[b].second);
    }
    
    void solve()
    { 
        int n;
        scanf("%d",&n);
        for(int i = 1;i <= n;i++)
        { 
            scanf("%d",&p[i].first);
            scanf("%d",&p[i].second);
        }
    
        for(int i = 1;i <= n;i++)
        { 
            for(int j = i+1;j <= n;j++)
            { 
                ll w = weight(i,j);
                graph[i][j] = w;
                graph[j][i] = w;
            }
            lowcost[i] = W;
        }
        for(int i = 2;i <= n;i++)
        { 
            mst[i] = 1;
            lowcost[i] = graph[1][i];
        }
        mst[1] = 0;
        ll ma = 0;
        for(int i = 2;i <= n;i++)
        { 
            ll mi = W;
            int minid = 0;
            for(int j = 2;j <= n;j++)
            { 
                if(lowcost[j]<mi&&lowcost[j]!=0)
                { 
                    mi = lowcost[j];
                    minid = j;
                }
            }
            lowcost[minid] = 0;
            mst[minid] = 0;
            ma = max(mi,ma);
            for(int j = 2;j <= n;j++)
            { 
                if(lowcost[j] > graph[minid][j])
                { 
                    lowcost[j] = graph[minid][j];
                    mst[j] = minid;
                }
            }
        }
        printf("%lld\n",ma);
    }
    int main()
    { 
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
        int t;
        scanf("%d",&t);
        while(t--)
        { 
            solve();
        }
        return 0;
    }

# 1006 GCD Game 博弈论sg函数 #

题目地址[1006 GCD Game][]  
题意：给定一个序列，Alice和Bob轮流操作，在序列中选一个数 a i a\_i ai，任意选一个 1 ≤ x < a i 1 \\le x < a\_i 1≤x<ai，用 g c d ( a i , x ) gcd(a\_i,x) gcd(ai,x)，替换掉原来的 a i a\_i ai，直到有一个人无法进行操作，即为失败。  
思路：关键在于质数和合数，最后序列中的数全部变为1。 赛场上感觉应该将合数拆分为质数的乘积，求质数的个数，但是我们当时不知道怎么拆分。。。后来才知道在筛素数的过程中，可以记录合数的质因子数。  
这样这个问题就变成了换皮Nim，把每个数看成一堆石子，石子个数就是每个数的质因子个数。  
好吧，先补补博弈论和sg函数的东西。。。

#include <bits/stdc++.h>
    
    using namespace std;
    
    typedef long long ll;
    const int N = 1e7 + 5;
    int sg[N];
    int prime[N], cnt;
    bool vis[N];
    
    void getPrime()
    { 
      for (int i = 2; i <= N - 1; i++) { 
        if (!vis[i]) { 
          prime[cnt++] = i;
          sg[i] = 1;
        }
        for (int j = 0; j < cnt && i * prime[j] <= N - 1; j++) { 
          vis[i * prime[j]] = 1;
          sg[i * prime[j]] = sg[i] + sg[prime[j]];
          if (i % prime[j] == 0) break;
        }
      }
    }
    
    int main()
    { 
      int t;
      getPrime();
      scanf("%d", &t);
      while (t--) { 
        int n;
        int x = 0;
        scanf("%d", &n);
        for (int i = 0; i < n; i++) { 
          int tmp;
          scanf("%d", &tmp);
          x ^= sg[tmp];
        }
        if (x) { 
          printf("Alice\n");
        } else { 
          printf("Bob\n");
        }
      }
      return 0;
    }

# 1009 Singing Superstar AC自动机 #

题目地址[1009 Singing Superstar][]  
这个题目是队友做的，他说是AC自动机的模板题，AC自动机暂时也不是我的内容，至于为什么要把这个题目记录在这里，当然是水博客啦。  
AC代码：

#include <cstdio>
    #include <cstring>
    #include <queue>
    using namespace std;
    const int N = 1e5 + 5, M = 6 * 1e5 + 5;
    int n, ty[N], T, len, tr[M][26], cnt[N][2], ne[M], fail[M], last[N], vis[N]; //last保存上一次匹配的位置
    char s[N], sp[N][100];
    void add(int id) { 
        int p = 0;
        for (int i = 0; sp[id][i]; i++) { 
            int j = sp[id][i] - 'a';
            if (!tr[p][j]) tr[p][j] = ++len;
            p = tr[p][j];
        }
        if (!fail[p]) fail[p] = id;
        else { 
            vis[id] = fail[p];   //代表重复的串 那么直接用前面的id就行了。
        }
    }
    void build() { 
        queue<int> q;
        for (int j = 0; j < 26; j++) { 
            if (tr[0][j]) q.push(tr[0][j]);
        }
        while (!q.empty()) { 
            int p = q.front();
            q.pop();
            for (int j = 0; j < 26; j++) { 
                int c = tr[p][j];
                if (!c) tr[p][j] = tr[ne[p]][j];
                else { 
                    ne[c] = tr[ne[p]][j];
                    q.push(c);
                }
            }
        }
    
    }
    int main() { 
        int T;
        scanf("%d\n",&T);
        while(T--) { 
            scanf("%s%d", s, &n);
            memset(tr, 0, sizeof(tr));
            memset(ne, 0, sizeof(ne));
            memset(vis, 0, sizeof(vis));
            memset(fail, 0, sizeof(fail));
            memset(last, -1, sizeof(last));
            len = 0;
            memset(cnt, 0, sizeof(cnt));
            for (int i = 1; i <= n; i++) { 
                scanf("%s", sp[i]);
                ty[i]=1;
                add(i);
            }
            build();
            for (int i = 0, j = 0; s[i]; i++) { 
                int k = s[i] - 'a';
                j = tr[j][k];
                int t = j;
                while (t) { 
                    if (fail[t]) { 
                        cnt[fail[t]][0]++;
                        int cha = i - last[fail[t]] - strlen(sp[fail[t]]);
                        if (cha >= 0) cnt[fail[t]][1]++, last[fail[t]] = i;;
                    }
                    t = ne[t];
                }
            }
            for (int i = 1; i <= n; i++) { 
                if (!vis[i])printf("%d\n", cnt[i][ty[i]]);
                else printf("%d\n", cnt[vis[i]][ty[i]]);
            }
        }
        return 0;
    }

[2021_MINIEYE_8]: https://acm.hdu.edu.cn/search.php?field=problem&key=2021%A1%B0MINIEYE%B1%AD%A1%B1%D6%D0%B9%FA%B4%F3%D1%A7%C9%FA%CB%E3%B7%A8%C9%E8%BC%C6%B3%AC%BC%B6%C1%AA%C8%FC%A3%A88%A3%A9&source=1&searchmode=source
[2021_MINIEYE_8 1]: https://acm.hdu.edu.cn/contests/contest_show.php?cid=992
[1003 Ink on paper]: https://acm.hdu.edu.cn/showproblem.php?pid=7058
[Dijkstra_]: https://blog.csdn.net/qq_45488453/article/details/119668032
[1006 GCD Game]: https://acm.hdu.edu.cn/showproblem.php?pid=7061
[1009 Singing Superstar]: https://acm.hdu.edu.cn/showproblem.php?pid=7064