Codeforces715 Div2

A题

题意：按照身高给n个成员排序，要求尽可能让相邻两人的身高平均数是整数，给出方案

解：直接分奇偶数输出即可

#include<bits/stdc++.h>
using namespace std;
 
const int maxn = 1e4 + 10;
int t,n,a[maxn];
 
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i = 1;i <= n; ++i) cin>>a[i];
        int f = 0;
        for(int i = 1;i <= n; ++i)
            if(a[i] % 2)
            {
                if(f) cout<<' ';
                f = 1;
                cout<<a[i];
            }
        for(int i = 1;i <= n; ++i)
            if(a[i] % 2 == 0)
            {
                if(f) cout<<' ';
                f = 1;
                cout<<a[i];
            }
        cout<<endl;
    }
    return 0;
}

B题

题意：一个仅由‘T’和‘M’组成的字符串，能否分成若干个“TMT”的子序列

解：首先M的数量*2是T的数量，然后看M的前后是否都有足够的T即可

#include<bits/stdc++.h>
using namespace std;
 
const int maxn = 1e4 + 10;
int t,n,a[maxn];
string s;
 
bool solve()
{
    int st = 0,sm = 0,q = 0;
    for(int i = 0;i < n; ++i)
    {
        if(s[i] == 'T') st++,q++;
        else
        {
            sm++;
            if(!q) return 0;
            q--;
        }
    }
    return 1;
}
 
bool check()
{
    if(!solve()) return 0;
    reverse(s.begin(),s.end());
    return solve();
}
 
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        cin>>s;
        int num = 0;
        for(int i = 0;i < n; ++i)
            if(s[i] == 'M') num++;
        if(num * 3 != n)
        {
            cout<<"NO\n";
            continue;
        }
        if(!check()) cout<<"NO\n";
            else cout<<"YES\n";
    }
    return 0;
}

C题

题意：定义di = max(a1,a2,...ai) - min(a1,a2,...ai),对a数组排序使得d1+d2+...+dn最小，输出d1+d2+...+dn

解：

Th1 将a进行排序，dn确定,然后枚举每一步删掉了哪个数字，记忆化一下

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

typedef long long ll;
ll n,a[2010];
ll f[2010][2010];

ll solve(int l,int r)
{
    if(l == r) return 0;
    if(f[l][r]) return f[l][r];
    return f[l][r] = min(solve(l,r - 1),solve(l + 1,r)) + a[r] - a[l];
}

int main()
{
    cin>>n;
    for(int i = 1;i <= n; ++i)
        cin>>a[i];
    sort(a + 1,a + n + 1);
    cout<<solve(1,n)<<endl;
    return 0;
}

结果光荣的TLE在了test18

Th2 你都记忆化了为啥不直接DP呢，也对哈，注意下枚举的顺序就行啦，区间DP走起

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

typedef long long ll;
ll n,a[2010],f[2010][2010];

ll solve()
{
    for(int i = 1;i <= n; ++i)
        for(int j = 1;j <= n; ++j)
            f[i][j] = 1e18;
    for(int i = 1;i <= n; ++i) f[i][i] = 0;
    for(int i = n - 1;i >= 1; --i)
        for(int len = 1;len + i <= n; ++len)
        {
            f[i][i + len] = min(f[i][i + len],f[i + 1][i + len] + a[i + len] - a[i]);
            f[i][i + len] = min(f[i][i + len],f[i][i + len - 1] + a[i + len] - a[i]);
            ///printf("f[%d][%d] = %d\n",i,i + len,f[i][i + len]);
        }
    return f[1][n];
}

int main()
{
    cin>>n;
    for(int i = 1;i <= n; ++i) cin>>a[i];
    sort(a + 1,a + n + 1);
    cout<<solve()<<endl;
    return 0;
}

D题

题意：给你3个长度为2*n的01串，要求构造一个长度不大于3*n的01串，使得给出的3个串至少两个能作为答案的子序列

解：瞎搞瞎搞

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

const int maxn = 2e5 + 10;
int t,n,t1,t2,t3;
string s1,s2,s3,a,b,ans,s;

int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        cin>>s1>>s2>>s3;
        ans = "";
        t1 = t2 = t3 = 0;
        while(t1 < 2 * n && t2 < 2 * n && t3 < 2 * n)
        {
            int k = (s1[t1] == '0') + (s2[t2] == '0') + (s3[t3] == '0');
            char ch = (k >= 2)?'0':'1';
            ans += ch;
            if(s1[t1] == ch) t1++;
            if(s2[t2] == ch) t2++;
            if(s3[t3] == ch) t3++;
        }
        if(t1 == 2 * n)
            if(t2 >= t3) while(t2 < 2 * n) ans += s2[t2++];
                else while(t3 < 2 * n) ans += s3[t3++];
        if(t2 == 2 * n)
            if(t1 >= t3) while(t1 < 2 * n) ans += s1[t1++];
                else while(t3 < 2 * n) ans += s3[t3++];
        if(t3 == 2 * n)
            if(t2 >= t1) while(t2 < 2 * n) ans += s2[t2++];
                else while(t1 < 2 * n) ans += s1[t1++];
        cout<<ans<<endl;
    }
    return 0;
}

E题

题意：求n的第k个满足a(i+1)>=a(i)-1的排列