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

日常训练。
比赛链接
不过今天这个div3是异常的艰难啊，感受一下。

A - Payment Without Change

题意：有a个n元硬币，b个1元硬币，问有没有可能从中凑出s元。
思路：显然要凑就肯定是尽量多堆n元硬币，然后不够的1元补。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdlib>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int MAX_N=1000000+5;
const int MAX_M=100000+5;
const int INF=0x7fffffff;
const int inf=1000000000;
const double EPS=1e-6;
const ull base=123;
const ll mod=998244353;
const double pi=4*atan(1.0);
int main()
{
   
    int t;
    cin>>t;
    while(t--)
    {
   
        int a,b,n,s;
        cin>>a>>b>>n>>s;
        int q=s/n;
        int p=n*min(a,q);
        if(s-p<=b)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
}

B - Minimize the Permutation

题意：给定由1~n组成的不重复序列，可以操作最多n-1次，每次操作交换a[i]和a[i-1]，其中i所对应的操作只能操作一次，也就是同样的位置不能交换两次。最后使其字典序最小。
思路：一开始没读明白题意，以为就是最多进行n-1次操作，但不限位置，那样的话就很简单了，尽量把小的数字往前移就行了。然后就wa了两发，看清楚题目后，就觉得也没啥区别，还是把尽量小的数字往左移，直到那个位置不能移了为止，然后又wa了两发，其实这个的反例4 2 1 3那么在把1移动到最左边以后，2是不能动了，那处理3的时候就把2给换到后面去了，所以在换的时候要额外考虑是否小于自己。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdlib>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int MAX_N=100+5;
const int MAX_M=100000+5;
const int INF=0x7fffffff;
const int inf=1000000000;
const double EPS=1e-6;
const ull base=123;
const ll mod=998244353;
const double pi=4*atan(1.0);
int a[MAX_M];
int vis[MAX_M];
int used[MAX_M];
int main()
{
   
    int t;
    cin>>t;
    while(t--)
    {
   
        me(used,0);
        me(a,0);
        me(vis,0);
        int n;
        scanf("%d",&n);
        int i;
        for(i=1; i<=n; i++)
        {
   
            scanf("%d",&a[i]);
            vis[a[i]]=i;
        }
        int sum=0;
        for(i=1; i<=n; i++)
        {
   
            if(sum==n-1)
                break;
            while(a[i]!=i)
            {
   
                if(used[vis[i]])
                {
   
                    break;
                }
                if(sum==n-1)
                    break;
                int pre=a[vis[i]-1];
                if(i>pre)
                    break;
                used[vis[i]]=1;
 
                a[vis[pre]]=i;
                a[vis[i]]=pre;
                vis[pre]++;
                vis[i]--;
                sum++;
            }
            //used[i]=1;
        }
        for(i=1; i<=n; i++)
        {
   
            printf("%d%c",a[i],i==n?'\n':' ');
        }
    }
}

C - Platforms Jumping

题意：在一个长n的水池，水池两岸做0和n+1，现在给几个给定长度的木板，按顺序铺在水池上，要求你移动这些木板，使你从0出发，每次最多移动d格，每次移动必须在木板上，是否可以顺利到达n+1.
思路：贪心。每次放置木板尽量放在当前位置+d的位置上，直到剩余空间放不下剩余木板时，因为题目要求木板不能重叠，所以每次在放置的时候都要考虑剩余空间是否最够放置剩余的所有木板。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdlib>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int MAX_N=100+5;
const int MAX_M=100000+5;
const int INF=0x7fffffff;
const int inf=1000000000;
const double EPS=1e-6;
const ull base=123;
const ll mod=998244353;
const double pi=4*atan(1.0);
int a[MAX_M];
int c[MAX_M];
int main()
{
   
    int n,m,d;
    cin>>n>>m>>d;
    int i;
    int sum=0;
    for(i=1; i<=m; i++)
    {
   
        scanf("%d",&c[i]);
        sum+=c[i];
    }
    int pos=0;
    for(i=1; i<=m; i++)
    {
   
        int p=max(sum,n-pos-d+1);
        int q=n+1-p;
        //if(n-pos-d<0)
        //q=pos+1;
        int j;
        for(j=0; j<c[i]; j++)
        {
   
            a[q+j]=i;
        }
        pos=q+j-1;
        sum-=c[i];
        //cout<<pos<<' '<<3424<<endl;
    }
    if(pos+d>=n+1)
    {
   
        cout<<"YES"<<endl;
        for(i=1; i<=n; i++)
            printf("%d%c",a[i],i==n?'\n':' ');
    }
    else
        cout<<"NO"<<endl;
 
 
}

D - Binary String Minimizing

题意：这题就和B差不多了。给定一个01序列，给k次操作，要求每次操作任选i，交换a[i]和a[i-1]，使序列字典序最小。但这题没有一个位置只能交换一次的限制。
思路：所以显然一个序列左边对字典序的影响要大于右边，所以就是尽量把左边的1统统往后移，1和1交换等于没交换，所以必然是往0移，也就是从左到右找0，然后这个0之前的1统一往后移一位，让再继续找0，当找到一个0，发现前面的1数量大于剩余的操作数的时候，那么就只移动操作数个1.

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdlib>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int MAX_N=1000000+5;
const int MAX_M=100000+5;
const int INF=0x7fffffff;
const int inf=1000000000;
const double EPS=1e-6;
const ull base=123;
const ll mod=998244353;
const double pi=4*atan(1.0);
char a[MAX_N];
int main()
{
   
    int t;
    cin>>t;
    while(t--)
    {
   
        ll n,m;
        scanf("%lld%lld",&n,&m);
        scanf("%s",a+1);
        ll i;
        ll sum=0;
        ll sum1=0;
        ll sum2=0;
        for(i=1;i<=n;i++)
        {
   
            if(a[i]=='1')
                sum1++;
            else
                sum2++;
        }
        for(i=1;i<=n;i++)
        {
   
            if(a[i]=='1')
                break;
        }
        int pos;
        int flag=1;
        for(i;i<=n;i++)
        {
   
            if(a[i]=='1')
                sum++;
            else
            {
   
                if(m>=sum)
                {
   
                    m-=sum;
                }
                else
                {
   
                    pos=i;
                    flag=0;
                    break;
                }
            }
        }
        if(flag)
        {
   
            for(i=1;i<=sum2;i++)
                cout<<0;
            for(i=1;i<=sum1;i++)
                cout<<1;
        }
        else
        {
   
            for(i=1;i<=pos-sum-1;i++)
                cout<<0;
            for(i;i<=pos-m-1;i++)
                cout<<1;
            cout<<0;
            for(i=pos-m+1;i<=pos;i++)
                cout<<1;
            for(i=pos+1;i<=n;i++)
                cout<<a[i];
        }
        cout<<endl;
    }
}

E - Yet Another Division Into Teams

题意：给定n个人，每个人的分数是a[i]，现在要求将他们分组，每组至少三人，每组的总分是该组分数最高的减分数最低的值，求如何分组，可以使所有队总分之和最低。
思路：显然一个队是由排序后连续的人组在一起的，所以先排序。由于一个队至少3人，所以显然n在小于等5个人的时候，必然只有一个队。从第6个人以后开始，就有两种选择：1.进入前一个人的队。2.和前两个人再新组一个队。所以设dp[i]，代表以i为结尾的所有队分数总和的最小值，所以dp[i]=min(dp[i-1]+a[i]-a[i-1],dp[i-3]+a[i]-a[i-2])。注意分组的时候只需从后往前找每个人找当初跟他承诺组队的人即可，不需要管那些人原来是哪个队的，因为我们的和是根据之后的人更新的。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdlib>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int MAX_N=200000+5;
const int MAX_M=100000+5;
const int INF=0x7fffffff;
const int inf=1000000000;
const double EPS=1e-6;
const ull base=123;
const ll mod=998244353;
const double pi=4*atan(1.0);
ll dp[MAX_N];
struct node
{
   
    int id;
    ll x;
    int vis;
    int ans;
} a[MAX_N];
bool cmp(node a,node b)
{
   
    return a.x<b.x;
}
bool cmp2(node a,node b)
{
   
    return a.id<b.id;
}
int main()
{
   
    int n;
    cin>>n;
    int i;
    for(i=1; i<=n; i++)
    {
   
        a[i].id=i;
        scanf("%lld",&a[i].x);
    }
    sort(a+1,a+1+n,cmp);
    if(n<=5)
    {
   
        ll sum=0;
        sum=a[n].x-a[1].x;
        cout<<sum<<' '<<1<<endl;
        for(i=1; i<=n; i++)
        {
   
            printf("%d%c",1,i==n?'\n':' ');
        }
    }
    else
    {
   
        for(i=1; i<=5; i++)
        {
   
            dp[i]=a[i].x-a[1].x;
            a[i].vis=1;
        }
        for(i=6; i<=n; i++)
        {
   
            ll p=a[i].x-a[i-2].x+dp[i-3];
            ll q=dp[i-1]+a[i].x-a[i-1].x;
            if(p<q)
            {
   
                a[i].vis=i-2;;
            }
            else
            {
   
                a[i].vis=a[i-1].vis;
            }
            dp[i]=min(p,q);
        }
 
 
        int cnt=1;
        int root=n;
        while(root>0)
        {
   
            for(i=root; i>=a[root].vis; i--)
            {
   
                a[i].ans=cnt;
            }
            cnt++;
            root=a[root].vis-1;
        }
        cout<<dp[n]<<' '<<cnt-1<<endl;
        sort(a+1,a+1+n,cmp2);
        for(i=1; i<=n; i++)
        {
   
            printf("%d%c",a[i].ans,i==n?'\n':' ');
        }
    }
 
}

F - Equalizing Two Strings

题意：给定两个字符串，每次操作可以选择len长度，分别将两个字符串的任意一个len长度的子串倒置，问有没有可能经过若干次操作后两个字符串相等。
思路：这题是看了题解了，首先两个字符串所含字母不同肯定是不行的，然后如果一个字符串有相同字符那肯定是可以的，因为我可以通过反复操作两个相同的字符，来把另一个字符串变成这个字符串。然后我们考虑在选择len长度操作的时候实际上是若干个2长度的操作组成，所以我们可以全部看成2个字符互换，这里用到一个求逆序数的方法，实际是冒泡排序的思想，就是我们将两个字符串都变成顺序的，那么变换的次数就是逆序数，如果两字符串的逆序数之差为偶数，就可以，奇数就不行。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdlib>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int MAX_N=200000+5;
const int MAX_M=100000+5;
const int INF=0x7fffffff;
const int inf=1000000000;
const double EPS=1e-6;
const ull base=123;
const ll mod=998244353;
const double pi=4*atan(1.0);
char s1[MAX_N];
char s2[MAX_N];
int vis1[30];
int vis2[30];
int main()
{
   
    int t;
    cin>>t;
    while(t--)
    {
   
        me(vis1,0);
        me(vis2,0);
        int n;
        scanf("%d",&n);
        scanf("%s",s1+1);
        scanf("%s",s2+1);
        int a,b;
        a=b=0;
        int i;
        for(i=1; i<=n; i++)
        {
   
            vis1[s1[i]-'a']++;
            vis2[s2[i]-'a']++;
            for(int j=0;j<26;j++)
            {
   
                if(j>s1[i]-'a')a+=vis1[j];
                if(j>s2[i]-'a')b+=vis2[j];
            }
        }
        int flag=1;
        for(i=0; i<26; i++)
        {
   
            if(vis1[i]!=vis2[i])
            {
   
                flag=0;
                break;
            }
        }
        if(!flag)
        {
   
            cout<<"NO"<<endl;
            continue;
        }
        flag=0;
        for(i=0; i<26; i++)
        {
   
            if(vis1[i]>1)
            {
   
                flag=1;
                break;
            }
        }
        if(flag)
        {
   
            cout<<"YES"<<endl;
            continue;
        }
        if(abs(a-b)%2==0)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;

    }
}