c/c++语言开发共享Ural 1238 Folding 题解

ural 1238 folding 题解

题意

定义折叠、展开为：

• 单个大写英文字母是一个折叠的串，把它展开后是它本身。
• 如果(s)和(q)是折叠的串，则(sq)也是折叠的串。如果(s)展开后为(s')，(q)展开后为(q')，则(sq)展开后为(s'q')。
• 如果(s)是个折叠的串，则(x(s))也是折叠的串，其中(x)是一个十进制大于(1)的整数，如果(s)展开为(s')，则(x(s))展开后为(s')重复(x)次。

给定一个字符串(长度小于等于(100))，求把它折叠后有最小长度的那个字符串。

题解

考虑记忆化搜索(dp也可以)。

定义(f(s))为(s)字符串折叠后有最小长度的那个字符串。

边界为当(|s|le4)((|s|)为(s)的长度)时，(f(s)=s)。

给定(s)，求出(f(s))有以下几种方式

• (f(s)=s)。

• 设(1<xle|s|,|s|%x=0)且有字符串(q)，(q)重复(x)次为(s)，(f(s)=x"("+f(q)+")")。

• 设(0<i<|s|)，(f(s)=f(s[0..i-1])+f(s[i..|s|-1]))。

取长度最小的值即可，不要忘了记忆化。

程序

// #pragma gcc optimize(2) // #pragma g++ optimize(2) // #pragma comment(linker,"/stack:102400000,102400000")  // #include <bits/stdc++.h> #include <map> #include <set> #include <list> #include <array> #include <cfenv> #include <cmath> #include <ctime> #include <deque> #include <mutex> #include <queue> #include <ratio> #include <regex> #include <stack> #include <tuple> #include <atomic> #include <bitset> #include <cctype> #include <cerrno> #include <cfloat> #include <chrono> #include <cstdio> #include <cwchar> #include <future> #include <limits> #include <locale> #include <memory> #include <random> #include <string> #include <thread> #include <vector> #include <cassert> #include <climits> #include <clocale> #include <complex> #include <csetjmp> #include <csignal> #include <cstdarg> #include <cstddef> #include <cstdint> #include <cstdlib> #include <cstring> #include <ctgmath> #include <cwctype> #include <fstream> #include <iomanip> #include <numeric> #include <sstream> #include <ccomplex> #include <cstdbool> #include <iostream> #include <typeinfo> #include <valarray> #include <algorithm> #include <cinttypes> #include <cstdalign> #include <stdexcept> #include <typeindex> #include <functional> #include <forward_list> #include <system_error> #include <unordered_map> #include <unordered_set> #include <scoped_allocator> #include <condition_variable> // #include <conio.h> // #include <windows.h> using namespace std;  typedef long long ll; typedef unsigned int ui; typedef unsigned long long ull; typedef float fl; typedef double ld; typedef long double ld; typedef pair<int,int> pii; #if (win32) || (win64) || (__win32) || (__win64) || (_win32) || (_win64) || (windows) #define lld "%i64d" #define llu "%i64u" #else #define lld "%lld" #define llu "%llu" #endif #define ui(n) ((unsigned int)(n)) #define ll(n) ((long long)(n)) #define ull(n) ((unsigned long long)(n)) #define fl(n) ((float)(n)) #define ld(n) ((double)(n)) #define ld(n) ((long double)(n)) #define char(n) ((char)(n)) #define bool(n) ((bool)(n)) #define fixpoint(n) fixed<<setprecision(n)  const int inf=1061109567; const int ninf=-1044266559; const ll linf=4557430888798830399; const ld eps=1e-15; #define mod (1000000007) #define pi (3.1415926535897932384626433832795028841971)  /* #define mb_len_max 5 #define shrt_min (-32768) #define shrt_max 32767 #define ushrt_max 0xffffu #define int_min (-2147483647 - 1) #define int_max 2147483647 #define uint_max 0xffffffffu #define long_min (-2147483647l - 1) #define long_max 2147483647l #define ulong_max 0xfffffffful #define llong_max 9223372036854775807ll #define llong_min (-9223372036854775807ll - 1) #define ullong_max 0xffffffffffffffffull */  #define mp make_pair #define mt make_tuple #define all(a) (a).begin(),(a).end() #define pall(a) (a).rbegin(),(a).rend() #define log2(x) log(x)/log(2) #define log(x,y) log(x)/log(y) #define sz(a) ((int)(a).size()) #define rep(i,n) for(int i=0;i<((int)(n));i++) #define rep1(i,n) for(int i=1;i<=((int)(n));i++) #define repa(i,a,n) for(int i=((int)(a));i<((int)(n));i++) #define repa1(i,a,n) for(int i=((int)(a));i<=((int)(n));i++) #define repd(i,n) for(int i=((int)(n))-1;i>=0;i--) #define repd1(i,n) for(int i=((int)(n));i>=1;i--) #define repda(i,n,a) for(int i=((int)(n));i>((int)(a));i--) #define repda1(i,n,a) for(int i=((int)(n));i>=((int)(a));i--) #define for(i,a,n,step) for(int i=((int)(a));i<((int)(n));i+=((int)(step))) #define repv(itr,v) for(__typeof((v).begin()) itr=(v).begin();itr!=(v).end();itr++) #define repv(i,v) for(auto i:v) #define repe(i,v) for(auto &i:v) #define ms(x,y) memset(x,y,sizeof(x)) #define mc(x) ms(x,0) #define minf(x) ms(x,63) #define mcp(x,y) memcpy(x,y,sizeof(y)) #define sqr(x) ((x)*(x)) #define un(v) sort(all(v)),v.erase(unique(all(v)),v.end()) #define filein(x) freopen(x,"r",stdin) #define fileout(x) freopen(x,"w",stdout) #define fileio(x)     freopen(x".in","r",stdin);     freopen(x".out","w",stdout) #define filein2(filename,name) ifstream name(filename,ios::in) #define fileout2(filename,name) ofstream name(filename,ios::out) #define file(filename,name) fstream name(filename,ios::in|ios::out) #define pause system("pause") #define cls system("cls") #define fs first #define sc second #define pc(x) putchar(x) #define gc(x) x=getchar() #define endl pc('n') #define sf scanf #define pf printf  inline int read() {     int x=0,w=0;char ch=0;while(!isdigit(ch)){w|=ch=='-';ch=getchar();}while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();     return w?-x:x; } inline void write(int x){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');}  inline ll powmod(ll a,ll b){ll res=1;a%=mod;assert(b>=0);for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res%mod;} inline ll gcdll(ll a,ll b){return b?gcdll(b,a%b):a;} const int dx[]={0,1,0,-1,1,-1,-1,1}; const int dy[]={1,0,-1,0,-1,-1,1,1}; /************************************************************begin************************************************************/ const int maxn=110;  inline string itoa(int x) {     string res="";     while(x)     {         res+=char(x%10+'0');         x/=10;     }     reverse(all(res));     return res; }  map<string,string> vis;  inline string sol(string s) {     if(vis.count(s)) return vis[s];     if(s.size()<=4) return vis[s]=s;      string ans=s;     rep1(i,s.size()) if(i>1&&s.size()%i==0)     {         int len=s.size()/i;         string x=s.substr(0,len);         bool f=1;          for(int j=0;j<s.size();j+=len) if(s.substr(j,len)!=x) f=0;          if(f)         {             string res=itoa(i)+'('+sol(x)+')';             if(ans.size()>res.size()) ans=res;         }     }      rep1(i,s.size()-1)     {         string res=sol(s.substr(0,i))+sol(s.substr(i));         if(ans.size()>res.size()) ans=res;     }      return vis[s]=ans; }  int main() {     string s;     cin>>s;     cout<<sol(s);      return 0; } /*************************************************************end**************************************************************/