首页 > 其他分享 >CF 1714 D

CF 1714 D

时间:2022-09-27 21:55:59浏览次数:63  
标签:sz 1714 int CF flag ans pair new

感觉这次 D 比 F 还难……

题面

传送门走起!

思路

原先我的贪心写挂了。
我只考虑了开头,没考虑结尾。
事实证明结尾才是最重要的!


本题数据非常小。
从开头起,贪心的选择染哪个部分。
$ r \leftarrow -1 $, $ r $ 代表染完的下标。(-1 只是开始)
每次我们从下标 $ 0 \to r + 1 $ 里选择开头,贪心的选择结尾最后面的。
把 $ r $ 更新上去,就完成了一次染色。


结束是什么时候呢?
$ r + 1 \geq \text{size} (t) $

代码

有点凌乱。

#include <bits/stdc++.h>
using namespace std;

pair<string, int> s[15];
vector<pair<int, int> > ans;

int main() {
	int q;
	cin >> q;
	while (q--) {
		ans.clear();
		string t;
		cin >> t;
		int n;
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> s[i].first;
			s[i].second = i;
		}
		sort(s, s + n);
		int r = -1;
		bool flag;
		while (r + 1 < t.size()) {
			flag = 0;
			pair<string, int> ths;
			int new_r = -1, new_i = -1;
			for (int i = r + 1; i >= 0; i--) {
				for (int sz = 10; sz >= r - i + 2; sz--) {
					pair<string, int> use = *lower_bound(s, s + n, make_pair(t.substr(i, sz), -1));
					if (use != *upper_bound(s, s + n, make_pair(t.substr(i, sz), 0x3f3f3f3f))) {
						if (i + sz - 1 > new_r) {
							ths = use;
							new_r = i + sz - 1;
							new_i = i;
							flag = 1;
							break;
						}
					}
				}
			}
			ans.emplace_back(ths.second + 1, new_i + 1);
			r = new_r;
			if (!flag) {
				puts("-1");
				break;
			}
		}
		if (flag) {
			printf("%d\n", ans.size());
			for (auto i : ans) {
				printf("%d %d\n", i.first, i.second);
			}
		}
	}
	return 0;
}

标签:sz,1714,int,CF,flag,ans,pair,new
From: https://www.cnblogs.com/AProblemSolver/p/16736166.html

相关文章

  • CF1089I
    考虑用总数(\(n!\))减去不合法的排列数。我们现在要研究不合法的排列长什么样。称【将子段排序后是连续的一段数值】的子段称为不合法子段。那么合法的排列,就是不存在长度在......
  • 【题解】CF1589D Guess the Permutation
    这是一个交互题!题目链接-->Problem-D-Codeforces题目大意这是一个交互题!给定一个长度为\(n\)的自然排列,但其中\([i,j-1],[j,k]\)两部分被翻转了。你可以进......
  • CF1188D Make Equal
    假设\(a\)数组有序,记\(\text{cnt}(x)\)表示\(x\)的二进制表示中\(1\)的个数。那么我们就是要找一个\(x\)使得\(\sum_{i=1}^{n}\text{cnt}(x+a_n-a_i)\)最小。......
  • CF830D Singer House
    \(\text{Description}\)给定一棵深度为\(k(\le400)\)的满二叉树,每个节点均与其所有祖先连边。求树中每个节点最多经过一次的不同有向路径数量。\(\text{Solution}\)......
  • 洛谷 CF1257F Make Them Similar 灰 题解
    前言本题解采用折半搜索算法完成,对于不打算用这种方法的同学,这篇题解可能会浪费你人生中宝贵的十几分钟。思路此题似乎找不出什么好的性质,那么考虑暴力。发现\(x,a\)......
  • CF494B Obsessive String KMP+前缀和优化DP
    给一份看起来字数比较少的题解?题意给一个字符串\(s\),和一个字符串\(t\)。在\(s\)中取出任意多个不重叠的子串(可以有子串没有被取出),使得每个子串都包含\(t\),求方案......
  • 【luogu CF1109E】Sasha and a Very Easy Test(线段树)
    SashaandaVeryEasyTest题目链接:luoguCF1109E题目大意维护一个长度为n的序列,有区间乘,单点除(保证能整除),区间求和答案对p取模。p不一定是质数。思路麻了考场......
  • 题解【CF1436E Complicated Computations】
    CF1436EComplicatedComputations解题报告。不一定更好的阅读体验。对于一个数\(x\),考虑什么条件\(x\)可以作为答案。首先要满足\(\forally\in[1,x)\),\(y\)......
  • CF1730
    感觉这场的题目出得很好啊,让人忍不住想记录下来!赛时通过ABCD,rank\(76\)。A把每一种数的出现次数和\(c\)取个\(\min\)再求和即可。B记\(l=\min_i\{a_i-t......
  • CF C. Mr. Kitayuta, the Treasure Hunter
    题目链接https://codeforces.com/problemset/problem/505/C题目描述首先这样的题目可以想到搜索和普通线性dp但是搜索的话时间复杂度到了1e12了(应该没错)而正常dp[......