题解 P3277 【[SCOI2011]飞镖】

# 恶心的模拟 只是思路难想一点，其他都还好做的 本文参考了网上的题解，可能会有点雷同 ------------ # 思路： - ### 我们先不考虑取中间大小红心的情况 那么我们发现，对于在$2*k+3*k$以内的除了$2*k+3*k-1$这个数的数，我们都可以用两次投镖来得到 - ### 证明： $1.\ \ \ 2*k+3*k-1$，即：$2*(k+1)-3*(k-1)$ 但是我们只能取$[1,k]$之间的数，而$k+1$越界了，所以不能被两次投镖表示 $2.\ \ \ 2*k+3*k-2$，即：$2*(k-1)+3*k$，可以用两次投镖表示 $3.\ \ \ 2*k+3*k-3$，即：$2*k+3*(k-1)$，可以用两次投镖表示 $4.\ \ \ 2*k+3*k-4$，即：$2*(k-2)+3*k$，可以用两次投镖表示 此后每$5$个一个循环，都可以被两次投镖（一次投双倍，一次投三倍）表示出来（也有特例：$1$） 那么大于$2*k+3*k$的数就只能把两个数都取三倍了，也就是$3*a+3*b$来表示 - ### 考虑加入取红心的情况 我们列出每种情况，下文的$i$表示$[1,k]$的$1-3$倍,$|$表示最后一个选的是什么，前两个顺序随意: $1.m\ i\ |\ i$ $2.2m\ i\ |\ i$ $3.m\ m\ |\ i$ $4.m\ 2m\ |\ i$ $5.2m\ 2m\ |\ i$ $6.i\ i\ |\ 2m$ $7.m\ i\ |\ 2m$ $8.2m\ i\ |\ 2m$ $9.m\ m\ |\ 2m$ $10.m\ 2m\ |\ 2m$ $11.2m\ 2m\ |\ 2m$ 十一种情况怎么来的就不用说了吧，要记得最后一个要是双倍这个限制 那么，我们对上面十一种分一下类来讨论 $A.\ 1\ 2$ $B.\ 3\ 4\ 5$ $C.\ 6$ $D.\ 7\ 8$ $E.\ 9\ 10\ 11$ - 对于$A$类，我们把要得到的分数$x-m$或者$x-2m$ 然后，因为最后一次取一定要取双倍，所以我们用$2*a+3*b$来判断能否被表示出来，注意减完不能为$0$ - 对于$B$类，我们把$x-2m$或者$x-3m$或者$x-4m$,看看减完后是不是$2$的倍数，并且在$2k$范围之内 - 对于$C$类，我们把$x-3m$后，看看能否用$2a+3b$或者$3a+3b$表示出来 - 对于$D$类，我们把$x-3m$或者$x-4m$后，看看是否是$[1,k]$中某个数本身或者两倍或者三倍 - 对于$E$类，我们直接判断$x$是不是$4m$,$5m$,$6m$ ------------ 接下来是美滋滋的代码时间~~~ ~~~cpp #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define N 7 #define ll long long using namespace std; int T; ll ans,k,m,x,k1,m1,x1; ll a[N],b[N],c[N],d[N]; bool Check1() { ll kx=k; if(x-k*2<=k*3+k*2&&x-k*2!=k*3+k*2-1) return 1; while((x-kx*2)%3!=0) kx--; if((x-kx*2)<=k*6) return 1; return 0; } bool Check2(ll now) { if(now<2) return 0; if(now<=k*3+k*2&&now!=k*3+k*2-1) return 1; return 0; } bool Check3(ll now) { if(now>=0&&now%2==0&&now/2<=k) return 1; return 0; } bool Check4(ll now) { if(now<0) return 0; ll kx=k; if(now<=k*3+k*2&&now!=k*3+k*2-1) return 1; if(now%3==0&&now<=k*6) return 1; return 0; } bool Check5(ll now) { if(now<0) return 0; if(now%3==0&&now/3<=k) return 1; if(now%2==0&&now/2<=k) return 1; if(now<=k) return 1; return 0; } int main() { scanf("%d",&T); scanf("%lld%lld%lld%lld%lld",&a[1],&b[1],&c[1],&d[1],&k); scanf("%lld%lld%lld%lld%lld",&a[2],&b[2],&c[2],&d[2],&m); scanf("%lld%lld%lld%lld%lld",&a[3],&b[3],&c[3],&d[3],&x); for(int i=1;i<=T;++i) { if(Check1()) ++ans; else if(Check2(x-m)||Check2(x-2*m)) ++ans; else if(Check3(x-2*m)||Check3(x-3*m)||Check3(x-4*m)) ++ans; else if(Check4(x-2*m)) ++ans; else if(Check5(x-3*m)||Check5(x-4*m)) ++ans; else if(x==4*m||x==5*m||x==6*m) ++ans; k1=(k*k)%d[1]; k=((k1*a[1])%d[1]+(k*b[1])%d[1]+c[1])%d[1]; m1=(m*m)%d[2]; m=((m1*a[2])%d[2]+(m*b[2])%d[2]+c[2])%d[2]; x1=(x*x)%d[3]; x=((x1*a[3])%d[3]+(x*b[3])%d[3]+c[3])%d[3]; k+=20; m+=20; x+=20; } printf("%lld",ans); } ~~~