codeforces 1178E-Archaeology

ゞ浴缸里的玫瑰 2023-06-05 12:44 15阅读 0赞

传送门：[QAQQAQ][]

题意：给你一个字符串，保证字符串中只包含有$ABC$三种字符，且两相邻字符不相同，求任意一个回文串，使回文串长度大于字符串长度一半（向下取整），不行则输出-1

题意：这道题是不存在不可能的情况的。要注意题目中的条件：“相邻字母不相同，只包含$ABC$，要求只要达到一半”。

——根据这些“奇怪的要求”能想到什么呢？我们可以每次“卡边界”，刚好达到一半，而且只有三种字符，且相邻不相同，我们就会想到抽屉原理，每次前后各取两个，则四个字符中前后必有一对匹配，将它们取出即可达到要求，对于4个4个匹配后剩下的余数，因为向下取整，只需任意取一个就可以啦~

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    const int N=1000050;
     
    char s[N];
    int n,bl[N],a[N];
     
    int main()
    {
        scanf("%s",s+1);
        n=strlen(s+1);
        for(int i=1;i<=n;i++) a[i]=s[i]-'a';
        int l=1,r=n;
        while(r-l+1>=4)
        {
            if(a[l]==a[r]) bl[l]=1,bl[r]=1;
            else if(a[l+1]==a[r]) bl[l+1]=1,bl[r]=1;
            else if(a[l]==a[l+1]) bl[l]=1,bl[l+1]=1;
            else if(a[l]==a[r-1]) bl[l]=1,bl[r-1]=1;
            else if(a[l+1]==a[r-1]) bl[l+1]=1,bl[r-1]=1;
            else bl[r]=1,bl[r-1]=1;
            l+=2; r-=2;
        }
        if(l<r) bl[l]=1;
        for(int i=1;i<=n;i++) if(bl[i]) printf("%c",s[i]);
        return 0;
    }

转载于:https://www.cnblogs.com/Forever-666/p/11261497.html

[QAQQAQ]: https://codeforces.com/contest/1178/problem/E
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/d922c0c2afdb450b8b8f3c28c4a9501c.png

发表评论取消回复

表情：

评论列表（有 0 条评论，15人围观）

还没有评论，来说两句吧...

相关阅读

相关 codeforces 1178E-Archaeology

传送门：[QAQQAQ][] 题意：给你一个字符串，保证字符串中只包含有$ABC$三种字符，且两相邻字符不相同，求任意一个回文串，使回文串长度大于字符串长度一半（向下取整），

ゞ浴缸里的玫瑰/ 2023年06月05日 12:44/ 0 赞/ 16 阅读

相关 LeetCode1178. 猜字谜

外国友人仿照中国字谜设计了一个英文版猜字谜小游戏，请你来猜猜看吧。字谜的迷面 puzzle 按字符串形式给出，如果一个单词 word 符合下面两个条件，那么它就可以算作谜底

妖狐艹你老母/ 2022年11月03日 10:45/ 0 赞/ 155 阅读

相关 1178: 零起点学算法85——夹角有多大I

Description 这次xhd面临的问题是这样的：在一个平面内有两个点，求两个点分别和原点的连线的夹角的大小。注：夹角的范围\[0，180\]，两个点不会

爱被打了一巴掌/ 2022年10月24日 06:06/ 0 赞/ 220 阅读

相关【codeforces】Divisibility

![这里写图片描述][20160723114657129] ![这里写图片描述][20160723114705957] 只要知道n/k为n一下能被k整除的数的总和就行了

红太狼/ 2022年09月24日 02:28/ 0 赞/ 215 阅读

相关【codeforces】Bulbs

![这里写图片描述][20160721230838563] ![这里写图片描述][20160721230850345] ![这里写图片描述][2016072123090

淡淡的烟草味﹌/ 2022年09月24日 00:26/ 0 赞/ 177 阅读

相关 Codeforces

Checking the Calendar You are given names of two days of the week. Please, determine w

电玩女神/ 2022年07月16日 06:16/ 0 赞/ 272 阅读

相关 Codeforce_732

A Buy a Shovel 水题，问买鞋子的个数，直接暴力。 include <bits/stdc++.h> using namespace

浅浅的花香味﹌/ 2022年07月15日 17:08/ 0 赞/ 221 阅读

相关 1178: 单词数

Description 统计一篇文章里不同单词的总数。 Input 有多组数据，每组一行，每组就是一篇小文章。每篇小文章都是由小写字母和空格组成，没有标点符号，遇

矫情吗；*/ 2022年06月11日 01:43/ 0 赞/ 179 阅读

相关 CODEFORCES-PROBLEMSET

[1A][] 水题然而看不仔细爆int了 c++ ![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] 1

悠悠/ 2021年12月24日 03:43/ 0 赞/ 305 阅读

相关 Codeforces 1178E Archaeology (鸽巢原理)

题意：给你1e6的字符串，保证只含'a''b''c'三种字符，且相邻两个字符一定不一样求一个大于等于n/2的回文子序列思路：朴素的最长回文子序列是n方的区间dp

小灰灰/ 2021年11月14日 15:24/ 0 赞/ 256 阅读