C - Concatenation Gym - 100801C

本文主要是介绍C - Concatenation Gym - 100801C，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：
$A$中取出一个前缀，$B$中取出一个后缀，问问拼出多少个字符串

思路：
感觉很巧妙的一道题。
首先能构造出的字符串总数为 $lena\ast lenb$。
那么假设从$A$中取出的前缀结尾字符为$x$，那么从$B$中取出的后缀首字符为$x$的有$m$个，那么将$A$的结尾去掉或者将$B$的首部去掉，拼成的字符串是一样的，也就是重复算了$m$次。

假设$A$中结尾为字符$x$的有$n$个，那么对于字符$x$来说，一共多算了$n\ast m$次。
所以统计出$A$中前缀结尾字符出现次数和$B$中所有后缀开头字符出现次数，减去所有相同字符个数乘积。

但是注意A串第一个字符和B串最后一个字符不统计，因为首字符往前和尾字符往后是空的，发生不了重复。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>using namespace std;typedef long long ll;
const int maxn = 1e5 + 9;
char a[maxn],b[maxn];
ll vis1[30],vis2[30];int main() {freopen("concatenation.in","r",stdin);freopen("concatenation.out","w",stdout);scanf("%s%s",a + 1,b + 1);int n1 = strlen(a + 1);int n2 = strlen(b + 1);ll num = 1ll * n1 * n2;for(int i = 2;i <= n1;i++) {vis1[a[i] - 'a']++;}for(int i = 1;i < n2;i++) {vis2[b[i] - 'a']++;}for(int i = 0;i < 26;i++) {num -= vis1[i] * vis2[i];}printf("%lld\n",num);return 0;
}

这篇关于C - Concatenation Gym - 100801C的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---