Codeworks round 807 (Div. 2) a-c problem solution

Codeforces Round #807 (Div. 2)

1. A、B、C Problem solving

A - Mark the Photographer

The question ： Mark is going to give 2n Personal photos , In two rows , Yipai station n people , Give everyone's height , The height of the back row is required to be at least higher than that of the front row x A unit of , Ask whether this requirement can be achieved ?

analysis ： Sort by height first , The corresponding relationship is that the height of the front row in the same position is ai, The height of the back row is ai+x, By traversing the height of the first row , Get the height of the second row , Judge whether the requirements are met .

Code:

1.	#include<bits/stdc++.h>  
2.	using namespace std;  
3.	typedef long long ll;  
4.	const int N=1e5+10;  
5.	int a[N];  
6.	bool solve(int n,int x)  
7.	{  
8.	    for (int i=0;i<2*n;i++)  
9.	        cin>>a[i];  
10.	    sort(a,a+2*n);  
11.	    for (int i=0;i<n;i++)  
12.	    {  
13.	        if (a[i+n]-a[i]<x) // Once it is found that the height difference between the second row and the first row is less than x It's definitely not true   
14.	            return false;  
15.	    }  
16.	    return true;  
17.	}  
18.	int main()  
19.	{  
20.	    int t;  
21.	    cin>>t;  
22.	    while (t--)  
23.	    {  
24.	        int n,x;  
25.	        cin>>n>>x;  
26.	        if (solve(n,x))  
27.	            puts("YES");  
28.	        else  
29.	            puts("NO");  
30.	    }  
31.	    return 0;  
32.	}  

B - Mark the Dust Sweeper

The question ： Yes n A room , Give the ash deposition degree of each room ,

Mark can choose from Elements that are not zero , to   Minus one , Add one , Record it as an operation ,

Finally, make all rooms except the last room have zero ash deposition , Ask at least how many operations ？

analysis ： When the accumulated ash is removed from i Move room to j Move to the farthest room as far as possible when you have two rooms , That is to say j To be the biggest , By moving right j The pointer finds out the sequence with continuous non-zero and performs an operation , Subtract the head element by one , Add one to the next element of the tail element , Until the header element is zero , Then the head element moves to the right by one room , Repeat the appeal operation until the operation is performed except for the last room . If you look carefully, , This operation can convert the zero element in the middle into a non-zero element, thereby creating a continuous non-zero sequence , Consistent with our intuitive strategy .

Code:

1.	#include<bits/stdc++.h>  
2.	using namespace std;  
3.	typedef long long ll;  
4.	const int N=1e5+10;  
5.	int a[2*N];  
6.	int solve(int n)  
7.	{  
8.	    for (int i=0;i<n;i++)  
9.	        cin>>a[i];  
10.	    int cnt=0,j=0;  
11.	    for (int i=0;i<n-1;i++) // The last element need not be considered   
12.	    {  
13.	        while (a[i])  
14.	        {  
15.	            while (a[j]&&j<n) // Determine that a continuous period is not 0 Sequence   
16.	                j++;  
17.	            a[i]-=1; // Operate according to the meaning of the question   
18.	            a[j]+=1;  
19.	            cnt++;  
20.	        }  
21.	    }  
22.	    return cnt; // The number of times obtained according to the above method is already the optimal solution   
23.	}  

Pick up B topic ：

The above code cannot AC Of , How to simplify the problem ？ From the above analysis, it can be concluded that the optimal strategy is to change non-zero elements into non-zero , If there is a sequence with non-zero elements at the beginning but zero elements in the middle , You can move the non-zero element to the zero element by one dust to reduce the non-zero element , The original non-zero element acts as a bridge , Thus, the continuous non-zero sequence becomes longer , Repetition can change the whole sequence into a non-zero sequence , The number of operation steps required here is the number of zero elements on the right of the first non-zero element , The preceding leading zero sequence does not require operation . Now we have a bridge , The bridgehead is moving , The end is set , Constantly use this bridge to move the elements of the bridgehead to the end , When the bridgehead element is zero , Remove the bridgehead , The new bridgehead is the next element , The elements of the bridge head cross the bridge in turn , The length of the bridge is also decreasing , Until the length of the bridge is zero . This idea is also consistent with the previous idea of continuously expanding the longest non-zero sequence . Add all non-zero elements to the final answer , Take a unit of a non-zero element to the zero element “ Bridging ” There is no need to calculate the process , Because the bridge is demolished step by step , This element must eventually move to the end . The final answer is the number of zero elements after removing the leading zero plus all non-zero elements .

Improved AC Code :

1.	#include<bits/stdc++.h>  
2.	using namespace std;  
3.	typedef long long ll;  
4.	const int N=1e5+10;  
5.	int a[2*N];  
6.	ll solve(int n)  
7.	{  
8.	    int start=-1;  
9.	    ll sum=0;  
10.	    for (int i=0;i<n;i++)  
11.	    {  
12.	        cin>>a[i];  
13.	        if (i<n-1) // The last element is not considered   
14.	        sum+=a[i];  
15.	        if (a[i]&&start==-1) // Record the position of the first non-zero element   
16.	            start=i;  
17.	    }  
18.	    if (sum==0)  
19.	        return 0;  
20.	    for (int i=start;i<n-1;i++) // Add the number of zeros that appear after non-zero elements   
21.	    {  
22.	        if (!a[i])  
23.	            sum++;  
24.	    }  
25.	    return sum;  
26.	}  
27.	int main()  
28.	{  
29.	    ios::sync_with_stdio(false);  
30.	    cin.tie(0);  
31.	    int t;  
32.	    cin>>t;  
33.	    while (t--)  
34.	    {  
35.	        int n;  
36.	        cin>>n;  
37.	        cout<<solve(n)<<'\n';  
38.	    }  
39.	    return 0;  
40.	}  

C - Mark and His Unfinished Essay

The question ： For a given string c operations , Each operation selects one of the segments and copies it to the end of the string , give q Queries , Answer string No k Characters in positions .

Got MLE:

1.	#include<bits/stdc++.h>  
2.	using namespace std;  
3.	typedef long long ll;  
4.	const int N=1e5+10;  
5.	int main()  
6.	{  
7.	    int t;  
8.	    cin>>t;  
9.	    while (t--)  
10.	    {  
11.	        int n,c,q;  
12.	        cin>>n>>c>>q;  
13.	        string s;  
14.	        cin>>s;  
15.	        while (c--)  
16.	        {  
17.	            ll l,r;  
18.	            cin>>l>>r;  
19.	            s+=s.substr(l-1,r-l+1); // Pay attention to the subscript   
20.	        }  
21.	        while (q--)  
22.	        {  
23.	            ll k;  
24.	            cin>>k;  
25.	            cout<<s[k-1]<<endl;  
26.	        }  
27.	    }  
28.	    return 0;  
29.	}  

All characters obtained by operation can be found in the original string , Every time a copy and paste operation is performed, the elements of the new string can be traced , Record this relationship , Until it is found in the original string .

AC:

1.	#include<bits/stdc++.h>  
2.	using namespace std;  
3.	typedef long long ll;  
4.	const int N=1e5+10;  
5.	ll slen[N],lb[N],diff[N];  
6.	int main()  
7.	{  
8.	    int t;  
9.	    cin>>t;  
10.	    while (t--)  
11.	    {  
12.	        int n,c,q;  
13.	        cin>>n>>c>>q;  
14.	        string s;  
15.	        cin>>s;  
16.	        slen[0]=n,lb[0]=0;  
17.	        for (int i=1;i<=c;i++)  
18.	        {  
19.	            ll l,r;  
20.	            cin>>l>>r;  
21.	            l--; // Transform subscript   
22.	            r--;  
23.	            lb[i]=slen[i-1]; // Record the starting position of the newly added replication string   
24.	            slen[i]=slen[i-1]+r-l+1; // Record the new string length   
25.	            diff[i]=lb[i]-l;  
26.	        }  
27.	        while (q--)  
28.	        {  
29.	            ll k;  
30.	            cin>>k;  
31.	            k--;  
32.	            for (int i=c;i>0;i--)  
33.	            {  
34.	                if (k<lb[i])  
35.	                    continue;  
36.	                k-=diff[i];  
37.	            }  
38.	            cout<<s[k]<<endl;  
39.	        }  
40.	    }  
41.	    return 0;  
42.	}  

For the remaining questions, please refer to the official solutions ：Codeforces Round #807 (Div 2.) Editorial - Codeforces