洛谷 3519 && bzoj 2213 Difference
2024-09-08 03:40:49
联考考试考到了这个题,随机化40分,现在来秒掉它吧。
题意:
给一个字符串,求其中的一段,使得出现次数最多的字符与出现次数最少的字符的出现次数之差最大。
输入输出样例
我们定义$cnt[i][j]$表示区间$[1,i]$中,j出现的次数,
定义字符a,b(非字符a,b),a为出现最多的字符,b为出现最少的字符。
我们利用前缀和统计每一个字符出现的次数。
那么对于一个区间$[i,j]$,字符a出现的次数为$cnt[j][a]-cnt[i][a]$,字符b出现的次数为$cnt[j][b]-cnt[i][b]$,我们枚举每一个字符的配对情况。
对于26个字符$$ans=max \{ ans,(cnt[j][a]-cnt[i][a])-(cnt[j][b]-cnt[i][b]) \}$$。
这样枚举时间复杂度$O(n^2 \times 26 \times 26)$,还可以啦。
现在我们来优化一下上边的过程。
$$(cnt[j][a]-cnt[i][a])-cnt[j][b]-(cnt[i][b])$$
可以变为
$$(cnt[j][a]-cnt[j][b])-(cnt[i][a]-cnt[i][b])$$
对于算式的前半边O(n \times 26)枚举,我们来优化一下后半边。
对于后边的式子,求得为j以前$cnt[i][a]-cnt[i][b]$的最小值,然而j是怎么过来的,到了j必然前边的数都有经过,所以我们在枚举是维护一个$cnt[i][a]-cnt[i][b]$的最小值即可(代码中用到minv数组)。
代码中有p[i][j]数组表示更新字符i和字符j差的最小值的位置。
总的时间复杂度$O(n \times 26)$
#include<complex>
#include<cstdio>
using namespace std;
const int N=1e6+,M=;
int n,ans;
int last[M],num[M],p[M][M],minv[M][M];
/* last表示字符最后出现的位置,num表示字符出现的次数。
p数组表示更新维护最小值的位置,minv表示维护的最小值。*/
char s[N];
int main()
{
// freopen("B.in","r",stdin);
// freopen("B.out","w",stdout);
scanf("%d%s",&n,s+);
for(int i=; i<=n; i++)
{
int c=s[i]-'a';
num[c]++;
last[c]=i;
for(int j=; j<; j++)
if(j!=c && num[j])
ans=max(ans,max(num[c]-num[j]-minv[c][j]-(last[j]==p[c][j])
,num[j]-num[c]-minv[j][c]-(last[c]==p[j][c])));
/*最后出现的位置与最小值更新的位置相等,那么在我们判断的区间里,
不会出现j,对于这段区间-j,就等于只是选定区间内c出现的次数,
这是不符合条件的,那么要让他更大,再向左选一个不同的字
符那么tot[u]-1一定是最优的。*/
for(int j=; j<; j++)
if(num[j]-num[c]<minv[j][c])
{
minv[j][c]=num[j]-num[c];
p[j][c]=i;
}
//更新最小值。
}
printf("%d\n",ans);
// fclose(stdin);fclose(stdout);
return ;
}
最新文章
- ionic入门01
- php随机生成验证码代码
- 为什么eclipse中代码提示错误,但是项目目录却不提示错误
- Java程序调用javascript等脚本的实现方法
- python中paramiko模块的使用
- CentOS-6.5安装zabbix 3.0.4
- centos6.4下安装php的imagick和imagemagick扩展教程
- (转) 实时SLAM的未来及与深度学习的比较
- Java之组合数组1
- 数据库连接池c3p0和dbcp
- Asp.net 图片文件防盗链介绍
- cocos2d-x的经历(含源码——)
- 又一次拾起C语言的威严
- 第一章:selenium + java 环境安装
- lr11录制脚本出现中文乱码
- MySQL数据库学习二 MSQL安装和配置
- Alpha冲刺Day1
- css 绘制三角形
- 莫烦scikit-learn学习自修第四天【内置训练数据集】
- Coursera Deep Learning 2 Improving Deep Neural Networks: Hyperparameter tuning, Regularization and Optimization - week1, Assignment(Regularization)
热门文章
- E20180418-hm
- Codeforces404C【构造】
- 用动态链表high-poj 1528
- bzoj 1022: [SHOI2008]小约翰的游戏John【anti-nim】
- bzoj 4622: [NOI 2003] 智破连环阵【dfs+匈牙利算法】
- Codeforces731F Video Cards
- Codeforces Round #261 (Div. 2) C
- python programming
- D. Tavas and Malekas DFS模拟 + kmp + hash || kmp + hash
- Linux离线安装pip和numpy