蒟蒻求问
  • 板块学术版
  • 楼主_yjh
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/2/8 11:05
  • 上次更新2023/10/28 09:26:40
查看原帖
蒟蒻求问
222104
_yjh楼主2022/2/8 11:05
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
set <ll> st;
string s,_s;
ll pw2[25],sit;
ll chg(string s) {
    ll base=0,ans=0;
    for(int i=s.size()-1;i>=0;i--) {
        if(s[i]=='1') ans+=pw2[base];
        base++;
    }
    return ans;
}
void Getans(ll a,ll len) {
    _s="";
    while(a) {
        if(a%2) _s+='1';
        else _s+='0';
        a/=2;
    }
    for(int i=1;i<=len-_s.size();i++) cout<<'0';
    for(int i=_s.size()-1;i>=0;i--) cout<<_s[i];
    cout<<'\n';
}
int main() {
    cin>>s;
    int ans,l=1,r=24,mid;
    pw2[0]=1;
    for(int i=1;i<=24;i++) pw2[i]=pw2[i-1]*2;
    while(l<=r) {
	    mid=(l+r)/2;
    	if(mid>s.size()) {
    		r=mid-1;
    		continue;
		}
    	_s="";
    	for(int i=0;i<mid;i++) _s+=s[i];
    	sit=chg(_s);
    	string::iterator it=_s.begin();
    	st.insert(sit);
    	//cout<<_s<<'\n';
    	for(int i=mid;i<s.size();i++) {
    		sit<<=1;
    		if(_s[0]=='1') sit-=pw2[mid];
    		if(s[i]=='1') sit++;
    		_s.erase(it);
    		_s+=s[i];
    		st.insert(sit);
    		//cout<<_s<<'\n';
		}
		if(st.size()<pw2[mid]) ans=mid,r=mid-1;
		else l=mid+1;
		st.clear();
	}
    st.clear();
    _s="";mid=ans;
    for(int i=0;i<mid;i++) _s+=s[i];
    string::iterator it=_s.begin();
    sit=chg(_s);
    st.insert(sit);
    //cout<<_s<<'\n';
    for(int i=mid;i<s.size();i++) {
    	sit<<=1;
    	if(_s[0]=='1') sit-=pw2[mid];
    	if(s[i]=='1') sit++;
    	_s.erase(it);
    	_s+=s[i];
    	st.insert(sit);
    	//cout<<_s<<'\n';
	}
    set<ll>::iterator its=st.begin();
    _s="";
    for(int i=1;i<=ans;i++) _s+='0';
    ll i=0;
    while(its!=st.end()) {
        if(i!=*its) break;
        //cout<<chg(*its)<<'\n';
        its++;i++;
    }
	Getans(i,ans);
    return 0;
}

这段代码跑不了文件输入输出,但直接编译答案没有问题。实在不知道是电脑的问题还是我的问题,有没有大佬能解答一下,谢谢了。

2022/2/8 11:05
加载中...