rt,思路是把影响横纵坐标的元素拆成两个数组然后折半搜索看能不能凑出横纵坐标值。
测评记录:https://atcoder.jp/contests/abc326/submissions/47053248
#include <bits/stdc++.h>
#define int long long
#define N 1100
using namespace std;
inline int read()
{
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -1; c = getchar();}
while(c <= '9' && c >= '0') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return x * f;
}
int n, X, Y, a[N], a1[N], a2[N], m1, m2, now1, now2, A1, A2;
unordered_map<int, int> mp;
inline void dfs1(int x, int sum)
{
// cout << "sum1 : " << sum << endl;
if(x == m1 / 2 + 1) return mp[sum] = (A1 | (1ll << 50)), void();
A1 |= (1 << x);
dfs1(x + 1, sum + a1[x]);
A1 ^= (1 << x);
dfs1(x + 1, sum - a1[x]);
return ;
}
inline void dfs2(int x, int sum)
{
// cout << "sum2 : " << sum << endl;
if(x == m1 + 1)
{
if(mp[Y - sum]) now1 = (A2 | mp[Y - sum]);
// cout << " S SD: " << Y - sum << " : " << mp[Y - sum];
return ;
}
A2 |= (1 << x);
dfs2(x + 1, sum + a1[x]);
if(now1) return ;
A2 ^= (1 << x);
dfs2(x + 1, sum - a1[x]);
return ;
}
inline void dfs3(int x, int sum)
{
if(x == m2 / 2 + 1) return mp[sum] = (A1 | (1ll << 50)), void();
A1 |= (1 << x);
dfs3(x + 1, sum + a2[x]);
A1 ^= (1 << x);
dfs3(x + 1, sum - a2[x]);
return ;
}
inline void dfs4(int x, int sum)
{
if(x == m2 + 1)
{
if(mp[X - sum]) now2 = (A2 | mp[X - sum]);
return ;
}
A2 |= (1 << x);
dfs4(x + 1, sum + a2[x]);
if(now2) return ;
A2 ^= (1 << x);
dfs4(x + 1, sum - a2[x]);
return ;
}
inline void print(int x)
{
while(x)
{
cout << ((x & 1) ? 1 : 0);
x /= 2;
}
cout << endl;
return ;
}
signed main()
{
n = read(), X = read(), Y = read();
for(int i = 1; i <= n; i ++)
{
a[i] = read();
if(i & 1) a1[++ m1] = a[i];
else a2[++ m2] = a[i];
}
// for(int i = 1; i <= m1; i ++) cout << a1[i] << " "; cout << endl;
// for(int i = 1; i <= m2; i ++) cout << a2[i] << " "; cout << endl;
dfs1(1, 0);
dfs2(m1 / 2 + 1, 0);
mp.clear();
A1 = A2 = 0;
if(m2 != 0) dfs3(1, 0);
// cout << "cao" << endl;
dfs4(m2 / 2 + 1, 0);
// print(now1);
// print(now2);
if(now1 == 0 || now2 == 0) return cout << "No" << endl, 0;
cout << "Yes" << endl;
int t = 1, ss1 = 0, ss2 = 0;
for(int i = 1; i <= n; i ++)
{
if(i & 1)
{
int k = (i % 2 == 0 ? i / 2 : i / 2 + 1);
if(t == 1)
{
if(now1 & (1 << k)) t = 2, cout << "L";
else t = 4, cout << "R";
}
else if(t == 3)
{
if(now1 & (1 << k)) t = 2, cout << "R";
else t = 4, cout << "L";
}
if(now1 & (1 << k)) ss1 += a1[k];
else ss1 -= a1[k];
}
else
{
int k = (i % 2 == 0 ? i / 2 : i / 2 + 1);
if(t == 2)
{
if(now2 & (1 << k)) t = 1, cout << "R";
else t = 3, cout << "L";
}
if(t == 4)
{
if(now2 & (1 << k)) t = 1, cout << "L";
else t = 3, cout << "R";
}
if(now2 & (1 << k)) ss2 += a2[k];
else ss2 -= a2[k];
}
}
// cout << endl;
// cout << ss1 << endl;
// cout << ss2 << endl;
return 0;
}
/*
6 0 9
1 2 3 4 5 6
*/