而另一个解想当然的没有判。。。炸锅 看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,如果方程a x 2 + b x + c = 0 ax^2+bx+c=0 a x 2 + b x + c = 0 成立,x一定是正数”这句话是不是对的,
所以就是方程不成立的时候也是YES
对于命题P->Q
所以这题注意下判断b 2 − 4 a c b^2-4ac b 2 − 4 a c 的符号就行了
附本题代码 ————————————————————————————
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包
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 tabris的博客 ! 赞助
wechat
alipay