第四次训练：Codeforces Round #598 (Div. 3)

1.Codeforces Round #598 (Div. 3) F

题意：给定两个字符串，每次选择一定长度片段反转（字符顺序倒过来），两个字符串要选同样长度但可以是不同位置，问是否可以使两个字符串相等。
　　读完题我觉得它最多是C题的难度，没想到又是F。当然，在实际思考一下后发现没那么简单，就先跳过了，不过幸好放弃了，不然又会浪费很长时间。之后琢磨了半天官方题解，发现这个题解的关键就是可以反转的长度是不限的，而我们做的却是选择反转两个（通过两个间的反转间接可以实现任意数目的反转），所以确实，这又像个冒泡。仿照题解和别人的思路写了一下，感觉上知道方法后比E题易实现。

#include<iostream>
#include<iomanip>
#include<fstream>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<cstdio>
#include<map>
#include<vector>
#include<ostream>
#include<istream>
typedef long long ll;
using namespace std;
#define mod 1e9+7
#define PI acos(-1.0)
const ll maxn=1e6+10;
const int mx=(1<<20)+99;
char s1[maxn],s2[maxn];
ll cnt1[26],cnt2[26];
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    int t;
    cin>>t;
    for(int o=1;o<=t;o++)
    {
        for(int i=0;i<26;i++)
        cnt1[i]=cnt2[i]=0;
        ll n,k=1;
        cin>>n;
        cin>>s1>>s2;
        for(int i=0;i<n;i++){
            cnt1[s1[i]-'a']++;
            cnt2[s2[i]-'a']++;
        }
        for(int i=0;i<26;i++)
        {
            if (cnt1[i]>1||cnt2[i]>1)
            k=2;
            if (cnt1[i] != cnt2[i])
            {
                k=0;
                break;
            }
        }
        if (k==0) cout<<"NO"<<endl;
        else if (k==2) cout<<"YES"<<endl;
        else
        {
            ll aans1=0,aans2=0;
            for(int i=0; i<n; i++)
            {
                for(int j=n-1; j>=i+1; j--)
                {
                    if (s1[j] < s1[j-1])
                    {
                        swap(s1[j],s1[j-1]);
                        aans1++;
                    }
                    if (s2[j]<s2[j-1])
                    {
                        swap(s2[j],s2[j-1]);
                        aans2++;
                    }
                }
            }
            //cout<<res1<<" "<<res2<<endl;
            if ((aans1-aans2)%2) cout<<"NO"<<endl;
            else cout<<"YES"<<endl;
        }
    }
    return 0;
}

2.Codeforces Round #598 (Div. 3) D

题意：给定一个长n的二进制串，最多可以进行k此1和0间的位置调换，求能够得到的最小串。
　　开始觉得这是一个二进制数，所以左端应该以1打头，并且程序存在小bug，导致有些测例没有任何输出，所以就放弃了这个题。参考了一下官方题解，并看了一下别人的题解，发现其他人都把它看作一个特殊冒泡做的。即优先把0换到前面去，每一个0换到的位置计数一下，如果 k 不足够把当前的 0 换到对应的位置，那么就往前换 k 个位置。

#include<iostream>
#include<iomanip>
#include<fstream>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<cstdio>
#include<map>
#include<vector>
#include<ostream>
#include<istream>
typedef long long ll;
using namespace std;
#define mod 1e9+7
#define PI acos(-1.0)
const ll maxn=1e6 + 10;
const int mx=(1<<20)+99;
char s[maxn];
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    int t;
    cin>>t;
    for(int o=1;o<=t;o++)
    {
         ll n,k;
        cin>>n>>k;
        cin>>s;
        int len=strlen(s),cnt=0,pos=0;
        for(int i=0;i<len;i++)
        {
            if(s[i]=='0')
            {
               // cout<<cnt<<" "<<k<<endl;
                if(cnt<=k)
                {
                    k-=cnt;
                    swap(s[pos++],s[i]);
                }
                else
                {
                    swap(s[i-k],s[i]);
                    break;
                }
            }
            else
            {
                cnt++;
            }
        }
        cout<<s<<endl;
    }
    return 0;
}

3.Codeforces Round #598 (Div. 3) A

题意：a个n和b个1，问能不能恰好组成s。
　　水题一个。

#include<iostream>
#include<iomanip>
#include<fstream>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<cstdio>
#include<map>
#include<vector>
#include<ostream>
#include<istream>
typedef long long ll;
using namespace std;
#define mod 1e9+7
#define PI acos(-1.0)
const ll maxn=1000000;
const int mx=(1<<20)+99;
ll n,a,b,s;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    int t;
    cin>>t;
    for(int o=1;o<=t;o++)
    {
        cin>>a>>b>>n>>s;
        if(a*n+b>=s&&b>=s%n) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }

}

4.Codeforces Round #598 (Div. 3) E

题意：给出一个包含n个数的数组，数组元素有一定值。将其分成k组，使所有组最大值减最小值总和最小，每组人数最少3人。输出最少总和和分的组数k，并表示出分组情况。
　　看了官方题解，看了官方代码，看了别的人写的代码，知道用dp甚至知道状态转移方程我也还是没能写出个ac的代码，所以，亮官方代码吧。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pt;
#define x first
#define y second
#define mp make_pair
const int N = 200043;
const int INF = int(1e9) + 43;
int n;
int dp[N];
int p[N];
pt a[N];
int t[N];
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
    	a[i].y = i;
    	scanf("%d", &a[i].x);
    }
    sort(a, a + n);
    for(int i = 1; i <= n; i++)
    {
    	dp[i] = INF;
    	p[i] = -1;
    }
    for(int i = 0; i < n; i++)
    	for(int j = 3; j <= 5 && i + j <= n; j++)
    	{
    		int diff = a[i + j - 1].x - a[i].x;
    		if(dp[i + j] > dp[i] + diff)
    		{
    			p[i + j] = i;
    			dp[i + j] = dp[i] + diff;
    		}
    	}
    int cur = n;
    int cnt = 0;
    while(cur != 0)
    {
    	for(int i = cur - 1; i >= p[cur]; i--)
    		t[a[i].y] = cnt;
    	cnt++;
    	cur = p[cur]; 
    }
    printf("%d %d\n", dp[n], cnt);
    for(int i = 0; i < n; i++)
    {
    	if(i) printf(" ");
    	printf("%d", t[i] + 1); 
    }
    puts("");
    return 0;
}

5.Codeforces Round #598 (Div. 3) C

题意：从河的一岸0走到另一岸n+1，每次可以走不多于d格，问有一定的木板和每个木板的长度，木板可以任意摆放，问能不能不掉到河里而过河。
　　看到这个题目能够马上意识到，在木板上怎么走都没问题，而关键由木板跳到另一块木板上是关键。也就是说，木板长度不重要，而木板与木板的距离才是关键。既然怎么跳（跳多少步和跳多少次）无所谓，而且木板长度和河宽度一定，也就是说会存在的没有木板的长度一定，那么就优先让木板间距离为最大距离，最后只要处理好最后不一定需要保持最大距离的那一步就好。按照木板和河分开输出，所以奇数次输出的是河，而偶数次输出的是木板。具体小细节就不多说了。

#include<iostream>
#include<iomanip>
#include<fstream>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<cstdio>
#include<map>
#include<vector>
#include<ostream>
#include<istream>
typedef long long ll;
using namespace std;
#define mod 1e9+7
#define PI acos(-1.0)
const ll maxn=1000;
const int mx=(1<<20)+99;
int n,m,d,a[maxn+10],aans,aans2;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    /*int t;
    cin>>t;
    for(int o=1;o<=t;o++)
    {

    }*/
        cin>>n>>m>>d;
        aans=0;
        for(int i=1;i<=m;i++)
        {
            cin>>a[i];
            aans+=a[i];
        }
        if((n-aans)>(d-1)*(m+1)) { cout<<"NO"<<endl; return 0; }
        else cout<<"YES"<<endl;
        int s=aans;
        //cout<<s<<endl;
        aans=0; aans2=0;
        for(int i=1,j=1;i<=n;j++)
        {
            if((n-s)==aans)
            {
                //cout<<n-s<<endl;
                for(int k=j/2;k<=m;k++)
                {
                    for(int x=1;x<=a[k];x++)
                    cout<<k<<" ";
                }
                break;
            }
            if(j%2)
            {
                int r=d-1;
                r=min(n-s-aans,r);
                if(s-aans+r>=n) r=n-(s-aans2);
                for(int k=1;k<=r;k++)
                cout<<"0 ";
                i+=r;
                aans+=r;
                //cout<<endl<<n-s<<" "<<aans<<" "<<i<<endl;
            }
            else
            {
                for(int k=1;k<=a[j/2];k++)
                cout<<j/2<<" ";
                i+=a[j/2]; aans2+=a[j/2];
            }
        }
    cout<<endl;
    return 0;
}

6.Codeforces Round #598 (Div. 3) B

题意：可以进行n-1次交换，第1到n-1位的数字可以跟下一位交换且只能交换一次，求如何交换得到最小的字典序（将其看作一个n位数就是求最小的值）。
　　当时没做，一个原因是它放到最后了而且题目很长，另一个原因是我觉得另一个题目能够做出来。搜了一些题解，都说做个标记然后交换后更改标记。而在我看来，可以分段处理，因为每次都是选取未移动区间的最小值包括其以前的所有位置移动，以把当前最小的数尽可能往前放，而同时，这样做以后，下一个未移动区间正好是包含上一个最小数位置的最右端的数字串，因此，可以一段一段打印出来。不过，我磨蹭了两个多小时没磨出来，所以，看看人家的思路吧。

#include<iostream>
#include<iomanip>
#include<fstream>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<cstdio>
#include<map>
#include<vector>
#include<ostream>
#include<istream>
typedef long long ll;
using namespace std;
#define mod 1e9+7
#define PI acos(-1.0)
const ll maxn=1e4 + 10;
const int mx=(1<<20)+99;
int a[maxn];
int vis[maxn];
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    int t;
    cin>>t;
    for(int o=1;o<=t;o++)
    {
        memset(vis,0,sizeof(vis));
        int n;
        cin>>n;
        for(int i=1; i<=n; i++)
        cin>>a[i];
        for(int i=1; i<=n; i++)
        {
            for(int i=n-1; i>=1; i--)
            {
                if (!vis[i] && a[i] > a[i+1])
                {
                    swap(a[i], a[i+1]);
                    vis[i] = 1;
                }
            }
        }
        for(int i=1; i<=n; i++)
        cout<<a[i]<<" ";
        cout<<endl;;
    }
    return 0;
}

－
　　总结：看到题目有思路，心里得出一个算法是一回事，能不能写出来又是另一回事，无论这个算法可行不可行。其实很多时候题目没那么难，但碰巧了写代码的时候就是磕在某个坎了，真正比赛时不要钻牛角尖，而补题纠错时可以死磕。而且，题目原本难度的顺序只是人家以为的难度顺序，不见的对于自己也一样，有些时候，有些题目难度虽高但恰巧学过相关知识或者碰巧能够想到一个可行的思路也说不准，所以所有题目都要看一边，再决定要做哪一个。