做题笔记 CF1107A 【Digits Sequence Dividing】

一开始我题目看成每一段的数字之和了。。结果搞了半个多小时///==///

所以这告诉我们要认真读题否则会把一道签到题想成黑题的


首先我们都知道,一个多位数必然比一个一位数大(十进制下,任何一个多位数都可以拆成很多个个位数相加)

所以考虑什么时候无解。仔细思考很容易知道,此情况无解,当且仅当原字符串长度为 2 且第一位比第二位大或等于第二位。

如果不是这种情况那么就可以拆成两部分,第一部分是 \(s_0\) ,剩下的是第二部分。

这么做的道理是,当 s 的长度为 2 的时候,只能拆成两个个位数,那么如果这两个个位数不满足条件,就不行;否则必然能够把 s 拆成 2 个字串,使之满足条件。

参考代码:

#include <iostream>
#include <stdio.h>
#include <string.h>
#define endl "\n"

using namespace std;

string s;
int n;

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n >> s;
        if (n == 2 && s[0] >= s[1])
        {
            cout << "NO" << endl;
            continue;
        }
        cout << "YES" << endl;
        cout << 2 << endl;
        cout << s[0] << ' ';
        for (int i = 1; i < n; i++)
            cout << s[i];
        puts("");
    }
    return 0;
}
上一篇:AtCoder Beginner Contest 159 E - Dividing Chocolate【枚举】


下一篇:728. Self Dividing Numbers*