P3277 [SCOI2011]飞镖 题解

发布时间 2023-10-02 20:21:50作者: yanghanyv

此题是极其恶心的大分类讨论。

结论

首先我们可以发现一个重要的结论,在用两镖只打数字的情况下,可以拼出 \(0\)\(5k\) 中除了 \(5k-1\) 的所有值,以及 \(0\)\(6k\) 中一些不连续的 \(3\) 的倍数
证明:
\(0\)\(5k\)\(5k-1=2(k+1)+3(k-1)\),由于其中有 \(k+1\) 所以是无法拼出的,其他值可以写成类似形式,所以可以拼出。
对于分值 \(5k<s\leq 6k\) ,只要满足 \(s\)\(3\) 的倍数就可以拼出。

分类标准

可以发现关于红心的条件显得很突兀,所以对红心的个数和位置进行分类。
为了描述方便,我们用 \(x/y+z/w(x+y=2,z+w=1)\) 来表示前两镖有 \(x\) 次数字,\(y\) 次红心,最后一镖有 \(z\) 次数字,\(w\) 次红心。

  1. \(2/0+1/0\)
    这是最复杂的情况,考虑再分为两类:
    • 小于两次三倍区:将前两镖结合,套用结论。
    • 两次三倍区:将前两镖中的一次三倍与最后一镖的两倍结合,套用结论。
  2. \(1/1+1/0\)
    只需检查 \(x-2m\) 是否为 \(2\)\(5k\) 中除了 \(5k-1\) 的所有值。
  3. \(0/2+1/0\)
    只需检查 \(x-0/m/2m/3m/4m\) 是否为 \(2t(1\leq t\leq k,t\in \mathbb{Z})\)
  4. \(2/0+0/1\)
    只需检查 \(x-2m\) 是否为 \(0\)\(5k\) 中除了 \(5k-1\) 的所有值或 \(0\)\(6k\)\(3\) 的倍数。
  5. \(1/1+0/1\)
    只需检查 \(x-2m/3m/4m\) 是否为 \(t/2t/3t(0\leq t\leq k,t\in \mathbb{Z})\)
  6. \(0/2+0/1\)
    只需检查 \(x-2m/3m/4m/5m/6m\) 是否等于 \(0\)

至此,分类讨论就结束了。如果觉得很复杂可以看代码。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int t,ans;
ll a1,b1,c1,d1,k,a2,b2,c2,d2,m,a3,b3,c3,d3,x;
bool flag;
bool check1(ll v){//2/0+1/0
	bool res=0;
	res=res||((v-5*k)%2==0&&v-5*k>=2&&v-5*k<=2*k)||(v-5*k+2<=2*k&&v>=2);//2+?+3
	res=res||((v-5*k)%3==0&&v-5*k>=0&&v-5*k<=3*k)||(v-5*k+2<=3*k&&v-2>=0);//2+3+3
	return res;
}
bool check2(ll v){//1/1+1/0
	return v>=2&&v<=5*k&&v!=5*k-1;
}
bool check3(ll v){//0/2+1/0
	return v>=2&&v%2==0&&v<=2*k;
}
bool check4(ll v){//2/0+0/1
	return v>=0&&((v<=5*k&&v!=5*k-1)||(v%3==0&&v<=6*k));
}
bool check5(ll v){//1/1+0/1
	return v>=0&&(v<=k||(v%2==0&&v<=2*k)||(v%3==0&&v<=3*k));
}
bool check6(ll v){//0/2+0/1
	return !v;
}
int main(){
	scanf("%d",&t);
	scanf("%lld%lld%lld%lld%lld",&a1,&b1,&c1,&d1,&k);
	scanf("%lld%lld%lld%lld%lld",&a2,&b2,&c2,&d2,&m);
	scanf("%lld%lld%lld%lld%lld",&a3,&b3,&c3,&d3,&x);
	while(t--){
		flag=0;
		flag=flag||check1(x);
		flag=flag||check2(x)||check2(x-m)||check2(x-2*m);
		flag=flag||check3(x)||check3(x-m)||check3(x-2*m)||check3(x-3*m)||check3(x-4*m);
		flag=flag||check4(x-2*m);
		flag=flag||check5(x-2*m)||check5(x-3*m)||check5(x-4*m);
		flag=flag||check6(x-2*m)||check6(x-3*m)||check6(x-4*m)||check6(x-5*m)||check6(x-6*m);
		ans+=flag;
		k=(a1*k%d1*k%d1+b1*k%d1+c1)%d1+20;
		m=(a2*m%d2*m%d2+b2*m%d2+c2)%d2+20;
		x=(a3*x%d3*x%d3+b3*x%d3+c3)%d3+20;
	}
	printf("%d",ans);
	return 0;
}