题解 | #数字游戏#

该题由于数据比较水，很多不完全的解法也可以通过，经过调查研究，这里写一下较为完整的解法，有遗漏请指正。

记左区间为 $L$ ，右区间为 $R$ 。 $w(r)=10^{i},r\in R,i$ 为 $r$ 的位数。

拼接得到的数为 $n=(l*w(r)+r),l\in L,r\in R$ 。

由模的性质可得，对于 $\forall r\in R$ ，都有 $(l*w(r)+r)\%mod=((l+mod)*w(r)+r)\%mod,l\in L$ ，所以要遍历 $L$ ，最多只需要遍历 $m o d$ 次。

对于 $w (r)$ ，这里直接对 $R$ 分段进行处理，相同位数分为一段。段数最多为r最大位数。

然后遍历简化的 $L$ ，和分出的段，先计算 $t=(l*w(r_f)+r_f)\%mod$ ，其中 $r_{f}$ 为在段首的数， $r_{e}$ 为在段尾的数

若 $t = 0$ ，此时对于 $l$ ，就找到了 $r = r_{f}$ 使 $n\%mod=0$

若 $t\neq0$ ，计算 $n e e d = m o d - t$ 。若 $r_{f} + n e e d > r_{e}$ ，则对于 $l$ ，在该段中找不到 $r$ 使 $n\%mod=0$ 。其中 $n e e d$ 表示要使 $n\%mod=0$ ， $r$ 至少需要比 $r_{f}$ 大多少。反之可以找到 $r = r_{f} + n e e d$ 。

若遍历完所有段，都找不到 $r$ ，则此时的 $l$ 可以使先手必胜。结束所有遍历。

若某段中找到 $r$ ，则先手不能选 $l$ ，进行遍历下一个 $l$ 。

若遍历完所有 $l$ ，都没有找到 $l$ 使先手必胜，则先手必败。

时间复杂度为 $mod*(i_{R_2}-i_{L_2}+1)$ ，其中 $i_{L_2},i_{R_2}$ 为 $L_{2}, R_{2}$ 的位数

AC代码如下：

#include <iostream>
using namespace std;

typedef long long ll;

typedef struct Seg{
	ll w;
	ll lef;
	ll rig;
}Seg;

int main(){
	int T;
	cin>>T;
	while(T--){
		ll L1,R1,L2,R2,mod;
		cin>>L1>>R1>>L2>>R2>>mod;
		
		R1=min(R1,L1+mod-1);//多于mod的部分重复了 
		
		//按位数分割 
		Seg seg[15];ll cnt=0;
		for(ll i=1,w=1;i<=10;i++,w*=10){
			if((w<=R2)&&(w*10-1>=L2)){//有交集 
				seg[cnt].w=w;
				seg[cnt].lef=max(w,L2);
				seg[cnt].rig=min(w*10-1,R2);
				++cnt;
			}
		}
		
		ll i=L1;
		for(;i<=R1;i++){
			int fg=false;
			for(ll j=0;j<cnt;j++){
				ll t=i*seg[j].w+seg[j].lef;//使用段的第一个值计算余数 
				if(t%mod!=0 && seg[j].lef+(mod-t%mod)>seg[j].rig){//余数为0直接找到，不为0通过计算范围判断是否能找到 
					;//该段中找不到使余数为零 
				}else{
					fg=true;//找到了使余数为零的数，有某一段找到即可break 
					break;
				} 
			}
			if(fg){
				//此时不能选i，继续寻找 
			}else{
				break;//找到了i，使对方无法找到使余数为零的数，break 
			} 
		}
		if(i>R1){//不存在i 
			cout<<"LOSE"<<endl;
		}else{
			cout<<"WIN"<<endl;
		}
	}
	return 0;
}