NC25254. 菜哭武的01串
描述
输入描述
输入一行包含一个字符串s（1<=|s|<=106），s是一个01字符串。
输出描述
输出一行，包含一个01字符串t，表示s能构成的1-N的二进制数最大整数N，使用二进制表示。如果不能构成任意正整数，输出0。
示例1
输入:
101
输出:
11
说明:
101可以构成1（取第一个或第三个字符）、10（取前两个字符）、11（取第一个和第三个字符），但是不能构成100。示例2
输入:
011
输出:
1
说明:
011可以构成1（取第二个或第三个字符），不能构成10C++14(g++5.4) 解法, 执行用时: 28ms, 内存消耗: 20056K, 提交时间: 2019-04-20 15:10:39
/*{{{*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<iostream>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include<bitset>
#include<vector>
#include<limits.h>
#include<assert.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define FOR(I, A, B) for (int I = (A); I <= (B); ++I)
#define FORS(I, S) for (int I = 0; S[I]; ++I)
#define RS(X) scanf("%s", (X))
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define CASET int ___T; scanf("%d", &___T); for(int cs=1;cs<=___T;cs++)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<PII> VPII;
typedef pair<LL,LL> PLL;
typedef vector<PLL> VPLL;
template<class T> void _R(T &x) { cin >> x; }
void _R(int &x) { scanf("%d", &x); }
void _R(LL &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }
template<class T> void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const LL &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template<class T,class U> void _W(const pair<T,U> &x) {_W(x.F); putchar(' '); _W(x.S);}
template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }
#ifdef HOME
#define DEBUG(...) {printf("# ");printf(__VA_ARGS__);puts("");}
#else
#define DEBUG(...)
#endif
int MOD = 1e9+7;
void ADD(LL& x,LL v){x=(x+v)%MOD;if(x<0)x+=MOD;}
/*}}}*/
const int SIZE = 1e6+10;
char s[SIZE];
int dp[SIZE];
int lt[SIZE][2];
int nxt[SIZE][2];
bool exist(int st,int n,int len){
int now=st;
REP(i,len){
now=nxt[now+1][0];
}
return now<=n;
}
char final_an[SIZE];
int main(){
RS(s+1);
int n=LEN(s+1);
nxt[n+1][0]=nxt[n+1][1]=n+1;
for(int i=n;i>0;i--){
REP(j,2)nxt[i][j]=nxt[i+1][j];
nxt[i][s[i]-'0']=i;
}
FOR(i,1,n){
REP(j,2)lt[i][j]=lt[i-1][j];
lt[i][s[i]-'0']=i;
}
if(nxt[1][1]==n+1)W(0);
else{
int st=nxt[1][1];
if(lt[n][0]<=st){
W(1);
return 0;
}
dp[1]=min(lt[n][0],lt[n][1]);
int now=1;
while(dp[now]>st){
dp[now+1]=min(lt[dp[now]-1][0],lt[dp[now]-1][1]);
now++;
}
if(!exist(st,n,now)){
W(string(now,'1'));
}
else{
int len=now;
now=st;
final_an[0]='1';
FOR(i,1,len-1){
if(nxt[now+1][0]<dp[len-i]){
final_an[i]='1';
now=nxt[now+1][1];
}
else{
final_an[i]='0';
now=nxt[now+1][0];
}
}
if(nxt[now+1][0]==n+1)final_an[len]='0';
else final_an[len]='1';
for(int i=len;i>0;i--){
if(final_an[i]=='1'){
final_an[i]='0';
break;
}
else final_an[i]='1';
}
W(final_an);
}
}
return 0;
}
Java(javac 1.8) 解法, 执行用时: 618ms, 内存消耗: 138188K, 提交时间: 2019-04-23 17:44:54
import java.io.BufferedInputStream;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class Mac{
int[][] next;
String temp;
public Mac(String temp) {
this.temp="*"+temp;
next=new int[temp.length()+2][2];
insert();
}
public void insert() {
int n=temp.length();
next[n][1]=next[n][0]=-1;
for(int i=n;i>=1;i--) {
for(int j=0;j<=1;j++) {
next[i-1][j]=next[i][j];
}
if(i<n)
next[i-1][temp.charAt(i)-'0']=i;
}
}
}
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(new BufferedInputStream(System.in));
String res=sc.next();
Mac mac=new Mac(res);
int[] pre=new int[res.length()+1];
boolean[] vis=new boolean[res.length()+1];
pre[0]=-1;
Queue<Integer> que=new LinkedList<Integer>();
PrintWriter out=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
que.offer(0);
while(!que.isEmpty()) {
int temp=que.poll();
for(int i=0;i<=1;i++) {
if(temp==0&&i==0)
continue;
int index=mac.next[temp][i];
if(index==-1) {
StringBuilder ans=new StringBuilder();
ans.append(""+(char)(i+'0'));
while(pre[temp]!=-1) {
ans.append(""+(char)(mac.temp.charAt(temp)));
temp=pre[temp];
}
ans=ans.reverse();
char[] str=new String(ans).toCharArray();
int len=str.length-1;
while(str[len]=='0') {
str[len]='1';
len--;
}
str[len]='0';
if(str.length==1) {
out.write(str);
}
else {
boolean flag=true;
for(int j=0;j<str.length;j++) {
if(str[j]=='0'&&flag)
continue;
flag=false;
out.write(str[j]);
}
}
out.println();
out.flush();
return ;
}
else
if(!vis[index]) {
vis[index]=true;
que.offer(index);
pre[index]=temp;
}
}
}
}
}
C++11(clang++ 3.9) 解法, 执行用时: 46ms, 内存消耗: 11000K, 提交时间: 2019-04-21 14:59:30
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
int f[maxn][2], n, tot;
char s[maxn];
bool ans[maxn];
int main()
{
scanf("%s", s + 1); n = strlen(s + 1);
for(int i = 1; i <= n; ++i) s[i] -= '0';
f[n + 1][0] = f[n + 1][1] = -1;
s[0] = 0;
for(int i = n; ~i; --i)
{
f[i][s[i]] = min(f[i + 1][0], f[i + 1][1]) + 1;
f[i][s[i] ^ 1] = f[i + 1][s[i] ^ 1];
}
f[0][0] = f[0][0] <= f[0][1] ? f[0][1] + 1 : f[0][0];
//for(int i = 0; i <= n; ++i) cout << f[i][0] << ' ' << f[i][1] << endl;
int l = 0, bit = f[0][0], zero = 1e9;
bool flag, one = 0;
while(l <= n)
{
if(!s[l])
{
if(zero < bit - f[l][0] - 1)//0的个数不够
++zero, one = 0;
else
{
bit = f[l][0];
ans[bit] = 1;
tot = max(tot, bit);
zero = 0;
flag = one;
if(!flag)
{
while(l <= n && !s[l]) ++l;
if(l > n) break;
flag = 1;
one = 0;
}
}
}
else one = 1;
++l;
}
if(zero < bit) flag = 0;
if(!flag)
{
for(int i = 0; i <= tot; ++i)
{
ans[i] ^= 1;
if(!ans[i]) break;
}
}
while(tot && !ans[tot]) --tot;
for(int i = tot; ~i; --i) cout << ans[i];
cout << endl;
return 0;
}
/*
11110100
*/