P9714「QFOI R1」摸摸
CJ_Fu
·
·
个人记录
洛谷
题意
给定一个序列 a（初始全为 0）和一个序列 t，求是否可以通过以下两种操作使 a 变成 b（序列长度均为 n）：
## 思路
考虑操作 1，容易证明只执行一次是没有影响的，因为因为执行 $k$ 次会让 $t$ 变成 $2^{k-1}(t+t')$，与先执行操作 1 一次再执行操作 2 $2^k$ 次没有区别。
于是就有这么一个想法：先加 $t$ $k_1$ 次，再加 $t+t'$ $k_2$ 次，枚举 $k_1,k_2(0\le k_1\le \left\lfloor\frac{\max b}{\min t}\right\rfloor,0\le k_2\le \left\lfloor\frac{\max b}{\min 2t}\right\rfloor)$，一定能符合要求或判断无解。
时间复杂度 $O(n\left\lfloor\frac{\max b}{\min t}\right\rfloor^2)$，赛时草过去了。
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,b[2003],t[2003],tt[2003],T,mb,mt=3235345;
void frdsgesgh(){
cin>>n;
for(int i=1;i<=n;i++) cin>>t[i];
for(int i=1;i<=n;i++) cin>>b[i],tt[i]=t[i]+t[n-i+1];
for(int i=0;i<=2000;i++){
for(int j=0;j<=1000;j++){
bool f=1;
for(int k=1;k<=n;k++)
if(t[k]*i+tt[k]*j!=b[k]){ f=0; break; }
if(f){ cout<<"YeS\n"; return; }
}
}
cout<<"nO\n";
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>T;
while(T--)frdsgesgh();
return 0;
}
```
即判断 $k_1t+k_2(t+t_1)=b$ 是否存在即可，应该有更快的做法。