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

[原创]第十三届北京师范大学程序设计竞赛决赛 【(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个人答对的概率}

$p_n$最大值显然是 n/m=$p_n \times n$

所以最后答案就是1/m

B 神奇的身高

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

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

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

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

# 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一下，在判每一个村庄他的状态就行了。

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

# 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如果有,那就不给它更新了,算是上一个大剪枝了.

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

# 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 贪心

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

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

# 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次没有传到甲的方案数$$

然后很容易构造矩阵

$$\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}$$

然后矩阵乘法即可

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

# 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 最长上升子序列

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