P8678题解

· · 题解

题目传送门

A 平方和。

我们可以直接从 1 \sim 2019 一个一个枚举。枚举一个数时要首先数位分离，如果这个数字某一位是 2 或 0 或 1 或 9，则把答案加上这个数的平方。

题目核心代码：

    while(n){
        if(n%10==2||n%10==0||n%10==1||n%10==9){
            sum+=a*a;
        }
                n/=10;
    }

最终答案。

2658417853

B 数列求值。

直接按题意模拟即可。

核心代码：

    int a, b, c, d;
    a = b = 1;
    c = 3;
    for(int i = 4; i < 20190324; i++) {
        d = (a + b + c) % 10000;
        a = b;
        b = c;
        c = d;
    }

最终答案。

4659

C 最大降雨量

为了方便理解，假设每一周都是递增，且每一周的中位数都是递增。

要找中位数的中位数，那么必须红色区域（要求的）要小于绿色区域。而每行的绿色区域要小于同一行的黄色区域。因为红色区域是在这 16 个格子中最小的一个，根据贪心策略，答案就是 49-16+1=34。

D 迷宫

思路： 直接 bfs 搜一遍。

核心代码：

   while(!q.empty()) {
        node now = q.front();
        q.pop();
        for(int k = 0; k < 4; k++) {
            int x = now.x + delta[k][0], y = now.y + delta[k][1];
            if(x < 0 || y < 0 || x >= n || y >= m
                    || vis[x][y] || map[x][y])
                continue;
            vis[x][y] = 1, way[x][y] = k;
            node tmp = {x, y};
            q.push(tmp);
        }
    }
    int x = n - 1, y = m - 1, num = 0;
    while(x != 0 || y != 0) {
        int k = way[x][y];
        ans[num++] = cc[k];
        x -= delta[k][0], y -= delta[k][1];
    }
    num--;
    do {
        cout << ans[num];
    } while(num--);

答案：

DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR

E RSA 解密

核心代码：

void getPrime(int n) {
    for(int i=2; i<=n; ++i) {
        if(!notPrime[i]) sushu[cnt++] = i;
        for(int j=0; j<cnt&&1ll*i*sushu[j]<=n; ++j) {
            notPrime[i*sushu[j]] = true;
            if(i%sushu[j]==0) break;
        }
    }
    for(int i=0; i<20; ++i) cout<<sushu[i]<<" ";
    cout<<endl;
}
void fenjie(LL x) {
    cout<<x<<" = 1";
    for(int i=0; i<cnt&&sushu[i]<=x/sushu[i]; ++i) {
        while(x%sushu[i]==0) {
            cout<<" * "<<sushu[i];
            x /= sushu[i];
        }
    }
    if(x>1) cout<<" * "<<x;
    cout<<endl;
}
void BF(LL x) {
    cout<<x<<" = ";
    for(LL i=1e8+1; i<x; i+=2) {
        if(x%i==0)
            cout<<i<<" * ",x/=i;
    }
    cout<<x<<endl;
}
void exgcd(LL a,LL b,LL &d,LL &x,LL &y) {
    if(b==0) {
        d = a;
        x = 1;
        y = 0;
        return;
    }
    exgcd(b,a%b,d,y,x);
    y -= (a/b)*x;
}
LL rev(LL t,LL m) {
    LL d,x,y;
    exgcd(t,m,d,x,y);
    return (x%m+m)%m;
}
LL fast_product(LL a,LL b,LL mod) {
    LL ans = 0;
    while(b) {
        if(b&1) ans = (ans+a)%mod;
        a = (a+a)%mod;
        b>>=1;
    }
    return ans;
}
LL fast_pow(LL a,LL b,LL mod) {
    LL ans = 1;
    while(b) {
        if(b&1) ans = fast_product(ans,a,mod);
        a = fast_product(a,a,mod);
        b>>=1;
    }
    return ans;
}
int main() {

    BF(n);
    LL y = (p-1)*(q-1);
    LL e = rev(d,y);
    LL answer = fast_pow(c,e,n);

答案：

579706994112328949

最终代码

#include<iostream>
using namespace std;
int main() {
    string ans [] = {
        "2658417853",
        "4659", 
        "34", 
        "DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR", 
        "579706994112328949", 
    };
    char T;
    cin >> T;
    cout << ans[T - 'A'] << endl;
    return 0;
}

直接把答案套进题目中的代码。 收工。