[原创]2016ZSTU新生赛个人题解 【未完待续。。】

2016-11-30 20:30:18 Tabris_ 阅读数：488

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

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

大二选手做新生题目，最后累死累活做了8道(3H) ，剩下的待补。。。
还是太菜 ,继续努力

----------------------------------------------------------------------------------------------------------------------.
Save the Princess
题目大意 ：就是有两个人要去九公主 ，一共有Ｎ个人　公主在第Ｋ个位置，两人轮流杀强盗，杀完最后一个强盗的人赢

解题思路：
没什么好说的，把题读明白就行了。
就是判断ｎ的奇偶性。

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
//#include <bits/stdc++.h>
# include <stdio.h>
# include <iostream>
# include <algorithm>
# include <string.h>
# include <math.h>
# include <vector>
# include <queue>
using namespace std;

# define INF         2100000000ll
# define pb          push_back
# define mp          make_pair
# define abs(a)      ((a)>0?(a):-(a))
# define lalal       puts("*******");
# define s1(x)       scanf("%d",&x)
# define Rep(a,b,c)  for(int a=(b);a<=(c);a++)

typedef long long int LL ;
typedef unsigned long long int LLu ;
/*******************************/
const int MOD = 1e9+7;
const int N = 1000005;
const double eps = 1e-9;

int main()
{
    int _;
    while(~s1(_))
    {
        while(_--)
        {
            int n,k;
            s1(n),s1(k);
            if(n&1) puts("BH");
            else    puts("LYF");
        }
    }

    return 0;
}

----------------------------------------------------------------------------------------------------------------------.
巴比伦花园
这题我不会　，待补。。
----------------------------------------------------------------------------------------------------------------------.
极差
题目:中文题

解题思路:
水题,只要扫一遍,维护个最大最小值,然后想减即可.

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
//#include <bits/stdc++.h>
# include <stdio.h>
# include <iostream>
# include <algorithm>
# include <string.h>
# include <math.h>
# include <vector>
# include <queue>
using namespace std;

# define INF         2100000000ll
# define pb          push_back
# define mp          make_pair
# define abs(a)      ((a)>0?(a):-(a))
# define lalal       puts("*******");
# define s1(x)       scanf("%d",&x)
# define Rep(a,b,c)  for(int a=(b);a<=(c);a++)

typedef long long int LL ;
typedef unsigned long long int LLu ;
/*******************************/

const int MOD = 1e9+7;
const int N = 100000+5;
const double eps = 1e-9;

LL a[N];
int main()
{
    int _;
    while(~s1(_))
    {
        while(_--)
        {
            int n,k,q;
            s1(n);//,s1(k),s1(q);
            int mx= -1,mi=INF,x;

            Rep(i,1,n) {
                s1(x);
                if(x>mx) mx=x;
                if(x<mi) mi=x;
            }
            printf("%d\n",mx-mi);
        }
    }

    return 0;
}

----------------------------------------------------------------------------------------------------------------------.
圣杯战争
还没有做这道题 ,做了也出不了…
----------------------------------------------------------------------------------------------------------------------.
校庆
题意 : 中文题

解题思路:直接暴力模拟,
(和2016hrbust校个人赛相似 ,就xjb搞就行

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
102
103
104
105
106
107
108
109
110
111
112
//#include <bits/stdc++.h>
# include <stdio.h>
# include <iostream>
# include <algorithm>
# include <string.h>
# include <math.h>
# include <vector>
# include <queue>
using namespace std;

# define INF         2100000000ll
# define pb          push_back
# define mp          make_pair
# define abs(a)      ((a)>0?(a):-(a))
# define lalal       puts("*******");
# define s1(x)       scanf("%d",&x)
# define Rep(a,b,c)  for(int a=(b);a<=(c);a++)

typedef long long int LL ;
typedef unsigned long long int LLu ;
/*******************************/

const int MOD = 1e9+7;
const int N = 100000+5;
const double eps = 1e-9;

int mon[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int dsum[]={};

int check(int y,int m,int d)
{
    if((y%4==0&&y%100!=0)||y%400==0) return 1;
    return 0;
}

bool judge(int y,int m,int d)
{
    if(y==2017&&m==10&&d==28) return true;
    return false;
}

int main()
{

    int _;
    while(~s1(_))
    {
        while(_--)
        {
            int y,m,d;
            s1(y),s1(m),s1(d);
            int days= 0;
            while(true)
            {
                if(judge(y,m,d)) break;
                days++;
                if(m==1){
                    if(d==mon[m]) m++,d=1;
                    else d++;
                }
                else if(m==2){
                    if(d==(mon[m]+check(y,m,d)))m++,d=1;
                    else d++;
                }
                else if(m==3){
                    if(d==mon[m]) m++,d=1;
                    else d++;
                }
                else if(m==4){
                    if(d==mon[m]) m++,d=1;
                    else d++;
                }
                else if(m==5){
                    if(d==mon[m]) m++,d=1;
                    else d++;
                }
                else if(m==6){
                    if(d==mon[m]) m++,d=1;
                    else d++;
                }
                else if(m==7){
                    if(d==mon[m]) m++,d=1;
                    else d++;
                }
                else if(m==8){
                    if(d==mon[m]) m++,d=1;
                    else d++;
                }
                else if(m==9){
                    if(d==mon[m]) m++,d=1;
                    else d++;
                }
                else if(m==10){
                    if(d==mon[m]) m++,d=1;
                    else d++;
                }
                else if(m==11){
                    if(d==mon[m]) m++,d=1;
                    else d++;
                }
                else if(m==12){
                    if(d==mon[m]) y++,m=1,d=1;
                    else d++;
                }

            }
            printf("%d\n",days);
        }
    }

    return 0;
}

----------------------------------------------------------------------------------------------------------------------.
牛吃草
题意 : 中文题

解题思路：
直接对牛能吃草的面积二分答案即可
check部分用相交圆面积计算即可；
不知道相交圆面积如何求的戳这里
二分范围即[0,dis(牛,圆心)+半径][0,dis(牛,圆心)+半径]
(如果不考虑牛在园内[dis(牛,圆心),dis(牛,圆心)+半径][dis(牛,圆心),dis(牛,圆心)+半径] ,这样的话绝对会WA

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
//#include <bits/stdc++.h>
# include <stdio.h>
# include <iostream>
# include <algorithm>
# include <string.h>
# include <math.h>
# include <vector>
# include <queue>
using namespace std;

# define INF         2100000000ll
# define pb          push_back
# define mp          make_pair
# define abs(a)      ((a)>0?(a):-(a))
# define lalal       puts("*******");
# define s1(x)       scanf("%d",&x)
# define Rep(a,b,c)  for(int a=(b);a<=(c);a++)

typedef long long int LL ;
typedef unsigned long long int LLu ;
/*******************************/

const int MOD = 1e9+7;
const int N = 100000+5;
const double eps = 1e-6;
const double PI = acos(-1.0);

struct Round {
    double x, y;
    double r;
}c1,c2;

double dis(Round p1,Round p2)
{
    return(sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)));
}


double solve(Round a, Round b)
{
    double d = dis(a, b);
    if (d >= a.r + b.r)
        return 0;
    if (d <= fabs(a.r - b.r))
    {
        double r = a.r < b.r ? a.r : b.r;
        return PI * r * r;
    }
    double ang1 = acos((a.r * a.r + d * d - b.r * b.r) / 2. / a.r / d);
    double ang2 = acos((b.r * b.r + d * d - a.r * a.r) / 2. / b.r / d);
    double ret = ang1 * a.r * a.r + ang2 * b.r * b.r - d * a.r * sin(ang1);
    return ret;
}

int main()
{
    int _;
    while(~s1(_))
    {
        while(_--)
        {
            scanf("%lf",&c2.x);
            scanf("%lf",&c2.y);
            scanf("%lf",&c1.x);
            scanf("%lf",&c1.y);
            scanf("%lf",&c2.r);

            double area = PI*c2.r*c2.r/2.0;
            double l=0,r=dis(c1,c2)+c2.r,mid;
            //printf("%lf\n",c2.r);
            while(abs(r-l)>eps)
            {
                mid = (l+r)/2.0;
                c1.r= mid;
                if(solve(c1,c2)+eps>area)   r=mid;
                else    l=mid;
            }
            printf("%.4lf\n",c1.r);
        }
    }
    return 0;
}

----------------------------------------------------------------------------------------------------------------------.
众数
题意 : 中文题

解题思路:
水题,还是扫一遍就行了;

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
//#include <bits/stdc++.h>
# include <stdio.h>
# include <iostream>
# include <algorithm>
# include <string.h>
# include <math.h>
# include <vector>
# include <queue>
using namespace std;

# define INF         2100000000ll
# define pb          push_back
# define mp          make_pair
# define abs(a)      ((a)>0?(a):-(a))
# define lalal       puts("*******");
# define s1(x)       scanf("%d",&x)
# define Rep(a,b,c)  for(int a=(b);a<=(c);a++)

typedef long long int LL ;
typedef unsigned long long int LLu ;
/*******************************/

const int MOD = 1e9+7;
const int N = 100000+5;
const double eps = 1e-9;

int a[N];
int ha[10001];

int main()
{

    int _;
    while(~s1(_))
    {
        while(_--)
        {
            int n;
            s1(n);
            int mx=-1,pre=0;
            int x;
            Rep(i,1,1000) ha[i]=0;
            Rep(i,1,n) s1(x),ha[x]++;
            Rep(i,1,1000)
            {
                if(ha[i]>mx)
                {
                    mx=ha[i];
                    pre=i;
                }
            }
            int flag= 0;
            Rep(i,1,1000)
            {
                if(ha[i]==mx)
                {
                    if(flag) printf(" ");
                    printf("%d",i);
                    flag=1;
                }
            }
            puts("");

        }
    }

    return 0;
}

----------------------------------------------------------------------------------------------------------------------.
KI的斐波那契
题意 : 中文题

解题思路:
首先考虑 ,字符串的变化规律和斐波那契是相同的规律的
那么我们可以将一个大的数依次减去斐波那契数列变成一个很小的值,这样的话我们就直接能求出来了.

(其实这样看的话 我的代码还是能优化很多的,直接让fibo数变成0or1 的话 根本不用写这么长…

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
//#include <bits/stdc++.h>
# include <stdio.h>
# include <iostream>
# include <algorithm>
# include <string.h>
# include <math.h>
# include <vector>
# include <queue>
using namespace std;

# define INF         2100000000ll
# define pb          push_back
# define mp          make_pair
# define abs(a)      ((a)>0?(a):-(a))
# define lalal       puts("*******");
# define s1(x)       scanf("%d",&x)
# define Rep(a,b,c)  for(int a=(b);a<=(c);a++)

typedef long long int LL ;
typedef unsigned long long int LLu ;
/*******************************/

const int MOD = 1e9+7;
const int N = 100000+5;
const double eps = 1e-9;
char ch[100][100]={
    "0b\n",
    "0a\n",
    "0ab\n",
    "0aba\n",
    "0abaab\n",
    "0abaababa\n",
    "0abaababaabaab\n",
    "0abaababaabaababaababa\n",
    "0abaababaabaababaababaabaababaabaab\n",
    "0abaababaabaababaababaabaababaabaababaababaabaababaababa\n"
};

LL f[100];

int main()
{
    f[0]=1ll,f[1]=1ll;
    Rep(i,2,90)
    {
        f[i]=f[i-1]+f[i-2];
        //printf("%lld\n",f[i]);
    }

    //Rep(i,0,9)   puts(ch[i]);

    int _;
    while(~s1(_))
    {
        while(_--)
        {
            int n;
            s1(n);
            LL m;
            scanf("%lld",&m);
            if(n==0&&m==1ll)
            {
                puts("b");
                continue;
            }
            while(m>55)
            {
                Rep(i,1,90)
                {
                    if(f[i+1]>=m)
                    {
                        n--;
                        m-=f[i];
                        break;
                    }
                }
            }
            printf("%c\n",ch[9][m]);
        }
    }

    return 0;
}

----------------------------------------------------------------------------------------------------------------------.
萌新吃果果
题意 : 中文题

阶梯思路:
就是一个模拟题 ,按要求直接来就行了.(不懂看代码

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
//#include <bits/stdc++.h>
# include <stdio.h>
# include <iostream>
# include <algorithm>
# include <string.h>
# include <math.h>
# include <vector>
# include <queue>
using namespace std;

# define INF         2100000000ll
# define pb          push_back
# define mp          make_pair
# define abs(a)      ((a)>0?(a):-(a))
# define lalal       puts("*******");
# define s1(x)       scanf("%d",&x)
# define Rep(a,b,c)  for(int a=(b);a<=(c);a++)

typedef long long int LL ;
typedef unsigned long long int LLu ;
/*******************************/

const int MOD = 1e9+7;
const int N = 100000+5;
const double eps = 1e-9;

char str[N];

int main()
{
    int _;
    while(~s1(_))
    {
        while(_--)
        {
            int n,k;
            s1(n),s1(k);
            scanf("%s",str+1);
            int ctn=1,sum=1;
            Rep(i,2,n)
            {
                if(str[i]=='a'){
                    ctn++,sum++;
                }
                else if(str[i]=='b'){
                    if(str[i-1]=='a'){
                        ctn=0;
                        sum++;
                    }
                    ctn++;
                    sum++;
                }
                else {
                    if(ctn>=k){
                        ctn=0;
                        sum++;
                    }
                    ctn++;
                    sum++;
                }
            }

            printf("%d\n",sum);
        }
    }
    return 0;
}

----------------------------------------------------------------------------------------------------------------------.
萌新的旅行
这题 没想明白 .待补…
----------------------------------------------------------------------------------------------------------------------.
KI的目标
题意 :中文题

解题思路:
这题就是在一个树上去掉一些子树,问最后剩下多少节点 ,

那么根据题意:
我们只要在遍历树的时候不遍历删掉的子树就行了,然后统计一下遍历了多少节点即可.

因为点很多 ,所以采用邻接表存储图.

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
//#include <bits/stdc++.h>
# include <stdio.h>
# include <iostream>
# include <algorithm>
# include <string.h>
# include <math.h>
# include <vector>
# include <map>
# include <queue>
using namespace std;

# define INF         2100000000ll
# define pb          push_back
# define mp          make_pair
# define abs(a)      ((a)>0?(a):-(a))
# define lalal       puts("*******");
# define s1(x)       scanf("%d",&x)
# define Rep(a,b,c)  for(int a=(b);a<=(c);a++)

typedef long long int LL ;
typedef unsigned long long int uLL ;

const int MOD = 1e9+7;
const int N = 100000+5;
const double eps = 1e-6;
const double PI = acos(-1.0);
/***********************************************************************/

vector<pair<LL,LL> >E[N];

int a[N],h[N];
int ans ;
LL fir,sec;
void dfs(int u,int v)
{
    h[u]=1,ans++;
    Rep(i,0,E[u].size()-1)
    {
        fir=E[u][i].first,sec=E[u][i].second;
        if(fir!=v&&!h[fir]&&sec>=a[u]-a[fir])
            dfs(fir,u);
    }
}

int main()
{
    int _;
    while(~s1(_))
    {
        while(_--)
        {
            int n;
            s1(n);
            Rep(i,1,n) E[i].clear();
            int u,v,l;
            Rep(i,2,n)
            {
                h[i]=0;
                s1(u),s1(v),s1(l);
                E[u].pb(mp(v,l));
                E[v].pb(mp(u,l));
            }

            Rep(i,1,n) s1(a[i]);
            ans=0,dfs(1,-1);
            printf("%d\n",ans);
        }
    }
    return 0;
}

----------------------------------------------------------------------------------------------------------------------.