SCOI 2013 密码 & 乱搞

题意:

Fish 是一条生活在海里的鱼。有一天他很无聊，就到处去寻宝。他找到了位于海底深处的宫殿，但是一扇带
有密码锁的大门却阻止了他的前进。
通过翻阅古籍，Fish 得知了这个密码的相关信息：
1. 该密码的长度为N。
2. 密码仅含小写字母。
3. 以每一个字符为中心的最长回文串长度。
4. 以每两个相邻字符的间隙为中心的最长回文串长度。
很快Fish 发现可能有无数种满足条件的密码。经过分析，他觉得这些密码中字典序最小的一个最有可能是答
案，你能帮他找到这个密码么？
注意：对于两个串A 和B，如果它们的前i 个字符都相同，而A 的第i +1 个字符比B 的第i +1 个字符小，
那么认为是则称密码A 的字典序小于密码B 的字典序，例如字符串abc 字典序小于字符串acb。如果密
码A 的字典序比其他所有满足条件的密码的字典序都小，则密码A 是这些密码中字典序最小的一个。

SOL:

　　就是乱搞,首先第一个字母一定是a,然后对于一个回文串,它的两边是对称的,那么我们可以对于每一个不位于某个回文串上的字母贪心,能取哪个取哪个,同时对于回文串的两头外侧一个字符显然不相同,那么我们标记一下. 维护一个右端点...O(n)乱搞即可.

　　说不清楚,正确性也说不清楚,实现细节看代码,正确性请自行脑补.

Code:

/*==========================================================================

# Last modified: 2016-03-09 08:39

# Filename: t1.cpp

# Description:

==========================================================================*/

#define me AcrossTheSky

#include <cstdio>

#include <cmath>

#include <ctime>

#include <string>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <set>

#include <map>

#include <stack>

#include <queue>

#include <vector>

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

#define FOR(i,a,b) for((i)=(a);(i)<=(b);(i)++)

#define FORP(i,a,b) for(int i=(a);i<=(b);i++)

#define FORM(i,a,b) for(int i=(a);i>=(b);i--)

#define ls(a,b) (((a)+(b)) << 1)

#define rs(a,b) (((a)+(b)) >> 1)

#define getlc(a) ch[(a)][0]

#define getrc(a) ch[(a)][1]

#define getl(i,t) (i)-a[(t)][(i)]/2

#define getr(i,t) (i)+a[(t)][(i)]/2

#define maxc 26

#define maxn 150000

#define maxm 100000

#define pi 3.1415926535898

#define _e 2.718281828459

#define INF 1070000000

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

template<class T> inline

void read(T& num) {

    bool start=false,neg=false;

    char c;

    num=0;

    while((c=getchar())!=EOF) {

        if(c=='-') start=neg=true;

        else if(c>='0' && c<='9') {

            start=true;

            num=num*10+c-'0';

        } else if(start) break;

    }

    if(neg) num=-num;

}

/*==================split line==================*/

bool ch[maxn][maxc];

int a[2][maxn];

char s[maxn];

int main(){

    int n; read(n);

    FORP(i,1,n) read(a[0][i]);

    FORP(i,1,n-1) read(a[1][i]);

    memset(ch,true,sizeof(ch));

    ch[1][0]=true;

    //int len=n+n-1;

    s[1]='a';

    int len=n; int r=0;

    FORP(i,1,len){

        if (i>r){

            FORP(j,0,25) if (ch[i][j]) {

                s[i]='a'+j; break;

            }

        }

        int rr=getr(i,0),ll=getl(i,0);

        if (rr>r){

            FORP(j,r+1,rr) s[j]=s[2*i-j];

            r=rr;

        }

        if (ll>0) ch[rr+1][s[ll-1]-'a']=false;

        if (i==len) continue;

        rr=getr(i,1),ll=getl(i,1);

        if (rr>r) {

            FORP(j,r+1,rr) s[j]=s[2*i-j+1];

            r=rr;

        }

        if (ll>0) ch[rr+1][s[ll]-'a']=false;

    }

    FORP(i,1,n) printf("%c",s[i]);

}

巴特西

SCOI 2013 密码 & 乱搞

题意:

SOL:

Code:

最新文章

热门文章