前段时间的考试试题

时间：2022-07-11 15:25:18

有趣的序列

洛谷链接
这一道题是一道卡特兰数的题，但是因为数据量以及要进行模运算的原因，要采用我先前博客中写到的通项式。当然因为不可以直接算阶乘，因此采取分解阶乘的方法转换成乘法。

Code

#include<bits/stdc++.h>
#define maxn 1000002
#define Int64 long long
using namespace std;
int primes[2*maxn];
int sum[2*maxn];
bool isp[2*maxn];
int newp=0;
void Eular_Sieve(){
    for(int i=2;i<2*maxn;i++){
        if(!isp[i]){
            primes[++newp]=i;
        }
        for(int j=1;j<=newp&&primes[j]*i<2*maxn;j++){
            isp[primes[j]*i]=true;
            if(!(i%primes[j]))break;
        }
    }
    return;
}
Int64 qkpow(int a,int b,int p){
    //a的b次方mod p 
    if(b==1)return a;
    if(b%2){
        Int64 t=qkpow(a,b/2,p);
        t=t*t%p;
        t=t*a%p;
        return t;
    }
    else {
        Int64 t=qkpow(a,b/2,p);
        t=t*t%p;
        return t;
    }
}
int n,p;
int main(){
    
    scanf("%d%d",&n,&p);
    Eular_Sieve();
    for(int i=1;i<=newp;i++){
        Int64 t=primes[i];
        Int64 cnt1=0,cnt2=0,cnt3=0;
        while(t<=2*n){
            cnt1+=(2*n/t);cnt2+=((n+1)/t);cnt3+=(n/t);
            t*=primes[i];
        }
        sum[i]=cnt1-cnt2-cnt3;
    }
    Int64 ans=1;
    for(int i=1;i<=newp;i++){
        if(sum[i]){
            (ans*=qkpow(primes[i],sum[i],p))%=p;
        }
    }
    printf("%lld",ans);
    return 0;
    
}

打气球

这道题我就不给网址了，yzoj上面最后一页找

题目描述

Descrition

周末何老板到磁器口游玩。街边有小贩在组织一种打气球游戏，何老板很感兴趣。

店家立了一块布，布上画了N*N的方格，有的方格里挂上了气球，有的没有。

游戏规则如下：

第1步.观察。如果每一行都至少有一个方格没有气球，并且每一列都至少有一个方格没有气球，游戏结束。否则进行第2步。

第2步.抛骰子。店家拿出一个特制的骰子，该骰子有N个面，上面依次有1到N这N 个数字。玩家先后抛两次骰子，设第一次抛出的数字为x，设第二次抛出的数字为y (注：抛出的数字是随机的)。

第3步.打气球。若坐标为(x,y)的格子里有气球，玩家必须将其打爆。子弹1块钱一发。

如果该格子没有气球，忽略该格子，玩家不用开枪，但玩家也需要支付给店家1块钱。

第4步.继续。执行第1步。

何老板是个神枪手，他能做到百发百中。他想你帮他算算，对于当前给出的这局游戏，预计要花多少钱才能结束。

Input

第一行，两个整数N和M，N表示方格的尺寸,M表示游戏开始时，有M个格子里是没有气球的。 接下来M行，每行两个整数x,y,表示坐标为x,y的格子里没有气球。

Output

一行，一个实数，完成游戏预计花费，保留2个小数位。

Sample Input

5 2 
2 3 
4 1

Sample Output

11.77

如果你想看更多的样例输出，可以去WYX大佬的博客

分析

这一道题啊，实际上啊，就是一道期望的题，如果你点开了上面的那一个链接，多半也看见了YB说的话了吧，那么接下来要做的事情就是找出递归的关系
首先，我们都知道每一个格子概率为1/(n*n)
我们设有r行已经打掉，c列已经打掉，函数为f[r][c]=......
那么分类讨论
1.如果说没有抽到有气球的地方，那么就是他自己乘上没有气球的地方的概率
2.如果说打掉的地方只能消除行，那么就是乘上f[r-1][c]以及这些地方的概率，只能消除列同理
3.如果可以同时消去的话，那么就可以类比上面的，写出式子来。
4.当然最后你应该加上1，因为每打一次收费1

式子和化简如下
\[ f[r][c]=\\\\ \frac{f[r-1][c]\times r(n-c)+f[r][c-1]\times c(n-r)+f[r-1][c-1]\times r\times c+f[r][c]\times(n-r)(n-c)+n^2}{n^2(n-r)(n-c)} \]
好了，既然已经知道了式子，那么就可以比较容易的做出来了，至于边界，那你也可以自己推出来，你可以选择两种方法，dfs ordp
我的代码里面把dfs的注释掉了

Code

#include<bits/stdc++.h>
#define maxn 2003
using namespace std;
double f[maxn][maxn];
bool row[maxn],col[maxn];//行 列 
int n,m;
double dfs(int r,int c){
    double ans=0;
    if(!r&&!c)return 0;
    if(f[r][c]!=-1)return f[r][c];
    if(r)ans+=dfs(r-1,c)*r*(n-c);
    if(c)ans+=dfs(r,c-1)*c*(n-r);
    if(r&&c)ans+=dfs(r-1,c-1)*r*c;
    return f[r][c]=(double)(ans+n*n)/(n*(c+r)-c*r);
}
int main(){
    
    scanf("%d%d",&n,&m);
    int r=n,c=n;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        if(!row[x])r--,row[x]=true;
        if(!col[y])c--,col[y]=true;
    }
    /*for(int i=0;i<=r;i++){
        for(int j=0;j<=c;j++)f[i][j]=-1;
    }
    dfs(r,c);*/
    for(int i=1;i<=n;i++){
        f[i][0]=f[i-1][0]+n/(i+0.0);
        f[0][i]=f[0][i-1]+n/(i+0.0);
    }
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            double tmp=f[i-1][j]*i*(n-j)+f[i][j-1]*(n-i)*j+f[i-1][j-1]*i*j+n*n;
            f[i][j]=tmp/(n*(i+j)-i*j);
        }
    }
    printf("%.2lf",f[r][c]);
    return 0;
}

还有一道题，不过比较水，居然用暴力枚举就可以做出来了，早知道我当时就直接枚举了，题目与韩信点兵类似

标签：

相关文章