CF Round #634

CF Round #634

A.数学

给定a个子，你现在要把它分成两堆AB,保证A的数量大于B，且B至少有一个

思路:奇偶分开即可

B.构造

给定n,a,b

你现在要构造一个长度为n的字符串使得它每相邻a个中出现b个字符

思路：构造长度为a的循环节，其中前0-b-1位是不同字符，后b-a-1位是相同字符

然后，i遍历n，输出a[i%a.len]即可

C.数学

给定一个序列

你要对他们分队

第一队全员不同，第二队全员相同，且两者数量相同

求这个数量的最大值

思路：暴力统计，要注意第二队的元素可能出现在第一队里，取最大值要注意

D.数独，构造

给定一个已成立数独

你至多改掉上面9个元素，使得它，满足：

输出你破坏的数独

思路：九行九列九大格，刚好每行每列每大格被破坏一个，例如:

a[1][1]++;
a[2][4]++;
a[3][7]++;
a[4][2]++;
a[5][5]++;
a[6][8]++;
a[7][3]++;
a[8][6]++;
a[9][9]++;

E.前缀和(E1&E2)

题意：

我们称满足条件的序列，它

1）回文

2）它至多有三块连续的相同字符串

给定你一个序列，从中求满足条件的最大的子序列

强调：序列中所有数取值从1->200(E1:1->26)

思路：

这题关键在于看到数据范围，它很小，200不到，这其实就是一个提醒

记录pre[元素种类][pos]，何元素何位置的前缀和

并且为每个种类开一个vector记录它出现过的位置

然后进行枚举，第一层枚举前后串种类，第二层枚举数量，第三次枚举中间种类，这里就要用前缀和了

注意aaaaa这种，要特判

AC：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
#define INF 1e10+5
#define maxn 105
#define minn -105
#define ll long long int
#define ull unsigned long long int
#define uint unsigned int
#define re register
inline int read()
{
	re int t=0;
	re char v=getchar();
	while(v<'0')v=getchar();
	while(v>='0')
	{
	    t=(t<<3)+(t<<1)+v-48;
	    v=getchar();
	}
    return t;
}
int pre[201][200000];
vector<int>num[201];
void solve()
{
    int n=read();
    int cur;
    for(int i=0;i<201;i++)num[i].clear();
    for(int i=0;i<n;i++)
    {
        cin>>cur;
        for(int j=1;j<=200;j++)pre[j][i]=(i?pre[j][i-1]:0);
        pre[cur][i]++;
        num[cur].push_back(i);
    }
    int ans=1;
    for(int i=1;i<=200;i++)
    {
        int siz=num[i].size();
        ans=max(ans,siz);
        for(int j=0;j<siz/2;j++)
        {
            for(int k=1;k<=200;k++)
            {
                if(k!=i)ans=max(ans,2*(j+1)-pre[k][num[i][j]]+pre[k][num[i][siz-j-1]]);
            }
        }
    }
    cout<<ans<<"
";
}
int main()
{
    int t;
    cin>>t;
    for(int i=0;i<t;i++)
    {
        solve();
    }
    return 0;
}