Educational Codeforces Round 78 (Rated for Div. 2)

A题

给出n对串，求s1，是否为s2一段连续子串的重排，串长度只有100，从第一个字符开始枚举，sort之后比较一遍就可以了；

char s1[200],s2[200],s3[200];

int main() {

    int q;

    cin >> q;

    while(q--) {

        cin >> s1 >> s2;

        int s11 = strlen(s1),s22 = strlen(s2),i;

        sort(s1,s1+s11);

        s3[s11] = '\0';

        for(i = 0; i + s11 <= s22; i++) {

            strncpy(s3,s2+i,s11);

            sort(s3,s3+s11);

            if(strcmp(s1,s3) == 0) {

                cout << "YES" << endl;

                break;

            }

        }

        if(i + s11 > s22) cout << "NO" << endl;

    }

    return 0;

}

B题

给出两个数a和b，第i次操作可以把i加给任意两个数，求将两个数变为相等的最小操作次数

把i求和得来的数sum和cha = abs(a-b)，相加，让sum和cha的和对2取模为0并且sum >= cha（如果小于的话全部加到比较小的数上也无法相等）,输出i就可以了。

int main() {

    int q;

    cin >> q;

    while(q--) {

        int a,b;

        cin >> a >> b;

        ll min = 0,cha = abs(a-b);

        int i = 1;

        while(cha > min || (cha + min)%2 != 0) min+=i++;

        cout << i-1 << endl;

    }

    return 0;

}

C题

给出2n个罐子，里面分别装着蓝色和红色的东西，分别从n和n+1之间向两边拿走一些，问最少需要拿走多少罐，就可以让两种颜色的数量相等。

输入的2改为-1，求前缀和和后缀和，用map记录位置，求除留下最大数量，然后用2n减去，输出就可以了

map<int,int> mmp;

int a[MAXN],lsum[MAXN],rsum[MAXN];

int main() {

    int q;

    cin >> q;

    while(q--) {

        mmp.clear();

        int n;

        cin >> n;

        for(int i = 0; i <= 2*n+1; i++) {

            lsum[i] = 0;

            rsum[i] = 0;

        }

        for(int i = 1; i <= 2 * n; i++) {

            cin >> a[i];

            if(a[i] == 2) a[i] = -1;

        }

        for(int i = 1; i <= n; i++) {

            lsum[i] = lsum[i-1] + a[i];

        }

        for(int i = 2*n; i >= n+1; i--) {

            rsum[i] = rsum[i+1] + a[i];

        }

        for(int i = 0; i <= n; i++) {

            mmp[lsum[i]] = i;

        }

        int ans = 0;

        for(int i = 2*n+1; i >= n+1; i--) {

            int t = -rsum[i];

            if(mmp.count(t)) ans = max(ans,mmp[t]+2*n - i + 1);

        }

        cout << 2*n - ans << endl;

    }

}

艰难的补题之旅开始了

巴特西

Educational Codeforces Round 78 (Rated for Div. 2)

A题

B题

C题

最新文章

热门文章