[原创]第十五届北京师范大学程序设计竞赛 [(6+1)/11,待补]

Tabris

CSDN各OJ套题

发布于：2017年4月24日

次浏览

[原创]第十五届北京师范大学程序设计竞赛 [(6+1)/11，待补]

2017-04-24 01:09:43 Tabris_ 阅读数：695

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

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

23 号和队友用一个账号一起做这套题，开了挂，用了两台电脑，由于我们做的时候还不能添加到 BNUVJ，队内交流还少，因为中文题面嘛，基本相当于两个人分别打个人了。。。

但是鄙队实在是菜的抠脚啊，最后仅出 6 题。j 题连题意都没懂有木有（这可是中文题面 qaq。

qls 说封顶 8 题，那最后我怎么也要补题补到 9 题啊....

BNUOJ 52517 A Another Server

————————————————————————————————————————————
思维题队友过的。明天起来补上。

原来就是傻逼题，，，
题目说的是第 i 条边链接的是[i+1/2]和[i+1/2]+1，我竟当成了第 i 个点...

懵逼到怀疑人生，全场最水的不出有木有啊... ，最后仔细看了发题，......

其实连起来发现是
1=2=3=4=...=n .(等号代表一个线，,,)

只要求max\{a_i+a_{i+1} | i\in [1,n-1]\} 就好了嘛。。。

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

typedef long long int LL;

const double eps = 1e-5;
const int    N   = 100+7;

int _,n;

int main(){
    int _;
    scanf("%d",&_);
    while(_--){
        scanf("%d",&n);
        int mx = 10000000;
        int a,b;
        for(int i=1;i<=n-1;i++){
            scanf("%d%d",&a,&b);
            mx = min(mx,a+b);
        }
        printf("%d\n",mx);
    }
    return 0;
}

BNUOJ 52509 B Borrow Classroom

————————————————————————————————————————————
明确题意后很好确定，这是 LCA 相关问题

只要满足

A 到 C 不比 B 到 C 慢
如果 A 和 C 在一个 1(根节点)的子树上， A 到 1 不比 C 到 1 加 B 到 C 慢
如果 A 和 C 不在一个 1 的子树上，A 到 1 不比 C 到[C 马上到 1 的那个节点]加 B 到 C 慢

满足以上任何一条都是 yes 的情况，否则就是 no

由于涉及了[C 马上到 1 的那个节点]，我是先预处理了一下这个然后直接判断

找树上两点关系的时候渣渣只会写树剖，代码长的一逼啊..

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

typedef long long int LL ;

const double pi  = acos(-1.0);
const double eps = 1e-8;
const int    N   = 1e5+7;

/***********************************************************************/

int _,n,q,cnt,mx;

vector<int >G[N];

void add(int u,int v){
    G[u].push_back(v);
    G[v].push_back(u);
}

int sz[N],son[N],fa[N],dep[N];
void dfs1(int u,int f,int d){
    sz[u]=1,son[u]=0,fa[u]=f,dep[u]=d;
    int gz = G[u].size();
    for(int i=0,to;i<gz;i++){
        to = G[u][i];
        if(to==f) continue;
        dfs1(to,u,d+1);
        sz[u] += sz[to];
        if(sz[son[u]]<sz[to]) son[u]=to;
    }
}

int top[N],tree[N];

void dfs2(int u,int tp){
    tree[u]=++cnt,top[u]=tp;
    if(son[u])dfs2(son[u],tp);
    int gz = G[u].size();
    for(int i=0,to;i<gz;i++){
        to = G[u][i];
        if(to==fa[u]||to==son[u]) continue;
        dfs2(to,to);
    }
}

int to1[N];

int findto1(int x){
    if(to1[x])   return to1[x];
    if(1==fa[x]) return x;
    else         return findto1(fa[x]);
}

int findi(int x,int y){
    int tx = top[x],ty = top[y];
    int ans = 0;
    while(tx!=ty){
        if(dep[tx]<dep[ty]) swap(tx,ty),swap(x,y);
//        printf("(%d %d) [%d %d]\n",x,y,tree[tx],tree[y]);
        ans+=tree[x]-tree[tx]+1;
        x=fa[tx],tx=top[x];
    }
//    printf("%d\n",ans);
    if(dep[x]<dep[y])swap(x,y);
    ans+=tree[x]-tree[y]+1;
    return ans-1;
}

int main(){
    int _;
    scanf("%d",&_);
    while(_--){
        cnt = 0;
        scanf("%d%d",&n,&q);
        for(int i=1,u,v;i<n;i++){to1[i]=0;
            scanf("%d%d",&u,&v);
            add(u,v);
        }
        dfs1(1,0,1);
        dfs2(1,1);

        for(int i=2;i<=n;i++)     to1[i]=findto1(i);
//        for(int i=2;i<=n;i++)     printf("to1[%d]=%d\n",i,to1[i]);
//        for(int i=1;i<=n;i++)     printf("tree[%d]=%d\n",i,tree[i]);

        int a,b,c;
        for(int tmp,i=1;i<=q;i++){
            scanf("%d%d%d",&a,&b,&c);
            tmp = findi(b,c);
//            printf("%d  ++\n",tmp);
            if(tmp>=findi(a,c)) puts("YES");
            else if(tmp+findi(c,to1[c])>=findi(a,1)&&to1[a]!=to1[c]) puts("YES");
            else if(tmp+findi(c,to1[c])>=findi(a,to1[c])) puts("YES");
            else puts("NO");
        }

        for(int i=1;i<=n;i++)G[i].clear();
    }
    return 0;
}

BNUOJ 52506 C Captcha Cracker

————————————————————————————————————————————
水签到，不解释

BNUOJ 52503 D Disdain Chain

————————————————————————————————————————————
思维题吧，就是画了画发现，因为是一个完全图，只要加一个节点，那么其最长链都是 n 的，所以无脑输出 n-1 个 0 和一个(1<<(n*(n-1)/2))就好了

int main(){
    int _;
    scanf("%d",&_);
    while(_--){
        scanf("%d",&n);
        for(int i=1;i<n;i++) printf("%d\n",0);
        printf("%d\n",1<<(n*(n-1)/2));
    }
    return 0;
}

BNUOJ 52505 E Euclidean Geometry

————————————————————————————————————————————
开始想的是枚举最长的边上的圆的半径，从 0 到边长。开始以为是一个凸函数，三分就行了，但是写完样例没有过，然后发现其实最大的园面积的和相当于在
x+y = a\ \\w = x^2+y^2
求 w 的最大值，显然x=a的时候 w 最大。
回来思考最大的面积和，也就是使一个圆的半径最大化，因为有不能相交的限制，所以最大的圆的半径就是第二长的边的长读，然后在算上当前状态下另外的两个园就好了(其中有一个是半径为 0 的园，另一个半径就是最长边减次长边。


int main(){
    int _;
    scanf("%d",&_);
    while(_--){
        scanf("%d%d%d",&a,&b,&c);
        if(b<c) swap(b,c);
        if(a<b) swap(a,b);
        if(b<c) swap(b,c);
        printf("%.12lf\n",pi*(b*b+(a-b)*(a-b)));
    }
    return 0;
}

BNUOJ 52513 F Find Quailty

————————————————————————————————————————————
神题啊我是不会补的，

BNUOJ 52514 G Graph Compression

————————————————————————————————————————————
还没看题。尽量补

BNUOJ 52512 H Honorable Mention

————————————————————————————————————————————
看 N 的大小，我想大力分块，

然后细节还没想好，想好补上。

BNUOJ 52508 I Idol Master

————————————————————————————————————————————
完全没想法啊

BNUOJ 52516 J Just A String

————————————————————————————————————————————
在我理解的题意中，字符串长什么样无关结果....hhh...gg

懂了字符串对结果的影响了

比如说我有一个字符串，这个时候我找到的是 f(i,j) ,
XXXABCABCABCXXX f(6,10)
那么 strA：XXXABC strB:ABC strC:ABCXXX
并不一定是前后缀相交的那个串才是 B

然后考虑怎么计算结果，
直接暴力算的话 +KMP 的话也是O(n^3)的
很好考虑，我们一定是枚举(i,j)找到前后缀，
然后找这个前后串的那个公共部分。

一般我们固定一个值去枚举另一个值，这里也是一样，
考虑 KMP 的过程中就是一个子串在一个母串上匹配，
然后我们惊奇的发现这个过程不就是在整个穿上进行 KMP，母串每个位置的时候匹配的子串最长是多长？

统计的过程直接放到 KMP 就好了

最后就是在枚举后缀的，对整个字符串进行 KMP，在 KMP 的过程中统计，

char a[N],*p;
int Next[N];

void get_next(char *s,int len){
    for(int i=0,j=-1;i<=len;++i,++j){
        Next[i]=j;
        while(j>=0&&s[i]!=s[j]) j = Next[j];
    }
//    for(int i=0;i<=len;i++) printf("%d%c",Next[i],(i==len)?'\n':' ');
}

int Main(){
    int _;
    scanf("%d",&_);
    while(_--){
        scanf("%s",a);
        int len = strlen(a);

        LL ans = 0;
        for(int k=0;k<len;k++){
            p=a+k;
            get_next(p,len-k);

            for(int j=0,i=0;i<=len;i++,j++){
                ans ^= 1LL*(j)*(j)*(len-k-j)*(i-j) ;
                while(j>=0&&a[i]!=p[j]) j=Next[j];
            }
        }

        printf("%lld\n",ans);
    }
    return 0;
}

BNUOJ 52511 K Keep In Line

————————————————————————————————————————————
简单模拟

int _,n;

map<string,int>mmp;
string a[N],op[N];

int h[N];
int main(){
    cin>>_;
    while(_--){
        mmp.clear();
        memset(h,1,sizeof(h));
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>op[i]>>a[i];
            if(!mmp[a[i]]) mmp[a[i]]=++cnt;
        }

        int ans = 0,tmp=0,tem=1;
        for(int i=1;i<=n;i++){
            if(op[i][0]=='o'){
                tmp = mmp[a[i]];
                if(tmp == tem)  ans++;
                h[tmp]=0;
                while(!h[tem])tem++;
            }
        }
        printf("%d\n",ans);

    }
    return 0;
}

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

CSDN

必须要会的Git基本使用及常用命令操作

之前一直用的 SVN，后来换了之后才发现 Git 的强大功能，是 SVN 不能比的。缺点就是可能上手比较难一点，刚开始自己研究了两天才摸索出来一些基本使用方法。最近做项目需要建库等等，都用到了...

[原创]Google Code Jam 2017 Round 1B [B-large不会]

[原创]Google Code Jam 2017 Round 1B [B-large 不会] 2017-04-23 04:05:38 Tabris_ 阅读数：991 博客爬取于 2020-0...