2019牛客暑期多校训练营（第五场）

左手的ㄟ右手 2021-10-26 18:24 372阅读 0赞

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

// 正式比赛我就A了一道水题，卡在B上，又卡在G上，最后去做立体几何又一直WA。等到队友过了一个G题的dp，然后集体自闭。

## A - digits 2 ##

题意：给定一个不超过100的正整数n，求一个不超过1e4位的能整除n且其数位和也整除n的数。

题解：直接输出n次n。

AC代码：略。

## B - generator 1 ##

题意：给定数列xn = a\*xn-1 + b\*xn-2，已知x1， x0， a，b， n， mod，求xn%mod。（ 1<=n<=10^(10^6) ）

题解：一看n这么大，就尝试求模mod的循环节，然后用矩阵快速幂求循环节以内即可。结果不熟悉模板调了很久样例都跑不出来。

直接用10进制的快速幂。官方题解说每位数要用2进制倍增计算，否则会T，我不信，A了。

AC代码：（注意n==1特判！！！pow()函数n==1返回单位矩阵是我自己弄错了）

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    typedef long long ll;
      
    ll x0, x1, a, b, mod;
    char n[1000100];
      
    struct mat {
        ll m[2][2];
        mat operator*(const mat& a) {
            mat b;
            b.m[0][0] = (m[0][0]*a.m[0][0] + m[0][1]*a.m[1][0])%mod;
            b.m[0][1] = (m[0][0]*a.m[0][1] + m[0][1]*a.m[1][1])%mod;
            b.m[1][0] = (m[1][0]*a.m[0][0] + m[1][1]*a.m[1][0])%mod;
            b.m[1][1] = (m[1][0]*a.m[0][1] + m[1][1]*a.m[1][1])%mod;
            return b;
        }
    };
    const mat I = {
         1, 0, 0, 1};
      
    mat pow() {
       // if(strlen(n)==1 && n[0]=='0') return I;  A^0 == I
          
        mat A = {a, b, 1, 0};
        mat res = I;
        for(int i=0;n[i];i++) {
            mat tmp = res*res;
            tmp = tmp*tmp;
            tmp = tmp*res;
            res = tmp*tmp;
             
            int t = n[i]-'0';
            tmp = A;
            mat tmp2 = I;
            while(t) {
                if(t&1) tmp2 = tmp2*tmp;
                tmp = tmp*tmp;
                t >>= 1;
            }
            res = res*tmp2;
        // 用上面的计算快一点点
        //    for(int k=1;k<=t;k++) {
        //        res = res*A;
        //    }
        }
        return res;
    }
      
    int main() {
        cin>>x0>>x1>>a>>b;
        scanf("%s", n);
        cin>>mod;
          
        mat m = pow();
        printf("%lld\n", (m.m[1][0]*x1 + m.m[1][1]*x0)%mod);
          
        return 0;
    }

## C - generator 2 ##

题意：给定 n, x0, a, b, p，数列由递推式 xi = a\*xi-1 + b 产生。有Q次询问，给定 v 求最小的 i 项使 xi = v % p;

思路：手算一下可得 xn = a^n\*x0 + b(1+a+...+a^(n-1)) = a^n + b(a^n - 1)/( a - 1)

即求解 a^n \* ( b / (a-1) + x0) = v + b / ( a - 1 ) % p

p 保证为素数，分别求逆元，问题变成了求解 a^x = b mod p 的裸题。

使用**BSGS算法**求对数，直接抄模板会T，需要改写一下（1. 增大baby step，减少查询复杂度 2. 并在同一组p下保留当前的map值）。

直接使用map会使复杂度乘上logn，手写map或采用unsorted\_map才能过。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<map>
    #include<cmath>
    using namespace std;
    typedef long long ll;
     
    ll n, x0, a, b, p;
     
    struct mymap {
        static const int N = (1<<22);
        int key[N], val[N];
     
        int query(int x) {
            int i = x&(N-1);
            while(key[i]!=-1 && key[i]!=x) i = (i+1)&(N-1);
            return val[i];
        }
     
        void update(int x, int v) {
            int i = x&(N-1);
            while(key[i]!=-1 && key[i]!=x) i = (i+1)&(N-1);
            key[i] = x, val[i] = v;
        }
     
        void clear() {
            memset(key, -1, sizeof(key));
            memset(val, -1, sizeof(key));
        }
    };
     
    ll pow(ll a, ll n, ll p) {
        ll res = 1;
        while(n) {
            if(n&1) res = res * a % p;
            a = a * a % p;
            n >>= 1;
        }
        return res;
    }
     
    // a^x = b (mod p)
    // 输入a, b, p返回 x
     
    inline ll BSGS(ll a, ll b, ll p) {             //  inline 会优化300ms
        static ll lasta = -1;
        static mymap mp;
        ll m = min(p/2, (ll)sqrt(p*1000));  // 直接采用sqrt(p)会TLE，增大baby step，减少查询
        ll v = 1;
        if(lasta!=a) {
            lasta = a;
            mp.clear();
            for(int i=0;i<m;i++) {
                if(mp.query(v)==-1)
                    mp.update(v, i);
                v = v * a % p;
            }
        }
     
        v = pow(a, p-1-m, p);
        for(ll i=0;i<p;i+=m) {  // giant step
            int qr = mp.query(b);
            if(qr!=-1)
                return i + qr;
            b = b * v % p;
        }
        return -1;
    }
     
     
    int main() {
        int T; cin>>T;
        while(T--) {
            scanf("%lld %lld %lld %lld %lld", &n, &x0, &a, &b, &p);
            int q; scanf("%d", &q);
            while(q--) {
                ll v;
                scanf("%lld", &v);
                if(v==x0) {
                    printf("0\n");
                    continue;
                } 
                if(a==0) {
                    if(v==b) printf("1\n");
                    else printf("-1\n");
                } else if(a==1) {
                    if(b==0) printf("-1\n");
                    ll invb = pow(b, p-2, p);
                    v = (v-x0 + p)%p;
                    ll ans = (v*invb)%p;
                    printf("%lld\n", ans<n?ans:-1);
                      
                } else {
                    ll ba_1 = b*pow(a-1, p-2, p) % p;
                    ll inv = pow(ba_1+x0, p-2, p);
                    ll ans = BSGS(a, (v+ba_1)*inv%p, p);
                    printf("%lld\n", ans<n?ans:-1);
      
                }
            }
              
        }
        return 0;
    }

## D - generator 3 ##

# #

## G - subsequence 1 ##

注意组合数C\[0\]\[0\]=1

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    typedef long long ll;
    const int maxn = 3010;
    const int mod = 998244353;
    
    ll dp[maxn];  // dp[j]表示前j个数都相等的方案数
    int C[maxn][maxn];
    char s[maxn], t[maxn];
    int n, m;
    
    void init() {
        for(int i=0;i<maxn;i++) {
            C[i][i] = C[i][0] = 1;
        }
        for(int i=2;i<maxn;i++) {
            for(int j=1;j<i;j++) {
                C[i][j] = C[i-1][j] + C[i-1][j-1];
                C[i][j] %= mod;
            }
        }
    }
    
    int main() {
        init();
        
        int T; cin>>T;
        while(T--) {
            scanf("%d %d", &n, &m);
            scanf("%s%s", s+1, t+1);
            ll ans = 0;
            memset(dp, 0, sizeof(dp)); dp[0] = 1;
            for(int i=1;i<=n;i++) {
                if(s[i]!='0') { // 长度大于|t|的子序列
                    for(int j=m;j<=n-i;j++) ans = (ans + C[n-i][j]) % mod;
                }
                
                // 长度等于|t|, 在第j个字符上大于t的子序列数目
                for(int j=1;j<=i&&j<=m;j++)
                    if(s[i]>t[j]) ans = (ans + C[n-i][m-j]*dp[j-1]) % mod;
                
                // 注意倒序处理, 是因为前状态推得后状态
                for(int j=min(i, m);j>=1;j--) {
                    if(s[i]==t[j]) dp[j] = (dp[j] + dp[j-1]) % mod;
                }
            }
            
            printf("%lld\n", ans);
        }
        return 0;
    }

## H - subsequence 2 ##

## I - three points 1 ##

题意：保证三边长度分别为a，b，c的三角形能放在长宽分别为w，h的矩形内，给出三角形的三点坐标。

题解：暴力枚举三角形三个端点是否放在原点，枚举三条边是否放在w和h边上。

WA代码：直接排序把最短边所对的顶点放在原点，然后尝试最长边在w和h边上。

AC代码：（注意精度！！！check函数)

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    const double eps = 1e-8;
    int w, h;
    struct P {
        double x, y;
    }ans[4];
      
    struct Edge {
        int l;
        int n1, n2;
    }e[4];
    double coss[4];
    bool check(double x, double y) { // 不写check直接与w，h比较就WA了
        if(x<-eps || y<-eps) return false;
        if(x>w+eps) return false;
        if(y>h+eps) return false;
        return true;
    }
    int main() {
        int t; cin>>t;
        while(t--) {
            cin>>w>>h>>e[1].l>>e[2].l>>e[3].l;
            e[1].n1 = 1; e[1].n2 = 2;
            e[2].n1 = 1; e[2].n2 = 3;
            e[3].n1 = 2; e[3].n2 = 3;
              
            coss[1] = (e[1].l*e[1].l+e[2].l*e[2].l - e[3].l*e[3].l + 0.0)/(2*e[1].l*e[2].l);
            coss[2] = (e[1].l*e[1].l+e[3].l*e[3].l - e[2].l*e[2].l + 0.0)/(2*e[1].l*e[3].l);
            coss[3] = (e[2].l*e[2].l+e[3].l*e[3].l - e[1].l*e[1].l + 0.0)/(2*e[2].l*e[3].l);
              
            bool f = false;
            for(int i=1;i<=3 && !f;i++) {  // 点i放在原点
                ans[i].x = ans[i].y = 0;
                  
                // 放在x轴方向上
                for(int j=1;j<=3 && !f;j++) { // 取线段j
                    if(i!=e[j].n1 && i!=e[j].n2) continue;
                      
                    int k = e[j].n1 + e[j].n2 - i; // 线段另一端点k
                    if(e[j].l<=w) {
                        ans[k].x = e[j].l;
                        ans[k].y = 0;
                          
                        double x = e[4-k].l*coss[i];
                        double y = e[4-k].l*sin(acos(coss[i]));
                        if(x>=0 && x<=w && y>=0 && y<=h) {
                            ans[6-i-k].x = x; ans[6-i-k].y = y;
                            f = true;
                        }
                          
                    } else {
                        ans[k].x = w;
                        ans[k].y = sqrt(e[j].l*e[j].l - w*w);
      
                        if(ans[k].y>h) continue;
      
                        double ang = acos(coss[i]) + acos(1.0*w/e[j].l);
                        double x = e[4-k].l*cos(ang);
                        double y = e[4-k].l*sin(ang);
                        if(check(x, y)) {
                            ans[6-i-k].x = x;
                            ans[6-i-k].y = y;
                            f = true;
                        }
                          
                    }
                }
                  
                // 放在y轴方向上
                for(int j=1;j<=3 && !f;j++) { // 取线段j
                    if(i!=e[j].n1 && i!=e[j].n2) continue;
                      
                    int k = e[j].n1 + e[j].n2 - i; // 线段另一端点k
                    if(e[j].l<=h) {
                        ans[k].x = 0;
                        ans[k].y = e[j].l;
                          
                        double y = e[4-k].l*coss[i];
                        double x = e[4-k].l*sin(acos(coss[i]));
                        if(x>=0 && x<=w && y>=0 && y<=h) {
                            ans[6-i-k].x = x;
                            ans[6-i-k].y = y;
                            f = true;
                        }
                          
                    } else {
                        ans[k].y = h;
                        ans[k].x = sqrt(e[j].l*e[j].l - h*h);
                        if(ans[k].x>w) continue;
      
                        double ang = acos(coss[i]) + acos(1.0*h/e[j].l);
                        double y = e[4-k].l*cos(ang);
                        double x = e[4-k].l*sin(ang);
                        if(check(x, y)) {
                            ans[6-i-k].x = x;
                            ans[6-i-k].y = y;
                            f = true;
                        }
                          
                    }
                }
            }
            for(int i=1;i<=3;i++) {
                printf("%.12lf %.12lf%c", ans[i].x, ans[i].y, i==3?'\n':' ');
            }
        }
        return 0;
    }

--------------------

（未完待补。。。）

转载于:https://www.cnblogs.com/izcat/p/11285915.html

[https_ac.nowcoder.com_acm_contest_885_question]: https://ac.nowcoder.com/acm/contest/885#question
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211026/968dc9d8a5d44ea1a67ced12ad57926c.png