题目

ABC221G

大意是你初始在\((0,0)\)，给你一个目标点\((X,Y)\)和一个序列\(D_i\)，第\(i\)次你可以选择上下左右四个方向中的一个前进\(D_i\)个单位，问是否可以到达\((X,Y)\)。

Sol

直接做显然不好做。

考虑转化：把坐标系顺时针旋转\(45\)度，目标点坐标变为\((\dfrac{X+Y}{2},\dfrac{Y-X}{2})\)。

发现现在横纵坐标可以分别考虑，也就是说问题变为给你一个序列\(D_i\)，求序列\(x_i\in\{1,-1\}\)，使得：

\[\sum\limits D_ix_i=w(w=\dfrac{X+Y}{2}/ \dfrac{Y-X}{2}) \]

可以分开讨论。

再进行一个转化：设\(\sum D_i=S\)，求出序列\(x_i\)等价于在\(D_i\)中选取若干个数，使得\(\sum x_i=\dfrac{S-w}{2}\)

这是一个经典的背包问题。

\(bitset\)优化即可。

总结：解题需要精巧的思路，试错的胆量。

Code

#include<bits/stdc++.h>
#define N (2001)
using namespace std;
int n,A,B,S,d[N],x[N],y[N];
bitset<3600010>f[N];
inline int read(){
	int w=0;
	char ch=getchar();
	while(ch>'9'||ch<'0') ch=getchar();
	while(ch>='0'&&ch<='9'){
		w=(w<<3)+(w<<1)+(ch^48);
		ch=getchar();
	}
	return w;
}
int main(){
	n=read();
	cin>>A>>B;
	f[0][0]=1;
	for(int i=1;i<=n;i++) S+=d[i]=read(),f[i]=((f[i-1]<<d[i])|f[i-1]);
	int S1=S-(A-B),S2=S-(A+B);
	if(S1<0||S2<0||(S1&1)||(S2)&1){puts("No");return 0;}
	if(S1>7200000||S2>7200000){puts("No");return 0;}
	if(!f[n][S1/2]||!f[n][S2/2]){puts("No");return 0;}
	S1>>=1,S2>>=1;
	for(int i=n;i>=1;i--){
		if(S1>=d[i]&&f[i-1][S1-d[i]]) S1-=d[i],x[i]=0;
		else x[i]=1;
		if(S2>=d[i]&&f[i-1][S2-d[i]]) S2-=d[i],y[i]=0;
		else y[i]=1;
	}
	puts("Yes");
	for(int i=1;i<=n;i++){
        //最后记得转回来
		if(x[i]&&y[i]) putchar('R');
		if(x[i]&&!y[i]) putchar('D');
		if(!x[i]&&y[i]) putchar('U');
		if(!x[i]&&!y[i]) putchar('L');
	}
	puts("");
	return 0;
}

完结撒花❀