题解 - WHOJ

0
Guest LV 0 MOD
|||
xxxxxxxxxx

100:0
- Guest

因为每一个春联有 $6$ 个间隔，对于每个间隔我们可以认为：不同的记为 $0$ （ $\text{false}$ ），相同记为 $1$ （ $\text{true}$ ）。一共有 $2^6=64$ 种可能，因此先设 $64$ 个桶，每个桶内，每两个均可能构成春联。

具体 $m$ 的实现方式：

int m=0;
        for (int j=0; j<6; j++)
            m=m*2+(s[j]==s[j+1]);

这样，如果有两个春联是对偶的，那么他们的 $m$ 最后结果一定相等。孝先，一定要知道这个（ 一致性 ）。

然后，我们把它们的结果记在一个 $a[m]$ 里：

a[m]++;

我们可以拿样例举例。

5
ABCCCDA
LLLMNNO
DEZZZBF
AAABCCD
KKKXPPQ

$a[i]$ 的每次结果如下：

0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3

但我们只需要注意最后一行。
只要 $n$ 个对联是对偶的，在同一个位置（ 一致性 ）一定是 $n$ 。之后，我们只需要在这 $n$ 个数里选 $2$ 个，即 $\text{C}(n,2)=n*(n-1)/2$ 。

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[64];
int main(){
    freopen("couplet.in","r",stdin);
    freopen("couplet.out","w",stdout);
    int n;
    char s[10];
    scanf("%d", &n);
    for (int i=0; i<n; i++){
        scanf("%s", s);
        int m=0;
        for (int j=0; j<6; j++)
            m=m*2+(s[j]==s[j+1]);
        a[m]++;
    } 
    ll ans=0;
    for (int i=0; i<64; i++)
        ans+=1ll*a[i]*(a[i]-1)/2;
    printf("%lld\n", ans);
    return 0;
}

xhcs (2009xhcs) LV 8 @ 2 年前

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[64];
int main()
{
    freopen("couplet.in","r",stdin);
    freopen("couplet.out","w",stdout);
    int n;
    char s[10];
    scanf("%d", &n);
    for (int i=0; i<n; i++)
    {
        scanf("%s", s);
        int m=0;
        for (int j=0; j<6; j++)
            m=m*2+(s[j]==s[j+1]);
        a[m]++;
    }
    ll ans=0;
    for (int i=0; i<64; i++)
        ans+=1ll*a[i]*(a[i]-1)/2;
    printf("%lld\n", ans);
    return 0;
}
/*
将所有佳句按如下规则进行归类:
相邻字母相同的设为0,不同的设为1，则一共有6个间隔，每位可以为0/1
一共有2^6=64种可能，因此先设64个桶，每个桶内，每两个均可能构成春联
即组合数C(x,2)=x*(x-1)/2，x为桶内数的个数
*/

ID

1501

难度

分类

字符串 | 枚举点击显示

标签

递交数

已通过

通过率

上传者

root (黑暗路西法08)

题解

2 条题解

Code:

拼凑春联（文件IO）

信息

状态

开发

支持

题解

2 条题解

Code:

拼凑春联（文件IO）

信息

状态

开发

支持

还没有账户？

登录