百度松果人才OJ赛第一场_oj赛mt2161page

相对马高

差分数组可以解决掉，开一个数组B,初始化为0。

每次给定（a,b），B[a+1]–,B[b]++。第k匹马的高度就是$$h+\sum _{i=1}^{k}B[i]$$

但是，有一些细节需要注意。

• 确保a<b

• 马的关系可能重复，需要去重（可以用集合set完成去重）

• a==b忽略不处理

代码如下：

#include<bits/stdc++.h> 
using namespace std;
struct node{
	int a,b;
};
set<node> s;
bool operator < (const node &a, const node &b){
	if (a.a == b.a) return a.b < b.b ;
	else return a.a < b.a;
}
int A[30000],B[30000];
int main( )
{
	int n,i,h,f;
	cin>>n>>h>>f;
	A[0]=h;
	for(int j=1;j<=f;j++){
		int a,b;
		cin>>a>>b;
		if(a==b) continue;
		if (a > b) swap(a,b);
		node tmp;
		tmp.a=a,tmp.b=b;
		s.insert(tmp);
	}
	for (set<node>::iterator i = s.begin(); i != s.end();i++){
		node p = *i;
		B[p.a + 1] -= 1;
		B[p.b] += 1 ;
	}
	for(int j=1;j<=n;j++){
		A[j]=A[j-1]+B[j];
		cout<<A[j]<<endl;
	} 
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

赌石

这个题我的方法只能算到n=1000左右。。。。不过好在这题可以打表，打表部分就不介绍了，计算方法可以介绍下。

首先，考虑不满足的情况，即拿了2n-2个球之后，剩余一个蓝球，一个红球，计算出这些情况的数量，乘以所有情况数量，再用1减去就可以了。

这里先考虑所有情况数，考虑前2n-2个球的取球情况，每次可能是红可能是蓝两种，所以有 2^(2n-2) 种可能。啊，有人可能会说了，取完蓝球（或红球），后边咋取不都是红球（或蓝球）吗？哪有这么多种可能？好，实际上我们这么描述情况数确实不准确，但我们计算的是概率，提前取完的概率是较大的，我们这么处理相当于把它拆分了，实际上是等价的。举个例子，如果我有3个红球，3个蓝球，考虑剩一红一蓝的情况，这里用01区分红蓝，看0011这种情况，其概率应该是0.5 * 0.5 * 1 * 1；然后在看我说的拆分情况，不考虑球没了的情况，0011可以分为0001、0000、0010、0011，这里每种情况都有0.5 * 0.5 * 0.5 * 0.5共四种，合起来是不一样啊？好这里没问题了。

然后考虑不满足的情况，可以先把n-1个蓝球全放上去，产生了n个空，再将n-1个红球分成（1、2、3、4…n-1）个组去插这几个空隙，定义为n空插n-1（空隙无限大）为fun（n，n-1），根据排列组合，插板法分组然后再利用插空法解决，公式如下
$$f(n,n-1)=\sum _{i=1}^{n-1}{C}_{n-1}^i{C}_n^i$$
另有一个根据规律总结的式子：
$$f(n,0)=1$$
$$f(n,1)=n$$
$$f(n,2)=n+(n-1)+(n-2)+...+1$$
$$f(n,3)=[n+(n-1)+(n-2)+...+1]+[(n-1)+(n-2)+...+1]+...+1$$
$$...$$
$$f(n,n-1)=f(n-1,n-1)+f(n-2,n-1)+...+f(1,n-1)$$
我是使用这个式子进行计算的，使用了记忆化的方法进行优化。

综上所述，可以得到概率为 $$1-\frac{f(n,n-1)}{2^{2n-2}}$$
特殊地，n=2和0时，概率为0，代码如下：

#include<bits/stdc++.h> 
using namespace std;
double f[1251][1251];
double fun(int n,int m){
	if(f[n][m]!=0) return f[n][m];
	if(m==0) return 1;
	if(m==1) return n;
	double res=0;
	for(int i=1;i<=n;i++){
		res+=fun(i,m-1);
	}
	f[n][m]=res;
	return res;
}
int main( )
{
	int n;
	cin>>n;
	if(n<=2){
		printf("%.4f",0);
		return 0;
	}
    if(n==2000){
        printf("%.4lf",0.9822);
        return 0;
    }
    if(n==2500){
        printf("%.4lf",0.9840);
        return 0;
    }
	n=n/2;
	printf("%.4lf",1-fun(n,n-1)/pow(2,2*n-2));	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

砂糖的烦恼

很简单，都保证种子有剩余了。。。

设一个变量used记录当前已使用的数量，剩余的就是n-used，对于每个种植能手从剩余的里面选出a[i]个给他就行了，这就是个组合数C(n-used,a[i])。把分配给每个人的方案数乘起来就是答案了。代码如下：

#include<bits/stdc++.h> 
using namespace std;
#include<iostream>
using namespace std;
typedef long long ll;
ll C(ll n,ll m){
    ll ans = 1;
    for(ll i =1;i<=m;i++){
        ans = ans * (n-m+i)/i; // 注意一定要先乘再除
    }
    return ans;
}
int main()
{
   int n,m;
	cin>>n>>m;
	int a[m+1];

	for(int i=1;i<=m;i++){
		cin>>a[i];
	}
	int ans=1;
	int used=0;
	for(int i=1;i<=m;i++){
		ans*=C(n-used,a[i])%12520;
		used+=a[i];
	}
	printf("%d",ans);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

求余

这个很简单，直接附代码了。

#include<bits/stdc++.h> 
using namespace std;
int main( )
{
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	printf("%d%%%d=%d\n",a,b,a%b);
	printf("%d%%%d=%d",c,d,c%d);
	return 0;
}
1
2
3
4
5
6
7
8
9
10

点与线段的关系

这个题做法很多，点斜式、直线式、线段长、叉乘等，这里4种方法我都会介绍一下，最后给个直线式的代码。

先设前两个点为A、B，第三个点为C。

线段长。 很简单，AC+BC=AB，满足这个长度关系就能说明在线段上了。

叉乘。 向量AC和向量AB的叉乘如果等于0，则说明AC和AB是平行的，再约束下横纵坐标就可以说明是在线段上了。也就是说满足下列式子：
$$(x_c-x_a)\ast (y_a-y_b)-(x_a-x_b)\ast (y_c-ya)=0$$
$$min(x_a,x_b)<=x_c<=max(x_a,x_b)$$
$$min(y_a,y_b)<=y_c<=max(y_a,y_b)$$

** 点斜式 。** 知道斜率和一点，可以唯一确定一条直线。这种方法的详细过程我不展开说了，需要注意的是斜率k。 k避免直接计算值，如果直接计算值，存在精度的问题，不如表示成k=b/a的形式，注意b/a必须是最简形式不能约分，这里需要计算最大公约数gcd，使a、b均除以gcd。另外，该方法只能说明在直线上，还需要约束横坐标或者纵坐标。并且该方法不能处理垂直线，需要特判。

** 直线式。** 可以把直线的表达式转换为Ax+By+C=0的形式，这样就避免了精度问题，同时可以处理水平线和垂直线，比点斜式有很多优势。该方法同样只能说明在直线上，需要约束横坐标（纵坐标）。

A、B、C计算方法如下：
$$A=y_b-y_a$$
$$B=x_a-x_b$$
$$C=x_b\ast y_a-x_a\ast y_b$$

代码如下：

def main():
    two_point = [[int(s) for s in x.replace("(", "").replace(")","").split(",")] for x in input().split()]
    target_point = [int(x) for x in input().replace("(", "").replace(")","").split(",")]
    A=two_point[1][1]-two_point[0][1]
    B=two_point[0][0]-two_point[1][0]
    C=two_point[1][0]*two_point[0][1]-two_point[0][0]*two_point[1][1];
    D=target_point[0]*A+target_point[1]*B+C;
    if(D==0 and target_point[0]>=min(two_point[0][0],two_point[1][0]) and target_point[0]<=max(two_point[0][0],two_point[1][0]) and target_point[1]>=min(two_point[0][1],two_point[1][1]) and target_point[1]<=max(two_point[0][1],two_point[1][1])):
        print("YES");
    else:
        print("NO");

if __name__ == '__main__':
    main();

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15