期望得分:60+60+60
实际得分:60+60+0
这次考试主要是T3搜索打挂了(我可是靠搜索吃饭的);
1.数组开小了，不过开大数组只拿到了10分的好成绩。
2.题意没审清（其实是他没说清）。
以后搜索不能打打挂了。
T1 方程的解：特判+exgcd
一看题就打了个exgcd，最后把exgcd删了骗了60分
但我们用exgcd是可以做的=_=（废话）。
考虑这个一次函数，然后就把纵截距和斜率一通特判AC >_<
#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(!b)
{
x=;
y=;
return a;
}
ll d=exgcd(b,a%b,x,y);
ll tmp=x;
x=y;
y=tmp-a/b*y;
return d;
}
int main()
{
#define C continue
ll t;
scanf("%lld",&t);
while(t--)
{
ll x,y,a,b,c;
scanf("%lld%lld%lld",&a,&b,&c);
if(!a&&!b)
{
if(!c)puts("ZenMeZheMeDuo");
else puts("");
C;
}
else if(!c)
{
if(!a&&!b)puts("ZenMeZheMeDuo");
else if(a*b>)puts("");
else puts("ZenMeZheMeDuo");
C;
}
else if(!a)
{
if(c%b==&&b&&b*c>)puts("ZenMeZheMeDuo");
else puts("");
}
else if(!b)
{
if(c%a==&&c&&a*c>)puts("ZenMeZheMeDuo");
else puts("");
C;
}
else if(a==&&b==)
{
if(c<=)puts("");
else if(c>)puts("ZenMeZheMeDuo");
else printf("%lld\n",c-);
C;
}
else if(a+b==c){puts("");C;}
else
{
if(a>&&b>&&c<){puts("");C;}
else if(a<&&b<&&c>){puts("");C;}
else
{
if(a<&&b<&&c<)a=-a,b=-b,c=-c;
ll gcd=exgcd(a,b,x,y);
if(c%gcd!=){puts("");C;}
else if(a*b<){puts("ZenMeZheMeDuo");}
else
{
//cout<<x<<endl;
x=(x%b+b)%b;
x*=(c/gcd);
x%=(b/gcd);
if(!x)x+=(b/gcd);
y=(c-a*x)/b;
if(y<=){puts("");continue;}
ll num=y/(a/gcd)+;
if(y%(a/gcd)==)num--;
if(num<=65535ll)printf("%lld\n",num);
else puts("ZenMeZheMeDuo");
}
} }
}
return ;
}
感谢mikufun的AC代码
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了
#include<cstdio>
#include<iostream>
#define MAXN 100005
#define ll long long
#include<cmath>
#define maxn 205
#define mod prime[num]
using namespace std;
ll t,js[MAXN],inv[MAXN],prime[],tot,m,num,w[];
ll abs(ll x)
{
return x<0ll?(-1ll*x):x;
}
ll qpower(ll a,ll b)
{
ll ans=;
while(b)
{
if(b&)ans=ans*a%mod;
a=a*a%mod;
b>>=;
}
return ans%mod;
}
void PP()
{
ll x=m;
for(ll i=;i<=sqrt(m)+;i++)
{
if(x==)break;
if(x%i==)prime[++tot]=i,x/=i;
}
if(x>)prime[++tot]=x;
return ;
}
void exgcd(ll a,ll b,ll &x,ll &y)
{
if(!b)
{
x=;
y=;
return ;
}
exgcd(b,a%b,x,y);
ll tmp=x;
x=y;
y=tmp-a/b*y;
return ;
}
ll crt()
{
ll ans=;
for(ll i=;i<=tot;i++)
{
ll xi=m/prime[i],x,y;
exgcd(xi,prime[i],x,y);
x=(x%prime[i]+prime[i])%prime[i];
ans=(ans+x*w[i]*xi)%m;
}
return ans%m;
}
void pre()
{
js[]=inv[]=;
for(ll i=;i<=min(mod,100000ll);i++)
{
js[i]=js[i-]*i%mod;
inv[i]=qpower(js[i],mod-);
}
return ;
}
ll C(ll n,ll m)
{
if(m==||m==n)return 1ll;
if(m>n)return 0ll;
return js[n]*inv[n-m]%mod*inv[m]%mod;
}
ll lucas(ll n,ll m)
{
if(m==||m==n)return 1ll;
if(m>n)return 0ll;
return C(n%mod,m%mod)*lucas(n/mod,m/mod)%mod;
}
int main()
{
ll a,b,c=,d=,ans=;
scanf("%lld%lld%lld%lld",&t,&m,&a,&b);
a=abs(a);b=abs(b);
if(m==){puts("");return ;}
ll k=t-abs(a)-abs(b);
if(k<||(k&)^){puts("");return ;}
k/=;PP();
for(num=;num<=tot;num++)
{
pre();
for(ll i=;i<=k;i++)
{
a+=i;
c+=i;
b+=(k-i);
d+=(k-i);
(w[num]+=lucas(t,a)*lucas(t-a,b)%mod*lucas(t-a-b,c)%mod*lucas(t-a-b-c,d)%mod)%=mod;
a-=i;
c-=i;
b-=(k-i);
d-=(k-i);
}
}
printf("%lld\n",crt());
return ;
}
T3 光：模拟+二分优化
我感觉这个题就是sb
但是不管怎么说，代码能力是很重要的一部分。
这个题有几个引理值得一提：
1.对于一个格子来说，之可能被（东南&&西北）||（东北&&西南）经过 证明：光线每次移动，其（x+y）||（x-y）奇偶性不变
我们可以画一个形象的图（自行）理解一下。
2.光线的碰撞反射次数只与n，m，k线性相关，这就不用我证明了叭。
3.光线的路径一定是一个环，所以它一定会回到初始状态，这可以作为终止边界。
在用。。。就是细心，耐心和lower_bound,upper_bound的应用了。
#include<bits/stdc++.h>
#define MAXN 200500
#define ll long long
#define mp make_pair
using namespace std;
vector<int>v1[MAXN*],v2[MAXN*];
map< pair<int,int>,bool >py;
ll ans;int n,m,k,sta,stb,sts,nn=,tot;
bool ok=,Getans=;
void search(int x,int y,int now)// 1 youshang 2 zuoxia 3 youxia 4 zuoshang
{
if(Getans)return ;
if(now==)
{
int id=x+y;bool za=,zb=;
int nxtx=(*--upper_bound(v1[id].begin(),v1[id].end(),x))+;
int nxty=id-nxtx;
if(sta+stb==id&&sta>=nxtx&&sta<=x&&sts==){nn++;if(nn!=){ans+=abs(sta-x);Getans=;return ;}}
ans+=abs(x-nxtx)+;
if(py[mp(nxtx,nxty+)])za=;if(py[mp(nxtx-,nxty)])zb=;
if(!za&&zb)search(nxtx,nxty+,);
else if(za&&!zb)search(nxtx-,nxty,);
else if(!za&&!zb){ok=;search(nxtx,nxty,);}
else {ok=;search(nxtx,nxty,);}
return ;
}
if(now==)
{
int id=x+y;bool za=,zb=;
int nxtx=(*upper_bound(v1[id].begin(),v1[id].end(),x))-;
int nxty=id-nxtx;
if(sta+stb==id&&sta>=x&&sta<=nxtx&&sts==){nn++;if(nn!=){ans+=abs(sta-x);Getans=;return ;}}
ans+=abs(x-nxtx)+;
if(py[mp(nxtx+,nxty)])za=;if(py[mp(nxtx,nxty-)])zb=;
if(!za&&zb)search(nxtx+,nxty,);
else if(za&&!zb)search(nxtx,nxty-,);
else if(!za&&!zb){ok=;search(nxtx,nxty,);}
else {ok=;search(nxtx,nxty,);}
return ;
}
if(now==)
{
int id=x-y+m+;bool za=,zb=;
int nxtx=(*upper_bound(v2[id].begin(),v2[id].end(),x))-;
int nxty=nxtx+m+-id;
if(sta-stb+m+==id&&sta<=nxtx&&sta>=x&&sts==){nn++;if(nn!=){ans+=abs(sta-x);Getans=;return ;}}
ans+=abs(x-nxtx)+;
if(py[mp(nxtx+,nxty)])za=;if(py[mp(nxtx,nxty+)])zb=;
if(!za&&zb)search(nxtx+,nxty,);
else if(za&&!zb)search(nxtx,nxty+,);
else if(!za&&!zb){ok=;search(nxtx,nxty,);}
else {ok=;search(nxtx,nxty,);}
return ;
}
if(now==)
{
int id=x-y+m+;bool za=,zb=;
int nxtx=(*--upper_bound(v2[id].begin(),v2[id].end(),x))+;
int nxty=nxtx+m+-id;
if(sta-stb+m+==id&&sta>=nxtx&&sta<=x&&sts==){nn++;if(nn!=){ans+=abs(sta-x);Getans=;return ;}}
ans+=abs(x-nxtx)+;
if(py[mp(nxtx-,nxty)])za=;if(py[mp(nxtx,nxty-)])zb=;
if(!za&&zb)search(nxtx-,nxty,);
else if(za&&!zb)search(nxtx,nxty-,);
else if(!za&&!zb){ok=;search(nxtx,nxty,);}
else {ok=;search(nxtx,nxty,);}
return ;
}
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
while(k--)
{
int a,b;
scanf("%d%d",&a,&b);
v1[a+b].push_back(a);
v2[a-b+m+].push_back(a);
py[mp(a,b)]=;
}
for(int i=;i<=n+;i++)
{
v1[i].push_back(i);
v2[i+m+].push_back(i);
v1[i+m+].push_back(i);
v2[i].push_back(i);
py[mp(i,)]=;py[mp(i,m+)]=;
}
for(int i=;i<=m+;i++)
{
v1[i].push_back();
v2[m+-i].push_back();
v1[i+n+].push_back(n+);
v2[n+-i+m+].push_back(n+);
py[mp(,i)]=;py[mp(n+,i)]=;
}
for(int i=;i<=n+m+;i++)sort(v1[i].begin(),v1[i].end());
for(int i=;i<=n+m+;i++)sort(v2[i].begin(),v2[i].end());
string ss;
cin>>sta>>stb>>ss;
if(ss=="NE")sts=,search(sta,stb,);
else if(ss=="NW")sts=,search(sta,stb,);
else if(ss=="SE")sts=,search(sta,stb,);
else if(ss=="SW")sts=,search(sta,stb,);
cout<<(ok==?(ans/):ans)<<endl;
return ;
}
总结：暴力不能打挂，模板必须理解