2019-08-05 22:56:27 |  0 Comments  |  思维题

2019 Multi-University Training Contest 1004 equation 思维题

题目大意

给出n个二元组(ai,bi),求出Σni=1|aix-bi| = c 的所有解,并用最简分数形式表示,若有无穷多解输出-1

题解

这道题卡我常……比赛的时候被卡常卡到心态炸裂

赛后发现我被排序用的cmp函数给卡了,真TM没想到啊……

首先我们不能直接求绝对值方程式的解,我们通常的想法是把绝对值号拿掉,然后再做。

但是这题一共有n个绝对值式,不是很好办。

我们想一下,每一个绝对值式都有一个对应的变号点,我们可以先把这些变号点求出来,然后根据变号点对每个式子排一遍序。

然后很明显的这些变号点把整个数轴分成了n+1个区间。每个区间对应了一个去掉绝对值后的方程式,也对应着一个合法的解区间。

然后我们对于每一个解区间所对应的无绝对值方程式,可以解出确切的一个解x’,或者解出无数组解。如果解出确切的一个解x‘,我们只需要判断x’是否在当前的合法解区间内即可。

至于解区间间的方程式变换,由于我们已经对式子排了序,也就是确定了每个式子变号点的前后顺序,所以可以做到O(1)变换方程式。

总复杂度O(T*(nlogn + n))

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
int p[maxn],q[maxn];
int tot = 0;
struct funct{
    int a,b;
    double k;
}f[maxn];
const double eps = 1e-5;
bool cmp(funct x,funct y){
    return x.k - y.k >= eps;
}
int T;
int n;
int suma,sumb;
int c;
int x,y,g;
bool flag;
double xx,yy;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&c);
        tot = 0;
        suma = 0;
        su
 2019-08-04 16:38:46 |  0 Comments  |  计算几何 凸包

SPOJ SPOINTS - Separate Points 凸包+判断点与凸包、线段的位置

题目大意

平面直角坐标系上有n个黑点和m个白点,判断能否用一条直线将黑点和白点分成互不相交的两部分。

题解

这题一眼望去就是个裸凸包+判断是否在凸包内。

但是我们要多考虑一些事情,就做一下分类讨论。

如果没有黑点或者没有白点,那么肯定是可以分开的。

如果黑点和白点都只有一个,那么判断一下黑点和白点是否重合。

如果其中一个有两个,另一种有1个,那么我们要判断后者的点是否在前者两个点所在的线段上。

具体的话,就是如下这样子:

if(cnt1 == 1 && cnt2 == 2){
    if(cross(st[1]-sp[1],st[1] - sp[2]) == 0 && mul(sp[1] - st[1],sp[1] - sp[2]) >= 0)
        flag = false;
}
else if(cnt1 == 2 && cnt2 == 1){
    if(cross(sp[1] - st[1],sp[1] - st[2]) == 0 && mul(st[1] - sp[1],st[1] - st[2]) >= 0)
        flag = false;
}

然后如果这两个集合都是组成一条线段的话,则判断两条线段是否相交(使用叉积)

如果以上情况都不满足,那么我们就直接求出两个凸包,然后分别判断两个集合的点是否在另一个集合所有点的凸包中,如果在,就输出NO,否则输出YES。

最终复杂度是O(n+nlogn)。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 505;
typedef long long ll;
struct point{
    int x,y;
}p[maxn],q[maxn],st[maxn],sp[maxn];
int cross(point a,point b){
    return a.x * b.y - b.x * a.y;
}
point operator - (point a,point b){
    point t;
    t.x = a.x - b.x;
    t.y = a.y - b.y;
    return t;
}
bool operator == (point a,point b){
    return (a.x == b.x &&
 2019-08-03 20:58:54 |  0 Comments  |  左偏树 并查集

HDU 1512 Monkey King 左偏树 并查集

题目大意

有n只猴子,每只猴子有自己的能力值,它们会有m次冲突,每次冲突若两只猴子不在同一阵营,则选出两只猴子所在阵营中能力值最高的猴子较量,能力值高的猴子会获胜,并且能力值减半,失败的一方加入胜利方的阵营,问每一次冲突获胜阵营出战的猴子在获胜后的能力值。若同一阵营则输出-1。

题解

每个阵营选出最大值,显然是要维护一个堆什么的,但是至于合并怎么办?

可并堆其实有很多种,这里感觉还是左偏树比较简单。

我们维护左偏树,每一个阵营对应一棵左偏树。

在发生一次冲突时,我们用并查集查询两只猴子所在阵营中能力值最大的猴子(在左偏树的维护过程中保证并查集的根即是左偏树的根),若在一个阵营,直接输出-1;若不在一个阵营,则直接合并两个左偏树,输出新的左偏树的根节点的能力值的二分之一后,将其能力值减半,并从左偏树中暂时删除,然后合并原先的左偏树的左子树和右子树,合并完以后再将刚刚删除的这个点并入新的左偏树,再生成一个左偏树,这个左偏树即是冲突后最新阵营的能力值大根堆了。

总的时间复杂度为O(mlogn)

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
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 << 3) + (num << 1) + c - '0';
    return (flag ? -1 : 1) * num;
}
const int maxn = 1e5+5;
int f[maxn];
int hp[maxn],d[maxn],val[maxn],l[maxn],r[maxn];
int find(int x){
    if(f[
 2019-08-03 20:32:45 |  0 Comments  |  Trie 贪心 启发式合并

Codeforces 965E Short Code Trie树+贪心(启发式合并)

题目大意

给你n个串,让你用每个串的某个前缀串重命名这个串并保证重命名后不会有重复的字符串。

题解

题目很显然需要我们处理n个串的前缀,所以很自然的想到用Trie树(字典树)来降低时间复杂度和空间复杂度。

所以我们先对n个串建立一棵Trie树,然后在这个Trie树上进行操作。

很多人都说后面是启发式合并,我也不是很清楚下面的思路算不算是启发式合并。

后面我们直接dfs整棵Trie树,并自叶节点向上维护信息。

对于每一个节点,维护一个大根堆(用优先队列实现即可),记录其与其子树上的所有的字符串的长度,若我们没有把某个字符串缩到当前节点,那么我们就将子树中深度最深节点所表示的字符串重命名为当前节点所表示的字符串,并回溯更新父节点的信息。

最终回溯到根后,直接将根所有的大根堆内维护的所有的字符串的深度(也就是最终长度)加入答案,最终输出就可以了。

最终的时间复杂度大概是O(nlogn)

代码

#include <bits/stdc++.h>
using namespace std;
int n;
const int maxn = 1e5+5;
string s[maxn];
int cnt = 0;
struct tree_node{
    int ch[26];
    int dep;
    int en;
}tr[maxn<<4];
int dep[maxn];
typedef pair<int,int>PI;
priority_queue<PI>q[maxn];
int ans = 0;
void build(int x,int now,int depth){
    int len = s[x].size();
    for(int i = 0;i < len;++i){
        char t = s[x][i];
        if(tr[now].ch[t - 'a'] == -1){
            tr[now].ch[t-'a'] = ++cnt;
            tr[cnt].dep = tr[now].dep + 1;
            for(int i = 0;i < 26;++i)
                tr[cnt].ch[i] = -1;
            tr[cnt].en = 0;
        
 2019-08-01 16:44:07 |  0 Comments  |  二分 可持久化线段树

2019 Multi-University Training Contest 4 1008 K-th Closest Distance 二分答案+可持久化线段树(主席树)

题目大意

给你一个长为n的序列,有q次询问,每次询问回答区间[l,r]中离p距离第k小的数距离p有多远(距离指在数轴上的距离,也就是差的绝对值)

题目强制在线。

题解

我们首先可以把问题转化为这样:

假设询问的答案为ans,那么就代表着区间[l,r]内的数中,在范围[p-ans,p+ans]中有k个。

所以我们就可以枚举答案,然后去查询区间[l,r]内的符合要求的数的个数。

但是枚举效率过于低下,我们又发现这个答案是具有二分性的,所以我们将枚举答案改为二分答案并且检查。

然后再来看我们怎么统计区间[l,r]内在范围[p-ans,p+ans]的数的个数。

一般来讲,我们判断在范围[p,k]内的数的个数,可以使用权值线段树,维护区间内所有数个数总和,然后查询。

但是此题还要求我们在限定的区间[l,r]内去寻找,所以我们就要使用可持久化权值线段树,也就是主席树维护。

主席树的最经典功能就是可以在静态区间内(无修改操作)查询排名第k的数,而这种功能的实现,实际上也是靠权值线段树统计区间内有多少小于x的数来实现的。

所以我们可以直接使用主席树的权值线段树所有的功能,直接寻找区间[l,r]内在范围[p-ans,p+ans]内的数。

(主席树的root[r]为时刻r的权值线段树的根,也就是表示区间1——r存储的权值线段树的根,当理解这一点以后主席树就没有那么难了)。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
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<<3) + (num<<1) + c - '0';
    return (flag ? -1 
 2019-08-01 11:29:45 |  1 Comments  |  主席树

主席树模板

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
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<<3) + (num<<1) + c - '0';
    return (flag ? -1 : 1) * num;
}
const int maxn = 2e5+5;
struct tree{
    int l,r;
    tree *lc,*rc;
    int sum;    
}pool[maxn<<5],*root[maxn],*null;
int cnt = 0;
void init(){
    null = pool;
    null->sum = 0;
    null->lc = null->rc = null; 
    null->l = null->r = 0;
    return;
}
tree *new_node(){
    tree *node = pool + ++cnt;
    node->lc = node->rc = null;
    node->sum = 0;
    node->l = node->r = 0;
    return node;
}
tree *build(int l,int r){
    tree *node = new_node();
    node->l = l;
    node->r = r;
    if(l == r)return node;
    int mid = (l + r) >> 1;
    node->lc = 
 2019-07-30 12:14:20 |  0 Comments  |  莫队 博弈论 NIM博弈

2019 Multi-University Training Contest 3 Game 经典NIM博弈SG函数 + 带修改莫队

题目大意

先手选出区间L-R的连续的石子堆,后手可以交换第pos 和 pos+1堆石子,然后再从L-R选出区间l-r的石子两人进行取石子博弈。

问在L-R中有多少种后手取l-r的方案能够使得先手必胜。

题解

这题是一个经典的NIM博弈。我们需要用SG函数来解决。

我们考虑前缀SG函数异或和,区间L-R内有多少选择l-r的方案使得先手必胜这一点我们可以转化为有都少方案使得先手必败(SG函数异或和为0)

l-r的SG函数异或和为0,即前缀异或和ssg满足ssg[r] = ssg[l-1],问题转化为统计区间中有多少ssg相等的点对数。

然后我们使用区间点对总数减去区间中ssg相等的点对数就是当前询问的答案。点对问题我们通常使用莫队的分治思想来处理。

然而此题还有交换石子堆的操作,我们能够发现,交换实际上只对一个前缀异或和有影响,所以交换操作实际上就是一个单点修改。

于是我们使用带修改莫队处理整个题目。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
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<<3) + (num << 1) + c - '0';
    return (flag ? -1 : 1) * num;
}
const int maxn = 1e5+5;
int n,m;
struct query{
    int l,r,t,id;
}q[maxn];
int belong[maxn];
int upd[maxn];
int qcnt,dcnt;
int a[maxn],b[ma
 2019-07-27 20:09:15 |  0 Comments  |  线性基

2019 Multi-University Training Contest 1 1002 Operation 线性基

题目大意

给出一个序列,有两种操作你需要完成:

0操作:询问l-----r区间内所有数中部分数通过异或运算所组成的所有数中的最大值。

1操作:在序列尾部插入值x。

注意题目强制在线。

题解

此题是个强制在线的题目,不能使用离线算法(如莫队、CDQ分治)完成。

从0操作我们可以看出来此题很明显是一个线性基的题目(线性基主要用来解决序列中取出若干数使得这些数的异或值最大的问题,当然线性基也可以放入图论问题中)

如果没学过线性基的建议先自学线性基,本篇只是线性基的应用。可能之后我会写线性基的博客吧。

线性基是可以使用一些数据结构维护的,很多人比赛的时候看到这道题要进行区间操作就直接上线段树平衡树来维护线性基了。但是由于这道题的数据范围过大,数据结构会有logn的一个复杂度导致超时。

这道题的正确的思路是贪心地维护以某个位置为结尾的所有数的线性基。

对于每一个线性基,我们尽量把出现时间较为靠后的数的二进制向量放在高位上,然后原来的线性基中各位置上的二进制向量不断下放。如此地贪心地维护以每个位置为结尾的线性基。

在求最大值的时候,首先找到区间右端点对应结尾的线性基,然后从高位向低位开始扫,如果当前扫到的线性基的位置为第j位,且第j位上的二进制向量出现的比查询区间左端点l要晚,那我们就要考虑这个二进制向量对答案的影响,如果异或此二进制向量能够使得答案变大,那我们就异或上这个二进制向量。否则就不需要考虑。

这样我们得出的线性基就有一个性质:对于每个线性基的每一位,与它异或过的线性基更高位置上的数字肯定都出现在它右侧 (否 则它就会被插入在那个位置了),因此做法的正确性显然。

最终复杂度位O(31*n)。(注意此题的强制在线的操作)

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
using namespace std;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag
 2019-07-23 13:56:02 |  0 Comments  |  最短路 网络流 最小割

2019 Multi-University Training Contest 1 1005 Path 最小割+最短路

题目大意

给出一张图,让你删除一些边,使得从1到n的最短路变大,代价为删除边的长度。若本身1与n不连通则输出0。

题解

有人说dinic 会T炸,那应该是他们dinic板子不够优。

这题其实就是先求出1——n的所有最短路,以所有最短路为边建一张图,然后割掉一些边使得1与n不连通。

这是很明显的最小割模型……我们最小割的原图中的所有边的流量即为其原先的长度。

至于如何求所有最短路。

直接求出从1出发的单源最短路,然后遍历一遍所有边,检查当前的边是否是最短路上的边即可。

我寻思我用复杂度比较玄学的SPFA+dinic也过去了啊……而且是1A那种,怎么那么多人说会T炸呢?

代码

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <queue>
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 * 10 + c - '0';
    return (flag ? -1 : 1) * num;
}
const int maxn = 1e4+5;
int T;
typedef long long ll;
const ll INF = 1e15;
struct Flow{
    struct edge{
        int to,next;
        ll cap;
    }e[maxn<<2];
    int h[maxn];
    int cur[maxn];
    int cnt;
    void init(){
        cnt = 0;
        memset(h,-1,sizeof(h));
 
 2019-07-23 13:46:23 |  0 Comments  |  思维题 模拟

2019 Multi-University Training Contest 1 1004 Vacation

题目大意

Tom和Jerry开着0号车,前面依次有1……n号车,且不能超车。

给出每个车的长度、距离停车线的长度、最大行驶速度,求出0号车头部通过停车线的时间。

注意:车开过停车线后依旧不能超车。

题解

正解实际上时用堆(优先队列)来维护各个车的追及时间以及距离什么的,时间复杂度时O(nlogn),而且非常难写。

听说他们有很多用二分做出来的,也不是很清楚怎么check的

这里有一个思维量稍大但代码简单的O(n)的做法。

首先我们要知道,每辆车开过停车线后依旧在走,不能超车,也就是即使此车开过停车线,也是可以堵住后面的车的。

第二点我们要知道的,就是如果前一辆车的尾部没有开过停车线,那么后面的车一定无法开过停车线(虽然看起来很显然,但是这其实是个关键点)。

然后我们考虑如果我们的车被堵了,比方前面所有车被i号车堵住了,那么我们的最少需要的通过时间是多少?

答案是i号车距离停车线的长度加上后面所有车(除去0号车)的长度除以i号车的最大速度。

因为后面的车都被i号车堵住了,所以他们都要按照i号车最终的的速度去通过停车线。

于是我们只需要这样对1……n号车算一遍时间,最后与0号车距离停车线的长度除以其最大行驶速度的值取个最大值就可以了。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 1e6+5;
int n;
double l[maxn],s[maxn],v[maxn],t[maxn];
int main(){
    while(scanf("%d",&n) != EOF){
        for(int i = 0;i <= n;++i)scanf("%lf",&l[i]);
        for(int i = 0;i <= n;++i)scanf("%lf",&s[i]);
        for(int i = 0;i <= n;++i)scanf("%lf",&v[i]);
        t[0] = s[0] / v[0];
        double ans = t[0];
        for(int i = 1;
Title - Artist
0:00