本文主要是介绍Codeforces Contest 1043 problem D —— Mysterious Crime —— 删除前后缀使得n个串相同，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Acingel is a small town. There was only one doctor here — Miss Ada. She was very friendly and nobody has ever said something bad about her, so who could’ve expected that Ada will be found dead in her house? Mr Gawry, world-famous detective, is appointed to find the criminal. He asked m neighbours of Ada about clients who have visited her in that unlucky day. Let’s number the clients from 1 to n. Each neighbour’s testimony is a permutation of these numbers, which describes the order in which clients have been seen by the asked neighbour.
However, some facts are very suspicious – how it is that, according to some of given permutations, some client has been seen in the morning, while in others he has been seen in the evening? “In the morning some of neighbours must have been sleeping!” — thinks Gawry — “and in the evening there’s been too dark to see somebody’s face…”. Now he wants to delete some prefix and some suffix (both prefix and suffix can be empty) in each permutation, so that they’ll be non-empty and equal to each other after that — some of the potential criminals may disappear, but the testimony won’t stand in contradiction to each other.
In how many ways he can do it? Two ways are called different if the remaining common part is different.
Input
The first line contains two integers n and m (1≤n≤100000, 1≤m≤10) — the number of suspects and the number of asked neighbors.
Each of the next m lines contains n integers a1,a2,…,an (1≤ai≤n). It is guaranteed that these integers form a correct permutation (that is, each number from 1 to n appears exactly once).
Output
Output a single integer denoting the number of ways to delete some prefix and some suffix of each permutation (possibly empty), such that the remaining parts will be equal and non-empty.
Examples
inputCopy
3 2
1 2 3
2 3 1
outputCopy
4
inputCopy
5 6
1 2 3 4 5
2 3 1 4 5
3 4 5 1 2
3 5 4 2 1
2 3 5 4 1
1 2 3 4 5
outputCopy
5
inputCopy
2 2
1 2
2 1
outputCopy
2
Note
In the first example, all possible common parts are [1], [2], [3] and [2,3].
In the second and third examples, you can only leave common parts of length 1.
题意：
给你m个长度为n的数组，问你如果每个都切掉任意长的前缀和任意长的后缀，在不变成空数组的情况下，有多少种可能使得这m个数组相同。
题解：
既然是切掉前缀和后缀，那么剩下的一定是连在一起的，所以我们对每一组的每一个值都求出他后面的是什么数，之后我们只需要遍历一遍第一个数组，然后看有哪些连在一起的数，之后对于长度为x的数，有(x+1)*x/2种取法，加起来就好了
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,m;
int nex[100005][15];
int a[100005][15];
ll preadd[100005];
vector<int>vec;
int judge(int pos,int val)
{for(int i=2;i<=m;i++){if(nex[pos][i]!=val)return 0;}return 1;
}
int main()
{for(ll i=1;i<=100000;i++){preadd[i]=(1+i)*i/2;}scanf("%d%d",&n,&m);int x;for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){scanf("%d",&x);a[j][i]=x,nex[a[j-1][i]][i]=x;}nex[a[n][i]][i]=1e9;}int pos=1;for(int i=2;i<=n+1;i++){if(!judge(a[i-1][1],a[i][1])){vec.push_back(i-pos);pos=i;}}if(pos!=n+1)vec.push_back(n+1-pos);ll ans=0;for(int i=0;i<vec.size();i++)ans+=preadd[vec[i]];printf("%lld\n",ans);return 0;
}这篇关于Codeforces Contest 1043 problem D —— Mysterious Crime —— 删除前后缀使得n个串相同的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
