最小表示法——牛客多校第七场A

梦里梦外; 2023-10-11 09:13 8阅读 0赞

脑瘫一样暴力，贪心找最小表示的串，判一个串是否是最小表示法时也是暴力地判。。

但是想不通复杂度是怎么算的。。

#include<bits/stdc++.h>
    using namespace std;
    #define maxn 205
    char s[maxn];
    int n;
     
    int check(int l,int r){
        //判断区间[l,r]是否是最小表示法
        int len=r-l+1;
        for(int st=l+1;st<=r;st++){
            int p1=l,p2=st;
            for(int i=0;i<len;i++){
                if(s[p1]<s[p2])break;
                else if(s[p1]>s[p2])return 0;
                ++p1;++p2;
                if(p1>r)p1=l;
                if(p2>r)p2=l;
            }
        }
        return 1;
    }
     
    int main(){
        int t;cin>>t;
        while(t--){
            scanf("%s",s+1);
            n=strlen(s+1);
            for(int l=1,r;l<=n;l++){
                r=n;
                while(!check(l,r))
                    --r;
                for(int i=l;i<=r;i++)cout<<s[i];
                if(r!=n)cout<<" ";
                l=r;
            }
            cout<<'\n';
        }  
    }

转载于:https://www.cnblogs.com/zsben991126/p/11323627.html

发表评论取消回复

表情：

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

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

相关阅读

相关单调栈(最大子矩形强化版)——牛客多校第八场A

求01矩阵里有多少个不同的1矩阵首先预处理出pre\[i\]\[j\]表示i上面连续的1个数，对每行的高度进行单调栈处理栈里的元素维护两个值：pre\[i\]\[j\]

川长思鸟来/ 2023年10月11日 09:14/ 0 赞/ 17 阅读

相关最小表示法——牛客多校第七场A

脑瘫一样暴力，贪心找最小表示的串，判一个串是否是最小表示法时也是暴力地判。。但是想不通复杂度是怎么算的。。 include<bits/stdc++.h>

梦里梦外;/ 2023年10月11日 09:13/ 0 赞/ 9 阅读

相关第k小团+bitset优化——牛客多校第2场D

模拟bfs，以空团为起点，用堆维护当前最小的团，然后进行加点更新在加入新点时要注意判重，并且用bitset来加速判断和转移构造 include<bits/std

快来打我*/ 2023年10月11日 09:12/ 0 赞/ 10 阅读

相关字符串dp——牛客多校第五场G

比赛的时候脑瘫了没想出来。。打多校以来最自闭的一场显然从s中选择大于m个数组成的数必然比t大，所以只要dp求出从s中选择m个数大于t的方案数官方题解是反着往前推，想了下

谁借莪１个温暖的怀抱￠/ 2023年10月11日 09:10/ 0 赞/ 20 阅读

相关思维题——牛客多校第六场D

这题的不能用二分做，因为不满足单调性的可以用multiset做 include<bits/stdc++.h> define ll long long

雨点打透心脏的1/2处/ 2023年10月11日 09:10/ 0 赞/ 17 阅读

相关 2019牛客暑期多校训练营第六场

题目链接：[https://ac.nowcoder.com/acm/contest/886\question][https_ac.nowcoder.com_acm_contes

今天药忘吃喽~/ 2021年11月02日 13:38/ 0 赞/ 387 阅读

相关 2019牛客暑期多校训练营（第七场）-C Governing sand

题目链接：https://ac.nowcoder.com/acm/contest/887/C 题意：有n种树，给出每种数的高度、移除的花费和数量，求最小花费是多少使得剩下树中

爱被打了一巴掌/ 2021年10月30日 02:36/ 0 赞/ 273 阅读

相关牛客多校第六场记录

A 题意: 垃圾分类思路: 模拟 include <cstdio> include <iostream> include <algorithm>

柔光的暖阳◎/ 2021年10月29日 12:20/ 0 赞/ 277 阅读

相关牛客多校第三场 F Planting Trees

牛客多校第三场 F Planting Trees 题意：求矩阵内最大值减最小值大于k的最大子矩阵的面积题解：矩阵压缩的技巧因为对于我们有用的信息只

淡淡的烟草味﹌/ 2021年10月15日 23:37/ 0 赞/ 278 阅读

相关牛客多校第七场 C Bit Compression 思维

链接：[https://www.nowcoder.com/acm/contest/145/C][https_www.nowcoder.com_acm_contest_145_C

ゝ一世哀愁。/ 2021年09月20日 13:50/ 0 赞/ 326 阅读