暑假N天乐【比赛篇】 —— 2019牛客暑期多校训练营（第五场）

àì夳堔傛蜴生んèń 2021-10-26 20:30 227阅读 0赞

以下题解包括：\\(A \\ \\ \\ B \\ \\ \\ G \\ \\ \\ H \\ \\ \\ I\\)

**比赛地址：** [https://ac.nowcoder.com/acm/contest/885\#question][https_ac.nowcoder.com_acm_contest_885_question]

# 【A】 digits 2 思维 #

每次输入一个 \\(n\\)，要求输出一个数 \\(x\\) 使得 \\(x \\% n == 0\\) 且 \\(x\\) 的每一位数之和也能整除 \\(n\\)。

思维题，输出 \\(n\\) 次 \\(n\\) 即可。

# 【B】 generator 1 十进制矩阵快速幂 #

给定一个类似斐波那契的等式：\\(x\_i = a\*x\_\{i-1\} + b\*x\_\{i-2\}\\)，其中 \\(x\_0,x\_1,a,b\\) 均给定。输入一个 \\(n\\)，输出 \\(x\_n \\% mod\\)。【\\(1 \\leq n \\leq 10^\{10^6\} \\ \\ 10^9 \\leq mod \\leq2\*10^9\\)】。

比赛时候一直想着欧拉降幂，然后发现好像矩阵有点问题，没意识到十进制矩阵快速幂的解法，然后 gg。

这题队友补了，我就偷了他的代码。

#include <bits/stdc++.h>
    typedef long long LL;
    using namespace std;
    const int MAXN = 1e6+5;
    const int inf = 0x3f3f3f3f;
    ///十进制快速幂 + 二进制优化
     
    struct Matrix{
        LL m[2][2];
    }E;
    char s[MAXN];
    LL mod;
     
    Matrix mmul(Matrix a, Matrix b) {
        Matrix ans;
        memset(ans.m, 0, sizeof(ans));
        for(int i = 0; i < 2; ++i) {
            for(int j = 0; j < 2; ++j) {
                for(int k = 0; k < 2; ++k) {
                    ans.m[i][j] += a.m[i][k] * b.m[k][j];
                    ans.m[i][j] %= mod;
                }
            }
        }
        return ans;
    }
     
    Matrix fpow(Matrix a, int b) {
        Matrix ans = E;
        while(b) {
            if(b & 1)   ans = mmul(ans, a);
            a = mmul(a, a);
            b /= 2;
        }
        return ans;
    }
     
    int main() {
        int T;
        LL x0, x1, a, b;
        scanf("%lld%lld%lld%lld%s%lld", &x0, &x1, &a, &b, s, &mod);
        Matrix tmp;
        tmp.m[1][1] = a, tmp.m[1][0] = b;
        tmp.m[0][0] = E.m[0][1] = E.m[1][0] = 0;
        tmp.m[0][1] = E.m[0][0] = E.m[1][1] = 1;
     
        Matrix ans = E;
        for(int i = 0; s[i]; ++i) {
            ans = mmul(fpow(ans, 10), fpow(tmp, s[i]-'0'));
        }
     
        printf("%lld\n", (ans.m[0][0] * x0 % mod + ans.m[0][1] * x1 % mod)%mod);
        return 0;
    }

# 【G】 subsequence 1 动态规划 #

给定长度为 \\(n\\) 的字符串 \\(s\\) 和长度为 \\(m\\) 的字符串 \\(t\\)（均没有前导零）。输出字符串 \\(s\\) 中有多少**子序列**（**无前导零**）是大于字符串 \\(t\\) 的，答案对 998244353 取模。

分成两段处理，子序列长度大于 \\(m\\) 时，只要没有前导零就能让 \\(ans\\) 增大，此时的增长就是组合数；恰好等于 \\(m\\) 时，需要进行 \\(dp\\)，\\(dp\[i\]\[j\]\\) 表示 “在 s 串的 i 位置，所选子序列长度为 j ”。**具体处理看代码，感谢队友的技术支持。**

# 【H】 subsequence 2 拓扑排序 #

> 本来讲道理应该是秒杀的，然后题读错了，没看到只能用前 m 个和输入 m(m-1)/2 次，硬是 WA 到死，赛后秒 A。

需要构造一个长度为 \\(n\\) 且只由字母顺序前 \\(m\\) 个构成的字符串，其满足给定的 \\(m(m-1)/2\\) 个限制条件。对于每个限制条件，确定两个字母，然后给定它们的总数，之后输入它们的相对位置。最后输出构造完成的字符串，不存在输出 -1。

对每一次的限制条件来说，对其中的每个字符和其后一个建边，我是采用：\\(a-\[0,9999\] \\ \\ \\ b-\[10000,19999\] ······ \\ \\ \\ z-\[250000,259999\]\\) 的标记方式。然后跑一次拓扑排序即可。

代码极丑，是比赛的时候疯狂魔改的成果，懒得重构了，将就看看就行。

#include <map>
    #include <set>
    #include <list>
    #include <cmath>
    #include <ctime>
    #include <deque>
    #include <stack>
    #include <queue>
    #include <bitset>
    #include <cctype>
    #include <cstdio>
    #include <vector>
    #include <string>
    #include <cstdlib>
    #include <cstring>
    #include <fstream>
    #include <iomanip>
    #include <numeric>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull;
    const double PI = acos(-1.0);
    const double eps = 1e-6;
    const int inf = 0x3f3f3f3f;
    const int mod = 1e9 + 7;
    
    const int maxn = 1e4+5;
    
    char str[55][maxn];
    int cnt[30];
    int head[50*maxn], in[50*maxn];
    char ans[50*maxn];
    int vis[30];
    int tot;
    int pw[30];
    int sum;
    int n, m;
    
    struct node {
        int to, nxt;
    }edge[maxn*55];
    
    void addedge(int u, int v) {
        edge[tot].to = v;
        edge[tot].nxt = head[u];
        head[u] = tot++;
        in[v] ++;
    }
    
    int Topo() {
        queue<int> q;
        for(int i = 1; i <= m; i++) {
            int x = pw[i];
            if(in[x] == 0 && vis[i] == 1) {
                // cout << x << endl;
                q.push(x);
            }
        }
        int cnt_ = 0;
        while(!q.empty()) {
            int u = q.front();
            q.pop();
            for(int i = 1; i <= m; i++) {
                if(u - pw[i] < 10000) {
                    ans[cnt_++] = 'a' + i - 1;
                    break;
                }
            }
            for(int i = head[u]; ~i; i = edge[i].nxt) {
                int v = edge[i].to;
                in[v] --;
                int temp = 0;
                for(int j = 1; j <= m; j++) {
                    if(v - pw[j] < 10000) {
                        temp = j;
                        break;
                    }
                }
                if(in[v] == 0 && vis[temp] == 1) {
                    q.push(v);
                }
            }
        }
        return cnt_;
    }
    
    void qm() {
        pw[1] = 0;
        for(int i = 2; i <= 28; i++) {
            pw[i] = pw[i-1] + 10000;
        }
    }
    
    int main() {
        while(~scanf("%d%d", &n, &m)) {
            qm();
            sum = 0;
            tot = 0;
            memset(edge, 0, sizeof(edge));
            memset(cnt, 0, sizeof(cnt));
            memset(in, 0, sizeof(in));
            memset(head, -1, sizeof(head));
            memset(vis, 0, sizeof(vis));
            int flag = 0;
            for(int i = 1; i <= (m-1)*m/2; i++) {
                int x;
                char s[10];
                scanf("%s%d", s, &x);
                getchar();
                gets(str[i]);
                int f1 = s[0] - 'a' + 1;
                int f2 = s[1] - 'a' + 1;
                int c1 = 0, c2 = 0;
                cnt[f1] = 0;
                cnt[f2] = 0;
                for(int j = 0; j < x; j++) {
                    int id = str[i][j] - 'a' + 1;
                    cnt[id] ++;
                    vis[id] = 1;
                }
                if(cnt[f1] == 0) {
                    vis[f1] = -1;
                }
                if(cnt[f2] == 0) {
                    vis[f2] = -1;
                }
                for(int j = 1; j < x; j++) {
                    int id1 = str[i][j-1] - 'a' + 1;
                    int id2 = str[i][j] - 'a' + 1;
                    // cout << id1 << "  " << id2 << endl;
                    int zzz1, zzz2;
                    if(id1 == f1) {
                        zzz1 = c1;
                        c1++;
                    }
                    else {
                        zzz1 = c2;
                        c2++;
                    }
                    if(id2 == f2) {
                        zzz2 = c2;
                        c2++;
                    }
                    else {
                        zzz2 = c1;
                        c1++;
                    }
                    addedge(zzz1+pw[id1], zzz2+pw[id2]);
                    if(id2 == f1) {
                        c1--;
                    }
                    else {
                        c2--;
                    }                
                }            
            }
            if(flag == 1) {
                printf("-1\n");
                continue;
            }
            for(int i = 1; i <= m; i++) {
                sum = sum + cnt[i];
            }
            // printf("%d\n", sum);
            int res = Topo();
            // cout << res << endl;
            if(res < sum || res > n || sum > n) {
                printf("-1\n");
            }
            else {
                int mo = -1;
                for(int i = 1; i <= m; i++) {
                    if(vis[i] == 0) {
                        mo = i;
                        break;
                    }
                }
                if(mo == -1 && res < n) {
                    printf("-1\n");
                    continue;
                }            
                for(int i = 0; i < res; i++) {
                    printf("%c", ans[i]);
                }
                for(int i = res; i < n; i++) {
                    printf("%c", 'a'+mo-1);
                }
                printf("\n");
            }   
        }
        return 0;
    }

# 【I】 three points 1 数学 #

> 比赛时候给了队友一个假算法：固定一个点在原点，选**最长边**一段固定在原点，然后从对角线往下“放”，直到另一端接触到矩形的边，然后通过这两个点确定第三个点（两圆相交的交点），然后在确定 x、y、z三点。事实证明是假算法，虽然我还没想明白为什么不行...

给定一个左下角为 \\((0,0)\\)，右上角为 \\((w,h)\\) 的矩形，要在这个矩形里找到三点 \\(X、Y、Z\\)，使这三点满足：\\(dis(X,Y) = a \\ \\ \\ dis(X,Z) = b \\ \\ \\ dis(Y,Z) = c\\)，输出这三点的坐标（按照顺序），保证存在。

参考：[https://blog.csdn.net/birdmanqin/article/details/98314514][https_blog.csdn.net_birdmanqin_article_details_98314514]

最优解就是把两个点固定在边上，其中一个固定在原点，另一个根据距离固定在边。这样的话，留出的空间最大，也最有可能放下第3个点。一共6种情况，挨个试一下，肯定能找到一个。【原来是要一个个试过去...】

转载于:https://www.cnblogs.com/Decray/p/11311369.html

[https_ac.nowcoder.com_acm_contest_885_question]: https://ac.nowcoder.com/acm/contest/885#question
[https_blog.csdn.net_birdmanqin_article_details_98314514]: https://blog.csdn.net/birdmanqin/article/details/98314514