题目链接：[SNOI2019]通信  很明显暴力建图，边数达到1e6的级别，费用流必然TLE。 然而连线都是到某个区间连线，所以我们可以想到线段树优化建图。 但是： 我们看一下这个图，可以发现增广的路径长度十分短？所以zkw费用流跑得很快。于是加上剪枝暴力一发！！！  AC代码： #pragma GCC optimize(2) #include<bits/stdc++.h> //#define int long long using namespace std; typedef long long ll; const int N=2e3+10,M=3e6+10,inf=0x3f3f...

题目链接：Tidying Up  题目求最小的交换个数。而不是最小的交换次数。 所以我们可以发现：因为是两两匹配，所以这是一张奇偶分割的二分图。 先对矩阵任意的划分：  对于划分当中，不相等的，必须要交换一个，相等的不用交换 然后我们对于不相等的元素-权重1，连接矩阵的相等元素的边的权重为0。 在任意的分区当中：最小数量的变化矩阵元素对应于不相等元素上的对数。 所以建图正确。  AC代码： #pragma GCC optimize(2) #include<bits/stdc++.h> //#define int long long using namespace std; cons...

题目描述 给你一棵TREE,以及这棵树上边的距离.问有多少对点它们两者间的距离小于等于K 输入格式 N（n<=40000） 接下来n-1行边描述管道，按照题目中写的输入 接下来是k 输出格式 一行，有多少对点之间的距离小于等于k 输入输出样例 输入 #1复制 7 1 6 13 6 3 9 3 5 7 4 1 3 2 4 20 4 7 2 10 输出 #1复制 5 说明/提示 k\leq 20000k≤20000 对于任意一条管道边权w_i\leq 1000w i ​  ≤1000  和统计长度为k的路径条数是一样的。 我们用树状数组维护权值前缀和即可。就能找到小于某个值的个数了。 注意：...

There are n cities in Berland and some pairs of them are connected by two-way roads. It is guaranteed that you can pass from any city to any other, moving along the roads. Cities are numerated from 1 to n. Two fairs are currently taking place in Berland — they are held in two different cities a and ...

2753: [SCOI2012]滑雪与时间胶囊 Time Limit: 50 Sec Memory Limit: 128 MB Submit: 3481 Solved: 1268 [Submit][Status][Discuss] Description a180285非常喜欢滑雪。他来到一座雪山，这里分布着M条供滑行的轨道和N个轨道之间的交点（同时也是景点），而且每个景点都有一编号i（1<=i<=N）和一高度Hi。a180285能从景点i 滑到景点j 当且仅当存在一条i 和j 之间的边，且i 的高度不小于j。 与其他滑雪爱好者不同，a180285喜欢用最短的滑行路径去访问尽量多的...

3747: [POI2015]Kinoman Time Limit: 60 Sec Memory Limit: 128 MB Submit: 2031 Solved: 840 [Submit][Status][Discuss] Description 共有m部电影，编号为1~m，第i部电影的好看值为w[i]。 在n天之中（从1~n编号）每天会放映一部电影，第i天放映的是第f[i]部。 你可以选择l,r(1<=l<=r<=n)，并观看第l,l+1,…,r天内所有的电影。如果同一部电影你观看多于一次，你会感到无聊，于是无法获得这部电影的好看值。所以你希望最大化观看且仅观看过一次的...

题目链接：Time to Raid Cowavans  题目大意：给你一个长度为n的序列w，求w[x] + w[x+y] + w[x+2y] + … + w[x + py],其中x+py <= n。 然后因为区间不是连续的，我们不能用线段树，BIT之类的数据结构去优化。 于是我们可以想到分块，我们对 mod 的值分块，然后对于块的大小大于根号就直接暴力，否则把答案的mod值存起来，然后枚举mod的值，O(n)计算当前mod 的值的答案。  AC代码： #pragma GCC optimize(2) #include<bits/stdc++.h> #define int lon...

有两台机器 A，B 以及 K 个任务。 机器 A 有 N 种不同的模式（模式0~N-1），机器 B 有 M 种不同的模式（模式0~M-1）。 两台机器最开始都处于模式0。 每个任务既可以在A上执行，也可以在B上执行。 对于每个任务 i，给定两个整数 a[i] 和 b[i]，表示如果该任务在 A 上执行，需要设置模式为 a[i]，如果在 B 上执行，需要模式为 b[i]。 任务可以以任意顺序被执行，但每台机器转换一次模式就要重启一次。 求怎样分配任务并合理安排顺序，能使机器重启次数最少。 输入格式 输入包含多组测试数据。 每组数据第一行包含三个整数 N, M, K。 接下来k行，每行三个整数 i...

Intervals Time Limit: 5000MS Memory Limit: 65536K Total Submissions: 9725 Accepted: 4185 Description You are given N weighted open intervals. The ith interval covers (ai, bi) and weighs wi. Your task is to pick some of the intervals to maximize the total weights under the limit that no point in the ...

Warm up Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others) Total Submission(s): 10532 Accepted Submission(s): 2432 Problem Description   N planets are connected by M bidirectional channels that allow instant transportation. It’s always possible to travel between any tw...

以MST的模板为例： 题目链接：MST模板  LCT维护MST一般是，图存在加边的动态MST，如果是删边，那么我们可以考虑使用时间倒流实现把删边变加边。但是如果是即加边又删边就不行了。 对于加边时，如果此两点没有连通，肯定是直接连接。但是如果连接了呢？,，我们就需要用当前的边来替换路径的最大值。然后我们还需要维护当前路径最大边的编号，方便cut断边。 LCT维护的点权，但是我们需要边权，所以我们可以用点来表示边。   AC代码： #pragma GCC optimize(2) #include<bits/stdc++.h> //#define int long long using...

题目链接：[HNOI2010]弹飞绵羊  国内第一道LCT，所以基本上是裸题。 如果我们可以把这个结构想成一棵树，然后如果一个点飞出去，我们可以想成到达另一个节点。所以我们建立一个虚拟节点。 然后用LCT维护子树大小，每次从一个点开始，我们对当前点和虚拟节点拉一条链即可。然后输出子树size。  AC代码： #pragma GCC optimize(2) #include<bits/stdc++.h> //#define int long long using namespace std; const int N=2e5+10; int n,m,k[N],ed; int cnt,s...

输出格式 对于每个询问操作，输出一行答案。 输入输出样例 输入 #1复制 6 5 2 2 1 2 1 1 1 2 1 3 2 4 2 5 2 6 Q 3 5 C 2 1 1 Q 3 5 C 5 1 2 Q 3 5 输出 #1复制 3 1 2  这道题真的是深有感触，当年写树剖一直过不了，也找不到bug，后来不了了之。然后现在换成LCT就好写多了，考虑的东西少了点。  我们用LCT维护链，当前节点颜色，当前表示的链的左颜色，右颜色，当前链的颜色段数量。然后转移即可。  AC代码： #pragma GCC optimize(2) #include<bits/stdc++.h> //#d...

D. Segment Tree time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output As the name of the task implies, you are asked to do some work with segments and trees. Recall that a tree is a connected undirected graph such that there is exactly one simple p...