E
首先发现无论何时，每个位置上至多只会有一个球。原因：每个时刻每个球都会移动，所以移动到某个点的时间一定，自然出生时间也一定，显然不可能会有 2 个点出生时间相同。
既然如此，假如 \(t\) 时刻某个位置有一个，那么显然它会在下个时刻到达 \(a\) 方向的点，那么下一个点到达这个位置的话，它会去与 \(a\) 相反的方向。这一步很厉害啊！要是分析到的话基本十拿九稳了。
那么既然如此，显然记录前缀时间在某个位置的球数前缀和之后 \(O(n^2)\) 转移。
这一步的思考来源于直接记录某个时刻的肯定不行，考虑前缀时刻的相减性，以及前缀时间的可转移性。
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define il inline
using namespace std;
const int N=123;
int a[N][N],b[N][N],n=120;
il int CEIL(int x) {
if(x%2==0) return x/2;
return x/2+1;
}
il int FLOOR(int x) {
return x/2;
}
int sol(int t,int x,int y) {
// cout<<"nex\n";
int qwq=x-1+y-1,s=t-qwq;
if(s<0) {
return 0;
}
// cout<<qwq<<" "<<s<<" "<<t<<" "<<x<<" "<<y<<'\n';
memset(a,0,sizeof(a));
a[1][1]=s+1;
// for(int i=1;i<=x;i++)
// for(int j=1;j<=y;j++) b[i][j]=0;
// for(int nw=1;nw<=qwq;nw++) {
// memset(b,0,sizeof(b));
for(int i=1;i<=x;i++) {
for(int j=1;j<=y;j++) {
a[i][j+1]+=(a[i][j]+1)/2;
a[i+1][j]+=a[i][j]/2;
// a[i][j]+=b[i][j];
}
}
// ++a[1][1];
// }
return a[x][y];
}
void solve() {
int t,x,y; cin>>t>>x>>y;
++x; ++y;
if(sol(t,x,y)!=sol(t-1,x,y)) cout<<"YES\n"; else cout<<"NO\n";
}
signed main() {
cin.tie(0); ios::sync_with_stdio(false);
int T; cin>>T; while(T--) solve();
return 0;
}
D
分析操作，典型套路确定每个位置操作奇偶性。
考虑显然最后有合法方案的当且仅当偶数个奇。
显然奇偶这个操作只会在为了 2 个奇使用相邻变换时使用。
偶偶显然废的。
所以仅考虑奇奇即可，即保留所有需要操作奇数的位置。我们发现假如相邻操作花费更少，这个的上界是确定的，我们一定可以通过 4 个分一组来实现全用这种操作。
否则的话，考虑一定当前剩余的是一段区间，不妨设挖空区间中间的 2 个，显然不会更优之类的。
#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int N=5002;
bool a[N],b[N];
int n,cx,cy,vec[N],f[N][N],tot;
inline int get(int x,int y) {
bool fl=0;
if(abs(x-y)==1) fl=1;
x=vec[x]; y=vec[y];
if(x>y) swap(x,y);
if(x+1==y) return min(cx,2*cy);
int qwq=cy;
if(fl) qwq=min(qwq,1ll*(y-x)*cx);
return qwq;
}
int dfs(int l,int r) {
if(~f[l][r]) return f[l][r];
if(l>r) return 0;
int qwq=(int)(2e18);
qwq=min(qwq,dfs(l+2,r)+get(l+1,l));
qwq=min(qwq,dfs(l+1,r-1)+get(r,l));
qwq=min(qwq,dfs(l,r-2)+get(r-1,r));
// cout<<l<<" "<<r<<" "<<qwq<<'\n';
return f[l][r]=qwq;
}
void sol() {
cin>>n>>cx>>cy;
for(int i=1;i<=n;i++) {
char ch; cin>>ch; a[i]=ch-'0';
}
for(int i=1;i<=n;i++) {
char ch; cin>>ch; b[i]=ch-'0';
}
tot=0;
for(int i=1;i<=n;i++) {
if(a[i]!=b[i]) {
vec[++tot]=i;
// cout<<i<<' ';
}
}
if(tot&1) {
cout<<"-1\n"; return ;
}
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)
f[i][j]=-1;
// cout<<get(1,4)<<' '<<get(2,3)<<" mmm "<<get(1,3)<<'\n';
if(cy<=cx&&tot>2) {
cout<<(tot/2)*cy<<'\n'; return ;
}
cout<<dfs(1,tot)<<"\n";
}
signed main() {
cin.tie(0); ios::sync_with_stdio(false);
int T; cin>>T; while(T--) sol();
return 0;
}