CF #541 E. String Multiplication
2024-10-06 10:06:08
题意:
给定一系列字符串,每次都是后一个字符串和前面的融合,这个融合操作就是原来的串分成独立的,然后把新串插入到这些空格中。问最后,最长的相同连续的长度。
思路:
这道题可以贪心的来,我们压缩状态,记录串中每个字母对应最长的长度。然后分类讨论处理就行了。
#include <algorithm>
#include <iterator>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <stack>
#include <cmath>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <cassert> /* ⊂_ヽ
\\ Λ_Λ 来了老弟
\('ㅅ')
> ⌒ヽ
/ へ\
/ / \\
レ ノ ヽ_つ
/ /
/ /|
( (ヽ
| |、\
| 丿 \ ⌒)
| | ) /
'ノ ) Lノ */ using namespace std;
#define lson (l , mid , rt << 1)
#define rson (mid + 1 , r , rt << 1 | 1)
#define debug(x) cerr << #x << " = " << x << "\n";
#define pb push_back
#define pq priority_queue typedef long long ll;
typedef unsigned long long ull;
//typedef __int128 bll;
typedef pair<ll ,ll > pll;
typedef pair<int ,int > pii;
typedef pair<int,pii> p3; //priority_queue<int> q;//这是一个大根堆q
//priority_queue<int,vector<int>,greater<int> >q;//这是一个小根堆q
#define fi first
#define se second
//#define endl '\n' #define boost ios::sync_with_stdio(false);cin.tie(0)
#define rep(a, b, c) for(int a = (b); a <= (c); ++ a)
#define max3(a,b,c) max(max(a,b), c);
#define min3(a,b,c) min(min(a,b), c); const ll oo = 1ll<<;
const ll mos = 0x7FFFFFFF; //
const ll nmos = 0x80000000; //-2147483648
const int inf = 0x3f3f3f3f;
const ll inff = 0x3f3f3f3f3f3f3f3f; //
const int mod = 1e9+;
const double esp = 1e-;
const double PI=acos(-1.0);
const double PHI=0.61803399; //黄金分割点
const double tPHI=0.38196601; template<typename T>
inline T read(T&x){
x=;int f=;char ch=getchar();
while (ch<''||ch>'') f|=(ch=='-'),ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x=f?-x:x;
} inline void cmax(int &x,int y){if(x<y)x=y;}
inline void cmax(ll &x,ll y){if(x<y)x=y;}
inline void cmin(int &x,int y){if(x>y)x=y;}
inline void cmin(ll &x,ll y){if(x>y)x=y;} /*-----------------------showtime----------------------*/
const ll big = 1e9+;
ll dp[],tmp[];
string str;
int main(){
int n;
scanf("%d", &n);
ll ans = ;
rep(cc, , n){ cin>>str; int len = str.length();
int flag = ;
for(int i=; i<len; i++) if(str[i] != str[]) flag = ; if(flag) {
int id = (str[] - 'a');
rep(i, , ) {
if(i == id) continue;
if(dp[i]) dp[i] = ;
} if(dp[id]){
ll t = min(big, 1ll*(dp[id] + ) * len + dp[id]);
dp[id] = max(dp[id], t);
}
dp[id] = max(1ll*len, dp[id]);
}
else {
rep(i, , ){
if(dp[i]) dp[i] = ;
tmp[i] = ;
}
ll e = ;char la = str[];
str+="A";
rep(i, , len){
if(str[i] != la){
int id = (int)(la - 'a');
tmp[id] = max(tmp[id], e);
// debug(e);
la = str[i];
e = ;
}
else e++;
}
ll c1 = ,c2 = ;
for(int i=; i<len && str[i] == str[]; i++) c1++;
for(int i=len-; i>= && str[i] == str[len-];i--) c2++; if(str[] == str[len-]) {
int id = (int)(str[] - 'a');
if(dp[id]) dp[id] = min(big, max(dp[id], 1ll + c1 + c2));
}
else {
int id = (int)(str[] - 'a');
if(dp[id]) dp[id] = min(big, max(dp[id], 1ll + c1));
id = (int) (str[len-] - 'a');
if(dp[id]) dp[id] = min(big, max(dp[id], 1ll + c2));
}
rep(i, , ) {
dp[i] = max(dp[i], tmp[i]);
}
}
} rep(i, , ) ans = max(ans, dp[i]);
printf("%lld\n", ans);
return ;
}
最新文章
- vue 命名视图
- iTOP-4412开发板低功耗高性能的开源硬件平台——上手评测
- 如果您想省略JS里的分号,了解一下JS的分号插入原理吧
- Sql Server建立链接服务器访问Access的MDB数据库
- Restfull API 示例
- 准备开发一个基于canvas的图表库,记录一些东西(一)
- hdu2304Electrical Outlets
- Xcode5新特性
- angular中控制器之间的通讯方式
- spring入门--Spring框架底层原理
- jQuery和js获取select元素的选中项value?
- Python入门学习(一)
- 用委托(Delegate)的BeginInvoke和EndInvoke方法操作线程
- scala函数
- lcd参数解释及刷新率计算,LCD时序
- 画多边形form并填充背景色(可以实现圆角边框 有锯齿)
- dll 修复....
- Windows下开启composer镜像服务来安装yii
- Java的家庭记账本程序(B)
- vue2.0 导出Excel表格数据