期望得分: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
",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
",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
",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 }
总结：暴力不能打挂，模板必须理解