【Codeforces Round #519 by Botan Investments D】Mysterious Crime
by Codeforces round
2023-09-14 09:03:44 时间
【链接】 我是链接,点我呀:)
【题意】
【题解】
枚举第1个数组以i为起点的子串。 假设i..j是以i开头的子串能匹配的最长的长度。 (这个j可以给2..m这些数组用一个类似链表的东西很快得到,O((j-i+1)*M)的复杂度即可完成。 那么我们会发现,我们不需要重新再从i+1开始枚举。 因为i..j这一段的任意一个子串都是满足要求(公共子串)的。 而它有len*(1+len)/2个子串 那么我们从j+1开始继续上述步骤就Ok了。 注意m=1的时候。。别死循环了。。。j加一个上界n哦.【代码】
#include <bits/stdc++.h>
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
using namespace std;
const int N = 1e5;
const int M = 10;
int a[M+2][N+10];
int n,m;
int main()
{
scanf("%d%d",&n,&m);
rep1(i,1,n) scanf("%d",&a[1][i]);
for (int i = 2;i <= m;i++){
rep1(j,1,n)
{
int x;
scanf("%d",&x);
a[i][x] = j;
}
}
int last = 0;
long long ans = 0;
for (int i = 1;i <= n;i++){
int k = i;
while (1){
int ok = 1;
rep1(j,2,m)
if (k+1<=n && a[j][a[1][k]]+1==a[j][a[1][k+1]])
ok++;
if (ok==m && k+1<=n){
k++;
}else break;
}
ans = ans + 1LL*(1+k-i+1)*(k-i+1)/2;
i = k;
}
printf("%lld\n",ans);
return 0;
}
相关文章
- 京东一面:MySQL 中的 distinct 和 group by 哪个效率更高?太刁钻了吧!
- 8c 数据库,MySQL数据库5.8以上与以下版本,Oracle数据库实现row_number() over(partition by 分组列 order by 排序列 desc)
- Yolo实用指南(step by step)之一环境搭建
- selenium源码通读·7 |webdriver/common/by.py-By类分析
- 不要think step by step!谷歌最新自然语言推理算法LAMBADA:「反向链推理」才是答案
- ORA-24302: host connection in use by another thread ORACLE 报错 故障修复 远程处理
- ORA-26879: “SET_ENQUEUE_DESTINATION” directive is not permitted on rules used by XStream outbound server “string” ORACLE 报错 故障修复 远程处理
- ORA-28027: privileged database links may be used by global users ORACLE 报错 故障修复 远程处理
- ORA-53050: The data model is being edited by another user. ORACLE 报错 故障修复 远程处理
- ORA-14146: Old CONNECT BY does not support partitioned tables ORACLE 报错 故障修复 远程处理
- 在sql中不指定Order by排序是按照主键吗
- MySQL Error number: MY-013863; Symbol: ER_IB_MSG_LOG_FILES_CREATED_BY_CLONE_AND_READ_ONLY_MODE; SQLSTATE: HY000 报错 故障修复 远程处理
- MYSQL实现Oracle的Start with…Connect By递归树查询详解编程语言