Codeforces Round #765 (Div. 2) 题解

题目前三段都是废话还死绕。。。。
题意：给定一组数，将两个单词之间的距离表示为这些单词不同的位置的数量。例如，10012和1100之间的距离(在二进制中)等于2，因为这些单词在第二个和第四个位置有不同的字母，从左到右计数。题目让构造一个数，使得该数和所有数的距离和最小。
**思路：**我们可以存所有数每一位是1的个数，比较数每一位取0或1的贡献，谁小，那一位取啥。

#include
#include
#include
#include 
using namespace std;
int main()
{
	int t;
	scanf ("%d",&t);
	while (t--)
	{
		int n,m;
		scanf ("%d%d",&n,&m);
		int a[32];
		memset(a,0,sizeof a);
		for (int i=0;i>=1;
				cnt++;
			}
		}
		int res=0;
		for (int i=0;i<32;i++)
		{
			
			if (a[i]!=0)
			{
				if (a[i]>=n-a[i])
				{
				   res|=1< 
B、 
**题意：**给一个序列，找到长度相同的两段连续子串（不能重合）使得保证相同位置上至少有一个数字相同，输出最长长度。
 思路：
 通过画图可以轻松发现，先找两个数字相同的位置，那找的串的长度最大等于位置靠前的那个数字的下标加上位置靠后的那个数字下标到数组长度的距离。
 那么就简单了，直接从后往前枚举，通过哈希表，遇到重复的数就更新长度取最小值就行了。
 从前往后枚举是固定前一段长度枚举后一段长度最大值（这样也行，主要是是要遍历所有相同数的每种情况）。
 
#include
#include
#include
#include 
using namespace std;
const int N = 1500010;
int st[N];
int a[N];
int main()
{
	int t;
	scanf ("%d",&t);
	while (t--)
	{
		memset(st,0,sizeof st);
		int n;
		scanf ("%d",&n);
		for (int i=1;i<=n;i++)
		scanf ("%d",&a[i]);
		int res=-1;
		for (int i=n;i>=1;i--)
		{
			if (st[a[i]])
			{
				res = max(res,i+n-st[a[i]]);
			}
			st[a[i]] = i;
		}
		printf ("%dn",res);
	}
    return 0;
}
 
C、 
DP，明天再补
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5702607.html