Codeforces Round #455 (Div. 2) 909D. Colorful Points

题

　　OvO http://codeforces.com/contest/909/problem/D

　　CF 455 div2 D

　　CF 909D

解

　　算出模拟的复杂度之后就是一个很水的模拟题

　　把字符串按照类似于行程编码的方式来表示，例如把 aaaabbccc 表示成 [4*a] [2*b] [3*c] 这样的形式（[4*a] 这个用一个结构体表示）

　　接下去就可以开心地敲模拟了，

　　例如对于 [5*a] [4*b] [2*c] [4*b] 这样一个表，

　　运行一次之后就变成了 [4*a] [2*b] [0*c] [3*b]

　　然后进行压缩变成 [4*a] [5*b]

　　重点是复杂度的计算，每当你进行一次 O(1) 的操作（遍历数组，删除元素）时候，元素的总量（按 aabbc 是个元素这样算）也会减1，所以总的复杂度是 O(n) 的，并不会超时

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <algorithm>

using namespace std;

const int M=1e6+44;

struct Node

{

	int val,num;

} q[M];

int lq;

char str[M];

void cps()

{

	int k=lq;

	lq=0;

	for(int i=1;i<=k;i++)

		if(q[i].num>0)

		{

			if(q[i].val==q[lq].val)

				q[lq].num+=q[i].num;

			else

				q[++lq]=q[i];

		}

}

void solve()

{

	int ans=0;

	while(lq>1)

	{

		ans++;

		for(int i=2;i<lq;i++)

			q[i].num-=2;

		q[1].num--,q[lq].num--;

		cps();

	}

	printf("%d\n",ans);

}

int main()

{

	scanf("%s",str+1);

	lq=strlen(str+1);

	q[0].val=-1;

	for(int i=1;i<=lq;i++)

		q[i].val=str[i]-'a',q[i].num=1;

	cps();

	solve();

	return 0;

}

巴特西

Codeforces Round #455 (Div. 2) 909D. Colorful Points

最新文章

热门文章