P7050 [NWRRC2015]Concatenation

· · 题解

题目传送门

引言

这个蒟蒻没有认真读题，交了几遍才过，写个题解纪念一下。

思路

一道简单的模拟，但要注意细节。

拿样例来说

cat
dog

分别可以组成

cg cog cdog cag caog cadog catg catog catdog

这九种可能。

那么，在没有构成重复单词的情况下，它一共可以构成第一个单词的字母个数乘上第二个单词的字母个数，现在我们需要知道如何去掉重复单词，那么，请看第二个样例

tree
heap

构成的不再展示，这里展示重复单词

(tre eap  tree ap)  (tre ap  tr eap)

不难发现，重复单词就是两个单词相同的字母数量乘积。

注意：他的构成方法是：使用第一个单词的非空前缀，第二个单词的非空后缀。

code

#include<bits/stdc++.h>
using namespace std;
long long sum,ans,a[60],b[60];
string s,s1;
int main()
{
    cin >> s >> s1;
    ans = s.size() * s1.size();
    for(int i = 1;i < s.size();i++) a[s[i] - 'a']++;
    for(int i = 0;i < s1.size() - 1;i++) b[s1[i] - 'a']++;
    for(int i = 0;i < 26;i++) sum += a[i] * b[i];
    printf("%lld",ans - sum);
    return 0;
}