首页 > 其他分享 >ZYB 玩字符串

ZYB 玩字符串

时间:2024-11-05 17:08:09浏览次数:2  
标签:return int LL len long 字符串 ZYB define

Link

Sol

好题!

我不是 DP 高手吗,怎么这么简单的 DP 题没场切。

考虑暴力枚举子串,显然最多有 \(n\sqrt n\) 个,这些子串一定包含答案。

对于一个串 \(t\) 和 原串 \(s\),考虑 \(s\) 是否能用 \(t\) 拼出来。

设 \(t\) 的长度为 \(len\)。

令 \(f_{i,j}\) 表示 \(i\sim j\) 最后不能被 \(t\) 拼出来的字母是否是 \(t\) 的前缀。

显然 \(f_{i,j}=f_{i,j-len}\operatorname{or}f_{i,j-2\times len}\operatorname{or}\dots\)。

注意到上面只考虑了直接拼接的情况,有可能还可以直接匹配,故 \(f_{i,j}\) 还可以被 \(f_{i,j-1}\operatorname{and} [s_j=t_{(j-i+1)\bmod len}]\)。

Code

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define pf push_front
#define desktop "C:\\Users\\MPC\\Desktop\\"
#define IOS ios :: sync_with_stdio (false),cin.tie (0),cout.tie (0)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair <int,int> PII;
const int dx[] = {1,0,-1,0},dy[] = {0,-1,0,1};
template <typename T1,typename T2> bool tomax (T1 &x,T2 y) {
	if (y > x) return x = y,true;
	return false;
}
template <typename T1,typename T2> bool tomin (T1 &x,T2 y) {
	if (y < x) return x = y,true;
	return false;
}
LL power (LL a,LL b,LL p) {
	LL ans = 1;
	while (b) {
		if (b & 1) ans = ans * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return ans;
}
int fastio = (IOS,0);
#define endl '\n'
#define puts(s) cout << s << endl
const int N = 210;
int n;
string s,s2;
string ans;
bool f[N][N];
bool check (int len) {
    memset (f,0,sizeof (f));
    for (int i = n;i >= 1;i--) {
        f[i][i - 1] = 1;
        for (int j = i - 1;j <= n;j++) {
            if (f[i][j]) {
                for (int l = j + len;l <= n;l += len) f[i][l] |= f[j + 1][l];
                f[i][j + 1] = s[j + 1] == s2[(j - i + 1) % len + 1];
            }
        }
    }
    return f[1][n];
}
int main () {
    int T;
    cin >> T;
    while (T--) {
        cin >> s;
        n = s.size ();
        s = ' ' + s;
        for (int len = 1;len <= n;len++) {
            if (n % len == 0) {
                ans = " ";
                for (int i = 1;i <= n + 1;i++) ans += (char)('z' + 1);
                for (int i = 1;i <= n - len + 1;i++) {
                    int j = i + len - 1;
                    s2 = " ";
                    for (int k = i;k <= j;k++) s2 += s[k];
                    if (s2 < ans && check (len)) ans = s2;
                }
                if (ans[1] <= 'z') {
                    for (int i = 1;i <= len;i++) cout << ans[i];
                    cout << endl;
                    break;
                }
            }
        }
    }
	return 0;
}

标签:return,int,LL,len,long,字符串,ZYB,define
From: https://www.cnblogs.com/incra/p/18528385

相关文章

  • C++——用指向指针的指针的方法对5个字符串排序并输出。
    没注释的源代码#include<iostream>#include<string.h>usingnamespacestd;voidsort(char**p);intmain(){  constintm=20;  char**p,*pstr[5],str[5][m];  for(inti=0;i<5;i++)    pstr[i]=str[i];  cout<<"pleaseinput5......
  • C++——输入一个字符串,内有数字和非数字字符,如a123x456_ 17960?302tab5876将其中连续
    没注释的源代码#include<iostream>#include<stdio.h>usingnamespacestd;intmain(){  charstr[50],*pstr;  inti,j,k,m,e10,digit,ndigit,a[10],*pa;  cout<<"pleaseinputstring:"<<endl;  gets(str);  pstr=&str[......
  • 数据结构,问题 G: 字符串匹配问题
    题目描述字符串中只含有括号(),[],<>,{},判断输入的字符串中括号是否匹配。如果括号有互相包含的形式,从内到外必须是<>,(),[],{},例如。输入:[()]输出:YES,而输入([]),([])都应该输出NO。输入文件的第一行为一个整数n(0<n<20),表示以下有多少个由括号组成的字符串。接下来的......
  • #Java-对象补充及字符串详讲
    0.类和对象深入解释在Java中,类(Class)和对象(Object)是两个核心概念,它们共同构成了面向对象编程(OOP)的基础。类(Class)定义:类是一个模板或蓝图,它描述了具有相同属性和行为的一组对象的共同特征。在Java中,类通过关键字class来定义。组成:类通常由成员变量(也称为属性或字段)和方......
  • 操作字符串都有哪些类以及它们之间有什么区别
     1.**String**:  -是不可变对象。每次对String类型进行修改时都会生成一个新的对象。  -适用于不频繁修改字符串的情况。2.**StringBuilder**:  -线程不安全,效率高,多用于单线程环境。  -适用于需要频繁修改字符串的操作。3.**StringBuffer**:  -线程安全......
  • 洛谷题单指南-字符串-P6824 「EZEC-4」可乐
    原题链接:https://www.luogu.com.cn/problem/P6824题意解读:已知整数序列a[i],i在1~n,有整数k,求一个整数x,要求a[i]^x<=k,使得符合要求的a[i]数量最多,求这个数量。解题思路:1、确定x的范围由于a[i]^x<=k,因此,x的有效二进制位不可能超过a[i],而a的取值范围<=1000000,因此x差不多......
  • 复训时很好的字符串题
    descriptionsolution考虑到这么一件事情,就是我最终的字符串\(t\)一定是由\(s\)的若干段前缀拼接而成,因为如果不是前缀,换成前缀一定不劣。然后我们拥有一个朴素的状态\(f_{i,j}\)表示填到第\(i\)个数,且最后一段是由一段长度为\(j\)的前缀拼接成的最大贡献。考虑转......
  • 字符串学习
    manacher马拉车算法(,OI-Wiki算法介绍:线性复杂度内找出以每个字符为回文中心的最长回文半径存下模板代码:intl=0,r=-1;for(inti=1;i<=n;i++){intk=i>r?1:min(d[l+r-i],r-i+1);while(i-k>0andk+i<=nands[i-k]==s[i+k])k++;d[......