求助站外题
  • 板块学术版
  • 楼主OceanBrawl
  • 当前回复8
  • 已保存回复8
  • 发布时间2022/2/7 15:08
  • 上次更新2023/10/28 09:31:01
查看原帖
求助站外题
567034
OceanBrawl楼主2022/2/7 15:08

rt 题面:

拼凑春联(couplet)
问题描述:
春节到了,春联是必不可少的东西。众所周知,一幅对联的“上联”和“下联”是对偶(也叫对仗)的。小明想从已知的佳句中找出两句对偶的,组合出一些新的春联。图书馆有一个“名句文库”, 小明想知道其中的名句一共可以拼凑出多少组不同的春联。为了简化问题,小明只选择七个字的佳句,并把它们的形式化成了字母(按意群将句子分组、断开)。例如“鲲鹏展翅乾坤大”可化为“AABBCCD”,也可以化为“YYQQZZH”,即字母只起显示结构的作用,与句子内容无关。两个句子按照字母的连续性分段后,如果各成分的字数依次相同,则这两个句子对偶。例如:例如“QBLLLDE”和“DEZZZBF”,将第一句按照字母的连续性分为5段:Q、B、LLL、D、E,每段长度分别为1、1、3、1、1,而第二句经过断句后,各段的长度也分别为1、1、3、1、1,因此这两个句子对偶。注意,“AABCCCD”和“EEFBBBE”这类句子也算作对偶:第二个句子中两次出现“E”,但“E”是断开的,所以断句情况仍为:2、1、3、1。由于字母只用来突出结构,所以如果出现两次同样的字母串,则它们表示的春联内容不相同,当然,它们是对偶的。
输入格式:
第一行,一个整数N,2≤N≤106;以下N行,每行都有一个由七个大写字母组成的字符串,代表一个佳句。
输出格式:
一个整数,表示这些佳句可以拼凑成的对联的组数。

输入:

5
ABCCCDA
LLLMNNO
DEZZZBF
AAABCCD
KKKXPPQ

输出:

4

我代码(小样例过了,大样例无输出):

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ewen using
#define ak namespace
#define ioi std
#define ewen_ak_ioi return 0;
ewen ak ioi;

ll in(){
	char c = getchar();
	int x = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c ^ 48);
	return x * f;
}
void put(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) put(x / 10);
	putchar(x % 10 + '0');
}
int a[11111115];
ll ans;
int C(int m,int n)
{
    int mm,nn,mn;mm=nn=mn=1;
    for(int i=1;i<=m;i++)mm*=i;
    for(int i=1;i<=n;i++)nn*=i;
    for(int i=1;i<=n-m;i++)mn*=i;
    return nn/(mn*mm);
}
int main()
{
	freopen("couplet1.in","r",stdin);
	freopen("couplet1.out","w",stdout);
	int t;scanf("%d",&t);
	for(int i=0;i<t;i++)
	{
        string w;cin>>w;
        char x=w[0];int n=1,s=0;
        for(int j=1;j<w.size();j++)
        {
            if(w[j]==x)n++;
            else
            {
                s=s*10+n;n=1;x=w[j];
            }
        }
        s=s*10+n;
        a[s]++;
	}//读入数据并转化为数字
    for(int i=1;i<=1111111;i++)
    {
        if(a[i]>1)ans+=C(2,a[i]);
    }
    put(ans);
	ewen_ak_ioi
}
/*
int main()
{
    freopen("couplet1.ans","r",stdin);
	freopen("couplet1.out","w",stdout);
	ll s;scanf("%lld",&s);printf("%lld",s);
	return 0;
}
*/

大样例

2022/2/7 15:08
加载中...