试题 A: 平方和

【问题描述】 ：

小明对数位中含有 2、0、1、9 的数字很感兴趣，在 1 到 40 中这样的数包 括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是 574，平方和是 14362。 注意，平方和是指将每个数分别平方后求和。
请问，在 1 到 2019 中，所有这样的数的平方和是多少？

思路：

只需要简单枚举就好。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long qq;
bool f(int x){
    while(x>0){
        int t=x%10;
        if(t==2||t==0||t==1||t==9)return 1;
        x/=10;
    }
    return 0;
}
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        qq ans=0;
        for(int i=1;i<=n;i++){
            if(f(i)==true) ans+=(qq)i*i;
        }
        printf("ans=%lld\n",ans);
    }
    return 0;
}

结果：

2658417853

试题 B: 数列求值

【问题描述】

给定数列 1, 1, 1, 3, 5, 9, 17, …，从第 4 项开始，每项都是前 3 项的和。求 第 20190324 项的最后 4 位数字。

思路：

类似于斐波那契数列的递推，也可以转成矩阵递推形式，用矩阵快速幂加速。

emmmmmmm… 可以，但没有必要~

至于只要求最后四位数字的问题，相当于求答案对10000取模。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long qq;
int n;
int main(){
    while(scanf("%d",&n)!=EOF){
        int a=1, b=1, c=1;
        for(int i=4;i<=n;i++){
            int temp= (a+b+c)%10000;
            a=b;
            b=c;
            c=temp;
        }
        printf("f(%d)=%d\n",n,c);
    }
    return 0;
}

结果：

4659

试题 C: 最大降雨量

【问题描述】

由于沙之国长年干旱，法师小明准备施展自己的一个神秘法术来求雨。 这个法术需要用到他手中的 49 张法术符，上面分别写着 1 至 49 这 49 个 数字。法术一共持续 7 周，每天小明都要使用一张法术符，法术符不能重复使 用。
每周，小明施展法术产生的能量为这周 7 张法术符上数字的中位数。法术 施展完 7 周后，求雨将获得成功，降雨量为 7 周能量的中位数。
由于干旱太久，小明希望这次求雨的降雨量尽可能大，请大最大值是多少？

思路：

这个题是留到了最后才做，纯口头分析了一下下，没写代码验证（也没太想好怎么写能比较快）。

（1）首先分成7组，每组7个数，那其中肯定有3个组的降雨量不管多小都对答案没影响，那肯定把最小的3*7=21个数字放到其中。

（2）剩下的四组，肯定每组的前3个数尽量平均，即：将剩下的最小的3*4个数字放进四个组。

（3）剩下的最小的数字肯定为中位数。

如图所示：

结果：

34

试题 D: 迷宫

【问题描述】

下图给出了一个迷宫的平面图，其中标记为 1 的为障碍，标记为 0 的为可 以通行的地方。

010000
000100
001001
110000

迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这 个它的上、下、左、右四个方向之一。
对于上面的迷宫，从入口开始，可以按DRRURRDDDR 的顺序通过迷宫， 一共 10 步。其中 D、U、L、R 分别表示向下、向上、向左、向右走。

对于下面这个更复杂的迷宫（30 行 50 列），请找出一种通过迷宫的方式， 其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。 请注意在字典序中D<L<R<U。（如果你把以下文字复制到文本文件中，请务 必检查复制的内容是否与文档中的一致。在试题目录下有一个文件 maze.txt， 内容与下面的文本相同）

01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000
11001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010
00111000001010100001100010000001000101001100001001
11000110100001110010001001010101010101010001101000
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001011101000
00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000

思路：

（1）首先01地图中找最短路，肯定选择广度优先级搜索（BFS）。

（2）然后需要路径，只需要在搜索过程中记录下每个节点由什么操作转换（或者记录前一个节点的二维坐标），之后再反向沿着路径找回去就知道了走法。

（3）最后还需要字典序最小，那么我们可以考虑方向数组的4个方向向量的顺序。想到的方法是，从右下角节点 T(n,m) 开始，向左上角S(1,1) 搜索找路径。同时维护好每个坐标点是如何由上一坐标点到达。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long qq;
const int maxn = 105;
const int mov[4][2]= { {1,0}, {0,-1}, {0,1}, {-1,0} };
const int inv_mov[4][2]= { {-1,0}, {0,1}, {0,-1}, {1,0} };
const char S[4]= {'U','R','L','D'};
struct state{
    int x,y,step;
    state(){};
    state(int x_, int y_, int step_){
        step= step_;
        x= x_;
        y= y_;
    }
};
int n, m, op[maxn][maxn], dis[maxn][maxn];
bool mp[maxn][maxn], vis[maxn][maxn];
void input(int nn, int mm){
    n=nn;   m=mm;
    char c[maxn]={0};
    for(int i=1;i<=n;i++){
        scanf("%s",c+1);
        for(int j=1;j<=m;j++){
            mp[i][j]=c[j]-'0';
        }
    }
}
void bfs(){
    memset(op,-1,sizeof(op));
    memset(vis,0,sizeof(vis));
    queue<state> q;
    q.push( state(n,m,0) );
    op[n][m]=-1;
    vis[n][m]=1;
    while(!q.empty()){
        state now= q.front();
        q.pop();
        for(int i=0;i<4;i++){
            state net= now;
            net.x+= mov[i][0];
            net.y+= mov[i][1];
            net.step++;
            if(net.x<=0||net.x>n||net.y<=0||net.y>m||mp[net.x][net.y]==true)continue;
            if(vis[net.x][net.y]==false || (dis[net.x][net.y]==net.step && op[net.x][net.y]>i) ){
                op[net.x][net.y]= i;
            }
            if(vis[net.x][net.y]==false){
                q.push(net);
                vis[net.x][net.y]=1;
            }
        }
    }
    /* for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ printf("%3d ",op[i][j]); } printf("\n"); }*/
}
void output(){
    int x=1, y=1;
    while(op[x][y]!=-1){
        printf("%c",S[op[x][y]]);
        int temp= op[x][y];
        x+= inv_mov[temp][0];
        y+= inv_mov[temp][1];
    }
}
int main(){
    input(30,50);
    bfs();
    output();
    return 0;
}

结果：

DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR

试题 E: RSA 解密

【问题描述】

RSA 是一种经典的加密算法。它的基本加密过程如下。

首先生成两个质数 $p,q$p,q，令 $n=p\cdot q$n=p⋅q，设 $d$d 与 $\left(p-1\right)\cdot \left(q-1\right)$(p−1)⋅(q−1) 互质，则可 找到 $e$e 使得 $d\cdot e$d⋅e 除 $\left(p-1\right)\cdot \left(q-1\right)$(p−1)⋅(q−1) 的余数为 $1$1。
$n,d,e$n,d,e 组成了私钥， $n,d$n,d 组成了公钥。

当使用公钥加密一个整数 $X$X 时（小于 $n$n），计算 $C=X^{d}mod\hspace{0.17em}\hspace{0.17em}n$C=Xdmodn，则 $C$C 是加 密后的密文。

当收到密文 $C$C 时，可使用私钥解开，计算公式为 $X=C^{e}mod\hspace{0.17em}\hspace{0.17em}n$X=Cemodn。

例如，当 $p=5,q=11,d=3$p=5,q=11,d=3 时， $n=55,e=27$n=55,e=27。
若加密数字 $24$24，得 $24^{3}mod\hspace{0.17em}\hspace{0.17em}55=19$243mod55=19。
解密数字 $19$19，得 $19^{27}mod\hspace{0.17em}\hspace{0.17em}55=24$1927mod55=24。

现在你知道公钥中 $n=1001733993063167141,d=212353$n=1001733993063167141,d=212353，同时你截获了 别人发送的密文 $C=20190324$C=20190324，请问，原文是多少？

思路：

（1）对 $n$n 因数分解可得到 $p,q$p,q 的值。

（2）设： $k=(p-1)\ast (q-1)$k=(p−1)∗(q−1) 。

因为： $d\ast e=1\left(mod\hspace{0.17em}\hspace{0.17em}k\right)$d∗e=1(modk)，所以： $e=\frac{1}{d}\left(mod\hspace{0.17em}\hspace{0.17em}k\right)$e=d1​(modk) 。

相当于求 $d$d 关于 $k$k 的逆元。即： $e=d^{\varphi \left(k\right)-1}\left(mod\hspace{0.17em}\hspace{0.17em}k\right)$e=dϕ(k)−1(modk)

（3）然后根据公式即可得到： $X=C^e\left(mod\hspace{0.17em}\hspace{0.17em}n\right)$X=Ce(modn)

（4）另外需要一些快速乘，快速幂 等优化技巧。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long qq;
qq fast_mul(qq x, qq y, qq p){
    qq ret=0;
    x%=p, y%=p;
    while(y>0){
        if(y&1){
            ret= (ret+x)%p;
        }
        y>>=1;
        x= (x+x)%p;
    }
    return ret;
}
qq fast_pow(qq x, qq k, qq p){
    qq ret=1;
    x%=p;
    while(k>0){
        if(k&1){
            ret= fast_mul(ret, x, p);
        }
        k>>=1;
        x= fast_mul(x, x, p);
    }
    return ret;
}
qq phi(qq n){
    qq ret= n;
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            ret= ret/i*(i-1);
            while(n%i==0) n/=i;
        }
    }
    if(n!=1){
        ret= ret/n*(n-1);
    }
    return ret;
}
qq get_p(qq n){
    for(qq i=2;i<=n;i++){
        if(n%i==0){
            return i;
        }
    }
}
int main(){
    qq n = (qq)1001733993063167141;
    qq d = 212353;
    qq C = 20190324;
    qq p,q,e,k;
    printf("n=%lld\n",n);
    p=get_p(n);
    q=n/p;
    printf("p=%lld, q=%lld\n",p,q);
    k=(p-1)*(q-1);
    printf("k=(p-1)*(q-1)=%lld\n",k);
    printf("phi(k)=%lld\n",phi(k));
    e=fast_pow(d,phi(k)-1,k);
    printf("e=d^(phi(k)-1)=%lld (mod k)\n",e);
    printf("d*e=%lld (mod k)\n",fast_mul(d,e,k));
    qq X=fast_pow(C,e,n);
    printf("X=C^e (mod n)= %lld\n",X);
    while(1)getchar();
    return 0;
}

运行截图：

结果：

579706994112328949

试题 F: 完全二叉树的权值

思路：

从根节点 DFS ，搜到每个节点就将它的值加到对应的层上，记录每层的数值和 即可。

注意一个坑点，有可能最大权值也为负数。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100052;
typedef long long int qq;
qq a[maxn], s[maxn];
int n;
void dfs(int x, int dep){
    if(x>n) return;
    s[dep]+=a[x];
    dfs(x<<1, dep+1);
    dfs(x<<1+1, dep+1);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    dfs(1,1);
    int ans=1;
    for(int i=2;i<maxn;i++){
        if(s[ans]<s[i])ans=i;
    }
    printf("%d\n",ans);
    return 0;
}

试题 G: 外卖店优先级

思路：

对于每个商店，分别记录其操作，再依次进行判断即可。可以用 vector 存储。

注意对于每个商店，其操作一定要小心，有可能添加到优先缓存之后，虽然接下来优先级下降，但是只有优先级小于等于3之后才会被移出。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100052;
typedef long long int qq;
vector<int>a[maxn];
int n,m,t;
bool f(int x){
    if(a[x].size()==0)return 0;
    bool ret=0;
    int now=2;
    for(int i=1;i<a[x].size();i++){
        now= max(0, now -(a[x][i]-a[x][i-1]-1) );
        if(now<=3) ret=0;
        now+=2;
        if(now>5) ret=1;
    }
    now= max(0, now -(t-a[x][a[x].size()-1]));
    if(now<=3) ret=0;
    return ret;
}
int main(){
    scanf("%d%d%d",&n,&m,&t);
    while(m--){
        int ts,id;
        scanf("%d%d",&ts,&id);
        a[id].push_back(ts);
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        if(f(i)==true)ans++;
    }
    printf("%d\n",ans);
    return 0;
}

试题 H: 修改数组

思路：

本来现场想的是二分+树状数组维护，时间复杂度： $O(n\ast \log n\ast \log n)$O(n∗logn∗logn)。

（1）设置 $vis$vis 数组， $vis\left[i\right]$vis[i] 表示数字 $i$i 是否在之前出现过。

（2）用树状数组维护 $vis$vis 数组的前缀和，记： s[x]=∑i=1i<=x​vis[i] 。

（3）对于每个数字，查询其是否出现过，如果未曾出现，则不改变其值，并且标记 $vis$vis数组。否则进行下面操作。

（4）目标找到最右没填的位置，那么我们发现，对于 $f\left(x\right)=x-s\left[x\right]$f(x)=x−s[x] ，是单调递增的，我们只需要找到最靠左边位置 $x’$x’ 满足 $f\left(x^{\prime }\right)$f(x′) 严格大于 $f(x) $ ，那么x‘就是第一个没有出现的数字。

（5）添加之后要记得在对应位置修改 $vis$vis 数组，维护好树状数组。

当时顺手还写了个暴力，用于解决小范围数据，省得写错了分都没了。

ps：然后队友出来后和我说可以用并查集，果然图论相关还是不熟。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100052;
const int maxm = 1000052;
typedef long long int qq;
int a[maxn], tr[maxm], n;
bool vis[maxn];
int lowbit(int x){
    return x&(-x);
}
void add(int x){
    while(x<maxm){
        tr[x]++;
        x+=lowbit(x);
    }
}
int ask(int x){
    int ret=0;
    while(x>0){
        ret+=tr[x];
        x-=lowbit(x);
    }
    return ret;
}
void input(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
}
void output(){
    for(int i=1;i<=n;i++){
        if(i!=1)printf(" ");
        printf("%d",a[i]);
    }
    printf("\n");
}
void work1(){
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++){
        while(vis[a[i]]==true) a[i]++;
        vis[a[i]]=true;
    }
}
void work2(){
    memset(vis,0,sizeof(vis));
    memset(tr,0,sizeof(tr));
    int now_max=0;
    for(int i=1;i<=n;i++){
        if(vis[a[i]]==true){
            int x=a[i]-ask(a[i]);
            int l=1, r=now_max+10;
            while(l<=r){
                int mid=(l+r)/2;
                if(mid-ask(mid)>x){
                    r=mid-1;
                }
                else{
                    l=mid+1;
                }
            }
            a[i]= r+1;
        }
        add(a[i]);
        vis[a[i]]=1;
        now_max= max(now_max, a[i]);
    }
}
int main(){
    input();
    if(n<=6000){
        work1();
    }
    else {
        work2();
    }
    output();
    return 0;
}

试题 I: 糖果

思路：

显然的状压dp ，顺便压缩一下空间。

$dp(i,j)$dp(i,j)表示前 $i$i 个数字组成j状态需要选择的最少糖果集合数。

$dp(i,j\mid a[i\left]\right)=min\left(dp\right(i-1,j\mid a\left[i\right]),dp(i-1,j)+1)$dp(i,j∣a[i])=min(dp(i−1,j∣a[i]),dp(i−1,j)+1)

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = (1<<20) +52;
const int inf = 9;
int a[505], n, m, k, dp[2][maxn];
int min(int a, int b, int c){
    return min( min(a,b), c );
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    int e=1<<m;
    //输入
    for(int i=1;i<=n;i++){
        a[i]=0;
        for(int j=0;j<k;j++){
            int temp;
            scanf("%d",&temp);
            a[i]= a[i]| 1<<(temp-1);
        }
    }
    //初始化
    for(int i=0;i<maxn;i++){
        dp[0][i]=dp[1][i]=inf;
    }
    dp[0][0]=0;
    //递推dp
    bool pos=1;
    for(int i=1;i<=n;i++,pos=!pos){
        for(int j=0;j<e;j++){
            dp[pos][j]=dp[!pos][j];
        }
        for(int j=0;j<e;j++){
            dp[pos][j|a[i]]= min(dp[pos][j|a[i]], dp[!pos][j|a[i]], dp[!pos][j]+1);
        }
    }
    //输出答案
    if(dp[!pos][e-1]==inf){
        printf("-1\n");
    }
    else  printf("%d\n",dp[!pos][e-1]);
    return 0;
}

试题 J: 组合数问题

思路：

不会，简单递推+维护区域前缀和，可以过前4组数据。

代码：

#include<bits/stdc++.h>
using namespace std;
#define modk(x) (((x)>=k)?((x)-k):(x))
const int maxn = 2005;
int c[maxn][maxn], n, m, k, T;
void init(){
    ///预处理C(i,j)
    c[0][0]=1;
    for(int i=1;i<maxn;i++){
        c[i][0]=1%k;
        for(int j=1;j<=i;j++){
            c[i][j]=modk(c[i-1][j]+c[i-1][j-1]);
        }
    }
    ///处理C(i,j)是否为k 的倍数
    for(int i=0;i<maxn;i++){
        for(int j=0;j<=i;j++){
            if(c[i][j]==0) c[i][j]=1;
            else c[i][j]=0;
        }
    }
    ///将二维数组C处理成区域前缀和
    for(int i=1;i<maxn;i++){
        int s=0;
        for(int j=0;j<maxn;j++){
            s+=c[i][j];
            c[i][j]=c[i-1][j]+s;
        }
    }
}
int main(){
    scanf("%d%d",&T,&k);
    init();
    while(T--){
        scanf("%d%d",&n,&m);
        printf("%d\n",c[n][m]);
    }
    return 0;
}