Codeforces Contest 1043 problem D —— Mysterious Crime —— 删除前后缀使得n个串相同

本文主要是介绍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个串相同的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/881256

相关文章

Mysql实现范围分区表(新增、删除、重组、查看)

《Mysql实现范围分区表(新增、删除、重组、查看)》MySQL分区表的四种类型(范围、哈希、列表、键值),主要介绍了范围分区的创建、查询、添加、删除及重组织操作,具有一定的参考价值,感兴趣的可以了解... 目录一、mysql分区表分类二、范围分区(Range Partitioning1、新建分区表:2、分

MySQL 删除数据详解(最新整理)

《MySQL删除数据详解(最新整理)》:本文主要介绍MySQL删除数据的相关知识,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录一、前言二、mysql 中的三种删除方式1.DELETE语句✅ 基本语法: 示例:2.TRUNCATE语句✅ 基本语

一文详解Git中分支本地和远程删除的方法

《一文详解Git中分支本地和远程删除的方法》在使用Git进行版本控制的过程中,我们会创建多个分支来进行不同功能的开发,这就容易涉及到如何正确地删除本地分支和远程分支,下面我们就来看看相关的实现方法吧... 目录技术背景实现步骤删除本地分支删除远程www.chinasem.cn分支同步删除信息到其他机器示例步骤

python删除xml中的w:ascii属性的步骤

《python删除xml中的w:ascii属性的步骤》使用xml.etree.ElementTree删除WordXML中w:ascii属性,需注册命名空间并定位rFonts元素,通过del操作删除属... 可以使用python的XML.etree.ElementTree模块通过以下步骤删除XML中的w:as

Navicat数据表的数据添加,删除及使用sql完成数据的添加过程

《Navicat数据表的数据添加,删除及使用sql完成数据的添加过程》:本文主要介绍Navicat数据表的数据添加,删除及使用sql完成数据的添加过程,具有很好的参考价值,希望对大家有所帮助,如有... 目录Navicat数据表数据添加,删除及使用sql完成数据添加选中操作的表则出现如下界面,查看左下角从左

如何在Mac上彻底删除Edge账户? 手动卸载Edge浏览器并清理残留文件技巧

《如何在Mac上彻底删除Edge账户?手动卸载Edge浏览器并清理残留文件技巧》Mac上的Edge账户里存了不少网站密码和个人信息,结果同事一不小心打开了,简直尴尬到爆炸,想要卸载edge浏览器并清... 如果你遇到 Microsoft Edge 浏览器运行迟缓、频繁崩溃或网页加载异常等问题,可以尝试多种方

Java实现删除文件中的指定内容

《Java实现删除文件中的指定内容》在日常开发中,经常需要对文本文件进行批量处理,其中,删除文件中指定内容是最常见的需求之一,下面我们就来看看如何使用java实现删除文件中的指定内容吧... 目录1. 项目背景详细介绍2. 项目需求详细介绍2.1 功能需求2.2 非功能需求3. 相关技术详细介绍3.1 Ja

Redis过期删除机制与内存淘汰策略的解析指南

《Redis过期删除机制与内存淘汰策略的解析指南》在使用Redis构建缓存系统时,很多开发者只设置了EXPIRE但却忽略了背后Redis的过期删除机制与内存淘汰策略,下面小编就来和大家详细介绍一下... 目录1、简述2、Redis http://www.chinasem.cn的过期删除策略(Key Expir

使用C#删除Excel表格中的重复行数据的代码详解

《使用C#删除Excel表格中的重复行数据的代码详解》重复行是指在Excel表格中完全相同的多行数据,删除这些重复行至关重要,因为它们不仅会干扰数据分析,还可能导致错误的决策和结论,所以本文给大家介绍... 目录简介使用工具C# 删除Excel工作表中的重复行语法工作原理实现代码C# 删除指定Excel单元

Python对PDF书签进行添加,修改提取和删除操作

《Python对PDF书签进行添加,修改提取和删除操作》PDF书签是PDF文件中的导航工具,通常包含一个标题和一个跳转位置,本教程将详细介绍如何使用Python对PDF文件中的书签进行操作... 目录简介使用工具python 向 PDF 添加书签添加书签添加嵌套书签Python 修改 PDF 书签Pytho