首页 > 代码库 > 【T^T 1871】获取敌情

【T^T 1871】获取敌情

2024-08-16 23:18:57   219人阅读

获取敌情

在公元4484年，人类展开了对外界星球的征途和探索，但也不可避免的展开了和外星人之间的战争。偶然的机遇之下，美国联邦调查局截获了一串来自外星球的信息。但不知道有什么特殊的意义。所以就委托你，人类世界仅存的Acmer来破解这串神秘的信息。所截获这条信息是长度为N的字符串Str，要重新组合成一个长度同样为N的字符串Ttr。Ttr一开始是一个空串。重新组合的规则如为：每次从Str的字符串的头部或者尾部去除一个字符，并且接到Ttr的尾部。重复操作,直到Str为空串，Ttr为长度为N的字符串。破解这条信息的关键在于要构造字典序尽可能小的字符串。字典序：是指从前到后比较两个字符串大小的方法。首先比较第一个字符。如果不同则第一个字符较小的字符串更小，如果相同继续比较第二个字符串，来比较整个字符串的大小。加油吧，聪明的Acmer，拯救人类的重担就靠你们了

Input

输入包含多组样例。首先输入整数N（1<=N<=1000）然后输入字符串Str（仅含有大写字母）

Output

对于每一组测试案例，在每一行输出破解后的字符串Ttr。

Sample Input

6ACDBCB

Sample Output

ABCBCD

Solution

技术分享

靠,历时悠久

最开始压根就没管两边相等的情况,直接输出

然后发现有相等的情况，开始各种讨论:

  1. 字典序最小,放前面的越小越好,然后得出基本思路,从两边开始找小的
  2. 相等的情况
    1. 一直是变小(一直相等)的,直到有变大的,一个变大,就输出另外一边
    2. 两边变大,就找下一个小的那边
    3. 并且第一种情况，要考虑和另一边第一个的大小

话说我的其实可以不讨论的,直接输出相等的比下一位即可.

还有发一份Marris的代码(thank him,借代码拍的),他的做法更简单,不用讨论,相同的就一直相同，考虑第一位不相同的大小决定删哪边(保证最优)→ 每次只删一个，所以不用讨论下一位大小关系

福利数据

这个是我拍了10w组WA的

7
dadeadd

daddade

Code

// This file is made by YJinpeng，created by XuYike‘s black technology automatically.// Copyright (C) 2016 ChangJun High School, Inc.// I don‘t know what this program is.#include <iostream>#include <cstring>#include <cstdio>using namespace std;typedef long long LL;const int MAXN=1010;char s[MAXN];int main(){	freopen("1871.in","r",stdin);	freopen("1871.out","w",stdout);	int n;    while(~scanf("%d",&n)){        scanf("%s",s);        int l=0,r=n-1;        while(l<r){            while(l<=r&&s[l]<s[r])                putchar(s[l++]);            while(l<=r&&s[l]>s[r])                putchar(s[r--]);            if(s[l]==s[r]){                int x=l+1,y=r-1;                if(l==r)break;                while(s[x]==s[y]&&y-x>=3&&s[x]<=s[x-1])x++,y--;                if(s[y]<s[r]&&s[y]<s[x])                    for(int i=r;i>=y;i--)putchar(s[i]),r=y-1;                else if(s[x]<s[l]&&s[x]<s[y])                    for(int i=l;i<=x;i++)putchar(s[i]),l=x+1;                else if(s[x]<s[y])                    for(int i=l;i<x;i++)putchar(s[i]),l=x;                else for(int i=r;i>y;i--)putchar(s[i]),r=y;            }        }if(l==r)putchar(s[l]);printf("\n");    }	return 0;}

　　this is good

// This file is made by YJinpeng，created by XuYike‘s black technology automatically.// Copyright (C) 2016 ChangJun High School, Inc.// I don‘t know what this program is.#include <iostream>#include <cstring>#include <cstdio>using namespace std;typedef long long LL;const int MAXN=1010;char s[MAXN];int main(){	freopen("1871.in","r",stdin);	freopen("1871.out","w",stdout);	int n;    while(~scanf("%d",&n)){        scanf("%s",s);        int l=0,r=n-1;        while(l<r){            while(l<=r&&s[l]<s[r])                putchar(s[l++]);            while(l<=r&&s[l]>s[r])                putchar(s[r--]);            if(s[l]==s[r]){                int x=l+1,y=r-1;                if(l==r)break;                while(s[x]==s[y]&&y-x>=3&&s[x]<=s[x-1])x++,y--;                if(s[x]<s[y])                    for(int i=l;i<x;i++)putchar(s[i]),l=x;                else for(int i=r;i>y;i--)putchar(s[i]),r=y;            }        }if(l==r)putchar(s[l]);printf("\n");    }	return 0;}

技术分享

　　

【T^T 1871】获取敌情


联系
我们