[原创]第十四届北京师范大学程序设计竞赛 [6/11]

Tabris

CSDN各OJ套题

发布于：2017年5月7日

次浏览

[原创]第十四届北京师范大学程序设计竞赛 [6/11]

2017-05-07 19:48:25 Tabris_ 阅读数：1295

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

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

虽然只是校赛，但是题目质量真的很高啊，

学到了新姿势，自己的思维还是太局限了。,

A Check In

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

水题，注意队伍名可能是 bnuu 这类

B Squared Permutation

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

其实还是一个基础的题目，维护区间和就行了，树状数组，线段树都可以

维护的时候，维护所有位置的真实值，即如果当前值是 b 那么就是 a[b]
再求区间和的时候就是基本的区间求和的操作了，

对于交换操作，很容易发现，交换的时候只对四个值有影响，
a[l],a[r]还有 a[i]==l 的位置，a[i]==r 的位置，
先处理交换操作，然后在去修改就可以了，

复杂度是O(n\log n)

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

# include <bits/stdc++.h>

using namespace std;
typedef long long int LL;
const int N = 1e5+7;

int n,m,a[N],pre[N];

LL sum[N<<2];

void pushup(int rt){
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}

void build(int rt,int l,int r){
    if(l==r){sum[rt]=a[a[l]];return;}
    int m = r+l >> 1;
    build(rt<<1,l,m);
    build(rt<<1|1,m+1,r);
    pushup(rt);
}

void update(int rt,int l,int r,int pos,int val){
    if(l==r){
        sum[rt]=val;
        return ;
    }
    int m = r+l >> 1;
    if(pos<=m) update(rt<<1,l,m,pos,val);
    else       update(rt<<1|1,m+1,r,pos,val);
    pushup(rt);
}

LL query(int rt,int l,int r,int L,int R){
    if(L<=l&&r<=R) return sum[rt];

    int m = r+l >> 1;LL ans = 0;
    if(L<=m) ans+=query(rt<<1,l,m,L,R);
    if(R> m) ans+=query(rt<<1|1,m+1,r,L,R);
    return ans;
}

int main(){
    int _;
    scanf("%d",&_);
    while(_--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            pre[a[i]]=i;
        }
//        for(int i=1;i<=n;i++) printf("%d ",pre[i]);puts("");


        build(1,1,n);
        scanf("%d",&m);
        int op,l,r;
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&op,&l,&r);
            if(op == 1){
                if(l==r) continue;

                swap(a[l],a[r]);swap(pre[a[l]],pre[a[r]]);
                update(1,1,n,l,a[a[l]]);
                update(1,1,n,r,a[a[r]]);
                update(1,1,n,pre[l],a[l]);
                update(1,1,n,pre[r],a[r]);

//printf("--%d %d   %d %d   %d %d   %d %d--\n",l,a[a[r]],r,,pre[l],a[l],pre[r],a[r]);


//                for(int i=1;i<=n;i++) printf("%d ",a[i]);puts("");
//                for(int i=1;i<=n;i++) printf("%d ",pre[i]);puts("");
//                for(int i=1;i<=n;i++) printf("%lld ",query(1,1,n,i,i));puts(" <---");
            }
            else printf("%lld\n",query(1,1,n,l,r));
        }
    }
    return 0;
}

C Quailty's Life

————————————————————————————————————————————————
不会

D Air Hockey

————————————————————————————————————————————————
其实很容易想到以一个点作为参照，然后计算另一个点，
然后讨论一下，动点与静点越来越远的轻况那么最开始的距离就是最近的
然后列方程可以求得静点到动点轨迹的垂足坐标，然后计算就可以了，

但是！但是！但是！无论怎么修精度什么的就是过不去，最后 GG，如果思路有纰漏请指正

最后用三分的方法过掉的，
首先我们能确定两个运动轨迹是直线，那么两点距离是先变小，在变大，这就是一个凹函数，可以三分求得极值，
给定时间了，就能求出两点当前的位置，然后算距离就好了
如果这个距离大于半径和，那就是不碰撞
否则就是碰撞了，在[0，三分结果]二分就能得到刚好相切的时刻

附本题代码

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

# include <bits/stdc++.h>
using namespace std;

const double eps  = 1e-6;

# define y1 y22

double x1,y1,r1,vx1,vy1;
double x2,y2,r2,vx2,vy2;

double dis(double x1,double y1,double x2,double y2){
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

double cal(double t){
    double xx1 = x1+vx1*t;
    double yy1 = y1+vy1*t;
    double xx2 = x2+vx2*t;
    double yy2 = y2+vy2*t;
    return dis(xx1,yy1,xx2,yy2);
}

int main(){
    int _;
    scanf("%d",&_);
    while(_--){
        scanf("%lf %lf %lf %lf %lf",&x1,&y1,&r1,&vx1,&vy1);
        scanf("%lf %lf %lf %lf %lf",&x2,&y2,&r2,&vx2,&vy2);
        double l = 0.0,r = 1e12,mid,midmid;
        for(int i=1;i<200;i++){
            mid = (l+l+r)/3.0;
            midmid = (l+r+r)/3.0;
            if(cal(mid) < cal(midmid)) r=midmid;
            else l=mid;
        }
        double dist = cal((r+l)/2.0);
        if(dist > r1+r2)  printf("%.9lf\n",dist-r1-r2);
        else {
            r=(r+l)/2.0,l=0;
            for(int i=1;i<200;i++){
                mid = (r+l)/2.0 ;
                if(cal(mid) < r1+r2) r=mid;
                else l=mid;
            }
            printf("%.9lf\n",(r+l)/2.0);
        }
    }
    return 0;
}

E Simple Database

————————————————————————————————————————————
一个大模拟，没有卡复杂度之类的，但是模拟 SQL 也是很复杂的，有时间补上

F Training Plan

————————————————————————————————————————————
水 dp，队友出的，过会儿补上

G Certain Maze

————————————————————————————————————————————
这个题很有意思，初看的时候没有什么想法，就想，要是像往常那样的 n*m 图 bfs 就好了，怎么搞了呢？
于是想到我将这个图按照原本的规则建立一个正常一点的图不就好了么。

然后将一个/\ 变成了 3*3 的方阵里的对角线，刚好能满足。

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

# include <bits/stdc++.h>
using namespace std;

bool vis[400][400],flag;
char a[400][400],b[200];
int xx,yy,n,m;
int fx[]={0,0,1,-1};
int fy[]={1,-1,0,0};

void dfs(int x,int y){
    vis[x][y]=true;
    for(int i=0;i<4;i++){
        xx = x + fx[i];
        yy = y + fy[i];
        if(xx<1||xx>n*3) continue;
        if(yy<1||yy>m*3) continue;
        if(vis[xx][yy]) continue;
        if(a[xx][yy]=='#') continue;
        dfs(xx,yy);
    }
}

void R(int x,int y){
    a[x][y]='#';
    a[x-1][y-1]='#';
    a[x-2][y-2]='#';
}

void L(int x,int y){
    a[x-2][y-0]='#';
    a[x-1][y-1]='#';
    a[x-0][y-2]='#';
}

int main(){
    int _;
    scanf("%d",&_);
    while(_--){flag = 0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n*3;i++){
            for(int j=1;j<=m*3;j++){
                a[i][j]='.';
                vis[i][j]=false;
            }
        }

        for(int i=1;i<=n;i++){
            scanf("%s",b+1);
            for(int j=1;j<=m;j++){
                if(b[j]=='L') L(i*3,j*3);
                else          R(i*3,j*3);
            }
        }

//        for(int i=1;i<=n*3;i++){
//            for(int j=1;j<=m*3;j++){
//                printf("%c",a[i][j]);
//            }puts("");
//        }

        for(int i=1;i<=m*3;i++)
            if(a[1][i]=='.') dfs(1,i);

        for(int i=1;i<=m*3;i++){
            if(a[n*3][i]=='.'&&vis[n*3][i]) {
                flag = true;
                break;
            }
        }
        if(flag) puts("Yes");
        else     puts("No");
    }

    return 0;
}

H Random Maze

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

I Cactus Exploration

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

J Whalyzh's Problem

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

K ACM Battle

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

其实重点就是那个 10 滴上面，所以只要对边爆搜即可，滴过得边就不用在滴，如果滴的大于 10 个就 return

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

# include <bits/stdc++.h>
using namespace std;

const int N = 1000+7;

/************************************************/
struct node {
    int u,v;
}e[N*2];
int n,m,mi,vis[N];
void dfs(int x,int sum){
    if(sum>mi) return;
    if(x==m){
        mi=min(mi,sum);
        return;
    }

    if(vis[e[x].u]||vis[e[x].v]){
        dfs(x+1,sum);
        return;
    }

    vis[e[x].u]=1;
    dfs(x+1,sum+1);
    vis[e[x].u]=0;

    vis[e[x].v]=1;
    dfs(x+1,sum+1);
    vis[e[x].v]=0;
}

int main(){
    int _;
    scanf("%d",&_);
    while(_--){
        mi = 11;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)vis[i]=0;
        for(int i=1,u,v;i<=m;i++)     scanf("%d%d",&e[i].u,&e[i].v);
        dfs(1,0);
        if(mi<=10) printf("%d\n",mi);
        else       puts("GG");
    }
    return 0;
}

本页文档最后更新于：2021年5月16日

CSDN

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

[原创]第十三届北京师范大学程序设计竞赛决赛【(6+2)/10】 2017-05-09 11:30:44 Tabris_ 阅读数：1236 博客爬取于 2020-06-14 22:40:4...

[原创]CSUOJ 1503: 点到圆弧的距离 [叉积+三角形外心]【计算几何】

[原创]CSUOJ 1503: 点到圆弧的距离 [叉积 + 三角形外心]【计算几何】 2017-05-07 11:24:54 Tabris_ 阅读数：696 博客爬取于 2020-06-1...