【Codeforces1109B_CF1109B】Sasha and One More Name(字符串)

题目:

Codeforces1109B

我打的是 Div2 ,所以我看到的题号实际上是 1113D ……

考场上傻了没敢大力猜结论没做出来这道题,不幸掉分…… 1869->1849 嘤嘤嘤

翻译:

读书是萨沙的爱好之一。有一次,他读书时了解到一个不同寻常的角色。这个角色这样介绍自己:“我在不同的地方有不同的名字。在精灵中叫米斯兰迪尔;在小矮人中叫塔空;在被遗忘的西方,幼年的我叫欧络因;在南方叫因卡诺斯;在北方叫甘道夫;至于东方,我没有去过。”

那时,萨沙想,这个角色在东方被怎样称呼?在东方,所有的名字都是回文串。如果一个字符串从前向后读和从后向前读是完全相同的,那么它是一个回文串。例如,像 "kazak", "oo" 和 "r" 这样的字符串是回文串,而 "abb" 和 "ij" 不是。

萨沙相信这个英雄将因东方的一个神而得名。为了避免有两个相同的名字,东方人会做如下的事:他们把原本的名字写在一张纸上,然后把纸剪 \(k\) 次,得到 \(k+1\) 张写有原串的子串的纸。接着,把这些纸拼在一起得到一个新字符串。纸不能翻转,只能打乱。

通过这种方式,可以把字符串 f|de|abc|g 剪 \(3\) 次后得到 abcdefg (交换 f 和 abc )。以相同的裁剪方式无法得到字符串 cbadefg 。

更形式化地,萨沙想为给定的字符串 \(s\) 找一个最小的 \(k\) ,你可以把它剪成 \(k+1\) 个部分,再把它们拼成一个与 \(s\) 不同的新回文串。如果无解,输出 "Impossible"(不含引号)。

输入

第一行包含一个字符串 \(s(1\leq |s| \leq 5000)\) ——初始的名字,只包含小写拉丁字母。保证 \(s\) 是回文串。

输出

输出一个整数 \(k\) ——获得新名字所需裁剪次数的最小值,或 "Impossible"(不含引号)。

分析:

论大胆猜结论的重要性……

结论:无解的充要条件是 \(s\) 中对称轴任意一侧的所有字母均相同。如果有解,则解不超过 \(2\) 。

证明:

先看前半句。充分性显然(长度为偶数相当于所有字母都一样;长度为奇数相当于除了对称轴所有字母都一样,此时对称轴字母是唯一的肯定不能动。剩下所有字母都相同怎么排都是一样的啊qwq)。必要性考虑构造。如果有解,则一定存在一个长度不超过一半的前缀 \(pre\) 满足 \(pre\) 不是回文串。设与 \(pre\) 长度一致的后缀为 \(suf\) ,则在 \(pre\) 后和 \(suf\) 前各剪一刀,然后交换 \(pre\) 和 \(suf\) ,则一定是一个与原串不同的新回文串。因此一定有解,且解不超过 \(2\) 。

于是暴力 \(O(n^2)\) 判断一下能不能只剪一刀,也就是把一个前缀挪到后面得到合法的字符串即可。

代码:

#include <string>
#include <iostream>
using namespace std;

namespace zyt
{
    string s;
    bool check(const string s)
    {
        for (int i = 0; i < (s.size() >> 1); i++)
            if (s[i] != s[0])
                return true;
        return false;
    }
    bool is_palindrome(const string s)
    {
        for (int i = 0; i < (s.size() >> 1); i++)
            if (s[i] != s[s.size() - i - 1])
                return false;
        return true;
    }
    bool solve(const string s)
    {
        string t = s;
        for (int i = 0; i < (s.size() >> 1); i++)
        {
            t = t.substr(1) + s[i];
            if (t != s && is_palindrome(t))
                return true;
        }
        return false;
    }
    int work()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin >> s;
        if (!check(s))
            cout << "Impossible";
        else if (solve(s))
            cout << 1;
        else
            cout << 2;
        return 0;
    }
}
int main()
{
    return zyt::work();
}
上一篇:#C++初学记录(set进阶#acm cf 190802 B. Subsegments)


下一篇:CF1109D Sasha and Interesting Fact from Graph Theory