消消乐

NC218767. 消消乐

描述

n颗任意颜色的珠子摆成一排，现在你知道每个珠子的颜色种类以及珠子的总数目。
现在你有一颗颜色为x的珠子。你可以将这颗珠子插在这一排珠子中的任意位置，
一旦存在连续的相同颜色的珠子数目大于等于三颗，那么这些连续的珠子将被消除。
同时两边的珠子向中间靠拢，将被消除的部分填满，这个过程不改变珠子的相对顺序。
保证初始状态不存在连续的同颜色珠子的数目大于等于三颗。

问：由你决定x的插入位置，问最多可以消除的珠子的数目是多少。（插入的珠子不计算在内）

输入描述

第一行输入一个整数t, 代表测试数目。（1<=t<=20）
第二行输入三个正整数n (n <= 100) 、k（k <= 100）以及x (x <= k)。 分别代表珠子的总数目、珠子的颜色数
以及初始时所拥有的珠子的颜色。
第三行输入n个正整数C1,C2......Cn(Ci <= k )。

输出描述

每行输出一个整数代表最大能消除的珠子的数量

示例1

输入:

1
10 2 1
2 1 2 2 1 2 2 1 1 2

输出:

说明:

显然将颜色为1的珠子插在第8颗珠子的前面，珠子顺序变成2 1 2 2 1 2 2 2，消除3颗珠子
又形成3个连续的颜色为2的珠子，珠子顺序变成2 1 2 2 1，消除3颗珠子
不存在连续的同颜色的珠子数目大于等于3，结束。答案为3 + 3 - 1 = 5（减去插入的珠子）

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 4ms, 内存消耗: 304K, 提交时间: 2022-03-27 09:57:16

#include<iostream>
using namespace std;
int main()
{
	int t;
	cin>>t;
	while(t--){
		int n,k,x;
		cin>>n>>k>>x;
		int a[105],b[105],t,m=1,ans=0,maxans=0;
		for(int i=0;i<105;i++){
			a[i]=0;
			b[i]=0;
		}
		cin>>a[1];
		b[1]=1;
		for(int i=2;i<=n;i++){
			cin>>t;
			if(t==a[m])
				b[m]++;
			else
				{
					m++;
					a[m]=t;
					b[m]=1;
				}
		}
		for(int i=1;i<=m;i++){
			if(a[i]==x&&b[i]==2){
				ans=2;
				int p=1,l=1;
				while(l){
					if(a[i-p]==a[i+p]&&b[i-p]+b[i+p]>=3){
						ans+=b[i-p]+b[i+p];
						p++;
					}
					else{
						l=0;
					} 
				}
			}
			if(ans>maxans)maxans=ans;
		}
		cout<<maxans<<endl;
	}
	return 0;
}

上一题

下一题

详情