[原创]第十三届北京师范大学程序设计竞赛决赛 【(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个人答对的概率}
pn最大值显然是 n/m=pn×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]×[01k−1k−2]=[甲i+1!甲i+1](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 最长上升子序列
————————————————————————————————————————————