• .Title|raw

    HDU6417 Rikka with APSP min25筛+mobius反演


    题目大意 给出一张n'>nn n 个点的完全图,两点i'>ii i 和j'>jj j (i&lt;j'>i<ji<j i )的路径的距离被定义为: dis(i,j)=mink[ijk=x2,x&#x2208;Z+]'>dis(i,j)=mink[ijk=x2,x∈Z+]dis(i,j)=mink[ijk=x2,x∈Z+] dis(i,j) = mink[ijk = x^2,x∈Z^+] 设dij'>dijdijd_{ij} 表示i到j的最短距离,求&#x2211;1&#x2264;i&lt;j&a

  • .Title|raw

    SWERC 2019-20 Problem G. Swapping Places 拓扑排序


    题目大意有s种动物排成一个长度为n的队伍,有l种朋友关系a b,动物a和动物b为朋友可以互相交换位置,但是当且仅当这两种动物在相邻位置时。 问在所有的可能交换位置的方案后,序列最小的字典序排列是什么。 题解挺难想的一个题,看题解只有一句话,看代码看了好久才想明白。 通过动物之间的朋友关系,我们可以确定可以互相交换的有哪些位置,也可以确定哪些动物的相对位置是不能发生改变的。 于是我们可以利用不是朋友的动物之间的相对位置不能发生改变这一点,来进行拓扑排序(当然是字典序更小的动物为更优先序的) 首先给所有物种的名字排序保证是字典序,然后用二维数组E:0 表示两个物种可以交换(是朋友),1表示不能交换

  • .Title|raw

    SWERC 2019-2020 Problem A Environment-Friendly Travel DP+bfs


      题目大意给定起点和终点以及一些中继点的坐标,距离如题目描述中所示,有0-T这些道路,每种道路上每公里排放CO2数量不同,为ci L / km。 你的车最多能跑B(B≤100)公里,每个中继点连接着另外一些中继点,且连通的道路种类有规定。起点和终点到其它中继点的道路全为种类0. 问能不能从起点到达终点,如果不能输出-1,否则输出最少排放的CO2数。 题解首先不管别的,先把道路建起来,所有中继点的关系已经给出,而起点和终点需要额外建立两个点,并且设定连向所有的点。 本来看起来是像是个最短路,但是因为有规定最大的里程数,所以普通的最短路算法并不能适用。 但是注意到最大里程数B较小,所以

  • .Title|raw

    CodeForces 1303G. Sum of Prefix Sums 点分治+李超线段树


    题目大意定义一种叫做前缀数组和的东西sum_i为某个数组的前缀和数组的前i项之和。 现在给定一个树,树上每个节点有权值,树上一条有向路径的权值定义为从起点u到终点v上的所有数字组成的前缀数组和。 求问这种路径权值的最大值是多少。 题解此题解为搬运CodeForces官方题解,为其中文翻译版本。(严正声明,可能中间会加一些个人的理解,代码的话个人的代码感觉还不如官方的好看所以就放官方的题解代码了) 首先确认这是一个树上路径问题,针对树上路径问题,一般可用的方法就是树分治和树链剖分。 考虑到这道题的路径权值的定义,我们并不能用树链剖分的传统的LCA和线段树的方法来进行计算,我们大概需要用搜索算法才

icontofig | 发布于 2020-02-10 23:17:59 | 阅读量 224 | 二分 可持久化线段树 可持久化数据结构
发布于 2020-02-10 23:17:59 | 二分 可持久化线段树 可持久化数据结构

Input

5
1 2 2 3 3
3
2 5 3
2 5 2
1 5 5

Output

2
3
1

题目大意

给出一个序列,有m组询问。

每一组询问有三个参数l,r,w,问区间[l,r]中所有由连续w个元素组成的子序列中的最小值中的最大值是多少。

题解

看到题目里面的最小值最大,肯定能意识到应该是用二分+check去验证元素的(因为其他能想到的方法基本都是暴力,复杂度太高,这题数据范围在105级别没法用的)。

然后问题就在于这个check如何去操作。

如果我们当前二分一个值mid,怎么检查区间l-r中是否所有的连续的w个元素中的最小值中的最大值是mid呢?

这个没法做到,我们只能去确定,是否存在连续w的区间的数全部大于等于mid。

我们假设当前二分到的值为mid,大于等于mid的数都设为1,小于mid的数都设为0,那么问题就变成了询问区间内[l,r]上最长的连续为1的子序列长度len是否大于w的问题。

但是我们注意到一些问题,序列中的数比较大,直接二分的话常数会大些,而且也没有办法对每次二分的mid建一棵线段树去check,时间上会炸掉。

这种情况下我们可以考虑将序列中的值从大到小排序,保留其原先所在的位置下标,对排完序之后的值,我们可以直接用序列进行二分。

而在排完序的情况下,可以注意到,以当前位置的值为check的值时,其构建的线段树就是上一个位置对应的check所用的线段树上在当前位置的值在原序列中的下标对应的位置插入1。

这个修改只有一次,因此可以建立可持久化线段树进行check。

当前二分的位置为mid时,对root[mid]对应的线段树进行check,检索是否可行就可以了。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int n,q;
struct height{
    int h;
    int id;
}a[maxn];
int rt[maxn];
int u,v;
const int INF = 1e9+7;
struct tree{
    int l,r;
    int lc,rc;
    int suml,sumr,sum,len;
}tr[maxn*25];
int cnt = 0;
void push_up(int now){
    tr[now].len = t
继续阅读
icontofig | 发布于 2020-02-06 20:52:24 | 阅读量 312 | 最小生成树 Trie
发布于 2020-02-06 20:52:24 | 最小生成树 Trie

题解

每条边的权值都是根据每个点的定值通过二进制异或得出的。

如果有两个点的数二进制高k位相等,那么我们如果要想要把这两个点的边加入最小生成树,那么花费的代价是与高k位无关的。

假设在第k+1位发生分歧,则这条边的最小权值即为这一位对应的二进制值。然后要做的就是继续向更低位检查。

这明显是个递归过程,而且很容易能想到这个过程是与01Trie的节点访问实际上是一样的。

于是所有的答案统计全部都在01trie上。

接下来看kruskal算法的核心:每一次将最小边权的边试图加入最小生成森林。

所以我们必然优先去找01Trie中同一个叶子节点上的点对的边。

假如一个叶节点上有k个点(k > 2),那么对应的建边方案就是kk-2种。

当从叶节点向上走的时候,假设某节点的父亲节点的两个子树上都有点存在(即两个子树都非空),那么我们肯定要用边把这两个子树连起来,连起来的时候就需要顺着trie往下找异或值最小的边的权值是多少。

细节不是很好解释,不过这种思路是二进制异或时一种常见的贪心思路,可以看代码理解一下。

这个题不需要并查集,因为当刚向上走到某个点时,如果其两个子树都非空,那么这两个子树代表的两个已经构建好的生成树必然属于两个不同的连通块。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PI;
const int maxn = 1e5+5;
const int INF = 2e9;
const ll MOD = 1e9+7;
int n, sz, fac[35], rt;
ll ans,sum;
struct tree{
    int l, r, cnt;
} tr[maxn*30];
ll quick_pow(ll x, ll y){
    ll ans = 1;
    while (y){
        if (y & 1)
            ans = ans * x % MOD;
        x = x * x % MOD;
        y >>= 1;
    }
    return ans;
}
void insert(int &d, int dep, int v){
    if (!d)
        d = ++sz;
继续阅读
icontofig | 发布于 2020-02-03 23:19:32 | 阅读量 355 | 点分治 树状数组
发布于 2020-02-03 23:19:32 | 点分治 树状数组

题解

树上点对距离问题,非常经典的点分治问题。

点分治的基本思路:

对于当前的树(子树),求出其重心,统计过重心的合法路径数,然后以重心为分隔点,分别递归对删除该重心后的子树进行求解(继续求重心、统计,再进行递归)。

重心的概念:若一个点为树的重心,那么其作为根的时候,其子树的大小的最大值最小。

重心的性质:重心分割出的子树的大小不会超过now_n/2,可以用来证明其时间复杂度为O(logn * 统计的时间)。

此题要求距离小于等于k的路径数目,如果把每一种都算出来累加复杂度是相当高的。

可以使用树状数组,不过要注意树状数组的0号位对答案是不会造成任何影响的,所以在统计入树状数组的时候要稍微处理一下。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
struct edge{
    int to,next,val;
}e[maxn<<1];
int siz[maxn],mx[maxn],vis[maxn],dis[maxn];
int c[maxn*100],tmp[maxn];
int n,rt;
int h[maxn];
int lowbit(int x){
    return x & -x;
}
void update(int now,int d){
    while(now <= n * 100 - 2){
        c[now] += d;
        now += lowbit(now);
    }
    return;
}
int query(int now){
    int ret = 0;
    while(now > 0){
        ret += c[now];
        now -= lowbit(now);
    }
    return ret;
}
int cnt = 0,num = 0,sum = 0;
void add(int u,int v,int d){
    e[cnt].to = v;e[cnt].val = d;e[cnt].next = h[u];h[u] = cnt++;
    return;
}
void get_root(int now,int fa){
    siz[now] = 1;mx[n
继续阅读
icontofig | 发布于 2020-01-27 16:34:36 | 阅读量 613 | 字符串
发布于 2020-01-27 16:34:36 | 字符串
#include <bits/stdc++.h>
const int maxn = 2e5 + 5;
using namespace std;
struct Trie{
    int nex[maxn][26], fail[maxn], end[maxn];
    int root, p;
    inline int newnode() {
        for (int i = 0; i < 26; ++i) {
            nex[p][i] = -1;
        }
        end[p++] = 0;
        return p - 1;
    }
    inline void init() {
    	p = 0;
    	root = newnode();
    }
    inline void insert(char *buf) {
        int now = root;
        for (int i = 0; buf[i]; ++i) {
            if (nex[now][buf[i]-'a'] == -1) 
                nex[now][buf[i]-'a'] = newnode();
            now = nex[now][buf[i]-'a'];
        }
        end[now]++;
    } 
    inline void build() {
        queue<int> que;
        fail[root] = root;
        for (int i = 0; i < 26; ++i) {
            if (nex[root][i] == -1)
                nex[root][i] = root;
            else {
                fail[nex[root][i]] = root;
                que.push(nex[root][i]);
            }
        }
        while (!que.empty()) {
            int
继续阅读
icontofig | 发布于 2020-01-15 19:57:24 | 阅读量 909 | 思维题 树状数组
发布于 2020-01-15 19:57:24 | 思维题 树状数组

题目大意

一开始有一个初始顺序的排列[1,n],一共有m次操作,每次将数ai从序列中取出,放到最开头的位置生成一个新的排列。

求问在所有过程中每一个数最小的下标位置和最大的下标位置。

题解

最小的下标位置是非常容易求得的,这很明显,因为如果从来没有被放到开头,那么答案一定是i,否则答案就是1。

需要思考的点在于求最大的下标位置。

这个数据范围不允许进行模拟,链表也不行(链表的单个操作、查询效率极差)。

先来考虑一种特殊情况1:

假设当前所有的数字都已经被放置到第一位过了,在满足这种条件后的最大的下标位置怎么求。

明显元素之间一开始的位置在哪里已经完全互不影响了。

如果一个数再被要求放到第一位,那么这个操作之前的下标位置可能就会影响答案。

而这个下标位置是什么?我们想什么样的操作会影响这个下标位置。很明显只有在上一次此数被放到第一位的时间之后,不同的数字放置到第一位才会使得这个数字的位置向后推移。也就是说,这个下标位置,就是当前未操作时刻和上一次这个数被放到第一位以后的时刻,这之间的不同数字的个数再+1,也就是区间内不同数的个数。

树状数组可以离线询问区间内不同数的个数。由于这道题的特殊性,我们无需对询问区间进行右端点优先排序,直接操作查询即可。

然后再考虑剩下的情况2:

如果一个数之前没有被放置在第一位的经历该如何计算?

这样在它被第一次放置到第一位的命令执行以前,其最大下标位置是之前的时刻被放置在第一位的大于此数的数字的个数 + 此数最初的坐标值。问题变成了维护区间内出现的不同数字的个数,需要用另外一个树状数组进行维护,只需要再每个数字第一次被放置在第一位时维护一次,查询一次即可。

在问题的最后,这样不一定已经求得最大值,因为对于每一个数字,最后可能有影响到最大值的问题但是没有查询更新。

所以在最后我们就要:

对于在操作序列中出现过的数字,我们执行情况1的查询一次。

对于未在操作序列中出现过的数字,我们执行情况2的查询一次。

代码

#include <bits/stdc++.h>
const int maxn = 3e5+5;
using namespace std;
map<int,int>mp;
int tr[maxn],a[maxn],ans[maxn],c[maxn];
int n,m;
int lowbit(int x){
	return x & (-x);
}
void add(int x,i
继续阅读
icontofig | 发布于 2020-01-14 18:21:16 | 阅读量 741 | DP 字符串
发布于 2020-01-14 18:21:16 | DP 字符串

题目大意

给出n个模式串和一个匹配串,求问最少要修改匹配串中多少个字符才能使得匹配串中不含有任意一个模式串。

题解

多个模式串一定要用AC自动机的

所以首先把AC自动机给建出来

然后在AC自动机上跑DP,dp[i][j]表示当前匹配到长度为i,在AC自动机的Trie树上走到节点j的状态下的所需要修改的字符数量的最小值。

要注意不能走到模式串结尾的节点上。

在转移的时候,从当前状态向其子节点转移(前提是子节点非模式串结束的位置对应的节点),如果转移的节点的字符与字符串下一个字符相同,那么下一个状态的dp值继承当前状态dp值,代表不修改下一个字符的情况;否则下一个状态的dp值要在当前状态的dp值的基础上+1,表示修改下一个字符。

最后对dp[len][i]的所有值取min,即为最终答案。

(做这个题主要是为了写一遍AC自动机的板子)

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
const int INF = (1<<30)-1;
struct AC_auto{
    int next[4];
    bool flag;
    int fail;
}tr[maxn];
int root;
int index = 0;
int newnode(bool f){
    tr[index].flag = f;
    tr[index].fail = 0;
    for(int i = 0;i < 4;++i){
        tr[index].next[i] = 0;
    }
    return index++;
}
int n;
char ss[maxn];
int change(char c){
    switch(c){
        case 'A' : return 0;break;
        case 'T' : return 1;break;
        case 'G' : return 2;break;
        default : return 3;break;
    }
    return 0;
}
void build(char *s){
    int now = root;
    int len = strlen(s);
  
继续阅读
icontofig | 发布于 2019-12-22 13:56:06 | 阅读量 347 | 思维题
发布于 2019-12-22 13:56:06 | 思维题

题目大意

给一个不完整的棋盘,每一列的方格数单调非升,问最多可以用多少个不重叠的1x2或者2x1的矩形覆盖棋盘(可以不完全覆盖)

题解

说实话思路比较巧妙

这种问题可以看成二分图匹配,相邻格子染色不同,假设分别染成黑白两种颜色,那么很明显想要用一个矩形覆盖,就必须要有一个黑格和一个白格匹配(两者相邻)。最大匹配数就是最终的答案。

但是这个数据范围过大,不能用匈牙利或者网络流解决。

注意到棋盘每一列的方格数是单调非升的,于是很明显只要先进行染色处理,然后从黑白格子中选出数量最少的那一种,其个数就是最大匹配数。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5+5;
int n;
long long ans;
long long a[maxn];
long long black,white;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 1;i <= n;++i){
        cin >> a[i];
        if(i & 1){
            black += a[i] / 2;
            white += (a[i] + 1) / 2;
        }
        else{
            black += (a[i] + 1) / 2;
            white += a[i] / 2;
        }
    }
    ans = min(black,white);
    cout << ans << endl;
    return 0;
}


继续阅读
icontofig | 发布于 2019-12-10 20:04:25 | 阅读量 581 | 并查集
发布于 2019-12-10 20:04:25 | 并查集

图的连通性问题 : 并查集的基础应用

提出背景

在图论问题中,我们经常性遇到一些关于两个点是否连通的问题。
比如在最小生成树kruskal算法中,我们在逐渐选取最小边的时候,我们需要判断当前要选的边的两个顶点是否已经在同一连通块中。
有基础的同学都知道,在大多数图论问题中,我们的图都是通过邻接表或点对表示边而非邻接矩阵存储的,这样能够提高遍历和存储的时间和空间效率。但实际上,这两种方式也有一个严重的缺陷:不方便查询、修改指定的两点u和v的关系。于是在这种情况下的这两种方式构成的图的连通性也非常难以判断。
这时我们需要一种数据结构能够方便的维护查询图的连通性。

并查集基本概念及操作介绍

所谓并查集,其实是相互连通的各点通过父节点表示法构成的森林(很多棵树的集合),我们判断两点是否相互连通,实际上就是通过他们是否在同一棵树内。很显然同一棵树内的所有点相互连通,这个通过刚才的定义就可以显然得出了,并不需要证明(实际上这里给出的定义是我个人对并查集的理解)。
由上面所说的父节点表示法,并查集这种数据结构自然而然地就是只需要一个一维数组表示就行了,被没有多么麻烦。我们假设为f[i]表示节点i在并查集构成的森林中的父节点。f[i]的初始值设定为i本身
通常来讲,并查集有两种基本操作:
1. 查询操作:查询当前点u的所在的并查集构成的树的根是哪个节点,具体代码实现为:

  1. int find(int x){
  2. if(x != f[x])
  3. return find(f[x]);//x == f[x]表示节点x即为本并查集的根
  4. return x;
  5. }
  1. 合并操作:将两个并查集(两个树)合并,其代表的是这两个连通块之间出现了一条连通边。我们只需要将这两个并查集的树的根进行合并即可,具体操作代码为:
  1. void merge(int u,int v){
  2. u = find(u);
  3. v = find(v);//分别寻找所在并查集的根
  4. f[v] = u;//f[u] = v也可以,通常来讲
  5. return;
  6. }

这两项就是并查集的基本操作了。


并查集构造、查询方式的优化

上面的并查

继续阅读
icontofig | 发布于 2019-12-06 08:04:34 | 阅读量 464 | 费用流 网络流
发布于 2019-12-06 08:04:34 | 费用流 网络流


#include <bits/stdc++.h>
using namespace std;
const int maxn = 405;
const int INF = 1e9;
typedef long long ll;
ll a[maxn],b[maxn],c[maxn];
int p[maxn];
int d[maxn<<1],vis[maxn<<1];
deque<int>q;
int n;
struct edge{
    int to,next,cap,cost;
}e[maxn*maxn*2];
int S,T;
int h[maxn<<1];
int cnt = 0;
void add(int u,int v,int cap,int cost){
    e[cnt].to = v;e[cnt].cap = cap;e[cnt].cost = cost;
    e[cnt].next = h[u];h[u] = cnt++;
    return;
}
bool spfa(int s,int t){
    for(int i = s;i <= t;++i){
        d[i] = -INF;
        vis[i] = 0;
    }
    d[t] = 0;
    vis[t] = 1;
    q.push_back(t);
    while(!q.empty()){
        int now = q.front();
        q.pop_front();
        vis[now] = 0;
        for(int i = h[now];i != -1;i = e[i].next){
            int v = e[i].to;
            if(e[i^1].cap && d[v] < d[now] - e[i].cost){
                d[v] = d[now] - e[i].cost;
                if(!vis[v]){
                    vis[v] = 1;
                    if(!q.empty() && d[q.front()] < d[v])q.push_front
继续阅读
icontofig | 发布于 2019-12-03 23:25:50 | 阅读量 466 | 二分图
发布于 2019-12-03 23:25:50 | 二分图
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 405;
const int INF = 0x3f3f3f3f
ll n, a[maxn],b[maxn],c[maxn],p[maxn];
ll w[maxn][maxn];
ll lx[maxn] , ly[maxn];
ll linker[maxn];
ll slack[maxn];
bool visy[maxn];
ll pre[maxn];
void bfs( ll k ){
    ll x , y = 0 , yy = 0 , delta;
    memset( pre , 0 , sizeof(pre) );
    for(int i = 1 ; i <= n ; i++ ) slack[i] = INF;
    linker[y] = k;
    while(1){
        x = linker[y]; delta = INF; visy[y] = true;
        for(int i = 1 ; i <= n ;i++ ){
            if( !visy[i] ){
                if( slack[i] > lx[x] + ly[i] - w[x][i] ){
                    slack[i] = lx[x] + ly[i] - w[x][i];
                    pre[i] = y;
                }
                if( slack[i] < delta ) delta = slack[i] , yy = i ;
            }
        }
        for(int i = 0 ; i <= n ; i++ ){
            if( visy[i] ) lx[linker[i]] -= delta , ly[i] += delta;
            else slack[i] -= delta;
        }
        y = yy ;
        if( linker[y
继续阅读