NOIP2018提高组模拟题（五） |
您所在的位置：网站首页 › 小亮亮m › NOIP2018提高组模拟题（五） |
|
字符串(string)
Description
小林与亮亮正在做一个游戏。小林随意地写出一个字符串，字符串只由大写 字母组成，然后指定一个非负整数 m，亮亮可以进行至多 m 次操作，每次操作 为交换相邻两个字符。亮亮的目标是使得操作后的字符串出现最长相同的字符的 长度最大。你能帮亮亮计算一下这个最大长度是多少吗？ Input第一行一个字符串 S。 第二行一个整数 m。 Output只有一个整数，表示所求的最大长度。 表示刚开始想了一个小时的\(DP\) 然后还出样例了, 要不是手出了一组样例就凉了 然后还有20分钟的时候,发现是个贪心+递归 将两侧的向中间移动显然更优. 容易发现,同种字母移动才会产生影响. 因此直接枚举每种字母,记录其位置. 由于从某一位置到目标位置的交换次数可求.所以这样是可做的. \(\color{red}{官方题解}\)表示没看太懂 考察内容：字符串、枚举与贪心 字符串长度不超过 50，我们就可以枚举哪一个字符不动，其他相同字符向它靠近，左 右两边相同字符计算出它们与选定字符相邻需要移动几次，以此为关键值从小到大排序，贪心地处理即可。 代码 #include #include #include #include #define R register using namespace std; inline void in(int &x) { int f=1;x=0;char s=getchar(); while(!isdigit(s)){if(s=='-')f=-1;s=getchar();} while(isdigit(s)){x=x*10+s-'0';s=getchar();} x*=f; } int ans,m,n; int pos[833]; char s[833]; inline int cs(char s) { return s-'A'+1; } inline int calc(int l,int r) { if(l==r)return 0; if(l==r-1)return pos[r]-pos[l]-1; return calc(l+1,r-1)+pos[r]-pos[l]-(r-l); } int main() { freopen("string.in","r",stdin); freopen("string.out","w",stdout); scanf("%s",s+1);in(m);n=strlen(s+1); for(R int i=1;i |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |