首页 > 其他分享 >Shrink-Reverse

Shrink-Reverse

时间:2024-02-24 15:44:21浏览次数:21  
标签:hsh Reverse int rep vec 区间 Shrink define

题目传送门

有趣的字符串题!抢在官方题解之前写一篇题解。

思路

因为需要使字符串代表的整数最小化,所以我们显然要删除前导零后的最终序列长度尽可能小。

我们发现为了达成这个目的,可以把所有的 \(1\) 都聚集到一个区间内,不妨设这个区间是 \([l,r]\)。

那么 \(1 \dots l-1\) 和 \(r+1 \dots n\) 就全是 \(0\),我们可以翻转一次把 \(1 \dots l-1\) 的 \(0\) 去掉,这样 \(r+1 \dots n\) 的 \(0\) 就变成前导零了,可以忽略它们。

容易发现使用更多的翻转次数不优,因为若使用更多翻转操作,一定会使得 \([l,r]\) 的长度增大,这与我们“要使最终序列长度尽可能小”的目的背道而驰。

更进一步,我们可以发现两个比较显然的性质:

  • 区间 \([l,r]\) 外的 \(1\) 一定尽可能移到区间内靠近 \(l\) 的位置(因为我们需要翻转序列)。

  • \(\forall l\),有用的区间只有一个。

我们可以双指针把所有有用的区间找出来,答案区间一定在这些区间中长度最小的那些区间之中。

现在问题变成如何比较两个长度相同的区间最终形成的字符串哪个字典序小。

经过简单的观察,又可以发现一个显然的性质:

  • 这两个区间填入的 \(1\) 的个数是相同的。

于是问题等价于比较原串的这两个区间翻转之后的字典序(证明不难,可以自己思考一下)。

而这个问题又等价于比较两个前缀翻转之后的字典序。

于是就非常简单了,exkmp,二分哈希,SA 均可。

但是这个做法当区间 \([l,r]\) 的 \(r=n\) 时有点小问题,因为此时有一种特殊的方案是把 \(1 \dots l-1\) 的 \(1\) 放在倒数若干个 \(0\) 上,特判一下即可。

时间复杂度 \(\Theta(n \log n/n)\)。

代码

//A tree without skin will surely die.
//A man without face is invincible.
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sqr(x) ((x)*(x))
#define all(x) (x).begin(),(x).end()
#define Tim ((double)clock()/CLOCKS_PER_SEC)
#define mid ((l+r)>>1)
#define lowbit(x) (x&-x)
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
int const N=5e5+10;
int const mod=1e9+7;
int n,k,sm,pw[N],qz0[N],qz1[N];string s;
struct Hash_Table{
    #define ull unsigned long long
    int const B=457;
    ull hsh[N],bse[N];
    inline void init(string s){
        s=" "+s,hsh[0]=bse[0]=1;
        rep(i,1,n) hsh[i]=hsh[i-1]*B+(s[i]-'0')*31+233;
        rep(i,1,n) bse[i]=bse[i-1]*B;
    }
    inline ull qry(int l,int r){
        ++l,++r;
        return hsh[r]-hsh[l-1]*bse[r-l+1];
    }
}T;
inline int qry0(int l,int r){if (l>r) return 0;if (r<0) return 0;if (!l) return qz0[r];return qz0[r]-qz0[l-1];}
inline int qry1(int l,int r){if (l>r) return 0;if (r<0) return 0;if (!l) return qz1[r];return qz1[r]-qz1[l-1];}
inline string get(string ans){
    int r=0; 
    while (ans[r]=='0') ++r;
    string t="";
    rep(i,r,(int)ans.size()-1) t+=ans[i];
    return t;
}
inline string chk(int L,int R){
    string t=s,ans=s;
    vector<int>vec;
    rep(i,L,R) if (t[i]=='0') vec.push_back(i);
    int re=0;
    rep(i,0,L-1) if (t[i]=='1') swap(t[i],t[vec[re]]),++re;
    per(i,n-1,R+1) if (t[i]=='1') swap(t[i],t[vec[re]]),++re;
    if (re<k){
        t=get(t),reverse(all(t)),t=get(t);
        if (t.size()<ans.size()) ans=t;
        else if (t.size()==ans.size()) ans=min(ans,t);
    }
    return ans;
}
inline int qry(int x,int y){
    int l=1,r=y+1,ans=0;
    while (l<=r)
        if (T.qry(x-mid+1,x)==T.qry(y-mid+1,y)) l=(ans=mid)+1;
        else r=mid-1;
    return ans;
}
inline string work(){
    string ans=s;
    vector<int>vec;
    per(i,n-1,0) if (s[i]=='0') vec.push_back(i);
    int m=k,l=0;
    rep(i,0,n-1){
        if (!m) break;
        if (l==(int)vec.size()) break;
        if (ans[i]=='1'){
            if (vec[l]<i) break;
            swap(ans[i],ans[vec[l]]),++l,--m;
        }
    }
    ans=get(ans),l=0;
    int ansl=-1e18,ansr=1e18;
    rep(i,0,n-1){
        while (l<n && (qry1(0,i-1)+qry1(l+1,n-1)>qry0(i,l) || qry1(0,i-1)+qry1(l+1,n-1)>=k)) ++l;
        if (l>=n) break;
        if (l-i+1>ansr-ansl+1) continue;
        if (l-i+1<ansr-ansl+1){ansl=i,ansr=l;continue;}
        int g=qry(l,ansr);
        if (g==ansr+1) continue;
        if (s[l-g]<s[ansr-g]) ansl=i,ansr=l;
    }
    if (ansr-ansl+1<(int)ans.size()) ans=chk(ansl,ansr);
    else if (ansr-ansl+1==(int)ans.size()) ans=min(ans,chk(ansl,ansr));
    return ans;
}
void solve(){
    cin>>n>>k>>s,T.init(s),qz0[0]=s[0]=='0',qz1[0]=s[0]=='1';
    rep(i,1,n-1) qz0[i]=qz0[i-1]+(s[i]=='0'),qz1[i]=qz1[i-1]+(s[i]=='1');
    string ans=work();
    int res=0;
    rep(i,0,(int)ans.size()-1)
        res+=(ans[i]=='1')*pw[ans.size()-1-i],res%=mod;
    cout<<res<<'\n';
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    pw[0]=1;
    rep(i,1,N-1) pw[i]=pw[i-1]*2%mod;
    int t=1;
    // cin>>t;
    while (t--) solve();
    cerr<<"Running Time: "<<(double)clock()/CLOCKS_PER_SEC<<" s\n";
    return 0;
}

标签:hsh,Reverse,int,rep,vec,区间,Shrink,define
From: https://www.cnblogs.com/tx-lcy/p/18031152

相关文章

  • NewStarCTF 2023 WEEK2|REVERSE SMC 使用IDApython静态解决SMC
    先来一篇IDApyhotn的指令教程https://www.cnblogs.com/zydt10/p/17676018.html*自己编的这题对应的expa=[0x11,0x22,0x33,0x44]foriinrange(38):result=a[i&3]ida_bytes.patch_byte(0x403040+i,get_wide_byte(0x403040+i)^result)在IDA中运行完exp之后,......
  • BUUCTF Reverse reverse2 wp
    与上一题相同。分析代码得将字符串中的“i”“r”替换成“1”即为flag值。......
  • CF1401F Reverse and Swap 题解
    解题思路巧妙的数据结构题,非常巧妙的利用的线段树的奇妙性质。操作逐条维护:Replace:直接线段树上单点修改;Sum:线段树查询区间和;Reverse:考虑线段树的形态。线段树第\(i\)层(除最后一层)有\(2^{i-1}\)个节点,那么将所有\(i\ge1\)的区间\([(i-1)\times2^k,i\times2^k]\)......
  • BUUCTF Reverse reverse1 wp
    分析代码由代码①得:用户需要输入字符串Str1,如果与Str2比较相同,则会提示flag正确。说明Str2中存储的字符串就是flag。点击代码中Str2,跳转至对应存储内容。代码②上方代码不影响字符判断,所以可不用分析。由代码②得:在for循序中遍历字符串Str2,(按R键,将数值转换为对应的ASCII码字......
  • [ARC154E] Reverse and Inversion 题解
    题目链接点击打开链接题目解法\(\sumj-i\)是不好维护的,考虑把\(j-i\)拆成之和\(i,j\)相关的项可以得到:\(\sum\limits_{i<j}[p_i>p_j](j-i)=\sum\limits_{i=1}^ni(\sum\limits_{j=1}^{i-1}[p_j>p_i]-\sum\limits_{j=i+1}^n[p_j<p_i])=\sum\limits_{i=1}^ni(i-1-\sum\......
  • BUUCTF Reverse easyre wp
    使用exeinfo工具查看文件信息使用IDA64位打开文件,再使用Shift+F12打开字符串窗口,发现flag字符串双击跳转到字符串在汇编代码中的存储地址点击字符串下方注释中的跳转链接,即可跳转至引用它的函数对应的汇编代码处按F5反汇编,生成对应汇编代码处的C语言伪代码分析代码。......
  • flex-shrink计算上的一些细节
    <!DOCTYPEhtml><htmllang="cmn-hans"><head><metacharset="UTF-8"><metaname="viewport"content="width=device-width,initial-scale=1.0"><title>Document</title&g......
  • 00000030.ReverseAnalysis.ring0层注册表监控
    00000030.ReverseAnalysis.ring0层注册表监控links深入理解注册表监控从0环监测注册表机制...好像还是有点门槛的如何监控注册表是windows的重要数据库,存放了很多重要的信息以及一些应用的设置,对注册表进行监控并防止篡改是十分有必要的。在64位系统下微软提供了CmRegiste......
  • Reverse a linked list【1月17日学习笔记·】
    点击查看代码//Reverssealinkedlist#include<iostream>usingnamespacestd;structnode{ intdata; node*next;};node*A;voidreverse(){ node*next;//用于保存下一个·节点地址以便索引 node*current=A;//当前索引 node*prev=NULL;//保存上一个节点......
  • P10058 Reverse and Rotate题解
    简单题意一共3个操作:rev:将字符串翻转。>\(x\):将后面\(x\)个字母移到前面。<\(x\):将前面\(x\)个字母移到后面。解法解法一看到#1到#3的范围可以打出暴力程序,按题意模拟,时间复杂度\(O(n|S|)\)。预计\(30\)pts。解法二很明显,第二个操作和第三个操作有点像......