关键词：
【BZOJ2213】[Poi2011]Difference
Description
A word consisting of lower-case letters of the English alphabet (‘a‘-‘z‘) is given. We would like to choose a non-empty contiguous (i.e. one-piece) fragment of the word so as to maximise the difference in the number of occurrences of the most and the least frequent letter in the fragment. We are assuming that the least frequent letter has to occur at least once in the resulting fragment. In particular, should the fragment contain occurrences of only one letter, then the most and the least frequent letter in it coincide.
已知一个长度为n的由小写字母组成的字符串，求其中连续的一段，满足该段中出现最多的字母出现的个数减去该段中出现最少的字母出现的个数最大。求这个个数。
Input
The first line of the standard input holds one integer (1<=N<=1000000)() that denotes the length of the word. The second line holds a word consisting of lower-case letters of the English alphabet.
第一行，n
第二行，该字符串
1<=n<=1000000
Output
The first and only line of the standard output is to hold a single integer, equal to the maximum difference in the number of occurrences of the most and the least frequent letter that is attained in some non-empty contiguous fragment of the input word.
一行，表示结果
Sample Input
aabbaaabab
Sample Output
Explanation of the example: The fragment that attains the difference of 3 in the number of occurrences of a and b is aaaba.
题解：我承认我做的可能有点麻烦~
先枚举出现次数最少的字符，然后设f[i][0]表示以i结束的最长一段区间使得（位置为i的字符出现次数-最少的字符出现的次数）最大，不强制要求区间中必须出现过次数最少的字符，f[i][1]表示强制区间中必须出现过次数最少的字符，然后DP搞一搞
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn=1000010;
int n,ans;
int pre[maxn],s[maxn],f[maxn][2],head[30];
char str[maxn];
void calc(int cn)
{
int i;
for(i=1;i<=n;i++) s[i]=s[i-1]+(str[i]==‘a‘+cn);
if(!s[n]) return ;
f[0][0]=0,f[0][1]=-1<<30;
for(i=1;i<=n;i++)
{
if(str[i]==‘a‘+cn) continue;
f[i][0]=max(f[pre[i]][0]+1-s[i]+s[pre[i]],1);
f[i][1]=(s[i]>s[pre[i]])?max(f[pre[i]][0]+1-s[i]+s[pre[i]],0):(f[pre[i]][1]+1);
ans=max(ans,f[i][1]);
if(s[n]-s[i]) ans=max(ans,f[i][0]-1);
}
}
int main()
{
scanf("%d%s",&n,str+1);
int i;
for(i=1;i<=n;i++) pre[i]=head[str[i]-‘a‘],head[str[i]-‘a‘]=i;
for(i=0;i<26;i++) calc(i);
printf("%d",ans);
return 0;
}
[bzoj2213][poi2011]difference_动态规划
Differencebzoj-2213Poi-2011题目大意：已知一个长度为n的由小写字母组成的字符串，求其中连续的一段，满足该段中出现最多的字母出现的个数减去该段中出现最少的字母出现的个数最大。求这个个数。注释：$1lenle10^6$。想法：“... 查看详情
bzoj2213[poi2011]differencedp
题目描述已知一个长度为n的由小写字母组成的字符串，求其中连续的一段，满足该段中出现最多的字母出现的个数减去该段中出现最少的字母出现的个数最大。求这个个数。输入第一行，n第二行，该字符串1<=n<=1000000输出一... 查看详情
[bzoj2527][poi2011]meteors
2527:[Poi2011]MeteorsTimeLimit:60Sec MemoryLimit:128MBSubmit:1807 Solved:646[Submit][Status][Discuss]DescriptionByteotianInterstellarUnion(BIU)hasrecentlydiscoveredanewplanetinan 查看详情
bzoj2529:[poi2011]sticks
2529:[Poi2011]SticksTimeLimit:10Sec MemoryLimit:128MBSec SpecialJudgeSubmit:257 Solved:133[Submit][Status][Discuss]DescriptionLittleJohnnywasgivenabirthdaypresentbyhis 查看详情
bzoj2530[poi2011]party
2530:[Poi2011]PartyTimeLimit:10Sec MemoryLimit:128MBSec SpecialJudgeSubmit:342 Solved:196[Submit][Status][Discuss]DescriptionByteasarintendstothrowupaparty.Naturally,h 查看详情
[bzoj]2276:[poi2011]temperature
2276:[Poi2011]TemperatureTimeLimit: 20Sec MemoryLimit: 32MBSubmit: 731 Solved: 334[Submit][Status][Discuss]DescriptionTheByteotianInstituteofMeteorology(BIM)m 查看详情
bzoj-2276:[poi2011]temperature(单调队列)
2276:[Poi2011]TemperatureTimeLimit: 20Sec MemoryLimit: 32MBSubmit: 763 Solved: 352[Submit][Status][Discuss]DescriptionTheByteotianInstituteofMet 查看详情
bzoj_2212_[poi2011]treerotations_线段树合并
BZOJ_2212_[Poi2011]TreeRotations_线段树合并DescriptionByteasarthegardenerisgrowingararetreecalledRotatusInformatikus.Ithassomeinterestingfeatures:Thetreeconsistsofstraightbranches,bifurcationsandleaves.The 查看详情
bzoj2212[poi2011]treerotations线段树合并
DescriptionByteasarthegardenerisgrowingararetreecalledRotatusInformatikus.Ithassomeinterestingfeatures:Thetreeconsistsofstraightbranches,bifurcationsandleaves.Thetrunkstemmingfromthegroundisalsoabranc 查看详情
[bzoj2212][poi2011]treerotations(线段树合并)(代码片段)
2212:[Poi2011]TreeRotationsTimeLimit:20Sec MemoryLimit:259MBSubmit:1562 Solved:614[Submit][Status][Discuss]DescriptionByteasarthegardenerisgrowingararetreecalledRotatusInformatik 查看详情
bzoj2527:[poi2011]meteors
这个。。。一開始用的是longlong然后改成int就wa了。。。。时间垫底。。。。。可怕全局分治 然后用线段树维护的时候直接永久化标记 不用下传然后这一题和上一道树套树一样。又是由于自己傻逼少了一倍的线段树节... 查看详情
bzoj2527[poi2011]meteors
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2527【题解】整体二分思想，其实就是把一坨二分拿一起处理了。。。（事实上这题暴力好像。。不需要二分？）我们定义solve(l,r,al,ar)为当前二分区间为[l,r]，在这个区间的公司为id[al... 查看详情
bzoj2212[poi2011]treerotations
题解：交换某节点的两棵子树仅对 此节点子树对答案的贡献 有影响Dfs,启发式合并时顺便求逆序对即可,贪心交不交换O(nlogn*logn)Noname讲过一种合并Treap求逆序对，仅需O(nlogn),还不会 查看详情
bzoj2217[poi2011]lollipop乱搞
【BZOJ2217】[Poi2011]LollipopDescription有一个长度为n的序列a1,a2,...,an。其中ai要么是1("W")，要么是2("T")。现在有m个询问，每个询问是询问有没有一个连续的子序列，满足其和为q。Input第一行n，m(1<=n,m<=1000000)第二行这个序列，起始... 查看详情
bzoj2529[poi2011]sticks贪心
【BZOJ2529】[Poi2011]SticksDescription给出若干木棍，每根木棍有特定的颜色和长度。问能否找到三条颜色不同的木棍构成一个三角形。(注意这里所说的三角形面积要严格大于0)第一行给出一个整数k(3<=k<=50),表示颜色的种数。这k种... 查看详情
bzoj2212[poi2011]treerotations(代码片段)
ByteasarthegardenerisgrowingararetreecalledRotatusInformatikus.Ithassomeinterestingfeatures:Thetreeconsistsofstraightbranches,bifurcationsandleaves.Thetrunkstemmingfromthegroundisalsoabranch.Eachbranchendswitheitherabifurcationoraleafonitstopend.Exactlytwobranchesforkoutfromabifurcationattheendofabr... 查看详情
bzoj2216[poi2011]lightningconductor决策单调性
【BZOJ2216】[Poi2011]LightningConductorDescription已知一个长度为n的序列a1,a2,...,an。对于每个1<=i<=n，找到最小的非负整数p满足对于任意的j,aj<=ai+p-sqrt(abs(i-j))Input第一行n，(1<=n<=500000)下面每行一个整数，其中第i行是ai。(0<=ai&l... 查看详情
bzoj2212[poi2011]rot-treerotations-线段树合并(代码片段)
2212:[Poi2011]TreeRotationsTimeLimit: 20Sec MemoryLimit: 259MBDescriptionByteasarthegardenerisgrowingararetreecalledRotatusInformatikus.Ithassomeinterestingfeatures:Thetreeconsist 查看详情