[原创]山东省第八届ACM大学生程序设计竞赛 训练总结 [8/11] 待补

2017-05-11 21:10:00 Tabris_ 阅读数：635

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

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

迟来的总结
队友缺席一人，两人，vj 5h模拟，1+小时从下开始看榜。

F题很迷，同时我很智障，居然浪费全队2个小时，个人3+小时的时间，，，，，导致最后的GG

做题的时候要更加细心，思维要缜密，同时不能有一点懒惰，有些认为可有可有的操作还是写上更为保险一点。

因为F题我只判了−b+det⁡2a\dfrac{-b+\sqrt {\det} }{2a} 而另一个解想当然的没有判。。。炸锅 看F之前3题。期间我清清脑子A了C，然后就GG了，

K题最后因为实验室清楼，时间不够了，算上回寝室走路的时间，队友晚了6分钟AC，然后这个A,D 都是我的题，当时想F想的，脑子一片浆糊，没有想出。赛后想到了。。。。

比赛时头脑要清晰，思维要严谨，尤其是不能懒，

Problem A SDUT 3893 Return of the Nim

————————————————————————————————————————————
有n(n 是素数)堆石子，两个人轮流玩，每次可以再一堆拿走任意个，或者在剩下的所有堆拿走相同的个数的石子，取走最后一个石子的人赢，问你谁赢

n是素数,所以切入点一定是这里，想了所有素数的性质，想不出什么所以然来，

然后玩了玩，其实可以发现，
对于n=2 时就是威佐夫博弈，

对于n=other 的时候，n是奇数，那么对于在所有堆拿走相同的石子，其实就是相当于两个人玩了多次的正常Nim， 因为Nim的最优策略就是对方拿了x个石子，我就在其他堆也拿x个石子，所以这就划归为基本的Nim游戏了，，

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

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
# include <bits/stdc++.h>
typedef long long int LL;
using namespace std;

const int MOD = 1e9+7;
const int N   = 1e5+7;

int main(){
    int _;
    scanf("%d",&_);
    while(_--){int n,x;
        scanf("%d",&n);
        if(n==2){
            int m;
            scanf("%d %d",&n,&m);
            if(n<m){
                n=n^m;
                m=m^n;
                n=n^m;
            }
            int k=n-m;
            n=(int)(k*(1+sqrt(5))/2.0);
            if(n==m) puts("Watson");
            else puts("Sherlock");
            continue;
        }
        int ans = 0;
        for(int i=1;i<=n;i++){
            scanf("%d",&x);
            ans ^=x;
        }
        if(ans) puts("Sherlock");
        else puts("Watson");
    }
    return 0;
}



Problem B SDUT 3894 Quadrat

————————————————————————————————————————————
还没弄懂题意,等邀请赛回来,

Problem C SDUT 3895 fireworks

————————————————————————————————————————————
就是在一个坐标轴上,有一些点(x)有一个价值(a)
每秒这些点和他们临近的点的价值变成(x-0) (x+1 - a) (x-1 - a)
价值会叠加，问你t秒后w位置有多少个值

写了写就会发现，每个点经过t妙对其他点的贡献是一个杨辉三角，

那么我们就枚举每个点对结果的贡献最后在加和就好了

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

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
# include <bits/stdc++.h>
typedef long long int LL;
using namespace std;

const int N   = 1e5+7;
const int MOD = 1e9+7;

int abs(int x){
    if(x>=0) return x;
    return -x;
}

int dis(int a,int b){
    return abs(a-b);
}

LL qmod(LL a,LL b){
    LL res = 1;
    while(b){
        if(b&1) res=res*a%MOD;
        b>>=1,a=a*a%MOD;
    }
    return res;
}
LL Fac[N],Inv[N];
void init(){
    Fac[0]=1;
    for(int i=1;i<N;i++) Fac[i]=(Fac[i-1]*i)%MOD;
    Inv[N-1]=qmod(Fac[N-1],MOD-2);
    for(int i=N-2;i>=0;i--) Inv[i]=(Inv[i+1]*(i+1))%MOD;
}

LL cal(LL t,LL c){
    return Fac[t]*Inv[c]%MOD*Inv[t-c]%MOD;
}

int main(){
    init();
    LL n,t,w,x,c;
    while(~scanf("%lld%lld%lld",&n,&t,&w)){
        LL ans = 0;
        for(int i=1;i<=n;i++){
            scanf("%lld%lld",&x,&c);
            if(dis(w,x)>t|| (dis(w,x)+t)&1) continue;
            ans=(ans+cal(t,(t-dis(w,x))/2)*c)%MOD;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

Problem D SDUT 3896 HEX

————————————————————————————————————————————
这个题就是一个点可以走到下面临近的三个位置上，问你从(1,1)到(n,m)的走法有多少个,

其实可以划到直角坐标系上,走法就是(0,1)(1,1)(1,0)

然后我们类比只有两种走法的情况 - (0,1)(1,0)

答案很明显是C(n+m,n), 那么对于三种情况当然也一样啊,

但是注意当(1,1)存在的时候(0,1)(1,0)相对就会变少结果也不一样,

然后我们可以枚举(1,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
# include <bits/stdc++.h>
typedef long long int LL;
using namespace std;

const int MOD = 1e9+7;
const int N   = 1e5+7;

LL qmod(LL a,LL b){
    LL res = 1;
    while(b){
        if(b&1) res=res*a%MOD;
        b>>=1,a=a*a%MOD;
    }
    return res;
}
LL Fac[N],Inv[N];
void init(){
    Fac[0]=1;
    for(LL i=1;i<N;i++) Fac[i]=(Fac[i-1]*i)%MOD;
    Inv[N-1]=qmod(Fac[N-1],MOD-2);
    for(LL i=N-2;i>=0;i--) Inv[i]=(Inv[i+1]*(i+1))%MOD;
}
LL C(LL t,LL c){
    return Fac[t]*Inv[c]%MOD*Inv[t-c]%MOD;
}

int main(){
    init();LL n,m;
    while(~scanf("%lld %lld",&n,&m)){
        n=n-m+1;n--,m--;if(n<m) swap(n,m);
//        printf("%lld %lld\n",n,m);
        LL ll = min(n,m),lll = max(n,m);
        LL ans = 0,tot,xia,zuo,xie;
        for(LL i=0;i<=ll;i++){
            tot = n+m-i;
            xia = n-i;
            zuo = m-i;
            xie = i;
            ans=(ans+C(tot,xia)*C(tot-xia,zuo)+MOD)%MOD;
        }
        printf("%lld\n",ans);
    }
    return 0;
}



Problem E SDUT 3897 news reporter

————————————————————————————————————————————
队友认为是01分数规划，，但是有不太一样，最后没出。

Problem F SDUT 3898 quadratic equation

————————————————————————————————————————————
让你判断“对于任意的x，如果方程ax2+bx+c=0ax^2+bx+c=0成立,x一定是正数”这句话是不是对的，

所以就是方程不成立的时候也是YES

对于命题P->Q

PQP->Q
001
011
100
111

所以这题注意下判断b2−4acb^2-4ac的符号就行了

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

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
# include <bits/stdc++.h>

using namespace std;
# define no  puts("NO");
# define yes puts("YES");

int abs(int x){
    if(x>=0) return x;
    return -x;
}

int main(){
    int _,a,b,c;
    scanf("%d",&_);
    while(_--){
        scanf("%d%d%d",&a,&b,&c);
        if(a==0&&b==0&&c==0){
            no
        }
        else if(a==0&&b==0&&c!=0){
            yes
        }
        else if(a==0&&b!=0&&c==0){
            yes
        }
        else if(a==0&&b!=0&&c!=0){
            if(c%b==0) yes
            else no
        }
        else if(a!=0&&b==0&&c==0){
            yes
        }
        else if(a!=0&&b==0&&c!=0){
            if(b*b-a*c*4<0) yes
            else {
                if(c%a==0){
                    int d=c/a;d=abs(d);
                    if(((int)(sqrt(d))*(int)(sqrt(d)))==d) yes
                    else no
                }
                else no
            }

        }
        else if(a!=0&&b!=0&&c==0){
            if(b*b-a*c*4<0) yes
            else {
                int d = b*b-4*a*c;
                d = abs(d);
                if(((int)(sqrt(d))*(int)(sqrt(d)))==d){
                    int e = (int)sqrt(d);
                    if( (e-b)%(a*2)==0 &&(e+b)%(a*2)==0) yes
                    else                 no
                }
                else no
            }
        }
        else if(a!=0&&b!=0&&c!=0){
            if(b*b-a*c*4<0) yes
            else {
                int d = b*b-4*a*c;
                d = abs(d);
                if(((int)(sqrt(d))*(int)(sqrt(d)))==d){
                    int e = (int)sqrt(d);
                    if( (e-b)%(a*2)==0 &&(e+b)%(a*2)==0) yes
                    else                 no
                }
                else no
            }
        }
    }
    return 0;
}

Problem G SDUT 3899 sum of power

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

水签到题 不解释

Problem H SDUT 3900 triangle

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

Problem I SDUT 3901 Parity check

————————————————————————————————————————————
很容易发现循环节 1 1 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
# include<stdio.h>
# include<string.h>
using namespace std;
char a[1050000];
int main()
{
    while(~scanf("%s",a))
    {
        if(strcmp(a,"0")==0)
        {
            printf("0\n");
            continue;
        }
        int sum=0;
        int n=strlen(a);
        for(int i=0;i<n;i++)
        {
            sum=sum*10+a[i]-'0';
            sum%=3;
        }
        if(sum==1||sum==2)printf("1\n");
        else printf("0\n");
    }
}

Problem J SDUT 3902 company

————————————————————————————————————————————
队友自己做的 ,我没读题

Problem K SDUT 3903 CF

————————————————————————————————————————————
队友自己做的 ,

贪心+01包