济南做网站优化公司,做网站销售怎么开发客户,网站建设与管理实践,网址格式D. Cases 题意
有一个长度为 n n n 且仅由前 c c c 个大写字母组成的字符串#xff0c;问最少选取多少种字母为每个单词的结尾#xff0c;使得每个单词长度不超过 k k k
思路
首先注意到最后一个字母一定要选择#xff0c;接下来我们给出一个断言#xff1a;如果一个…D. Cases 题意
有一个长度为 n n n 且仅由前 c c c 个大写字母组成的字符串问最少选取多少种字母为每个单词的结尾使得每个单词长度不超过 k k k
思路
首先注意到最后一个字母一定要选择接下来我们给出一个断言如果一个字母被选上了那么对于这个字母在字符串中所有出现的位置用这些位置作为结尾是最优的 这是因为如果最优的答案存在一个单词横跨了所选的这个字母因为这个单词长度本身小于等于 k k k所以我们把他划分成两段一段以所选的字母结尾另一段以原先单词自己的字母结尾这样子并不会使得答案更劣所以我们一旦选择了某个字母一定是选择其在字符串中出现的所有位置
进一步观察发现对于每 k k k 个连续的字符我们一定至少选择 1 1 1 个字母作为结尾 简化一下单词长度不超过 k k k 的这个条件我们如果对于每一个长度恰好为 k k k 的一个窗口把这个窗口里所有出现的字母记录一下形成一个 m a s k mask mask那么对于所有的 O ( n ) O(n) O(n) 个 m a s k mask mask我们等价于要满足每个 m a s k mask mask 都至少有 1 1 1 位被选作最终的答案集合
至此问题便转化为了对于 O ( n ) O(n) O(n) 个 m a s k mask mask我们要选择一个含 1 1 1 数量最少的且与每个 m a s k mask mask 有交且 a n s ans ans 必须包含最后一个字母
直接枚举 a n s ans ans 并与 O ( n ) O(n) O(n) 个 m a s k mask mask 求交太慢我们可以先把全部不合法的 a n s ans ans 筛出来再从剩下的所有合法的 a n s ans ans 中选一个最少的即可
接下来我们将 O ( n ) O(n) O(n) 个 m a s k mask mask 放入数组 a a a 中注意到一个答案 b b b 如果不合法那么一定有 b a i 0 b \; \ \; a_i 0 bai0即一定存在至少一个 m a s k mask mask使得 b b b 与其没有任何的交集那么这个 b b b 不合法 剩下的一定是合法的。 注意到 a b 0 ⇔ b ⊂ a ˜ ( a 的补集 ) a \; \ b \; 0 \Lrarr b \subset \~a (a 的补集) ab0⇔b⊂a˜(a的补集)即 b b b 是 a a a 的补集的子集 现在我们有了 O ( n ) O(n) O(n) 个母集 a i a_i ai我们需要筛出其所有的子集 b ⊂ a i b \subset a_i b⊂ai这个过程我们可以使用 S O S D P SOS \; DP SOSDP
时间复杂度 O ( c n c 2 c ) O(cn c2^c) O(cnc2c)
#includebits/stdc.h
#define fore(i,l,r) for(int i(int)(l);i(int)(r);i)
#define fi first
#define se second
#define endl \n
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()
#define Debug(x, ed) std::cerr #x x ed;const int INF0x3f3f3f3f;
const long long INFLL1e18;typedef long long ll;int main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int t;std::cin t;while(t--){int n, c, k;std::cin n c k;std::string s;std::cin s;s 0 s;std::vectorstd::vectorint sum(n 1, std::vectorint(26, 0));std::vectorint a;fore(i, 1, n 1){int ch s[i] - A;fore(j, 0, c) sum[i][j] sum[i - 1][j];sum[i][ch];if(i k){int mask 0;fore(j, 0, c)if(sum[i][j] - sum[i - k][j])mask | 1 j;a.push_back(mask);}}for(int mask : a) mask (~mask ((1 c) - 1));std::vectorint dp(1 c, 1);for(auto mask : a) dp[mask] 0;fore(i, 0, c)fore(mask, 0, 1 c)if(!(mask i 1))dp[mask] dp[mask ^ (1 i)];int last s.back() - A;int ans c;fore(mask, 0, 1 c)if(dp[mask] (mask last 1))ans std::min(ans, __builtin_popcount(mask));std::cout ans endl;}return 0;
}
