目录

---

?题目地址： ?

---

A.Chino with Geometry(简单证明)

这里我提供两种方法,来说明代码中的式子.(做题还是要动笔试一试的)

方案一:过A点向BC做垂线,垂足为F.我们要求的是:BD×BE

根据勾股定理:BD=BF-DF=sqrt(AB^2-AH^2)-sqrt(r^2-AH^2)

BF=sqrt(AB^2-AH^2)       DF=sqrt(r^2-AH^2)

BE=BF+EF=BF+DF=sqrt(AB^2-AH^2)+sqrt(r^2-AH^2)

综上所述:BD×BE=AB^2-r^2

方案二:既然是随机输入,那么我们可以尝试特殊情况,当直线与圆相切时:

D、E重合:BE×BD=AB^2-r^2

#include 
    
     using namespace std;typedef long long LL;const int Max_n=1e5+5;int main(){    ios::sync_with_stdio();    LL x0,y0,r,x1,y1,y2;    cin>>x0>>y0>>r>>x1>>y1>>y2;    cout<<(x1-x0)*(x1-x0)+(y1-y0)*(y1-y0)-r*r<
    

---

B.Chino with Repeater(简单计算,找规律)

原始：

printf("Hello, world!");

第一次：

printf("Hello, world!"); 2

第二次：

printf("Hello, world!");

printf("Hello, world!"); 4

第三次：

printf("Hello, world!");

printf("Hello, world!");

printf("Hello, world!");

printf("Hello, world!"); 8

第四次：

printf("Hello, world!");

printf("Hello, world!");

printf("Hello, world!");

printf("Hello, world!");

printf("Hello, world!");

printf("Hello, world!");

printf("Hello, world!");

printf("Hello, world!"); 16

#include
    
     using namespace std;typedef long long LL;const int Max_n=(int)1e3+10;int main(){    int n;    cin>>n;    if(n==2){        cout<
     
      <
      
       =n) break;        cnt++;    }    cout<
       
        <
       
      
     
    

---

D.Chino with Equation(卢卡斯定理模板)

我先来介绍解决组合数使用的方法：

1.n,m比较小时：C(n,m)=C(n-1,m)+C(n-1,m-1);

2.n,m比较大时：C(n,m)%mod=C(n%mod,m%mod)*C(n/mod,m/mod)%mod;(卢卡斯定理,不做证明)

接下来我们看题：

1.正整数解的个数我们可以抽象为：

有n个相同的球和m个相同的盒子，不允许盒子为空，那么有多少种放法？

我们先把n个球放成一排，我们的目的是把它分成m份，此时我们采用隔板法，n个球之间有n-1个空,

我们需要放置m-1个隔板才能将它分成m份，此时的结果就是：C(n-1,m-1)

2.非负整数解的个数我们可以抽象为：

有n个相同的球和m个相同的盒子，允许盒子为空，那么有多少种放法？

我们此时不能保证每一个盒子都有一个球，所以此时就不能使用隔板法，但是我们如果从外面拿来m个

球，保证每个盒子至少有一个球，那么我们把n+m个球摆成一排，那么我们要分成m份就是在n+m-1个

空中放置m-1个隔板，等到我们放置完了以后，分别从没一个盒子拿出来一个球，那么我们就分配好了。

此时的九个就是：C(n+m-1,m-1)

//卢卡斯定理模板#include 
    
     using namespace std;typedef long long LL;const int mod=1e9+7;const int Max_n=1e5+5;LL mul(LL a,LL b){    LL ans=0;    LL res=a;    while(b){        if(b&1) ans=(ans+res)%mod;        res=(res+res)%mod;        b>>=1;    }    return ans;}LL q_pow(LL a,LL b){    LL ans=1;    LL res=a%mod;    while(b){        if(b&1) ans=mul(res,ans);        res=mul(res,res);        b>>=1;    }    return ans%mod;}LL comb(int a,int b){//组合数原始公式    if(a
     
      a-b) b=a-b;    LL ca=1,cb=1;    for(int i=0;i
      
       >m>>n;    cout<
       
        <<" "<
        
         <
        
       
      
     
    

---

F.Chino with Expectation(期望+两点分布)

首先此题需要注意数据类型，输入的数组可能是double

下面我们来分析此题：

拿第一个样例来说：共有五种情况(1 2 3 4 5)  (1 3 3 4 5)  (1 2 4 4 5)  (1 2 3 4 5)  (1 2 3 4 5)

此时的期望：6/2×(2/5)+5/2×(3/5)    我们可以发现:没有加x时：题中公式的概率是：n-(r-l+1)  有x时：题中变形过的公式概率为：r-l+1

那么我们就可以得到期望的公式：ans=(x+sum[r]-sum[l-1])/(r-l+1)  ×  (r-l+1)/n  +  (sum[r]-sum[l-1] ) / (r-l+1) × (n-(r-l+1))/n

#include 
    
     using namespace std;typedef long long LL;const int mod=1e9+7;const int Max_n=1e5+5;double a[Max_n];int sum[Max_n];///注意数据类型int main(){    ios::sync_with_stdio(false);    int n,q;    scanf("%d%d",&n,&q);    for(int i=1;i<=n;i++){        scanf("%lf",&a[i]);        sum[i]=sum[i-1]+a[i];//前缀和    }    while(q--){        double x;        int l,r;        scanf("%lf%d%d",&x,&l,&r);        double res=sum[r]-sum[l-1];        int res1=r-l+1;        double ans=((x+res)*res1+res*(n-res1))*1.0/n/res1;        printf("%.6f\n",ans);    }    return 0;}
    

---

H. Chino with Ciste(bfs)

每次都按照某一个方向去走一条直线,先加进去的点就会先找到一个路去走当从

某个点走直线能够到达终点的时候,我们也就可以找到最小的转弯次数了.step表

示第几次被加进去的点,先加进去的点先处理,这样能够保证找到最小的转弯次数.

#include
    
     using namespace std;typedef long long LL;const int Max_n=(int)2e3+10;char a[Max_n][Max_n];int sx,sy,ex,ey,n,m,vis[Max_n][Max_n];int net[4][2]={-1,0,0,1,1,0,0,-1};struct Node{    int x,y,step;};bool judge(int x,int y){    if(x<0 || x>=n || y<0 || y>=m)        return false;    return true;}int bfs(){    queue
     
      q;    Node now;now.x=sx;now.y=sy;now.step=-1;    vis[sx][sy]=1;    q.push(now);    while(q.size()){        Node nt;        Node node=q.front();q.pop();        if(node.x==ex&&node.y==ey)            return node.step;        nt.step=node.step+1;        for(int k=0;k<4;k++){            nt.x=node.x+net[k][0];            nt.y=node.y+net[k][1];            while(judge(nt.x,nt.y)&&a[nt.x][nt.y]!='*'){                if(!vis[nt.x][nt.y]){//访问过的都是在某一个方向走过的                    vis[nt.x][nt.y]=1;                    q.push(nt);//未访问过代表要转弯                }//一直走到该方向无法再走                nt.x+=net[k][0];                nt.y+=net[k][1];            }        }    }    return -1;}int main(){    ios::sync_with_stdio(false);    cin>>n>>m;    for(int i=0;i
      
       >a[i];    for(int i=0;i