[C++知识库] H. Loneliness

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> C++知识库 -> H. Loneliness -> 正文阅读

[C++知识库]H. Loneliness

H. Loneliness

首先，奇数一定无解。
其次，"DRUL"可以减1，"RULD"可以减2。

对于偶数的情况，如果不要求终点，那么构造起来就会比较简单，所以我们考虑移动通过上面两种操作转移起点。

为了使起点移动后方便构造，我们使初值为0。

#pragma GCC optimize("Ofast","inline")

#include<bits/stdc++.h>
using namespace std;

#define BEGIN signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define END return 0;}
#define endl '\n'

#define sqr(x) ((x)*(x))
#define lowbit(x) ((x)&-(x))

typedef long long ll;
typedef unsigned long long ull;

template<class T>void read(T& x)
{
    x=0;int f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
    x*=f;
}//快读

template<class T>void write(T& x)
{
    int num=0;char c[40];
    while(x)c[++num]=(x%10)+48,x/=10;
    while(num)putchar(c[num--]);
}//快写

void solve()
{
    ll n;
    cin >> n;

    if (n & 1)
    {
        cout << -1 << endl;
        return;
    }

    int a[100] = {};
    int top = 0;
    while (n)
    {
        a[++top] = n % 2;
        n /= 2;
    }

    int sum1 = 0;
    for (int i = 1;i <= top;++i)
        sum1 += (a[i] == 1);
    int down = 100 - (top - 1);
    int left = 100 - (sum1 + 1);
    
    // 将初值改为0，并转移起点，保证构造后刚好到达点（100，100）
    cout << "DRUL";
    for (int i = 1;i <= down;++i)cout << 'D';
    for (int i = 1;i <= left;++i)
    {
        cout << "R";
        cout << "RULD";
    }
    
    //  开始构造
    vector<int>ve;
    for (int i = top;i >= 1;--i)
        if (a[i])ve.push_back(i - 1);
    ve.push_back(1);
    cout << 'R';
    for (int i = 0;i < ve.size() - 1;++i)
    {
        while (ve[i] != ve[i + 1])cout << 'D', --ve[i];
        if (i < ve.size() - 2)cout << 'R';
    }
    cout << endl;
}

BEGIN
#ifdef FSLSE
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);

    //  手动修改栈内存
    int size=64<<20;  //  申请64MB栈空间

    //  32位Windows使用
    //  __asm__("movl %0, %%esp\n"::"r"((char*)malloc(size)+size));

    //  Linux以及64位Windows使用
    __asm__("movq %0, %%rsp\n"::"r"((char*)malloc(size)+size));

#endif

    int T, n;
    cin >> T >> n;
    while (T--){
        solve();
    }

#ifdef FSLSE
    exit(0);  //  手动修改栈内存时一定要有exit(0)
#endif
END