求助昨晚的F
  • 板块学术版
  • 楼主Aisaka_Taiga
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/10/29 08:52
  • 上次更新2023/11/2 10:58:36
查看原帖
求助昨晚的F
526519
Aisaka_Taiga楼主2023/10/29 08:52

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
*/
2023/10/29 08:52
加载中...