金华自闭 Day1

A. 串

20pts

暴力枚举 .

具体来说,我们先枚举 ,然后按等差数列枚举 ,check 一下统计即可

check 失败就 break

40pts

其他人好像都是前缀和来着。。。

变换一下枚举顺序,先枚举 ,即单位串长度

再枚举变换串的起点 ,然后统计

我们把变换串 按单位串的长度分为

那么我们称 子变换串,这个串也满足变换串的性质

因此,枚举了 就不用枚举 了,我们枚举起点只用枚举 ,即取遍 的剩余系即可。之后的起点都被 包括了,那么就不需要统计啦

在统计答案的时候, 的贡献显然为 . 另外,我们 check 是检查前后两个串是否至多有一个不同位置,那么在 check 失败的时候就不用 break 了,把 x 清零即可

做这件事情后呢,我们考虑优化 check 的过程

本来我们需要遍历字符串 check,这里考虑一下起点从 变化到 的时候,其实每个字符串只改变了两个位置(开头少一个,结尾多一个),那么我们记录一下相邻两个单位串的不同字符数,就可以做到均摊 的 check,那么复杂度为 .

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=1e5+5;
char s[N];
int ans;
int del[N];
int calc(int a,int b){// unsimilarity
    int tot=0;
    for(int i=0;i<b-a;i++)tot+=(s[i+a]!=s[i+b]);
    return tot;
}
int main(){cin>>s;
    int n=strlen(s);
    for(int len=2;len<n;len++){for(int i=0;i<len;i++){// 起点
            int tot=1;
            for(int k=0;i+k+len+len-1<n;k+=len){if(i==0)del[i+k]=calc(i+k,i+k+len);// 初始时计算 check
                else del[i+k]=del[i+k-1]-(s[i+k-1]!=s[i+k+len-1])+(s[i+k+len-1]!=s[i+k+len+len-1]);//O(1) 维护 check
                if(del[i+k]<=1)++tot;
                else ans+=tot*(tot-1)/2,tot=1;
            }
            ans+=tot*(tot-1)/2;// 累加答案
        }
    }
    cout<<ans;
    return 0;
}

60pts

杜教:因为 20pts等概率随机,那么枚举 len 的时候枚举小一点就行

100pts

略解:

若要求绝对相同,这时我们枚举长度,后缀数组来 求 LCP,LCS,转化为 01 序列上的 1 区间的个数,做到 的统计,那么总复杂度 .

那么当有一个位置可以不同的时候,在求 LCP,LCS 的过程中就会遇到失配点

那么我们跳过失配点继续求 LCP,LCS,记录区间即可;同样可以转化为 01 序列上的 1 区间的个数(把失配点连上),继续统计即可

B. 树

咕咕。。。

C. 图

分析这道题首先了解一个概念,线图

线图

对于无向图 ,它的线图 也是一个无向图:

  • 它的点集为 ,每个点唯一对应着原图的一条边。
  • 线图上的两个点之间有边当且仅当这两个点对应的边在原图上有公共点 (注意不会有自环)。

如果我们我们把图 的点和边都赋上权值。在 中,我们可以认为点权为原图中对应边的边权,边权为原图中对应公共点的点权。

上述为线图变换,而由此推出, 即为 经过 次变换的图,现在要求求 的 MST.

鉴于 ,分情况讨论

k=0

直接 MST,kruskal 走起

k=1

这时我们考虑一下一次线图变换的意义。假设原图是这样的

p1

那么经过线图的变换后会变成这样

p2

什么意思呢?就是每个顶点会变成对应的团,而边则变成了顶点

在这样的图当中求 MST,我们考虑 kruskal 算法的过程:找到当前未选择的边中最小的边。

注意到我们的 中的每一条边都包含在某一个团里面,那么这个团里面的边权又都是相等的(都为 中对应顶点的点权),因此对于这个团的顶点,假设顶点数为 ,如果要在这个团里面选边,那么选的边的数量不会超过 . 因为你选 条边后这些顶点就都连通了,因此剩下的边没必要考虑。

于是 中的每个团只需要考虑 数目的边,这个数目与 中的顶点数是同级的,因此 kruskal 的复杂度仍为 .

k=2

我们继续考虑两次线图变换的含义

  • 对于 中的点,其本质等价于 中的边,等价于 中两个具有公共顶点的边
  • 对于 中的边,其本质等价于 中两个具有公共顶点的边,而这也等价于 中三个连续边链

抽象图示一下,点:

p3

边:

p4

也就是说, 一条边对应 中的两个有公共边的 v 字形结构。并且这个结构也包含了点的线图变换结构,红色和绿色分别对应一个线图的点结构,这两个点结构有公共边。

那么我们考虑一下 kruskal 算法的过程。之前 的时候,我们的分析建立在团的连通性上的,相似的逻辑,这次我们把分析建立在边上。那么首先我们要知道,经过线图变换后的边会变成什么

经过一次线图变换后,一条边会变成一个顶点;而再经过一次变换后,这个顶点会变成一个团。也就是说,一条边经过两次线图变换会变成一个团!

那么这个团有怎样的性质呢?易得,这个团的边权是 中原边的边权!

的边又是怎么分布的呢?显然,每一条边都在某一个团里面。而又因为某些团是有各自的公共点的,那么只要我们让部分团内部连通,那么就可以使得整个图连通啦(尝试对第 2 幅图做 MST,显然你不用使得每个团内部连通)

既然我们是要求 MST,那么点权什么的就可以忽略啦。因此,这个团中的边显然也不用全部枚举,只要使其中的点连通即可。首先,我们要知道 的顶点数。即求 中 v 字形的个数。这个组合数学算一下即可:

那么我们就连 条边即可。

同样的,考虑 kruskal 的算法过程。我们尝试把在 上的 kruskal 映射为 上的 kruskal:

我们从小到达枚举 中的边,

  • 对于选择的第一条边,它对应 中的一个团,假设这条边两个端点的分别为 ,那么这个团的顶点数显然为 。显然初始时这个团有 个连通块,那么我们贪心地连接其中的任意 条边,使其连通成一个整体。这时,这个团显然可以缩点。那么在 上的缩点对应在 上的什么操作呢?——删边!既然这个团缩了点,那么其所有的边都消失了,这个团也消失了(这里的团偏指边集),不就相当于删边吗!因此,我们在原图中把这条边删除(其实就是两个点的度 -1)
  • 对应之后的边,显然和上述操作一样,根据端点的度来判断连的边数,减少对应的连通块数量,然后在原图上删边即可。直到删去了 为止.
  • 复杂度 .

  转载请注明: Sshwy's Blog 金华自闭 Day1

 上一篇
KMP 算法 KMP 算法
摘要 用于字符串匹配,在 O(n) 复杂度内完成匹配。 算法思想对于朴素算法,当 即匹配失败时,是将整个 S 向后移动一位,复杂度 O(mn)。这种算法的缺点在于,移动一
2019.02.12
下一篇 
初探母函数 初探母函数
摘要 本文主要介绍普通母函数及其应用 定义在数学中,某个序列 的母函数(又称生成函数,英语:Generating function)是一种形式幂级数,其每一项的系数可以提供关于这个序列的信
2019.01.26
  目录