链接：

https://codeforces.com/contest/1251/problem/B

题意：

A palindrome is a string t which reads the same backward as forward (formally, t[i]=t[|t|+1−i] for all i∈[1,|t|]). Here |t| denotes the length of a string t. For example, the strings 010, 1001 and 0 are palindromes.

You have n binary strings s1,s2,…,sn (each si consists of zeroes and/or ones). You can swap any pair of characters any number of times (possibly, zero). Characters can be either from the same string or from different strings — there are no restrictions.

Formally, in one move you:

choose four integer numbers x,a,y,b such that 1≤x,y≤n and 1≤a≤|sx| and 1≤b≤|sy| (where x and y are string indices and a and b are positions in strings sx and sy respectively),

swap (exchange) the characters sx[a] and sy[b].

What is the maximum number of strings you can make palindromic simultaneously?

思路:

考虑所有串的长度，当有奇数长度存在时，保证可以交换出全部，当没有时，可能存在0或1为奇数，不能配对，有奇数可以将奇数减位，同时保证剩下的偶数相等。

代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

int n;

string s;

int main()

{

    int t;

    scanf("%d", &t);

    while(t--)

    {

        int one = 0, zer = 0;

        int q = 0;

        scanf("%d", &n);

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

        {

            cin >> s;

            int len = (int)s.length();

            if (len%2)

                q++;

            for (int j = 0;j < len;j++)

            {

                if (s[j] == '0')

                    zer++;

                else

                    one++;

            }

        }

        if (q > 0)

            printf("%d\n", n);

        else

        {

            if (one%2 || zer%2)

                printf("%d\n", n-1);

            else

                printf("%d\n", n);

        }

    }

    return 0;

}

巴特西

Educational Codeforces Round 75 (Rated for Div. 2) B. Binary Palindromes

链接：

题意：

思路:

代码：

最新文章

热门文章