ZR2020普转提七连测day3

http://www.zhengruioi.com/contest/704

没有上场毒瘤啊

打眼一看好像直接模拟就好了

但是可能有 $k>n/2$ 情况

这种情况下根据kmp的错位相同原理,我们可能有很多字符是要一样的

那么我们用一个并查集把这样的字符形成的连通块找出来然后暴力看看每一块改成什么就好了

时间复杂度 $O(nalogn)$ 属于不精细的实现QAQ

code:


#include<bits/stdc++.h>
const int MAXN = 1e5 + 7;
int n, k, ans;
char a[MAXN];
int fa[MAXN], num[MAXN][26];
inline int getf(int x) {
	return fa[x] == x ? x : fa[x] = getf(fa[x]);
}

inline void merge(int x, int y) {
	for(int i = 0; i < 26; ++i) {
		num[getf(x)][i] += num[getf(y)][i];
	}
	fa[getf(y)] = getf(x);

	return ;
}

inline void init() {
	for(int i = 1; i <= n; ++i) {
		fa[i] = i;
		num[i][a[i] - 'a'] = 1;
	}
	return ;
}
int main() {
	scanf("%d%d", &n, &k);
	scanf("%s", a + 1);
	init();
	int l = n - k + 1, r, tmp;
	//错位相同,显然我们错位不能多了
	for(int i = 1; i <= k; ++i) {
		if(fa[i] != i)continue;
		r = l + i - 1;
		merge(i, r);
		tmp = r - 1 + l;
		while(tmp <= n) {
			merge(i, tmp);
			if(tmp > k) {
				break;
			}
			tmp = tmp - 1 + l;
		}
	}
	for(int i = 1; i <= k; ++i) {
		if(fa[i] == i) {
			int S = 0, Max = -1;
			for(int j = 0; j < 26; ++j) {
				if(num[i][j] > Max)Max = num[i][j];
				S += num[i][j];
			}
			ans += S - Max;
		}
	}
	printf("%d\n", ans);
	return 0;
}

/*

10 7
aabaabaabc
5 4
abcde
5 3
abcba
6 4
abbbaa

*/

每一位只要出现011三个字符就一定可以判断出三种运算了

因为&和其他可以用01去试,然后xor和|可以用11去试

显然不存在其他的不包括这个011的方案能验证出来....

答案每一位取max即可

code:



#include<bits/stdc++.h>
using namespace std;
const int MAXN = 505;

int n, m, T;
char a[MAXN][MAXN];
int cnt[MAXN], flg[MAXN];

inline void init() {
	for(int i = 1; i <= m; ++i) {
		cnt[i] = flg[i] = 0;
	}
}

int main() {
	scanf("%d", &T);
	while(T-- > 0) {
		scanf("%d%d", &n, &m);
		init();
		for(int i = 1; i <= n; ++i) {
			scanf("%s", a[i] + 1);
		}
		for(int i = 1; i <= n; ++i) {
			for(int j = 1; j <= m; ++j) {
				if(a[i][j] == '0') {
					flg[j] = 1;
				}
				if(a[i][j] == '1') {
					cnt[j]++;
				}
			}
		}
		int ans = 0;
		for(int i = 1; i <= m; ++i) {
			if(flg[i] && cnt[i] >= 2) {//110
				continue;
			} else if(!flg[i] && cnt[i] >= 2) {//111
				ans = max(ans, 1);
			} else if(flg[i] && cnt[i] < 2) {//0??
				ans = max(ans, 2 - cnt[i]);
			} else if(!flg[i] && cnt[i] < 2) {//???
				ans = max(ans, 3 - cnt[i]);
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

md....好像做过啊!

结论:大于53的质数没有用处,大于60的数没有用处

因为我们改成1一定更优秀

所以你会发现我们最后序列每个质因数一定只用了一次....

所以状压一下这16个质因数

然后考虑dp,f_{i,S}表示考虑了前i个数已经用了的质因数集合为S的最小代价

转移枚举下个数填什么,然后一定要是某个补集的子集才行

有很多种优化的方法

60个数不用全部枚举,可以剪掉一些显然sb的
只枚举当前有用集合中的,而有用集合可以预处理

code就没有了

重题

跟沈睿哥哥吐糟还被骂了

参照某篇叫[国家集训队]等差子序列的题

夏晓光(loveJY)的博客

P5384 [Cnoi2019]雪松果树