首页 > 其他分享 >CF1158B The minimal unique substring

CF1158B The minimal unique substring

时间:2024-10-27 23:12:31浏览次数:7  
标签:限制 位置 substring define 这道题 考虑 unique minimal 性质

这题是有迹可循的!下面从一个思考者的角度讲述解题方法。

首先这两条限制很奇怪,但感觉都是很强的性质。所以这道题光想入手都是比较难的,先考虑怎么入手。

第二条限制相对简单,先考虑第二条限制。我们注意到,如果一个串的数字全是 \(1\),显然可以满足限制一。那限制二我们考虑将一个 \(1\) 变成 \(0\) 达到。考虑变第一个 \(1\),发现有烦人的性质一,考虑把第 \(k\) 个 \(1\) 变成 \(0\),并将末尾变成 \(0\),这可以解决 \(2k\le n\) 的情况。

若 \(2k>n\) 怎么办?我们考虑找到一个恰当的位置塞下唯一的那个子串,但是我手玩了亿点点方案都没能解决,怎么办?这道题最厉害的地方来了,别忘了 \(n,k\) 奇偶性相同,而一共有 \(n-k+1\) 个位置可以塞下满足性质二的串,我们对前 \(n-k+1\) 个位置进行思考,我们发现,位置个数是奇数,我们把正中间的 \(1\) 变成 \(0\),其它位置不变,这样性质二就满足了。对于性质 \(1\),我们发现每隔 \(\frac{n-k}{2}\) 个 \(1\) 中塞一个 \(0\) 就能满足性质一,然后一个很优美的构造方法就这样想出来啦!

事实上,这道题我一共想了一小时,而真正有进展的只有寥寥几分钟,这种题虽然很巧妙,但还是希望这种题不要在正赛考场中出现。。

代码:

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; ++ i)
#define rrp(i, l, r) for (int i = r; i >= l; -- i)
#define pii pair <int, int>
#define eb emplace_back
#define id(x, y) m * ((x) - 1) + (y)
#define ls p << 1
#define rs ls | 1
using namespace std;
constexpr int N = 1e5 + 5;
constexpr double PI = acos (-1.0);
typedef long long ll;
typedef unsigned long long ull;
inline int rd () {
  int x = 0, f = 1;
  char ch = getchar ();
  while (! isdigit (ch)) {
    if (ch == '-') f = -1;
    ch = getchar ();
  }
  while (isdigit (ch)) {
    x = (x << 1) + (x << 3) + ch - 48;
    ch = getchar ();
  }
  return x * f;
}
int n, k;
char s[N];
int32_t main () {
  // freopen ("1.in", "r", stdin);
  // freopen ("1.out", "w", stdout); 
  n = rd (), k = rd ();
  int o = (n - k) / 2 + 1, i;
  for (i = 1; i + o - 1 <= n; i += o) {
    rep (j, 1, o - 1) putchar ('1');
    putchar ('0');
  }
  for (; i <= n; ++ i) putchar ('1');
}

标签:限制,位置,substring,define,这道题,考虑,unique,minimal,性质
From: https://www.cnblogs.com/lalaouyehome/p/18509240

相关文章

  • [题解]CF825E Minimal Labels
    LPhang为什么是神?思路显然可以想到一个错误的贪心:直接拓扑排序,每一次选择当前可以拓展的点中最小的元素进行编号。由于可能存在一个值较小的元素被藏在一个较大的元素后面,这种贪心就会出问题。出问题的本质原因就是我们希望字典序最小,就得使得越小的位置分配到更小的值。不妨......
  • LeetCode 1371. Find the Longest Substring Containing Vowels in Even Counts
    原题链接在这里:https://leetcode.com/problems/find-the-longest-substring-containing-vowels-in-even-counts/description/题目:Giventhestring s,returnthesizeofthelongestsubstringcontainingeachvowelanevennumberoftimes.Thatis,'a','e&......
  • 【MYSQL】MYSQL约束-----非空约束(not null)和唯一约束(unique)
    1、概念MYSQL非空约束(notnull),指字段的值不能为空。对于使用了非空约束的字段,如果用户在添加数据时没有指定值,数据库就会报错。注意:非空约束一张表中可以有多个。2、语法方式1:在创建表时指定(常用)<字段名><数据类型>not null例如:create table  t_user(i......
  • std::unique_lock
    std::unique_lock是C++11标准库中的一个类,提供了一种灵活的方式来管理互斥量(mutex)。它比std::lock_guard更加灵活,允许在不同的作用域和不同的锁定策略之间进行选择。以下是对unique_lock的详细解释,包括其用途、使用方法和优点。1.定义std::unique_lock是一种RAII(资......
  • C++ 智能指针详解: std::unique_ptr 和 std::shared_ptr
    C++11引入了智能指针,它们是管理动态分配内存的强大工具。本文将详细介绍两种最常用的智能指针:std::unique_ptr和std::shared_ptr。std::unique_ptr概述std::unique_ptr是一种独占所有权的智能指针。它确保一个对象只能被一个unique_ptr所拥有,这意味着不能复制unique_......
  • BZOJ 2555 = P5212 SubString 题解
    Statement给你一个字符串 \(\text{init}\),要求你支持两个操作:在当前字符串的后面插入一个字符串;询问字符串 \(s\) 在当前字符串中出现了几次?(作为连续子串)你必须在线支持这些操作。Solutionextend中link[cur]=q,相当于link,链加新建copy那里,相当于link,cut,链加询......
  • UNIQUE VISION Programming Contest 2024 Autumn (AtCoder Beginner Contest 372)
    总结(我的塘人局):单调栈是忘得差不多了 A-delete.题意:输出删除所有'.'的字符串思路:遍历输出不是'.'复杂度:O(n) Code:#include<bits/stdc++.h>usingnamespacestd;usingLL=longlong;usingi64=int64_t;voidsolve(){strings;cin......
  • 智能指针unique_ptr<>创建的过程
    智能指针unique_ptr<>创建的过程两种初始化方式的比较std::unique_ptr可以通过两种方式进行初始化:直接构造或者使用std::make_unique()。它们之间的区别如下:直接构造std::unique_ptr:你可以通过直接构造来创建一个unique_ptr,如下:std::unique_ptr<int>ptr(newint(42));......
  • [1060] Create the unique ID from the index (DataFrame, GeoDataFrame)
    Thereareseveralwaystoimplementit!Hereisasampledataset:importpandasaspd#SampleDataFramedf=pd.DataFrame({'A':[1,2,3,4],'B':[None,5,None,7]})1.pd.Series()#ConverttheindextoaSerieslikeac......
  • 【C++基础概念理解——std::unique_ptr如何管理动态分配的对象的生命周期?】
    文章目录问题解释问题std::unique_ptr用于管理动态分配的对象的生命周期,那么这种智能指针怎么实现管理生命周期的呢?解释用于确保对象不再使用时自动释放,从而避免内存泄漏。std::unique_ptr独占管理对象的所有权,同一时间只能有一个std::unique_ptr指向该对象。确保......