P7184 [CRCI2008-2009] MAJSTOR 题解

· · 题解

题意翻译：给定一个长度为 n 的排列 \mathrm{A}，并给定 r 个类似排列，根据每个排列对应字符的不同可以获得相应得分。让 \mathrm{A} 与其余排列比较。求出总得分，并给出一个最优排列方案，使得总得分最大。

显然可以将得分判定封装为一个函数，代码如下:

void Sven(int c,int g,int d) {
    if(a[c]==b[g][d]) ans++;
    if(a[c]=='S'&&b[g][d]=='P') ans+=2;
    if(a[c]=='P'&&b[g][d]=='R') ans+=2;
    if(a[c]=='R'&&b[g][d]=='S') ans+=2;
}

设 ans 为总得分。

可以用一个二维字符数组 b 来储存其余排列，b_{i,\,j} 为第 i 个排列的第 d 个字符。

可以边读入边处理，代码如下:

for(int i=1; i<=r; i++) {
    for(int j=1; j<=n; j++) {
        cin>>b[i][j];
        Sven(j,i,j);
    }
}

第一问就做完了。

第二问可以用一个贪心的想法，因为排列各字符之间互不影响，局部最优策略可以产生全局最优策略，于是可以枚举 \mathrm{A} 上的每个字符的可能情况并依次与其余排列比较，选择最优，证明显然。

for(int j=1; j<=n; j++) {
    for(int i=1; i<=r; i++) {
        c[i]=b[i][j];
    }
}

这里用了一个临时数组 c 存储当前排列，然后是计算得分的函数。

void Sven1(int a) {
    if(c[a]=='R') l++;
    if(c[a]=='S') l+=2;
}
void Sven2(int a) {
    if(c[a]=='S') f++;
    if(c[a]=='P') f+=2;
}
void Sven3(int a) {
    if(c[a]=='P') h++;
    if(c[a]=='R') h+=2;
}

接下来是总代码。

#include <bits/stdc++.h>
#define N 120
using namespace std;
int n,r,ans=0,l,f,h,anss=0;
char a[N],b[N][N],c[N];
char s='R',su='S',sum='P';
void Sven(int c,int g,int d) {
    if(a[c]==b[g][d]) ans++;
    if(a[c]=='S'&&b[g][d]=='P') ans+=2;
    if(a[c]=='P'&&b[g][d]=='R') ans+=2;
    if(a[c]=='R'&&b[g][d]=='S') ans+=2;
}
void Sven1(int a) {
    if(c[a]=='R') l++;
    if(c[a]=='S') l+=2;
}
void Sven2(int a) {
    if(c[a]=='S') f++;
    if(c[a]=='P') f+=2;
}
void Sven3(int a) {
    if(c[a]=='P') h++;
    if(c[a]=='R') h+=2;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];
    cin>>r;
    for(int i=1; i<=r; i++) {
        for(int j=1; j<=n; j++) {
            cin>>b[i][j];
            Sven(j,i,j);
        }
    }
    for(int j=1; j<=n; j++) {
        for(int i=1; i<=r; i++) c[i]=b[i][j];
        for(int z=1; z<=r; z++) {
            Sven1(z);
            Sven2(z);
            Sven3(z);
        }
        anss+=max(l,max(f,h));
        l=f=h=0;
    }
    cout<<ans<<endl<<anss;
    return 0;
}