首页 > 其他分享 >CodeForces 1789F Serval and Brain Power

CodeForces 1789F Serval and Brain Power

时间:2023-03-09 09:33:49浏览次数:44  
标签:cnt int 1789F CodeForces long Brain typedef maxn define

洛谷传送门

CF 传送门

很牛逼的题啊!感觉套路很实用,感谢 ntf。

考虑 \(totlen = cnt \times len \le 80\)。若 \(cnt \le 3\),可以 \(O(|S|^{2cnt - 1})\) 暴力枚分割点。\(cnt = 4\) 包含在 \(cnt = 2\) 内,无需考虑。\(cnt \ge 5\) 也即 \(len \le 16\),这时候有一个很牛逼的结论:答案的循环节一定包含于 \(S\) 的其中一个长度为 \(16\) 的子串内。证明考虑反证,若均不包含则 \(cnt\) 不可能取到 \(\ge 5\)。然后暴力枚举循环节即可。

启发:没有好的想法考虑根号分治或类根号分治(此题)。

code
// Problem: F. Serval and Brain Power
// Contest: Codeforces - Codeforces Round 853 (Div. 2)
// URL: https://codeforces.com/problemset/problem/1789/F
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 85;

int n, m, m1, m2, m3, f[maxn][maxn], g[maxn][maxn][maxn];
char s[maxn], t[maxn], a[maxn], b[maxn], c[maxn];

void solve() {
	scanf("%s", s + 1);
	n = strlen(s + 1);
	int ans = 0;
	for (int p = 1; p < n; ++p) {
		m1 = m2 = 0;
		for (int i = 1; i <= p; ++i) {
			a[++m1] = s[i];
		}
		for (int i = p + 1; i <= n; ++i) {
			b[++m2] = s[i];
		}
		for (int i = 0; i <= m1; ++i) {
			for (int j = 0; j <= m2; ++j) {
				f[i][j] = 0;
			}
		}
		for (int i = 1; i <= m1; ++i) {
			for (int j = 1; j <= m2; ++j) {
				f[i][j] = max({f[i - 1][j], f[i][j - 1], a[i] == b[j] ? f[i - 1][j - 1] + 1 : 0});
			}
		}
		ans = max(ans, f[m1][m2] * 2);
	}
	for (int p1 = 1; p1 < n; ++p1) {
		for (int p2 = p1 + 1; p2 < n; ++p2) {
			m1 = m2 = m3 = 0;
			for (int i = 1; i <= p1; ++i) {
				a[++m1] = s[i];
			}
			for (int i = p1 + 1; i <= p2; ++i) {
				b[++m2] = s[i];
			}
			for (int i = p2 + 1; i <= n; ++i) {
				c[++m3] = s[i];
			}
			for (int i = 0; i <= m1; ++i) {
				for (int j = 0; j <= m2; ++j) {
					for (int k = 0; k <= m3; ++k) {
						g[i][j][k] = 0;
					}
				}
			}
			for (int i = 1; i <= m1; ++i) {
				for (int j = 1; j <= m2; ++j) {
					for (int k = 1; k <= m3; ++k) {
						g[i][j][k] = max({g[i - 1][j][k], g[i][j - 1][k], g[i][j][k - 1], (a[i] == b[j] && b[j] == c[k]) ? g[i - 1][j - 1][k - 1] + 1 : 0});
					}
				}
			}
			ans = max(ans, g[m1][m2][m3] * 3);
		}
	}
	for (int i = 1; i <= n; ++i) {
		for (int S = 1; S < (1 << 16); ++S) {
			m = 0;
			for (int j = 0; j < 16 && i + j <= n; ++j) {
				if (S & (1 << j)) {
					t[++m] = s[i + j];
				}
			}
			int cnt = 0;
			for (int j = 1, k = 1; j <= n; ++j) {
				if (s[j] == t[k]) {
					if ((++k) > m) {
						k = 1;
						++cnt;
					}
				}
			}
			ans = max(ans, cnt > 1 ? cnt * m : 0);
		}
	}
	printf("%d\n", ans);
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

标签:cnt,int,1789F,CodeForces,long,Brain,typedef,maxn,define
From: https://www.cnblogs.com/zltzlt-blog/p/17197111.html

相关文章

  • 程序员推荐!JetBrains IDEs使用技巧与必备插件
    JetBrains是耳熟能详的软件开发工具提供商,旗下的IDE集成开发环境被广泛应用于不同的开发领域。本文将向新手介绍JetBrainsIDEs的基本知识和常用功能。什么是JetBrainsID......
  • CF1780F Codeforces Round 846 (Div. 2) F. Three Chairs
    https://codeforces.com/contest/1780/problem/F计算\[\sum_{i,j,k}[gcd(min(a_i,a_j,a_k),max(a_i,a_j,a_k))=1]\]对\(a_i\)排序,则需计算\[\sum_{i<k......
  • Codeforces Round 855 (Div. 3) F
    F核心思路首先我们可以知道的是只要满足了条件2和条件3必然会满足条件1.因为奇数和奇数的乘积一定是奇数。这一个比较显而易见的性质。然后就是我们需要思考我们得使用......
  • Codeforces Round 855 (Div. 3)(E,F)
    CodeforcesRound855(Div.3)(E,F)在\(div2\)受虐久了,这次\(div3\)打的还蛮顺利的(虽然\(wa\)了好几次)EE题目大意就是有两个字符串,我们要通过以下两种操作把第一个字符变......
  • CF1789 Codeforces Round 853 (Div. 2) D. Serval and Shift-Shift-Shift
    https://codeforces.com/contest/1789/problem/D给定两个n位二进制数a,b,你可以每次使\(a=a\oplusa>>k\)或\(a=a\oplusa<<k\),你需要用不超过n次操作......
  • CF1793 Codeforces Round 852 (Div. 2) D. Moscow Gorillas
    https://codeforces.com/contest/1793/problem/D对于给定的两个长度为\(n\)的排列\(a_i,b_i\),定义\(MEX(S)\)为集合\(S\)中没有出现的最小的正整数,找出所有满足......
  • Codeforces Round 856 (Div. 2)
    《C.ScoringSubsequences》  这道题有很多解法:二分,双指针等,但是无论哪一种都要知道如下:想要得到当k时,最大的分数,那么就会贪心地将后面的数相乘再......
  • Codeforces Round 855 (Div
    Problem-E2-UnforgivableCurse(hardversion)给定一个初始字符串s和目标字符串t,我们可以对字符串s进行以下任意次操作:对于位置\(i\),如果\(i+k+1<=s.length()\)......
  • Codeforces Round 855 (Div. 3)
    链接CodeforcesRound855(Div.3)A题这个题先将大写变小写然后将重复元素去除,判断是不是等于meow就可以#include<iostream>#include<algorithm>#include<cstdi......
  • Codeforces Global Round 3
    A   题解:显然就拼一下$a,b$然后再把$c$用完,记得判一下$a=b$的特殊情况。#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;consti......