比赛网址：https://codeforces.com/contest/1311

A

题面：

给出a和b，一共可以执行两种操作，问你最少需要的操作次数，将a变成b
操作1，可以加上任意x（x为奇数）。操作2，可以减去任意x（x为偶数）

solution：

判断a和b的大小以及相差的大小，最大次数为2

std：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int a,b;
        cin>>a>>b;
        int cnt = abs(a - b);
        if(a == b){
            cout<<"0"<<endl;
            continue ;
        }
        else if(a > b){
            if(cnt%2 == 1){
                cout<<"2"<<endl;
            }else{
                cout<<"1"<<endl;
            }

        }else{
            if(cnt%2 == 1){
                cout<<"1"<<endl;
            }else{
                cout<<"2"<<endl;
            }
        }
    }
    return 0;
}

B

题面：

先给出数组a，然后给出m个数字，每个数字x代表a[x]可以和a[x+1]互换位置，问你是否能将a数组sort为一个递增的数组

solution：

先将m个数组合并，比如1，2，4，5，那么可以调换位置的区间为[1,3],[4.6]，我们sort这些子区间，判断和sort(a+1,a+1+n)的数组是否相同即可

std：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int a[105],b[105],c[105];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        map<int ,int > mp;
        mp.clear();
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(c,0,sizeof(c));
        int n,m;
        scanf("%d %d",&n,&m);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            c[i] = a[i];
        }
        sort(c+1,c+1+n);
        for(int i=1;i<=m;i++){
            scanf("%d",&b[i]);
            mp[b[i]] = 1;
        }
        int l ,r ;
        for(int i=1;i<=n;i++){
            if(mp[i] == 1){
                l = i,r = i+1;
                int j;
                for(j=i+1;j<=n;j++){
                    if(mp[j] == 1){
                        r = j+1;
                    }else{
                        break ;
                    }
                }
                sort(a+l,a+1+r);
                i = j-1;
            }
        }
        int flag = 0;
        for(int i=1;i<=n;i++){
            if(a[i] != c[i]){
                flag =1 ;
            }
        }
        if(flag){
            printf("NO\n");
            continue ;
        }
        printf("YES\n");
    }
    return 0;
}

C

题面：

题意就是个前缀和

solution：

我发毒誓，以后再也不乱用memset了，生气
这一题最快的解法是后缀和，从后往前遍历每个点会走的次数，然后再从前往后遍历一遍即可，注意爆int

std：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
char s[200005];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {

        int n,m,x;
        scanf("%d %d",&n,&m);
        scanf("%s",s+1);
        vector<int> fpre(n+2 , 0);
        for(int i=1;i<=m;i++){
            scanf("%d",&x);
            fpre[x]++;
        }

        for(int i=n;i>=1;i--){
            fpre[i] += fpre[i+1];
        }

        vector<ll> ans(26 , 0);
        for(int i=1;i<=n;i++){
            ans[s[i]-'a'] += 1ll*(fpre[i] + 1);
        }
        for(int i=0;i<26;i++){
            if(i != 0)
                printf(" ");
            printf("%lld",ans[i]);
        }printf("\n");

    }
    return 0;
}

D

题面：

给出a，b，c，每个数都可以加1减1，问你最少需要多少次操作使得c%b == 0&&b%a == 0

solution：

暴力枚举

std：

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int a,b,c,ans = 1e9,ans1,ans2,ans3;
        scanf("%d %d %d",&a,&b,&c);
        for(int i=1;i<=20000;i++){
            for(int j=i;j<=20000;j+=i){
                for(int k=j;k<=20000;k+=j){
                    if(abs(a - i) + abs(b - j) + abs(c - k) < ans){
                        ans = abs(a - i) + abs(b - j) + abs(c - k);
                        ans1 = i,ans2 = j,ans3 = k;
                    }
                }
            }
        }
        printf("%d\n",ans);
        printf("%d %d %d\n",ans1,ans2,ans3);
    }

    return 0;
}