CodeForces 1204 (#581 div 2)

Portal

A.BowWow and the Timetable

•Title

Give you a binary Number, let you find the number of powers of all 4 less than this number

•Thinking

The first reaction is binary and Quaternary conversion

(In fact, there is no need to actually convert QwQ)

Because the two bits of the binary system correspond to the one bit of the quaternary system

, the quartet can be obtained The number of digits in the system

The number of digits in the quaternary system is the number less than or equal to the power of 4 of this number. It is analogous to the power of 10 in the decimal system.

Equal, so judge whether this number is a power of 4 according to the binary system

Because 1₂, 100₂, 10000₂ , the power of 4 in binary except the first 1, followed by an even number of 0s

So it is judged whether it is 1 with an even number of 0s, and if so, the number is reduced by one

•Code

 1 #include

 2 using  namespace std;

 3 const int maxn=1e6+5;

 4 char s[maxn];

 5 int main()

 6 {

 7 scanf("%s",s+1);

 8 int len=strlen(s+1),flag=0;

 9 int cnt=(len+1)/2;

10 for(int i=2;i<=len;i++)

11 if(s[i]==< span style="color: #800000;">'0' ) flag++;

12 if(flag==len-1 && len&1)

13 cnt--;

14 printf("%d
",cnt);

15 }

View Code

B.Mislove Has Lost an Array

•Title

In the array Only $1$ or $x$ exists

$x$ is an even number and $x/2$ ​​must exist in the array

Given $l, there is at least $ in the r$ array l$ different numbers, up to $r$ different numbers

Find the minimum and maximum values ​​of the sum of the numbers in the array

•Thinking

The minimum is the number of $1, $1,2,4…$ etc. If there are less than n, use $1$ to fill in

The maximum is There are $1,2,4…$ and other $r$, if not enough, use the largest of these $r$ to make up

•Code

 1  #include

 2 using  namespace std;

 3 #define ll long long

 4 int main()

 5 {

 6 int n,l,r;

 7 cin>>n>>l>>r;

 8 ll Min=0;

 9 int cnt,i;

10 for(i=1,cnt=1;i<=l;cnt*=2,i++)

11 Min+=cnt;

12 Min+=(n-l);

13

14 ll Max=0;

15 for(cnt=1,i=1;i<=min(n,r);cnt*=2,i++)

16 Max+=cnt;

17 cnt/=2;

18 if(r<=n)

19 Max+=1ll*(n-r)*cnt;

20 cout<' '<endl;

21 }

View Code

D.Kirk and a Binary String

•Title

Give you a $01$ string s, let you find a t string, so that

• t string and s All monotonic non-decreasing lengths of the interval of the string are the same.
• The number of 0 in the string is the most.

•Thinking

h3>

For a string, the current position has two cases: $0,1$

• The current position is 0

　　 The current position is 0, It will definitely contribute to the monotonic non-decreasing subsequence starting from him.

If 　　 becomes 1, the length will decrease in most cases (except for the case where all 1s are followed by 0, the length of 011111 remains unchanged)

　　 If it becomes 1, the number of 0s will decrease compared to the constant. It violates the second task

• The current position is 1

　　 If Becomes 0. For the monotonic non-decreasing subsequence starting from him (that is, 1), the length has no effect

　　 For the monotonic non-decreasing subsequence starting from 0, the length will be Affected

Since you want more 0s, you need to change 1 to 0 as much as possible. How can it be unaffected?

Then you need to use him (also That is, the length of the monotonic non-decreasing subsequence starting from 1) is greater than the length of the monotonic non-decreasing subsequence starting from 0

Because of the longest impact on the overall situation, even small changes , It will not have an impact on the overall situation!

In other words, if you want to change $1$ to $0$, you must ensure that the length of the monotonic non-decreasing subsequences of all subsequent intervals must be equal to the number of 1

That is to look from the back to the front. When the number of $1$ is greater than the number of $0$, $1$ can become $0$

•Code

 1 #include 

 2 using  namespace std;

 3 #define ll long long

 4 const  int maxn=1e6+4;

 5 char s[maxn];

 6 int a[maxn];

 7 int main()

 8 {

 9 scanf("%s",s+1);

10 int len=strlen(s+1);

11 int cnt=0;

12 for(int i=len;i>=1;i-- )

13  {

14 if(s[i]==< span style="color: #800000;">'0' )

15 cnt++;

16 else

17  {

18 if(cnt) --cnt;

19 else s[i]='0';

20 }

21 }

22

23 printf("%s",s+1);

24 }

View Code

 1 #include

 2 using  namespace std;

 3 const int maxn=1e6+5;

 4 char s[maxn];

 5 int main()

 6 {

 7 scanf("%s",s+1);

 8 int len=strlen(s+1),flag=0;

 9 int cnt=(len+1)/2;

10 for(int i=2;i<=len;i++)

11 if(s[i]==< span style="color: #800000;">'0' ) flag++;

12 if(flag==len-1 && len&1)

13 cnt--;

14 printf("%d
",cnt);

15 }

View Code

 1 #include

 2 using  namespace std;

 3 const int maxn=1e6+5;

 4 char s[maxn];

 5 int main()

 6 {

 7 scanf("%s",s+1);

 8 int len=strlen(s+1),flag=0;

 9 int cnt=(len+1)/2;

10 for(int i=2;i<=len;i++)

11 if(s[i]==< span style="color: #800000;">'0' ) flag++;

12 if(flag==len-1 && len&1)

13 cnt--;

14 printf("%d
",cnt);

15 }

 1 #include

 2 using  namespace std;

 3 #define ll long long

 4 int main()

 5 {

 6 int n,l,r;

 7 cin>>n>>l>>r;

 8 ll Min=0;

 9 int cnt,i;

10 for(i=1,cnt=1;i<=l;cnt*=2,i++)

11 Min+=cnt;

12 Min+=(n-l);

13

14 ll Max=0;

15 for(cnt=1,i=1;i<=min(n,r);cnt*=2,i++)

16 Max+=cnt;

17 cnt/=2;

18 if(r<=n)

19 Max+=1ll*(n-r)*cnt;

20 cout<' '<endl;

21 }

View Code

 1 #include

 2 using  namespace std;

 3 #define ll long long

 4 int main()

 5 {

 6 int n,l,r;

 7 cin>>n>>l>>r;

 8 ll Min=0;

 9 int cnt,i;

10 for(i=1,cnt=1;i<=l;cnt*=2,i++)

11 Min+=cnt;

12 Min+=(n-l);

13

14 ll Max=0;

15 for(cnt=1,i=1;i<=min(n,r);cnt*=2,i++)

16 Max+=cnt;

17 cnt/=2;

18 if(r<=n)

19 Max+=1ll*(n-r)*cnt;

20 cout<' '<endl;

21 }

 1 #include

 2 using  namespace std;

 3 #define ll long long

 4 const  int maxn=1e6+4;

 5 char s[maxn];

 6 int a[maxn];

 7 int main()

 8 {

 9 scanf("%s",s+1);

10 int len=strlen(s+1);

11 int cnt=0;

12 for(int i=len;i>=1;i-- )

13  {

14 if(s[i]==< span style="color: #800000;">'0' )

15 cnt++;

16 else

17  {

18 if(cnt) --cnt;

19 else s[i]='0';

20 }

21 }

22

23 printf("%s",s+1);

24 }

View Code

 1 #include

 2 using  namespace std;

 3 #define ll long long

 4 const  int maxn=1e6+4;

 5 char s[maxn];

 6 int a[maxn];

 7 int main()

 8 {

 9 scanf("%s",s+1);

10     int len=strlen(s+1);

11     int cnt=0;

12     for(int i=len;i>=1;i--)

13     {

14         if(s[i]==‘0‘)

15             cnt++;

16         else

17         {

18             if(cnt) --cnt;

19             else s[i]=‘0‘;

20         }

21     }

22 

23     printf("%s",s+1);

24 }