玄妙的方程 ------ P9714
MoCaRabbit
·
·
题解
此题我们发现最多做一次操作一。
因为做了一次操作一之后 t 将会是对称的。
如果再做一次的话，那么 t 数组将会被整体乘 2。
是没有意义的。
于是问题被转化为了。
列出 $n$ 个条件等式。
$x \times t_i + y \times t'_i=b_i$。
现在问题被转化为了找到一组 $x,y$ 使这 $n$ 个等式成立。
我们可以暴力枚举判断。
时间复杂度 $O(nw^2)$。
其中 $w$ 为值域。
能得 80 分。
前四个点因为 $T$ 太大而 $TLE$。
我们可以枚举 $x$ 进而可以通过其中一组等式求出 $y$。
如果 $y$ 是小数或者负数，肯定不行。
时间复杂度 $O(nw)$。
可以通过。
代码。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
int t1[signed(2e3)+10],t2[signed(2e3)+10];
int b[signed(2e3)+10];
inline void solve(){
cin>>n;
for(int i=1;i<=n;i++) cin>>t1[i];
for(int i=1;i<=n;i++)
t2[i]=t1[i]+t1[n-i+1];//计算t'
for(int i=1;i<=n;i++) cin>>b[i];
bool flag=0;
for(int i=0;i<=2e3;i++){
bool p=1;
int j=0;
if((b[n]-i*t1[n])%t2[n]!=0) continue;//判断y是否是小数
else j=(b[n]-i*t1[n])/t2[n];
if(j<0) continue;
for(int k=1;k<=n;k++)
if(i*t1[k]+j*t2[k]!=b[k]){//判断成不成立
p=0;
break;
}
if(p){
flag=1;
break;
}
}
if(flag) cout<<"yEs\n";
else cout<<"nO\n";
}
signed main() {
int t;
cin>>t;
while(t--) solve();
return 0;
}
```
当然有 $O(n)$ 的解方程。
我这个蒟蒻没写出来。
此做法惊艳了我旁边的两位暴力哥。