Codeforces Round #590 (Div. 3)

------------恢复内容开始------------

从今天开始我要每天都要做一波div3来提高自己的思维，，，，

传送门

A题

题意：给你a个n元的，b个1元的硬币，问你可不可以组成S元

思路：就是看看s最大可以用几个n元的，剩下的都要用一元的来补

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>

using namespace std;
int main()
{
    int q;
   scanf("%d",&q);
    while(q--)
    {
        int a,b,n,s;
        scanf("%d%d%d%d",&a,&b,&n,&s);
        int d = s/n;
        int p = s - min(d,a)*n;
        if(b>=p){
            printf("YES
");
        }
        else{
            printf("NO
");
        }
    }
}

B题

题意：给你n个数，你可以进行n-1次（前提每个i位置的操作，只有一次，也就是可以从1——n-1每个点只能操作一次）操作（就是交换第i和第i+1 两个数的位置），问经过这么多次的操作，输出可能的最小字典序

思路：倒着从后往前，将最小的数尽可能的往前交换，而且每个位置交换一次，循环交换，之到不可以交换位置为止

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>

using namespace std;
typedef long long ll;
int main()
{
    int q;
    cin >> q;
    while(q--)
    {
        int n;
        int a[110],b[110];
        cin >> n;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            b[i]=0;
        }
        int d =n-1;
        while(d)
        {
            int flag =0;
            for(int i=n;i>1;i--)
            {
                if(a[i]<a[i-1]&&b[i-1]==0)
                {
                    int t=a[i-1];
                    a[i-1]=a[i];
                    a[i]=t;
                    d--;
                    b[i-1]=1;
                    flag=1;
                    if(d==0)break;
                }
            }
            if(!flag||!d)break;
        }
        for(int i=1;i<n;i++)
        {
            printf("%d ",a[i]);
        }
        printf("%d
",a[n]);
    }
    return 0;
}

C题（第一波没有写出）

题意：有m个木板，有一个n个宽度的河，每次可以跳d距离，问可不可以跳过去，跳的过去的话，就把每个木板的位置表现出来

思路：贪心处理每个空隙（每次都是（跳的最大距离和剩余水宽）的最小值），跳一次紧跟木板，最后如果水还有，就把所有水都输出

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <string>
#include <algorithm>
#include <map>
#include <vector>
#include <queue>

using namespace std;
typedef long long ll;
int a[1010];
int main()
{
    int n,m,d;
    cin >> n >> m >> d;
    int sum=0;
    for(int i=1;i<=m;i++)
    {
        cin >> a[i];
        sum+=a[i];
    }
    int q = ceil((n-sum)*1.0/(m+1));
    if((d<=q))
    {
        cout<<"NO"<<endl;
        return 0;
    }
    else{
        cout << "YES"<<endl;
        int num =1;
        for(int i= 1;i<=m;i++)
        {
            int j = min(d-1,n-sum);
            for(int k=0;k<j;k++)
                cout<<0<<' ';
            for(int k=0;k<a[i];k++)
            {
                cout<<num<<' ';
            }
            num++;
            sum+=j;
        }
    }
    for(int i=0;i<n-sum;i++)cout<<0<<' ';
    return 0;
}

D题

题意：给你一个字符串（只含有1,0），长度为N,一个操作数d,输出经过操作后的最小字典序

思路：判断每个零的位置，将他尽可能往前移动

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>

using namespace std;
typedef long long ll;
int main()
{
    int q;
    cin >> q;
    while(q--)
    {
        ll n,d;
        cin >> n >> d;
        string s;
        cin >> s;
        ll num=0,cun=0;
        int end_i=0,end_j=0;
        for(int i = 0 ;i<n;i++)
        {
            if(s[i]=='0')
            {
                num +=(i-cun);
                s[i]='1';
                cun++;
                //cout << num<<endl;
                if(num>d)
                {
                    //cout<<"sfew"<<endl;
                    cun--;
                    num-=i-cun;
                    d=d-num;
                    s[i]='1';
                    end_i=i-d;
                    s[i-d]='0';
                    break;
                }
            }
        }
       // cout <<cun<<"wfw"<<endl;
        //if(cun)
        //cout << cun<<endl;
        for(int i=0;i<cun;i++)cout<<0;
        for(int i=cun;i<n;i++)
        {
          cout<<s[i];
        }
        cout<<endl;
    }
    return 0;
}

------------恢复内容结束------------