nywOJ15 114 514 题解

题目链接：114 514

题意：

ty 想通过 114514 凑成别的数字, 比如

$$6=+1+1-4+5-1+4$$

ty 想在 至少一个连续 的 114514 拼接成的字符串的 每一位 前添加 + 或 - 号使得计算结果为 $X$ 。

输入格式：

第一行输入 $T$ 表示有 $T$ 组询问。

接下来 $T$ 行，每行一个整数表示 $X$ 。

输出格式：

共 $T$ 行，每行一个字符串

设每次询问输出字符串长度为 $L$， 你要保证 $12\le L\le 1.2\times 10^6$ 。

若在长度限制内有解，输出任意解即可，若在长度限制内无法凑出 $X$，输出 114514 。

数据范围：

$T \le 50, -114^{514} \le X \le 114^{514}$

居然写了好多遍才过 $😡$ 。

先打个表把 114514 的所有可能情况枚举出来，发现 $[-16,16]$ 的偶数都可以表示

那么总字符数 $= 12\left(\left\lfloor\frac{X}{16}\right\rfloor + X \bmod 16\right)$ ，把瞎七搭八边界判一判就好了

时间复杂度 $\mathcal{O}(T\log_{16} 1.6\times 10^6)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())

string ans[55];
void solve()
{
    string s; cin >> s;
    if((s[0] != '-' && s.size() > 7) || (s[0] == '-' && s.size() > 8)) return cout << "114514\n", void(0);
    int n = stoll(s); if(n > 1600000 || n < -1600000) return cout << "114514\n", void(0);
    if(n == 0) return cout << ans[0 + 18] << '\n', void(0);
    if(n > 0)
    {
        if(n & 1) return cout << "114514\n", void(0);
        int t = n / 16, r = n % 16;
        for(int i = 1; i <= t; i++) cout << ans[16 + 18];
        if(r != 0) cout << ans[r + 18] << '\n'; else cout << '\n';
    }else
    {
        n = -n; if(n & 1) return cout << "114514\n", void(0);
        int t = n / 16, r = n % 16;
        for(int i = 1; i <= t; i++) cout << ans[-16 + 18];
        if(r != 0) cout << ans[-r + 18] << '\n'; else cout << '\n';
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    ans[0 + 18] = "+1+1-4+5+1-4";
    ans[2 + 18] = "+1-1+4-5-1+4"; ans[-2 + 18] = "+1+1+4-5+1-4";
    ans[4 + 18] = "+1+1+4-5-1+4"; ans[-4 + 18] = "+1+1-4-5-1+4";
    ans[6 + 18] = "+1+1+4+5-1-4"; ans[-6 + 18] = "+1-1+4-5-1-4";
    ans[8 + 18] = "+1+1-4+5+1+4"; ans[-8 + 18] = "-1-1+4-5-1-4";
    ans[10 + 18] = "-1-1+4+5-1+4"; ans[-10 + 18] = "+1+1-4-5+1-4";
    ans[12 + 18] = "+1-1+4+5-1+4"; ans[-12 + 18] = "-1+1-4-5+1-4";
    ans[14 + 18] = "+1+1+4+5-1+4"; ans[-14 + 18] = "-1-1-4-5+1-4";
    ans[16 + 18] = "+1+1+4+5+1+4"; ans[-16 + 18] = "-1-1-4-5-1-4";
    int qwq; cin >> qwq; while(qwq--) solve();
    return 0;
}