Codeforces Gym 101981 D Country Meow 三维计算几何
题目大意
给出n个点的三维空间坐标，在空间内找任意一个点使得其距离这n个点中的最远的点的欧几里得距离最小。
题解
说实话，马上考期末了应该复习来着，但是总是感觉不写完这篇心里闷得慌……
这题实际上应该是个最小覆盖球，不过此篇博客不打算使用这种算法来做，这里介绍一种比较纯数学的方法去做。
我们假设我们选的点为P(x,y,z)，
那么距离的平方的表达式一定为
如果固定其中的x，y，那么这个式子就是关于z的一个二次函数，且是有极小值的二次函数。
对于x，y当然也是同理的。
我们要求的就是所有距离的平方的最大值的最小值，于是就是求取极小值的一个过程。
众所周知二次函数是个单峰函数，最小值就是极小值，而单峰函数求极小值我们可以用三分来做。
但是这有三个变量(x,y,z)那怎么办？
上面说到如果其中两个固定了，那么不会对第三个变量取值后的函数值产生影响。
于是我们考虑可以使用三分套三分套三分（三层三分套在一起），由于每一层三分并不会影响另外两层三分，于是这个做法是正确的。
这个题没有卡精度，其实eps没有什么用处。
代码
#include <bits/stdc++.h>
using namespace std;
struct point{
double x,y,z;
}p[105];
int n;
double eps = 1e-6;
double mix,miy,miz,mxx,mxy,mxz;
double calc3(double x,double y,double z){
double ans = 0;
for(int i = 1;i <= n;++i){
double ret = 0;
ret += (x - p[i].x) * (x-p[i].x);
ret += (y - p[i].y) * (y-p[i].y);
ret += (z - p[i].z) * (z-p[i].z);
ans = max(ans,ret);
}
return ans;
}
double calc2(double x,double y){
double l = miz - eps,r = mxz + eps,midl,midr;
double ans = 1e15;
for(int cnt2 = 1;cnt2 <= 60;++cnt2){
midl = l + (r-l)/3
题解
青蛙的世界真是简单啊，而人类就不一样了QAQ
扯远了扯远了……
对这个题目进行比较小的数学建模，我们可以得到这样一个式子
然后我们移一下项，可以得到
我们要求解的就是t的最小值。
上式可以转化以下一元二次不定方程：
然后我们都清楚一元二次不定方程的解法无非就是扩展欧几里得……
其中如果gcd((m-n),l)不能整除(y-x)的话，此方程则是无解的，直接输出Impossible。
否则的话，就利用扩展欧几里得去计算t。
先对两边式子的系数同时除以gcd((m-n),l)，利用扩展欧几里得算法解出a*t’ + b*p‘ = 1的解中的t’，然后再乘(y-x)/gcd(m-n,l)转化为需要的t。
此时不一定能够保证t为最小非负值。只需要t 对 (l/gcd((m-n,l)))取膜（如果t<0则取膜后再加膜数），即得到最终结果。
扩展欧几里得算法的讲解与证明将在之后的一篇博客中给出。
代码
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
typedef long long ll;
ll a, b, n, m, l;
void gcd(ll a, ll b, ll &d, ll &x, ll &y){
if(b == 0){
x = 1;
y = 0;
d = a;
return;
}
gcd(b, a % b, d, x, y);
ll tp = x;
x = y;
y = tp - (a / b) * y;
return;
}
ll ans,ans2,g;
int main(){
while ((cin >> a >> b >> m >> n >> l)){
ll sp = m - n;
ll d = b - a;
if(sp < 0){
sp = -sp;
d = -d;
}
if(sp == 0 && d != 0){
cout
BUPT校内训练 Codeforces Gym 101572 G Galactic Collegiate Programming Contest 离散化+树状数组计数
题目大意
一场ICPC赛制比赛，有n支队伍和m次正确提交
每次正确提交包含a,b两个参数，a表示队伍编号，b表示此题的罚时。
要求对于每次事件，输出1号队伍的排名（并列的算同样的排名）
具体排名方法为：通过题目数多的队伍排名靠前，通过题目数相同的队伍总罚时低的靠前。
题解&分析
如果暴力做的话，每一修改O（1），排序查询O（nlogn），总复杂度O(mnlogn)，这对于10^6的数据是不现实的。
我们要求做到O(nlogn)，也就是说不能有每修改一次就排序的操作。
我们可以注意到，每一次事件发生后，只会有一个队伍的成绩发生变化，其余的成绩是不动的。
所以我们可以读入所有数据，然后计算每一次事件发生后出现的成绩二元组(通过题目数，总罚时)。这样我们可以预处理出所有可能的成绩。
之后对所有成绩排序并离散化标号，保证成绩高的离散化后标号较小。
之后我们从头开始模拟每一次事件发生。
对于每一次事件，某一个队伍成绩发生变化，从(a,b)变为（a+1，b+t），而这两个二元组都有与之对应的离散化标号。
于是我们可以考虑使用树状数组（或者线段树，不过树状数组的常数较小）对于当前所有队伍的成绩二元组进行统计。
对每一次事件，(a,b)对应的标号位置数目-1，(a+1,b+t)对应的标号位置数目+1，表示某只对于的成绩发生变化，从(a,b)变为（a+1，b+t）
每次修改完以后查询当前1号队伍的成绩二元组(nowpass,nowtime)所对应的标号之前的一共有多少支队伍，假设为k，则k+1即为当前1号队伍的排名。
代码
#include <bits/stdc++.h>
using namespace std;
int get_num(){
int num = 0;
char c;
bool flag = false;
while((c = getchar()) == ' ' || c == '\r' || c == '\n');
if(c == '-')
flag = true;
else num = c - '0';
while(isdigit(c = getchar()))
num = (num<<1) + (num<<3) + c - '0';
return (flag ? -1 : 1) * num;
}
t
本该早就发出来的一篇……emmm兴许会代表我性格中比较倾向于感伤的一面。
5月12日，从海风吹拂的宜人的秦皇岛返回北京途中，凝望窗外，想了很多……
因为不够成熟，最终在比赛中与冠军失之交臂，仅仅取得了季军的成绩。兴许有人觉得这个成绩挺好的，但这并不是我们想要的成绩，那场比赛的冠军本该属于我们。
不知不觉中，已经过去6年了吧，从一个什么都不懂的普通初中生，稀里糊涂地成为了一个OIer，而后到现在成为一个ICPC竞赛选手。真的是回首才会发现自己已经走了这么长的路了。
在这中间，我曾固执己见，违逆家长和老师的意见；也曾犹豫彷徨，不敢奋力一搏走得更远。这一路，真可谓是坎坷呢：我曾登临顶峰，也曾跌落谷底。这些人生中该走过的经历，我都在这么早的时间走过一遍了呢。兴许我人格中比较成熟的一面，就是因为这段时光的磨砺而诞生的吧。
两年前，当在OI生涯中的最后一场比赛败下阵来，望着同校好友走向省队的面试间，我没有什么反应。是的，我麻木了，令人心碎的麻木。我面无表情地离开了赛场，宣告了自己的退役，去和大多数人一样，接受高考的命运。回学校的路上，本来心性已经被磨砺的十分坚强的我少见的流泪了。那种感觉，是我想要忘记却一直无法忘记的。
如今的我，成为了一个ICPC选手。这也使得我平时的压力更大。寒假回家的时候，家里人都问我：别人家的大学都轻轻松松的，为什么你的大学压力这么大啊？我沉默不语，我知道，解释也没有什么作用。这是我自己选择的道路啊，就算再难，也要走下去啊。
如果要问我：你热爱这个竞赛吗？或许我的回答是，有，但是没有如同很多真正的竞赛大佬那样的近乎于疯狂的热爱。那么，是什么让我坚持着在这条路上走下来呢？在秦皇岛站候车的时候，遇上的某河北高校的竞赛教练如是问我，他的队员们也等候着我的答案。思考良久，我给出了我的回答：大概是因为不甘心吧，心中仍有遗憾，想要消除这种遗憾，不想在这最后能够实现自己梦想的地方留下遗憾。这种不甘的感觉，才是我选择这条路的原因。相比于许多教练所说的我们对于竞赛的热爱，要强这种本性才是我的理由。
我不是一个利益至上的人，而是一个喜欢遵从本心的人。我父亲一直让我问这次比赛到底有没有保研加分一类的东西，然而我想的是，这是我想要做的，那便去做。大学四年，还是不要把时间浪费在自己完全不想去做的事情上。更多地，去做一些自己想
XTCPC2019 湘潭邀请赛 Problem C Chika and Friendly Pairs （莫队+树状数组）
题意：
给定n个数，m条询问，每个询问中包含l、r查询这个区间[l,r]中有多少个数对满足两个数的绝对值之差小于等于K
题解：
上来一看区间查询，第一反应一般都是线段树/树状数组等数据结构。
但是看一下这道题要求什么，求区间内满足条件的数对个数。
我好像没有见过能维护数对个数的树状数组或者线段树什么的。
对于数对而言，一般都应该先枚举其中一个数，剩下的才能去判断吧。
如果两个数i，j满足绝对值之差小于等于K，那么肯定能有这样一个关系式：i−k<=j<=i+k
这样的话，对于某个区间内的所有数，能跟当前枚举出来的数x组成满足题意的数对的，一定在[x-k,x+k]这个区间里，我们只需要统计这个区间有多少个数就行了，这样每一侧的操作是O（Llogn）（L代表区间长度）的。
但是现在问的是对于某个给定的区间内的所有数能够组成的合法数对个数，我们就不能对区间每个数都像上面这样子暴力去统计了。那要怎么办呢？
答案就是使用莫队算法，里层查找答案时使用树状数组。
使用莫队算法能够使得我们有效利用重叠区间所统计的答案，而不必过多的修改统计树状数组来查询答案。
莫队的基本做法就是：先√n对区间分块，然后按照左端点所属块的序号为第一关键字，右端点大小为第二关键字对询问操作进行排序，然后设置l和r代表当前的位置指针， 枚举询问，不断移动l和r使之与当前的询问的l和r重合，期间添加修改信息。
对于此题，在l，r移动时，区间每加入一个数，先用树状数组统计当前区间内的满足条件的数的个数，然后将此数插入树状数组中。区间中要移除一个数的时候类似，不过两个步骤要反过来一下。读者可以自行理解一下为什么。
此题还有一个关键点是，离散化数x、x-k，x+k所组成的新数组，否则数太大树状数组会开不下的。然后离散化后的标号要O（n）用数组处理，不能使用map记录（map的查询复杂度是O（logn）的，会超时）。
总体复杂度O（n√nlogn）（实际上达不到这么大好像）
代码
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <algorithm> #include <map> using namespace std; const int maxn = 1e5+5; map<int,int>u
题解：
我们先来考虑一下我们在使用kruskal算法的时候是怎么生成最小生成树的。
Kruskal算法是一种贪心算法，每次选择边权最小的一条边，检测一下两个端点是否都在一个并查集里，如果不是就加上这一条边，代表最小生成树选择这一条边。
于是这便是此题的关键，如果想要让新加进去的边可能出现在最小生成树中，那么在所有边权小于新边的边集中，就不能有一个子集使得新边的u和v连通。
如果有这样的边集，我们就要通过删边去破坏掉，而且使得破坏掉的边尽可能的少。
诶这不是完美契合最小割模型吗……可是这数据范围……
放心，dinic能顶得住……网络流的复杂度从来都是玄学，这话可不是假的……
于是对于最小生成树，我们就将所有的小于新边权值的边选出来建一张图，每条正向边的容量均为1，求出u，v之间的最小割，就是求出u，v之间的最大流，就可以得出最小生成树部分的答案。
对于最大生成树，其实和最小生成树类似，类比一下就可以了。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 2e4+5;
const int maxm = 2e5+5;
struct edge{
int fr,to,next,cap;
}e[maxm<<3];
int cnt = 0;
int h[maxn];
int cur[maxn],d[maxn];
const int INF = 1e9;
struct edge2{
int fr,to,dis;
}e2[maxm];
int n,m;
/*
bool cmp(edge2 a,edge2 b){
return a.dis < b.dis;
}//其实不用排序
*/
void add(int u,int v,int c){
e[cnt].fr = u;e[cnt].to = v;e[cnt].cap = c;
e[cnt].next = h[u];h[u] = cnt++;
e[cnt].fr = v;e[cnt].to = u;e[cnt].cap
poj - IMMEDIATE DECODABILITY Trie树模板
题解
本题为Trie（字典树）的模板题。
我们先来说一下Trie的基本构造：
Trie树，又名字典树，故名思义，将字符串各个字符以类似字典的方式构造成一棵树，以便检索。
Trie树的每一个节点的深度代表着当前检索到的字符串的长度。而Trie树的每两个节点之间的边可以认为是代表着字典中的一个字符。
字典树的根节点是我们检索字符串的起始，我们每次检索字符串都是由这个根节点开始的。我们每检索一个字符，就顺延着当前这个字符所代表的边走向下一个节点。
有些节点会打一个flag标记，这代表着Trie树中一个单词的结束。
以上是Trie树的基本构造。
对于这个题目，它的要求是判断任意一个字符串不能是另外任意一个字符串的前缀。
所以我们对每个节点加一个cnt标记统计在建立Trie树过程中当前节点的访问次数。
所以题意在我们的思路中，就变为了：
在建Trie树的过程中，如果当前访问的节点打上了flag标记（一个单词的结尾）并且访问次数大于了1，则说明出现一个单词为其它单词的前缀。就输出not immediately decodable，如果建完Trie都不存在这样的单词，就输出immediately decodable。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;
string s;
int num = 0;
const int maxn = 10005;
struct trie{
int cnt;
bool flag;
int child[2];
}pool[maxn],root;
bool pp = false;
void init(){
memset(pool,0,sizeof(pool));
num = 0;
root = pool[0];
pp = false;
return;
}
int sum = 0;
int main(){
init();
while(cin >> s){
int len = s.size();
if
不解释，就是KMP模板题……给出个人常用KMP模板QAQ
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;
string s1;
string s2;
int n;
int cnt = 0;
const int maxn = 10005;
int nxt[maxn];
void KMP_pre(){
int j = -1;
nxt[0] = -1;
for(int i = 1;i < s1.size();++i){
while(j != -1 && s1[j+1] != s1[i])
j = nxt[j];
if(s1[j+1] == s1[i]){
j++;
nxt[i] = j;
}
else nxt[i] = -1;
}
return;
}
void KMP(){
int j = -1;
cnt = 0;
for(int i = 0;i < s2.size();++i){
while(j != -1 && s1[j+1] != s2[i])
j = nxt[j];
if(s1[j+1] == s2[i])j++;
if(j == s1.size()-1){
cnt++;
j = nxt[j];
}
}
return;
}
int main(){
cin >> n;
while(n--){
cin >> s1;
cin >> s2;
KMP_pre();
KMP();
cout << cnt << endl;
}
return 0;
}
UvaLive-6437 Power Plant（变种Kruskal）
题外话
还是vjudge不错233，可以不用注册新帐号了。
这是本人第一篇关于Uva题目的题解。
题目链接放上面大家自己去点，因为PDF格式真的是粘不过来。
题目大意
现在有n个城市，城市之间有m个预期修筑电缆的方案线，其中有k个城市有发电站。
现在要求建设电线，使得每个城市都能有供电。由于每条线路有一定的花费，所以现在要求满足题目的最小花费。
题解
其实题目里已经简化成一个图了，剩下的就是自己想该怎么解决了。
其实思考一下，这好像跟用最小代价选边使得图连通的问题非常接近，第一感觉就是个最小生成树啊，直接kruskal或者Prim就行了啊。
但是回过头来想想，好像有那么一点不对劲的地方。
你看那个样例演示图，明明是不连通的啊。
这是因为本身就有发电站的城市不一定要跟外部连通。所以这题就不是一个纯粹的最小生成树了。但是还是很像，所以我们选择对kruskal进行一下修改。
记录一个cnt，表示当前供上电城市的数量，并查集跟普通kruskal一样的路径压缩写法，不过要加上一个siz数组来记录这一个并查集里有多少城市。
排序也和正常的kruskal一样。
关键点来了。
如何合并并查集啊？以及cnt怎么更新啊？
由于本身就有发电站的城市不一定要和外部连通，所以我们这样：
定义当前边的两个端点的父亲（并查集find后）为x，y，分以下三种情况：
1.x，y都不是有发电站的城市：直接合并并查集，f[y] = x;siz[x] += siz[y]；ans（总花费） += dis。
2.x，y都是有发电站的城市：直接跳过，不需要这条边，也不计入答案。
3.x为有发电站的城市，y则是没有发电站的城市：将y所在的并查集合入x所在的并查集内，维持x在并查集的根节点的位置，并更新当前已经有供电的城市数cnt。
f[y] = x;siz[x] += siz[y];ans += dis;cnt += siz[y];
cnt的初值就是赋为k，表示一开始共有k个城市有供电。
这样这个问题就很轻松的解决了。
为什么不选择Prim？因为Prim没有像Kruskal这样顺手的并查集啊QAQ。（好吧实际上是我Kruskal打习惯了）
参考代码
#include <bits/stdc++.h>
using namespace std;
int get_num(){
int num = 0;
char c;
bool flag = f
题目大意
给出矩形的左下端点和右上端点的坐标，求所有的矩形的面积的并。
题解
求矩形面积并是扫描线的基础经典问题。这篇blog是借助这个来介绍初步入门扫描线。
扫描线，顾名思义，就是一条上下扫描或者左右扫描的虚拟的自主创造的线。
在扫描线扫描到一条线段的时候，就进行操作。而这种操作常常是利用线段树这种数据结构来进行存储的。
在矩形面积的并这一个问题中，我们可以这样去把要计算的总的面积分为这样几个部分来看：
（图来自于别人的博客，实在是不想自己画图了QAQ）
我们可以看到，这个图就是按照扫描线来分区计算面积的。
我们每一次找到一条扫描线，就要维护当前在这条扫描线上（当然这里扫描线是向上扫的）所有的线段的覆盖总长（覆盖部分不再重复计算）。
然后我们用两条扫描线的高度差去乘前一条扫面先上的所有线段的覆盖总长，就是这两条扫描线与矩形围成的面积并。
对于扫描线的顺序，只需要把矩形的上下边去离散化排序以下就可以了。
于是我们剩下的任务就是维护当前扫描线上的线段覆盖总长。
由于x坐标可能会很大，我们一样要对x进行离散化，并且记录离散化后的元素对应的离散化前的元素。
然后我们可以类比前缀和的方式：
对于每一个矩形的下边，我们设这里的标记为+1，对于每一个矩形的上边，我们设这里的标记为-1
这里的标记就可以使用线段树来维护了（但是这里的标记并不需要下放，也不需要向上更新，这里的标记是用于记录这段区间线段是否被覆盖的）。
于是我们在线段树中维护两个变量，一个表示这段区间表示的线段是否被完全覆盖，另一个表示这段区间被覆盖的线段的总长。
在求被覆盖线段总长时，要分两种情况进行讨论：
1.当前区间表示的线段被完全覆盖：区间被覆盖的线段总长即为这段区间表示的线段总长。
2.当前区间表示的线段未被完全覆盖：当前区间被覆盖的线段的总长=其左区间被覆盖的线段的总长+其右区间被覆盖的线段的总长。
我们是一边更新一边统计答案，统计答案只需要每次答案加上总区间被覆盖的线段总长×两条扫描线之间的高度差。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
struct node
{
double x1, x2, y1, y2; int id;
node(double X1 = 0, double Y1 = 0, double X2 = 0, do