博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Codeforces 1159D The minimal unique substring(构造)
阅读量:5162 次
发布时间:2019-06-13

本文共 2074 字,大约阅读时间需要 6 分钟。

首先我们先观察三个串 1010,110110,11101110,答案都是红色部分,我们可以下一个结论,形如 abab ( a 中有非负整数个 1 , b 中只有一个 0 )这类的字符串答案恒为 2 ,也就是 k==2 ,然后就是用这类字符串去构造出我们所需的 k 。我们可以尝试从末尾加一个1,那么之前的串变成了 10101,1101101,111011101,那么答案为红色部分。我们可以发现,通过我们末尾添加的1,导致之前红色部分的 01 与我们末尾添加的1与前面一个0构成的 01 重复,使得之前的红色部分向后挪一位。于是,我们可以用这一规律去构造出我们想要的k,显然答案就是末尾部分的01(蓝色部分111...10111...10111满足 0 的个数加 1 的个数等于 k-1  ,那么对中间的影响(绿色部分111...1011111...110111)往后挪一位也就是我们的答案 k ,最后就是算出这形如 abab 字符串 a 部分中的 1 的个数有多少就行了,设 x 为 a 中 1 的个数,方程为 2*x+1+k-1=n  ,化简为 x=(n-k)/2 ,根据题意 n k 同奇偶,那么 x 也是唯一确定的,最后构造也由此生成。

 

1 //      ——By DD_BOND 2  3 //#include
4 #include
5 #include
6 #include
7 #include
8 #include
9 #include
10 #include
11 #include
12 #include
13 #include
14 #include
15 #include
16 #include
17 #include
18 #include
19 #include
20 #include
21 #include
22 #include
23 #include
24 #include
25 26 #define fi first27 #define se second28 #define MP make_pair29 #define pb push_back30 #define INF 0x3f3f3f3f31 #define pi 3.141592653589832 #define lowbit(a) (a&(-a))33 #define lson l,(l+r)/2,rt<<134 #define rson (l+r)/2+1,r,rt<<1|135 #define Min(a,b,c) min(a,min(b,c))36 #define Max(a,b,c) max(a,max(b,c))37 #define debug(x) cerr<<#x<<"="<
<<"\n";38 39 using namespace std;40 41 typedef long long ll;42 typedef pair
P;43 typedef pair
Pll;44 typedef unsigned long long ull;45 46 const ll LLMAX=2e18;47 const int MOD=1e9+7;48 const double eps=1e-8;49 const int MAXN=1e6+10;50 const int hmod1=0x48E2DCE7;51 const int hmod2=0x60000005;52 53 inline ll sqr(ll x){ return x*x; }54 inline int sqr(int x){ return x*x; }55 inline double sqr(double x){ return x*x; }56 ll __gcd(ll a,ll b){ return b==0? a: __gcd(b,a%b); }57 ll qpow(ll a,ll n){ll sum=1;while(n){ if(n&1)sum=sum*a%MOD;a=a*a%MOD;n>>=1;}return sum;}58 inline int dcmp(double x){ if(fabs(x)
0? 1: -1); }59 60 int main(void)61 {62 ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);63 int n,k; cin>>n>>k;64 for(int i=0,j=(n-k)/2;i

 

转载于:https://www.cnblogs.com/dd-bond/p/10858347.html

你可能感兴趣的文章
JS实现全选与取消 Jquery判断checkbox是否被选中
查看>>
如果重新设计网络,有没有可能合并IP地址跟MAC地址?
查看>>
德州扑克总纲
查看>>
linux下password的用法
查看>>
[poj1986]Distance Queries(LCA)
查看>>
BPM配置故事之案例11-操作外部数据源
查看>>
uniGUI试用笔记(一)
查看>>
漫谈python中的搜索/排序
查看>>
js_类数组转化为数组
查看>>
centos 7 安装 rvm 超时
查看>>
类库间无项目引用时,在编译时拷贝DLL
查看>>
module 'socket' has no attribute的解决方案
查看>>
Java NIO vs. IO
查看>>
BIO、NIO、AIO通信机制
查看>>
STL priority_queue<> 用法 <转>
查看>>
POJ-3009 Curling 2.0 简单BFS
查看>>
vs 2010 快捷键
查看>>
ref用于类类型
查看>>
canvas
查看>>
Balanced Binary Tree
查看>>