Codeforces

A.暴力把每个位置的字符改成另外25个字符，判断是否回文。

#include<bits/stdc++.h>

using namespace std;

string s;

int main()

{

    ios::sync_with_stdio(false);

    cin >> s;

    for(int i = ;i < s.length();i++)

    {

        for(char j = 'a';j <= 'z';j++)

        {

            if(s[i] == j)   continue;

            string ss = s;

            ss[i] = j;

            string sss = ss;

            reverse(sss.begin(),sss.end());

            if(sss == ss)

            {

                cout << "YES" << endl;

                return ;

            }

        }

    }

    cout << "NO" << endl;

    return ;

 }

B.先判断是否都能变成相同串，若可以，则有一个特点，最后的串肯定与初始某个串相同，直接暴力就可以了。

#include<bits/stdc++.h>

using namespace std;

int n,a[][];

string s[];

map<string,int> mp;

int main()

{

    ios::sync_with_stdio(false);

    cin >> n;

    for(int i = ;i <= n;i++)   cin >> s[i];

    int cnt = ;

    for(int i = ;i < s[].length();i++)

    {

        string ss = s[].substr(i)+s[].substr(,i);

        mp[ss] = ;

    }

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

    {

        if(s[i].length() != s[].length() || !mp.count(s[i]))

        {

            cout << - << endl;

            return ;

        }

    }

    int ans =1e9;

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

    {

        int sum = ;

        for(int j = ;j <= n;j++)

        {

            if(i == j)  continue;

            for(int k = ;k < s[i].length();k++)

            {

                string ss = s[j].substr(k)+s[j].substr(,k);

                if(ss == s[i])

                {

                    sum += k;

                    break;

                }

            }

        }

        ans = min(ans,sum);

    }

    cout << ans << endl;

    return ;

 }

C.这道题首先注意负数和0的gcd，可以用__gcd尝试一下。

先判断初始的gcd是否大于1，若大于1，直接YES。

否则，剩下的数我们只用考虑它们的奇偶性。

相邻两个分为4中情况：

　　①奇奇　　直接操作这两个位置　　ans+1

　　②偶偶　　不用动

　　③奇偶　　操作两次变成奇奇　　ans+2

　　④偶奇　　考虑到最少的操作次数，把奇与其后面的数操作，若奇已经是最后一位，偶奇操作两次，变成奇奇

#include<bits/stdc++.h>

using namespace std;

int n,a[];

int main()

{

    ios::sync_with_stdio(false);

    cin >> n;

    cin >> a[];

    int t = a[];

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

    {

        cin >> a[i];

        t = __gcd(t,a[i]);

    }

    if(t > )

    {

        cout << "YES" << endl <<  << endl;

        return ;

    }

    int ans = ;

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

    {

        if(a[i]% && a[i+]% == )

        {

            ans += ;

        }

        else if(a[i]% && a[i+]%)

        {

            ans++;

            a[i+]++;

        }

    }

    if(a[n]%)  ans += ;

    cout << "YES" << endl << ans << endl;

    return ;

 }

D.我们对个数分奇偶。

若是奇数个：

　　对A排序，A₁对应下标加入，剩下偶数个数，两两分，每组取B中最大的那个下标。

若是偶数个：

　　对A排序，A₁对应下标加入，剩下n-2个跟上面相同操作，A_n对应下标加入。

这样操作的结果肯定是符合要求的。

#include<bits/stdc++.h>

using namespace std;

int n,b[],c[];

struct xx

{

    int x,id;

    friend bool operator <(xx a,xx b)

    {

        return a.x > b.x;

    }

}a[];

vector<int> ans;

int main()

{

    ios::sync_with_stdio(false);

    cin >> n;

    long long sum1 = ,sum2 = ;

    for(int i = ;i <= n;i++)   cin >> a[i].x,a[i].id = i;

    for(int i = ;i <= n;i++)   cin >> b[i];

    sort(a+,a++n);

    ans.push_back(a[].id);

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

    {

        if(i == n)  ans.push_back(a[i].id);

        else

        {

            if(b[a[i].id] > b[a[i+].id])   ans.push_back(a[i].id);

            else    ans.push_back(a[i+].id);

        }

    }

    cout << ans.size() << endl;

    for(int i = ;i < ans.size();i++)   cout << ans[i] << " ";

    cout << endl;

    return ;

 }

另外还有种做法，随机大法，好厉害的样子。

#include<bits/stdc++.h>

using namespace std;

int n,a[],b[],c[];

int main()

{

    ios::sync_with_stdio(false);

    cin >> n;

    long long sum1 = ,sum2 = ;

    for(int i = ;i <= n;i++)   cin >> a[i],sum1 += a[i];

    for(int i = ;i <= n;i++)   cin >> b[i],sum2 += b[i];

    int k = n/+;

    for(int i = ;i <= n;i++)   c[i] = i;

    while()

    {

        long long x1 = ,x2 = ;

        for(int i = ;i <= k;i++)

        {

            x1 += a[c[i]];

            x2 += b[c[i]];

        }

        if(x1* > sum1 && x2* > sum2)

        {

            cout << k << endl;

            for(int i = ;i <= k;i++)   cout << c[i] << ' ';

            cout << endl;

            return ;

        }

        random_shuffle(c+,c++n);

    }

    return ;

 }

巴特西

Codeforces_798

最新文章

热门文章