期望得分:60+60+60
实际得分:60+60+0
这次考试主要是T3搜索打挂了(我可是靠搜索吃饭的);
1.数组开小了，不过开大数组只拿到了10分的好成绩。
2.题意没审清（其实是他没说清）。
以后搜索不能打打挂了。
T1 方程的解：特判+exgcd
一看题就打了个exgcd，最后把exgcd删了骗了60分
但我们用exgcd是可以做的=_=（废话）。
考虑这个一次函数，然后就把纵截距和斜率一通特判AC >_<
1 #include<cstdio>
2 #include<iostream>
3 #define ll long long
4 using namespace std; 5 ll exgcd(ll a,ll b,ll &x,ll &y) 6 { 7 if(!b) 8 { 9 x=1; 10 y=0; 11 return a; 12 } 13 ll d=exgcd(b,a%b,x,y); 14 ll tmp=x; 15 x=y; 16 y=tmp-a/b*y; 17 return d; 18 } 19 int main() 20 { 21 #define C continue
22 ll t; 23 scanf("%lld",&t); 24 while(t--) 25 { 26 ll x,y,a,b,c; 27 scanf("%lld%lld%lld",&a,&b,&c); 28 if(!a&&!b) 29 { 30 if(!c)puts("ZenMeZheMeDuo"); 31 else puts("0"); 32 C; 33 } 34 else if(!c) 35 { 36 if(!a&&!b)puts("ZenMeZheMeDuo"); 37 else if(a*b>0)puts("0"); 38 else puts("ZenMeZheMeDuo"); 39 C; 40 } 41 else if(!a) 42 { 43 if(c%b==0&&b&&b*c>0)puts("ZenMeZheMeDuo"); 44 else puts("0"); 45 } 46 else if(!b) 47 { 48 if(c%a==0&&c&&a*c>0)puts("ZenMeZheMeDuo"); 49 else puts("0"); 50 C; 51 } 52 else if(a==1&&b==1) 53 { 54 if(c<=0)puts("0"); 55 else if(c>65536)puts("ZenMeZheMeDuo"); 56 else printf("%lld\n",c-1); 57 C; 58 } 59 else if(a+b==c){puts("1");C;} 60 else
61 { 62 if(a>0&&b>0&&c<0){puts("0");C;} 63 else if(a<0&&b<0&&c>0){puts("0");C;} 64 else
65 { 66 if(a<0&&b<0&&c<0)a=-a,b=-b,c=-c; 67 ll gcd=exgcd(a,b,x,y); 68 if(c%gcd!=0){puts("0");C;} 69 else if(a*b<0){puts("ZenMeZheMeDuo");} 70 else
71 { 72 //cout<<x<<endl;
73 x=(x%b+b)%b; 74 x*=(c/gcd); 75 x%=(b/gcd); 76 if(!x)x+=(b/gcd); 77 y=(c-a*x)/b; 78 if(y<=0){puts("0");continue;} 79 ll num=y/(a/gcd)+1; 80 if(y%(a/gcd)==0)num--; 81 if(num<=65535ll)printf("%lld\n",num); 82 else puts("ZenMeZheMeDuo"); 83 } 84 } 85
86 } 87 } 88 return 0; 89 }
T2 visit：组合数学+CRT
考试的时候推出式子了，也想到CRT了。
（嘿嘿刚才搬了好多吃的，发家致富！！！）
好啦继续说，但我不会打CRT板子（摆手）。
所以只能骗60分。
公式 ans=∑C(T,a)*C(T-a,b)*C(T-a-b,c)*C(T-a-b-c,d) (a+b+c+d==T&&a-b==n&&b-c==m)
大概说一下我的思路，以n，m均大于零为例
如果T=n+m，那么答案显然，C(T,n)。
如果T更小，显然无解
考虑T>n+m，因为最后一定要到n,m，所以如果你多往前走一步就一定会对应地往后走一步，左右同理。
由此可得：a-b=n，c-d=m（不用管a,b,c,d是神魔）然后就可以AC了
1 #include<cstdio>
2 #include<iostream>
3 #define MAXN 100005
4 #define ll long long
5 #include<cmath>
6 #define maxn 205
7 #define mod prime[num]
8 using namespace std; 9 ll t,js[MAXN],inv[MAXN],prime[11],tot,m,num,w[11]; 10 ll abs(ll x) 11 { 12 return x<0ll?(-1ll*x):x; 13 } 14 ll qpower(ll a,ll b) 15 { 16 ll ans=1; 17 while(b) 18 { 19 if(b&1)ans=ans*a%mod; 20 a=a*a%mod; 21 b>>=1; 22 } 23 return ans%mod; 24 } 25 void PP() 26 { 27 ll x=m; 28 for(ll i=2;i<=sqrt(m)+1;i++) 29 { 30 if(x==1)break; 31 if(x%i==0)prime[++tot]=i,x/=i; 32 } 33 if(x>1)prime[++tot]=x; 34 return ; 35 } 36 void exgcd(ll a,ll b,ll &x,ll &y) 37 { 38 if(!b) 39 { 40 x=1; 41 y=0; 42 return ; 43 } 44 exgcd(b,a%b,x,y); 45 ll tmp=x; 46 x=y; 47 y=tmp-a/b*y; 48 return ; 49 } 50 ll crt() 51 { 52 ll ans=0; 53 for(ll i=1;i<=tot;i++) 54 { 55 ll xi=m/prime[i],x,y; 56 exgcd(xi,prime[i],x,y); 57 x=(x%prime[i]+prime[i])%prime[i]; 58 ans=(ans+x*w[i]*xi)%m; 59 } 60 return ans%m; 61 } 62 void pre() 63 { 64 js[1]=inv[1]=1; 65 for(ll i=2;i<=min(mod,100000ll);i++) 66 { 67 js[i]=js[i-1]*i%mod; 68 inv[i]=qpower(js[i],mod-2); 69 } 70 return ; 71 } 72 ll C(ll n,ll m) 73 { 74 if(m==0||m==n)return 1ll; 75 if(m>n)return 0ll; 76 return js[n]*inv[n-m]%mod*inv[m]%mod; 77 } 78 ll lucas(ll n,ll m) 79 { 80 if(m==0||m==n)return 1ll; 81 if(m>n)return 0ll; 82 return C(n%mod,m%mod)*lucas(n/mod,m/mod)%mod; 83 } 84 int main() 85 { 86 ll a,b,c=0,d=0,ans=0; 87 scanf("%lld%lld%lld%lld",&t,&m,&a,&b); 88 a=abs(a);b=abs(b); 89 if(m==1){puts("0");return 0;} 90 ll k=t-abs(a)-abs(b); 91 if(k<0||(k&1)^0){puts("0");return 0;} 92 k/=2;PP(); 93 for(num=1;num<=tot;num++) 94 { 95 pre(); 96 for(ll i=0;i<=k;i++) 97 { 98 a+=i; 99 c+=i; 100 b+=(k-i); 101 d+=(k-i); 102 (w[num]+=lucas(t,a)*lucas(t-a,b)%mod*lucas(t-a-b,c)%mod*lucas(t-a-b-c,d)%mod)%=mod; 103 a-=i; 104 c-=i; 105 b-=(k-i); 106 d-=(k-i); 107 } 108 } 109 printf("%lld\n",crt()); 110 return 0; 111 }
T3 光：模拟+二分优化
我感觉这个题就是sb
但是不管怎么说，代码能力是很重要的一部分。
这个题有几个引理值得一提：
1.对于一个格子来说，之可能被（东南&&西北）||（东北&&西南）经过 证明：光线每次移动，其（x+y）||（x-y）奇偶性不变
我们可以画一个形象的图（自行）理解一下。
2.光线的碰撞反射次数只与n，m，k线性相关，这就不用我证明了叭。
3.光线的路径一定是一个环，所以它一定会回到初始状态，这可以作为终止边界。
在用。。。就是细心，耐心和lower_bound,upper_bound的应用了。
1 #include<bits/stdc++.h>
2 #define MAXN 200500
3 #define ll long long
4 #define mp make_pair
5 using namespace std; 6 vector<int>v1[MAXN*2],v2[MAXN*2]; 7 map< pair<int,int>,bool >py; 8 ll ans;int n,m,k,sta,stb,sts,nn=0,tot; 9 bool ok=0,Getans=0; 10 void search(int x,int y,int now)// 1 youshang 2 zuoxia 3 youxia 4 zuoshang
11 { 12 if(Getans)return ; 13 if(now==1) 14 { 15 int id=x+y;bool za=0,zb=0; 16 int nxtx=(*--upper_bound(v1[id].begin(),v1[id].end(),x))+1; 17 int nxty=id-nxtx; 18 if(sta+stb==id&&sta>=nxtx&&sta<=x&&sts==1){nn++;if(nn!=1){ans+=abs(sta-x);Getans=1;return ;}} 19 ans+=abs(x-nxtx)+1; 20 if(py[mp(nxtx,nxty+1)])za=1;if(py[mp(nxtx-1,nxty)])zb=1; 21 if(!za&&zb)search(nxtx,nxty+1,3); 22 else if(za&&!zb)search(nxtx-1,nxty,4); 23 else if(!za&&!zb){ok=1;search(nxtx,nxty,2);} 24 else {ok=1;search(nxtx,nxty,2);} 25 return ; 26 } 27 if(now==2) 28 { 29 int id=x+y;bool za=0,zb=0; 30 int nxtx=(*upper_bound(v1[id].begin(),v1[id].end(),x))-1; 31 int nxty=id-nxtx; 32 if(sta+stb==id&&sta>=x&&sta<=nxtx&&sts==2){nn++;if(nn!=1){ans+=abs(sta-x);Getans=1;return ;}} 33 ans+=abs(x-nxtx)+1; 34 if(py[mp(nxtx+1,nxty)])za=1;if(py[mp(nxtx,nxty-1)])zb=1; 35 if(!za&&zb)search(nxtx+1,nxty,3); 36 else if(za&&!zb)search(nxtx,nxty-1,4); 37 else if(!za&&!zb){ok=1;search(nxtx,nxty,1);} 38 else {ok=1;search(nxtx,nxty,1);} 39 return ; 40 } 41 if(now==3) 42 { 43 int id=x-y+m+1;bool za=0,zb=0; 44 int nxtx=(*upper_bound(v2[id].begin(),v2[id].end(),x))-1; 45 int nxty=nxtx+m+1-id; 46 if(sta-stb+m+1==id&&sta<=nxtx&&sta>=x&&sts==3){nn++;if(nn!=1){ans+=abs(sta-x);Getans=1;return ;}} 47 ans+=abs(x-nxtx)+1; 48 if(py[mp(nxtx+1,nxty)])za=1;if(py[mp(nxtx,nxty+1)])zb=1; 49 if(!za&&zb)search(nxtx+1,nxty,2); 50 else if(za&&!zb)search(nxtx,nxty+1,1); 51 else if(!za&&!zb){ok=1;search(nxtx,nxty,4);} 52 else {ok=1;search(nxtx,nxty,4);} 53 return ; 54 } 55 if(now==4) 56 { 57 int id=x-y+m+1;bool za=0,zb=0; 58 int nxtx=(*--upper_bound(v2[id].begin(),v2[id].end(),x))+1; 59 int nxty=nxtx+m+1-id; 60 if(sta-stb+m+1==id&&sta>=nxtx&&sta<=x&&sts==4){nn++;if(nn!=1){ans+=abs(sta-x);Getans=1;return ;}} 61 ans+=abs(x-nxtx)+1; 62 if(py[mp(nxtx-1,nxty)])za=1;if(py[mp(nxtx,nxty-1)])zb=1; 63 if(!za&&zb)search(nxtx-1,nxty,1); 64 else if(za&&!zb)search(nxtx,nxty-1,2); 65 else if(!za&&!zb){ok=1;search(nxtx,nxty,3);} 66 else {ok=1;search(nxtx,nxty,3);} 67 return ; 68 } 69 } 70 int main() 71 { 72 scanf("%d%d%d",&n,&m,&k); 73 while(k--) 74 { 75 int a,b; 76 scanf("%d%d",&a,&b); 77 v1[a+b].push_back(a); 78 v2[a-b+m+1].push_back(a); 79 py[mp(a,b)]=1; 80 } 81 for(int i=0;i<=n+1;i++) 82 { 83 v1[i].push_back(i); 84 v2[i+m+1].push_back(i); 85 v1[i+m+1].push_back(i); 86 v2[i].push_back(i); 87 py[mp(i,0)]=1;py[mp(i,m+1)]=1; 88 } 89 for(int i=0;i<=m+1;i++) 90 { 91 v1[i].push_back(0); 92 v2[m+1-i].push_back(0); 93 v1[i+n+1].push_back(n+1); 94 v2[n+1-i+m+1].push_back(n+1); 95 py[mp(0,i)]=1;py[mp(n+1,i)]=1; 96 } 97 for(int i=0;i<=n+m+2;i++)sort(v1[i].begin(),v1[i].end()); 98 for(int i=0;i<=n+m+2;i++)sort(v2[i].begin(),v2[i].end()); 99 string ss; 100 cin>>sta>>stb>>ss; 101 if(ss=="NE")sts=2,search(sta,stb,2); 102 else if(ss=="NW")sts=4,search(sta,stb,4); 103 else if(ss=="SE")sts=3,search(sta,stb,3); 104 else if(ss=="SW")sts=1,search(sta,stb,1); 105 cout<<(ok==1?(ans/2):ans)<<endl; 106 return 0; 107 }
总结：暴力不能打挂，模板必须理解