[原创]第十三届北京师范大学程序设计竞赛决赛 【(6+2)/10】

2017-05-09 11:30:44 Tabris_ 阅读数:1236


博客爬取于2020-06-14 22:40:44
以下为正文

版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/71440571


日常6题 然后GG

最后这个B题和D题也没有过掉

套路啊 智商还是不行啊

A Araleii & Bill的冠名权争夺战之登顶校赛

————————————————————————————————————————————
这个A题开场几分钟队友就匆忙上机给秒了 666啊

我们这样考虑

对于一个说对的概率是1/m ,那么n个人的期望就是n/m

然而这个期望其实就是

E = n/m =\sum_{i=1}^n {(p_i\times i)} \tag{p_i为i个人答对的概率}

pnp_n最大值显然是 n/m=pn×np_n \times n

所以最后答案就是1/m

B 神奇的身高

————————————————————————————————————————————

对于一个序列我们将其变成升序序列,可以直接 a[i]-i 然后求LIS. 但是这样的结果可能是负数或者0的,

然而其实很简单 对于每个a[i]-i 如果小于0 那就一定要变化,所以就对剩下的序列求LIS就可以了,求得的结果就是不用修改的,那么修改的就是n减去

附本题代码
——————————————————————————————————————————

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
# include <bits/stdc++.h>

using namespace std;
typedef long long int LL;

const int N = 100000+7;
const int INF = 2000000007;

int b[N],cnt,n;

int main(){
while(~scanf("%d",&n)){
int mx=0,x;cnt=0;

for(int i=0;i<=n;i++) b[i]=INF;
for(int i=1,id;i<=n;i++){
scanf("%d",&x);x-=i;
if(x<0) continue;
id = upper_bound(b+1,b+1+n,x)-b;
b[id]=x;
mx=mx>id?mx:id;
}
printf("%d\n",n-mx);
}
return 0;
}

C Attack on Titan

————————————————————————————————————————————
这个题就是用50条直线,将平面内的一些点给分堆了,

如果直接找两个点之间的关系的话是复杂度是O(NKM)的,不可取,

但是问什么这个M给的是50呢? 仔细想一想,这个50 一定是一个可以枚举的,

然后想到,对于每一条直线来说,都会将平面内的点分成两部分,那么我们给直线一边的标记为1,另一边的标记为0,这样就能将每一个点的状态压缩下来,然后将titan的状态map一下,在判每一个村庄他的状态就行了。

附本题代码
————————————————————————————————————————————

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
37
38
39
40
41
42
43
44
45
46
# include <bits/stdc++.h>

using namespace std;
typedef long long int LL;

const int N = 1e6+7;

int n,m,k;
struct point{
LL x,y;
LL flag;
}cty[N],titan[N],a,b;
map<LL,bool>mmp;

LL mutli(point p0,point p1,point p2){
return ((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y));
}

int main(){
int _;
scanf("%d",&_);
while(_--){ mmp.clear();
scanf("%d%d%d",&n,&k,&m);
for(int i=1;i<=n;i++) scanf("%lld%lld",&cty[i].x,&cty[i].y),cty[i].flag=0ll;

for(int i=1;i<=k;i++) scanf("%lld%lld",&titan[i].x,&titan[i].y),titan[i].flag=0ll;

for(int i=0;i<m;i++){
scanf("%lld%lld%lld%lld",&a.x,&a.y,&b.x,&b.y);
for(int j=1;j<=n;j++)
if(mutli(a,b,cty[j]) > 0) cty[j].flag |=(1ll<<i);
for(int j=1;j<=k;j++)
if(mutli(a,b,titan[j]) > 0) titan[j].flag |=(1ll<<i);
}
for(int i=1;i<=k;i++){
mmp[titan[i].flag]=true;
// printf("titan[%d] : %d\n",i,titan[i].flag);
}
for(int i=1;i<=n;i++){
// printf("country[%d] : %d\n",i,cty[i].flag);
if(mmp[cty[i].flag]) puts("1");
else puts("0");
}
}
return 0;
}

D 超级线段树

————————————————————————————————————————————
这个题简直666 啊

本质就是一个区间覆盖问题,
但是直接区间覆盖会TLE ,然后就一直想怎么做到O(n),最后GG了

其实我们可以逆序覆盖,然后每次更新的时候lazy_tag如果有,那就不给它更新了,算是上一个大剪枝了.

附本题代码
————————————————————————————————————————————

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
# include <bits/stdc++.h>

using namespace std;
typedef long long int LL;

const int N = 1e6+7;

inline int read(){
int x=0,f=1;char ch = getchar();
while('0'> ch||ch> '9') {if(ch=='-')f=-1;ch=getchar();}
while('0'<=ch&&ch<='9') {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*f;
}

int lazy[N<<2];

inline void build(int rt,int l,int r){
lazy[rt]=0;
if(l==r)return;
int m = r+l >> 1;
build(rt<<1 ,l ,m);
build(rt<<1|1,m+1,r);
}

inline void pushdown(int &rt){
if(lazy[rt]){
if(!lazy[rt<<1]) lazy[rt<<1] =lazy[rt];
if(!lazy[rt<<1|1])lazy[rt<<1|1]=lazy[rt];
}
}

inline void update(int rt,int l,int r,int &L,int &R,int &val){
if(lazy[rt]) return ;
if(L<=l&&r<=R){
lazy[rt]=val;
return;
}
pushdown(rt);
int m = r+l >> 1;
if(L<=m) update(rt<<1 ,l ,m,L,R,val);
if(R> m) update(rt<<1|1,m+1,r,L,R,val);
}

inline void visit(int rt,int l,int r){
if(l==r){printf("%d\n",lazy[rt]);return;}
pushdown(rt);
int m = r+l >> 1;
visit(rt<<1 ,l ,m);
visit(rt<<1|1,m+1,r);
}

int l[N],r[N],p[N];

int main(){
int _=read(),n,m;
while(_--){
n=read(),m=read();
build(1,1,n);
for(int i=1;i<=m;i++) l[i]=read(),r[i]=read(),p[i]=read();
for(int i=m;i;i--) update(1,1,n,l[i],r[i],p[i]);
visit(1,1,n);
}
return 0;
}

E rating计算

————————————————————————————————————————————
签到水题,不解释

F 进化之地(Evoland)

————————————————————————————————————————————
稍微多点细节的搜索, 队友A的 不想补

G 贪心

————————————————————————————————————————————
没什么说的直接二分答案就好了

附本题代码(队友代码 不要脸的贴过来了)
————————————————————————————————————————————

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
37
38
39
40
41
42
43
44
45
46
47
48
# include<stdio.h>
# include<string.h>
# include<algorithm>
using namespace std;
# define ll long long int
struct node
{
ll x,y,ss;
}a[150000];
ll n,m;
ll cmp(node a,node b)
{
return a.ss<b.ss;
}
int Slove(ll mid)
{
ll sum=0;
for(ll j=1;j<=n;j++)a[j].ss=mid*a[j].y+a[j].x;
sort(a+1,a+1+n,cmp);
for(ll j=1;j<=mid;j++)
{
sum+=a[j].ss;
}
if(sum<=m)return 1;
else return 0;
}
int main()
{
while(~scanf("%lld%lld",&n,&m))
{
ll output=0;
for(ll i=1;i<=n;i++)scanf("%lld",&a[i].x);
for(ll i=1;i<=n;i++)scanf("%lld",&a[i].y);
ll l=0;
ll r=n;
while(r-l>=0)
{
ll mid=(l+r)/2;
if(Slove(mid)==1)
{
output=mid;
l=mid+1;
}
else r=mid-1;
}
printf("%lld\n",output);
}
}

H 简单的传球游戏

————————————————————————————————————————————
这题如果直接计算的话,会涉及每次到甲的概率,通式推不出来

然后当时就分成两个值

i:第i次传到甲的方案数!i:i次没有传到甲的方案数甲_i :第i次传到甲的方案数 \\ !甲_i : 第i次没有传到甲的方案数

然后很容易构造矩阵

[i!i]×[0k11k2]=[i+1!i+1](2)\left[\begin{matrix} 甲_i & !甲_i \\ \end{matrix}\right] \times \left[\begin{matrix} 0 & k-1 \\ 1 & k-2 \end{matrix}\right] =\left[\begin{matrix} 甲_{i+1} & !甲_{i+1} \\ \end{matrix}\right]\tag{2}

然后矩阵乘法即可

附本题代码
——————————————————————————————————————————

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
# include <bits/stdc++.h>

using namespace std;
typedef long long int LL;

const LL MOD = 1e9+7;
const int M = 2;

struct Matrix{
LL m[M][M];

void clear0(){
for(int i=0;i<M;i++)
for(int j=0;j<M;j++)
m[i][j]=0;
}

void clearE(){
for(int i=0;i<M;i++)
for(int j=0;j<M;j++)
m[i][j]=(i==j);
}

};

Matrix operator * (Matrix &a,Matrix &b){
Matrix c;
c.clear0();

for(int k=0;k<M;k++)
for(int i=0;i<M;i++)
for(int j=0;j<M;j++)
c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j]+MOD)%MOD;
return c;
}

Matrix operator ^(Matrix a,LL b){
Matrix c;c.clearE();
while(b){
if(b&1) c=c*a;
b>>=1,a=a*a;
}
return c;
}

LL n,k;
int main(){
int _;
scanf("%d",&_);
while(_--){
scanf("%lld%lld",&n,&k);
Matrix a,b;
a.clear0(),b.clearE();
a.m[0][0]=1,a.m[0][1]=0;
a.m[1][0]=0,a.m[1][1]=0;

b.m[0][0]=0,b.m[0][1]=k-1;
b.m[1][0]=1,b.m[1][1]=k-2;

b=b^(n);
a=a*b;
printf("%lld\n",a.m[0][0]);
}
return 0;
}

I 打怪兽

————————————————————————————————————————————

K 最长上升子序列

————————————————————————————————————————————