A.Chino with Geometry
Chino的數學很差，是以Cocoa非常擔心。這一天，Cocoa準備教Chino學習圓與直線的位置關系。
衆所周知，直線和圓有三種位置關系：相離、相切、相割，主要根據圓心到直線的距離來判定。 現在我們來看看作業吧：
圓A是以整點為圓心、正整數為半徑的圓，整點分别是圓外一點以及軸上的一點，形成一條圓的割線（也就是和圓有兩個交點）。現在Cocoa想要知道，的值是多少？
題目對于Chino來說太難啦，你能幫一幫Chino嗎？
輸入描述:
六個正整數x0, y0, r, x1, y1, y2
輸出描述:
題目要求的答案，精确到整數
示例1
輸入
2 2 1 3 1 2
輸出
1
題解：數學題，推了好久太浪費時間，太菜了…
過點A對直線BC作垂線于O，連接配接AE AD AB, 直角三角形AEO和直角三角形AOB兩組勾股定理聯立就能得出BD*BE =（x1-x0） * （x1-x0）+（y1-y0） * （y1-y0）-r * r
AC代碼：
#include<iostream>
using namespace std;
typedef long long ll;
int main()
{
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<<endl;
return 0;
}
B.Chino with Repeater
Chino的數學很差，是以Cocoa非常擔心。今天，Cocoa準備教Chino數數。
我們都知道人類的本質之一是複讀機，而複讀機就是複讀别人說過的話。
現在有下面這段程式： #include <stdio.h> // 包含标準庫的資訊
main() // 定義名為main的函數，它不接受參數值
{ // main函數的語句都被括在花括号中
printf(“Hello, world!”); // main函數調用庫函數printf以顯示字元串序列
} 顯然，它的功能是列印一行.
現在，Cocoa想要知道，如果一台複讀機每次可以複讀若幹行（但不超過已有的行數），那麼最少複讀幾次可以讓消息記錄達到行呢？
題目對Chino來說太難啦，你能幫一幫Chino嗎？
輸入描述:
一個正整數n
輸出描述:
題目中要求的答案
示例1
輸入
複制
9
輸出
4
說明
1→2→3→6→9
題解：水題，找規律，從大到小找，如果n為奇數 n=n/2+1 n為偶數 n=n/2 直到n=1結束，記錄次數就ok了。
AC代碼：
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
const int mmax=1e6+10;
int main()
{
ll n,k;
cin>>n;
for(int i=1;i<1000;i++)
{
if(n==1)
{
k=i-1;
break;
}
if(n%2==0)
n/=2;
else
n=n/2+1;
}
cout<<k<<endl;
return 0;
}
D.Chino with Equation
題目描述
Chino的數學很差，是以Cocoa非常擔心。今天，Cocoa要教Chino解不定方程。
衆所周知，不定方程的解有0個或者若幹個。
給出方程: X1+X2+…+Xm=n(1<=m<=n<=1e6)
Cocoa想知道這個不定方程的正整數解和非負整數解各有幾個。
題目對Chino來說太難啦，你能幫一幫Chino嗎？
輸入描述:
兩個正整數m, n
輸出描述:
題目要求的答案，即正整數解的個數和非負整數解的個數 。由于答案可能會很大，你隻需要輸出答案 mod(109 + 7) 即可。
示例1
輸入
4 7
輸出
20 120
題解：組合數問題，搞明白就好做了
正整數解（都>0）: m個位置，要求和=n， 他隻會有n-1個數組合（因為最小值是1，是以最大不可能是n），隻需要确定m-1個位置 剩餘的1個數自然就确定。是以正整數解為C（n-1，m-1）
非負整數解（都>=0）: m個位置可能是0，此時這個位置為空，這樣就有n+m-1個數組合（1~n 加上 m-1個空位子） 隻需要确定m-1個位置 剩餘的1個數自然就确定。是以正整數解為C（n+m-1，m-1）
思路明白了看怎麼解決，資料要2e6 求組合數有技巧，首先打個從1到2e6的階乘，
利用逆元定理求出最後的解。（因為同餘定理沒有除法，的需要計算他的逆元，利用費馬小定理，aa ^ (p-2)=1(mod p) gcd(a,p)=1 ）,主要計算a^(p-2)
組合數公式C（n,m）=n!/(m!(n-m)!)
AC代碼：
#include<iostream>
using namespace std;
typedef long long ll;
const int mmax=2000010;
const int mod=1e9+7;
ll mul[mmax];
void init()
{
mul[0]=1;
for(int i=1;i<=2000000;i++)
{
mul[i]=(mul[i-1]*i)%mod;
}
}
ll quick_mul(ll a,ll b)
{
ll temp=a%mod;
ll ans=1;
while(b)
{
if(b&1)
ans=(ans*temp)%mod;
temp=(temp*temp)%mod;
b>>=1;
}
return ans%mod;
}
ll ni(ll a, ll b)
{
return quick_mul(a,b-2)%mod;
}
ll c(ll n,ll m)
{
return (mul[n]*ni(mul[n-m]*mul[m]%mod,mod))%mod;
}
int main()
{
init();
ll m,n;
cin>>m>>n;
cout<<c(n-1,m-1)<<" "<<c(n+m-1,m-1)<<endl;
return 0;
}
F.Chino with Expectation
題目描述
Chino的數學很差，是以Cocoa非常擔心。這一天，Cocoa準備教Chino學習數學期望。衆所周知，數學期望就是所有可能的結果乘以機率,那麼我們可以說的期望
定義非常簡單，Chino也一下就學會了。現在是作業時間啦！
Cocoa在紙上寫下個正整數，接下來Cocoa會進行次詢問，每次詢問形如“x,l,r ”，表示如果Cocoa把數列中的某個數加上x以後的期望。
題目對于Chino來說太難啦，你能幫一幫Chino嗎？
輸入描述:
第一行是兩個正整數n, q；接下來一行是n個數ai，接下來q行每行三個數xi, li, ri，描述了一組詢問
輸出描述:
對于每組詢問，給出相應的回答。你的答案會被認為是正确的，當且僅當你的答案是a，标準答案是b，并且|a−b|max(1,b)≤10−6|a−b|max(1,b)≤10−6
示例1
輸入
5 3
1 2 3 4 5
1 2 3
2 1 4
4 3 5
輸出
2.700000
2.900000
4.800000
題解：從l到r的和用字首和表示，難點是那個數加x 。
分兩種情況讨論（P表示L，R 的期望）
- x加到非 L , R 區間，（非區間/總長度 ） * L,R的期望
-
x加到L , R 區間，（區間長度/總長度） * （L,R的期望 + x /區間長度）
把兩個加起來就是答案
AC代碼：
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const int mmax=1e6+10;
ll sum[mmax],a[mmax];
int main()
{
ll n,p;
scanf("%lld %lld",&n,&p);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
for(int i=1;i<=n;i++)
sum[i]=sum[i-1]+a[i];
for(int i=1;i<=p;i++)
{
ll x,l,r;
scanf("%lld %lld %lld",&x,&l,&r);
double ans=0,p1,p2;
double ans0=(sum[r]-sum[l-1])/(double)(r-l+1);
p1=(double)(r-l+1)/n;
p2=(double)(n-(r-l+1))/n;
ans=p2*ans0+p1*(ans0+((double)x/(r-l+1)));
//cout<<p2<<" "<<p1<<" "<<ans0<<endl;
printf("%.6lf\n",ans);
}
return 0;
}
![2021牛客暑期多校訓練營2.I Penguins BFS廣搜 簡單2021牛客暑期多校訓練營2.I Penguins BFS廣搜 簡單[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)