[原创]第十五届北京师范大学程序设计竞赛 [(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{ai+ai+1∣i∈[1,n−1]}max\{a_i+a_{i+1} | i\in [1,n-1]\} 就好了嘛。。。

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
# 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相关问题

只要满足

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

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

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

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

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
# 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))就好了

1
2
3
4
5
6
7
8
9
10
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=x2+y2x+y = a\ \\w = x^2+y^2
求w的最大值，显然x=ax=a的时候w最大.
回来思考最大的面积和,也就是使一个圆的半径最大化,因为有不能相交的限制,所以最大的圆的半径就是第二长的边的长读,然后在算上当前状态下另外的两个园就好了(其中有一个是半径为0的园,另一个半径就是最长边减次长边.

1
2
3
4
5
6
7
8
9
10
11
12
13

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(n3)O(n^3)的
很好考虑，我们一定是枚举(i,j)找到前后缀,
然后找这个前后串的那个公共部分.

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

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

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

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
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

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

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
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;
}