Top_xiao-CSDN博客

原创 2020牛客暑期多校训练营（第八场）A All Star

题目连接每个球员有一些粉丝，一个粉丝会去看某个球员比赛的条件是他喜欢这个球员和他喜欢同一个球员的人喜欢这个球员。球员与粉丝的关系可以动态改变，问每一次改变之后，最少请多少球员来比赛才可以使得所有粉丝来看比赛。改变就是对于 b a 两个数，b 是粉丝编号， a 是球员编号，如果 b 是 a 的粉丝，那么现在b 就不是a 的粉丝了，反之 b 变成了 a 的粉丝。相当于线段树分治，对于每个询问，丢到线段树的每个叶子节点中，然后记录每个关系持续的区间。使用线段树区间覆盖就可以了。cnt 代

2020-10-05 13:55:30 194

原创 Space Gophers 校赛排位

题意：在一个巨大的三维网格空间中建造 n 条垂直坐标系的隧道，q 个询问，询问两点之间是否可以通过隧道到达。分析：考虑使用并查集维护，但是如何合并两条隧道较难处理，因为这个网格空间的量级是 1e6 的，我们不可能每次都将整条隧道中的点合并。假设建了一条 (x,y,−1) 的隧道，如下图加粗蓝色柱体：题解链接总结：写完这个题给我的体会就是我缺少三维空间的想象能力。然后还有并查集可以写一个 struct ，这样就会很方便。还有一个匿名函数，写在主程序里面，也很方便。#include<bi

2020-09-28 12:06:13 198

原创 HDU - 4598 Difference

2020-08-09 19:58:31 220

原创 CodeChef - LNDNCK 回滚莫队

链接题意：给你两个数组， B， P，数组个数n 小于等于 2e5.m 个询问，每次询问 l r，把区间 [l, r] 按照 b 的升序排序，然后求和 abs(p[i] - p[i-2]).思路：一开始的思路就是直接暴力莫队，每次把 b 插入到map 里面去，删除也是直接从 map 里面删除。每次修改只会影响周围的几个值。但是每次map 的查询是 log 的，会超时。所以要想一个方法，每次查询时 O（1）的。这个时候用回滚莫队。用一个链表把 b 从小到大串起来。只有

2020-07-24 16:55:01 150

原创 2020牛客多校第二场（G题）Greater and Greater

题目描述：给定大小为n的序列A和大小为m的序列B，计算A中所有大小为m的子区间S，满足Si>=Bi1<=i<=m S_{i} >= B_{i} {1 <= i <= m }Si>=Bi1<=i<=mf 是 a 中哪些位置的数大于等于当前数。如果大于置为1，ans 就是哪些位置满足条件， ans[i] 代表区间 [i, i + m], 是不是满足条件。用 bitset 搞一下，直接暴力肯定是不行的，然后我们考虑到每一个 b[i], 它

2020-07-17 12:40:35 276 1

原创 2020牛客暑期多校训练营（第二场）H. Happy Triangle

三个操作1 多重集合中添加一个数2 多重集合中删除一个数给你一个数x，问能不能从集合中找到两个数 a b，使得 a b x 构成三角形。思路：对于多重集合中，我们假设他有序，那么我们只要找到连续的 a b，使得 a + b > x, b - a < x, 其中 a <= b, 如果符合这样就好了，使得多重集合有序，我们用 map 实现。我们只需要在map中找到 x / 2 + 1 的位置，说明之后的位置两数相加都会大于 x，再找之后位置两数之差

2020-07-17 08:34:45 182

原创 2020牛客暑期多校训练营（第二场） J Just Shuffle

对于一个排列A，给定一个置换规则P，在使用置换P K 次置换得到 A，即，Pk=AP^{k} = APk=AAxk=AA^{xk} = AAxk=AP=AxP = A^{x}P=Ax所以 x 就是 k 关于m的逆元，m 就是每个环的大小。/*求 p， p^k = a, k 为质数。 a ^ xk = ap = a ^ x其中 xk = 1 mod m (m 是每个环的周期数)*/#include<bits/stdc++.h>using namespace std

2020-07-15 12:04:03 136

原创 2020牛客暑期多校训练营（第一场）B Infinite Tree

构造出来之后，就是一棵树，树的根节点就是1.这道题要求 i！， i 的大小最大是 1e5，肯定不能求啊，所以就要拆分，求出来 i！中每个 i 对阶乘的贡献。预处理出来 i 的 mindiv。假设我们选择的 u 就是根节点，那么我们要求的值是多少呢。i < j, i 阶乘中的某个数 x， x / dv[x] 代表 x 向根节点走一步，因为 j 大于 i，所以 j 中肯定也包含数 x，只要 x 走一步，j 也会走一步，所以产生的价值就是 sum[n] - sum[i.

2020-07-14 11:19:35 375

原创 Aizu - 1388 Problem K Counting Cycles

题目意思：给你一个n个点m条边的无向图，求简单环(度数为2的连通子图)个数。 (n≤1e5,n−1≤m≤n+15,保证图联通)思路：看了 m 的范围，就要想到要在树上做。最多有 16 条多余的边，想到状压。二进制枚举。首先想一下如果 n 很小的话怎么做。二进制枚举每次要加的边，然后判断加上这些边能不能构成一个简单环。这些边能不能构成一个简单环的条件是：所有点的度数为 ...

2020-04-13 14:37:51 159

原创利用github hexo 搭建个人博客。

Windos 10 系统按照 Node.js官方地址安装 git官方网站根据自己的电脑系统下载下来一路安装就好。安装git之后，就可以换用 git bash 了，在文件夹里面鼠标右键，找到 git bash 就可以了。以下所有的命令都会在 git bash 中完成。安装 hexo新建一个文件夹，命名 blog，就是自己的博客放在这个 blog 文件夹里面。查看...

2020-04-04 17:16:11 93

原创 Java 学习（三）接口与继承

父类引用指向子类。如果父类是 static 那么调用的还是父类方法，如果不是 static 那就调用子类的方法。记住 static 就好了。子类引用指向子类那就调用子类的方法。...

2020-03-30 11:17:42 77

原创 Java 学习（二）懒汉，饿汉，单例模式

饿汉式单例模式GiantDragon 应该只有一只，通过私有化其构造方法，使得外部无法通过new 得到新的实例。GiantDragon 提供了一个public static的getInstance方法，外部调用者通过该方法获取12行定义的对象，而且每一次都是获取同一个对象。从而达到单例的目的。这种单例模式又叫做饿汉式单例模式，无论如何都会创建一个实例懒汉式单例模式懒汉式单例模式与饿汉式...

2020-03-29 22:00:23 102

原创 Java 学习(一）数组

数组复制：System.arraycopy(src, srcPos, dest, destPos, length)src: 源数组srcPos: 从源数组复制数据的起始位置dest: 目标数组destPos: 复制到目标数组的起始位置length: 复制的长度定义一个数组：int a[] = new int[15]然后用 a.length 那么， length 就是 15；获取...

2020-03-29 20:15:41 124

原创 bzoj 1040: [ZJOI2008]骑士（树形DP）

　Z国的骑士团是一个很有势力的组织，帮会中汇聚了来自各地的精英。他们劫富济贫，惩恶扬善，受到社会各界的赞扬。最近发生了一件可怕的事情，邪恶的Y国发动了一场针对Z国的侵略战争。战火绵延五百里，在和平环境中安逸了数百年的Z国又怎能抵挡的住Y国的军队。于是人们把所有的希望都寄托在了骑士团的身上，就像期待有一个真龙天子的降生，带领正义打败邪恶。骑士团是肯定具有打败邪恶势力的能力的，但是骑士们互相之间...

2020-02-24 09:38:14 151

原创 Educational Codeforces Round 82 (Rated for Div. 2) E Erase Subsequences

题目链接题意：给定字符串 s 和 t ，问能否用至多两个 s 的非重叠子序列相加构造出 t思路：首先把 t 串分成两个小串， t1 和 t2然后 dp[i][j] 代表 t1 的 i 位置， t2 串的 j 位置，匹配 s 串的最短长度。那么 if (i && dp[i-1][j] < n) dp[i][j] = min(dp[i][j], nx[dp[i-1]...

2020-02-23 23:23:48 158

原创 2019 USP-ICMC K. Candies

链接题意：n 个数，还有 L， R，问有多少个本质不同的区间和在 L R 之间。思路：先考虑一个问题，长度为 n 的字符串，求本质不同的子串有多少个。n * (n + 1 ) / 2 然后在减去 height[i] ，这种是求总的，然后减去重复的。sa 代表排名为 i 的子串在的位置，然后 height[i] 代表排名为 i 的子串和排名为 i - 1 的子串重...

2020-02-22 22:40:19 252

原创 SDU-ACM 2020 Winter Camp Day1

题目链接A Codeforces Round #457 (Div. 2) C. Jamie and Interesting Graph题意：给你 n， m，让你构造一个图出来，n 个点， m 条边，每条边有权重。没有重边，没有自环。且从 1 号点到 n 号点最短路的长度是素数。这个图组成的最小生成树的权重和也是素数。思路：先挑一个素数 x 出来， x 大于等于 n，然后我们先...

2020-02-10 23:41:13 169

原创 Codeforces Round #355 (Div. 2)

linkD Vanya and Treasure题意：n*m的格子，一开始再（1，1）的位置，每个位置都有一个宝箱，每个宝箱都有一个编号，编号为x的宝箱可以被编号为x-1的宝箱里的钥匙打开，1号宝箱没有锁，问打开p号宝箱最少走多少步思路：很显然，由于 x 只能打开 x+1 的，所以我们很容易的就想到了暴力 dp，但是如果 x 的个数， x + 1 的个数乘起来很大的话，那么我们就...

2020-02-04 12:08:32 99

原创 Educational Codeforces Round 81 (Rated for Div. 2)

题目链接D. Same GCDs题意：You are given two integers a and m. Calculate the number of integers x such that 0≤x<m and gcd(a,m)=gcd(a+x,m).思路：gcd(a,m) = gcd(a+x, m)so if gcd(a, m) = kthen gcd(a,m) /...

2020-01-31 19:51:48 101

原创 Educational Codeforces Round 80 (Rated for Div. 2) D. Minimax Problem

题目链接题目意思：n*m的数组，选取两行，两行合并成一行，取对应位置上的最大值，然后再取这行的最小值。使这个最小值最大，问这两行的行号。每行的数字最多八个，思路：看到每行最多八个数，就要想到二进制位优化。首先要二分出来最大的数 x ，对于这个数，我们进行check。然后对于每一行，这一行中如果大于 x，就设为1，否则就设为 0，这样每行就可以组成一个数 y 。vis[...

2020-01-26 20:03:28 126

原创 Codeforces Round #605 (Div. 3) E. Nearest Opposite Parity

题目链接题意：N 个数，每个数a[i], 从 i 这个位置只可以走到 i + a[i], i - a[i], 前提是走到的位置在 1 - n 之间，问从 i 这个位置最少走几步走到j，a[i] 和 a[j] 的奇偶不一样思路：我一开始的思路就是用记忆化搜索， f 数组代表当前位 i 的答案，如果搜到了 j 这个位置且 j 这个位置的 f[j] 有值，那么就直接返回就可以了，但...

2020-01-24 13:47:05 179

原创 Educational Codeforces Round 78 (Rated for Div. 2) D. Segment Tree

题目链接题意：n 个点，每个点有一个区间，任意两个区间的值都不一样，值从 1 - 2*n，如果两个区间有交，那么代表这两个点有边，问这n个点是不是一棵树思路：刚看完题就会有一个简单的思路：那就是先排序，然后判断两个点的区间是不是交，如果是交的话那么就用并查集并起来。简单的思路就是这样，但是实现起来的时候，时间复杂度会很大，所以我们要想一种优化的方法，优化时间复杂度。...

2020-01-22 21:32:37 211

原创 Codeforces Round #352 (Div. 2)

C. Recycling Bottles题意：在网格上有n个瓶子，现在有两个人A和B，他们有自己的起始位置，还有一个垃圾桶的位置，求捡完瓶子之后两个人走的最短距离是多少。捡瓶子的步骤是：先去捡瓶子，然后扔到垃圾桶。思路：我们先假设把所有的瓶子都捡了，记录一个答案 ans，代表要走多少路，然后我们找出来从 A 的出发点走会减少多少距离，从 B 的出发点走会减少多少距离。所以我们只需要...

2020-01-20 20:02:23 133

原创 Hello 2020 D. New Year and Conference

题目链接题意：有 n 个事件，在 A 会议室开会的时间段是 abegin aend，在 B 会议室开会的时间段是bbegin bend。现在的要求是在 A 会议室中任意事件相交，那么在 B 会议室中这些事件也要相交，同理，在 B 会议室中任意事件相交，那么在 A 会议室中这些事件也要相交，如果满足条件输出 YES ，否则输出 NO。思路：对于所有的事件，我们按照在 A 会议室...

2020-01-20 15:58:22 141

原创 Codeforces Round #613 (Div. 2) D. Dr. Evil Underscores

题意：给你一些数，找一个数x，使得与所有数的亦或最大的那个值最小 x思路：亦或的话，肯定是位数是从大到小来枚举，如果所有的数中，当前位上的值是一样的，那么 x 在这个位上就一定是 0，如果这个位既有0也有1，那么就要分两种情况来考虑，填 1 会怎么样，填 0 会怎么样，然后把数分成两拨，一波是当前位是1 的，一波是当前位是0的。然后不断递归下去。所以dfs 转移的时候...

2020-01-18 18:25:31 132

原创 Codeforces Round #612 (Div. 2) B. Numbers on Tree

题意：给你一棵树，还原树上每个节点的价值，首先树上的每个节点都有一个数，代表这个节点子树中有多少个节点的价值小于当前节点。思路：对于每一个节点，我们维护一个数组，然后数组中的值就是当前节点和当前节点子树的编号，然后数组中的下标就代表每个节点的价值。dfs 回溯之后，我们就可以知道当前节点插入到数组的哪一个位置。对于怎么维护一个数组，我们就可以用 vector 。vector 支...

2020-01-18 17:29:41 120

原创 Codeforces Round #350 (Div. 2) F. Restore a Number

题意：小明写了一个大数字 n ，然后再这个数字后面又加了一个数字 k ， k 是 n 的位数现在小明把完整的数字传给了小红，但是在传输的过程中出现了意外，小红收到的数字的内容是打乱的，现在知道的是小明还记得大数字 n 的一部分，也就是他的字串，让你还原这个数字 n，且让这个数字 n 尽可能的小。记住，不能又前导零，一个单个的零是允许的。输入是小红收到的数还有小明记住的数思...

2020-01-14 11:39:40 98

原创 dij + spfa + Tarjan

Dij#include<bits/stdc++.h>using namespace std;typedef pair<long long,int> P; //const int N = 2e5+100;int a[N],n,m,k,t;int Head[N],Next[N*2],To[N*2],cnt = 0,val[N*2];long long dis...

2020-01-13 15:52:04 187 1

原创 Codeforces Round #567 (Div. 2)

A. Chunga-Changa简单题B. Split a Number题意：给你一串数字，要你把这串数字分成两部分，然后把两部分加起来的和最少。要分成的两部分有一个原则，就是分成的两部分不能有前导零。思路：一个大体的思路肯定就是把串分成相同长度的两个串，这样才能最小。所以就找中间位置就可以了。如果中间位置上是0，那就向前或者向后找第一个不为零的位置。C. Flag题意：...

2020-01-12 15:41:49 128

原创 Python3 requests爬虫访问HTTPS， HTTP 站点报错SSLError

搞了半天，有时报错有时又不报错，最后把代理关掉了，然后就不报错了。一开始关闭代理还是挺好使的，然后过了一会儿，又不好使了。以下两种方案，任选其一，我是可以了，#这个是使版本适配。adapter = SSLAdapter('TLSv1')s = requests.Session()s.mount('https://', adapter)#这个...

2019-11-23 20:09:11 2223

原创 Python pip install SSL异常处理，[SSL: DECRYPTION_FAILED_OR_BAD_RECORD_MAC]

处理办法：打开以下目录，并创建pip文件夹C:\Users\用户\AppData\Roaming进入pip文件夹，创建pip.ini文件，内容如下换一个阿里的源。[global]index-url = http://mirrors.aliyun.com/pypi/simple/[install]trusted-host = mirrors.aliyun.com...

2019-11-23 16:30:20 1307

原创 csp 201903-2 二十四点

#include<bits/stdc++.h>using namespace std;const int N = 500000;int n;char s[220];stack<int>st;int main(){ int len,x,y; scanf("%d",&n); while(n--){ while(...

2019-11-20 20:21:31 127

原创 Luogu P2602 [ZJOI2010]数字计数

链接:https://www.luogu.org/problem/P2602/*首先我们要知道, 从 0 - 99, 0 - 999, 0 - 9999 , 每个数字出现的次数是一样的. 我们先算在 i 的位置, x 这个数出现了多少次, 9999 假设有四位数,我们现在推到第五位,那么第五位的数 x 出现的所有数就是, x + (0-9999), (0 - 9)+((0 -...

2019-08-19 10:38:37 117

原创 bzoj 2959: 长跑 (LCT 维护双联通分量.)

链接:https://www.lydsy.com/JudgeOnline/problem.php?id=2959三种操作,修建一条路,修改点的权值,从a走到b的权值和.我们用 LCT来做.首先我们用LCT来动态加边,如果两个点不连接,那么我们直接连上就可以了,如果两个点已经连接了,那么我们有 access 这条路径,splay 一下, 然后把路径上的点的权值加...

2019-08-18 10:55:04 121

原创 POJ - 2778 DNA Sequence (AC自动机,求可以构造出来多少串.不包含原串,原串有10个左右,)

链接:https://vjudge.net/problem/POJ-2778总共有101 个节点,可以建一个101*101的矩阵.a[i][j] 代表从节点 i 走到节点 j 的方案数.每走一步,都会形成一个后缀.就需要这个后缀不能包含给定的串,且在构造的串中,加上一个字符不能达到给定的串.如何构造矩阵呢.,就是从 i 节点,然后加上任意一个字符可以到达的节点 j...

2019-08-17 10:16:23 83

原创 2019牛客暑期多校训练营（第七场）F Energy stones (树状数组 + set)

题目:一开始有 n 个石头, 每个石头都有一个初始的能量 e[i] , 然后时候的能量以每秒 l[i] 的速度增加, 每个石头的能量有一个上限 c[i].现在有 m 个询问, t, l, r, 代表在 t 秒, 询问区间 [l,r] 的石头能量之和, 然后询问之后区间的石头能量变成 0.最后输出一个答案, 所有能量之和.思路:考虑每个石头对答案的贡献, 首先要算出来...

2019-08-09 20:22:24 359

原创 2019牛客暑期多校训练营（第七场） E (线段树, 点代表一个区间)

给你的区间是 1e9 的,所以需要我们离散一下,然后每个点代表一个区间就可以了.思路:首先我们考虑到 N 是4e5 的,所以说不同点的个数最多就是 2*N 的,我们就可以用线段树来做了.方法一:我们考虑离散一个区间,把右区间的端点 +1,区间算是左闭右开的, 这样算一个区间的值就是右端点的值减去左区间的值.我们就可以用左区间的值代表整个区间.[1,...

2019-08-09 14:29:54 419 9

原创 Problem F Palindromadness

简单题意, 找两个字符串, A B,A, B 都是回文串, A 是 B 的子串,A 和 B 的位置任意,可以相同,f[x] 为 A 的长度为 x , 的 A B 的对数.根据回文树的性质,如果A 是B 的子串,那么一定会有一条路径, B 找它的父亲,然后直接 fail 指向 A.所以我们只要考虑, A 的子树, fail 指针指向 A 的那些节点的子树....

2019-08-04 10:39:20 167

原创 bzoj 4129: Haruna’s Breakfast (树上莫队 + 修改)

https://www.lydsy.com/JudgeOnline/problem.php?id=4129DescriptionHaruna每天都会给提督做早餐！这天她发现早饭的食材被调皮的 Shimakaze放到了一棵树上，每个结点都有一样食材，Shimakaze要考验一下她。每个食材都有一个美味度，Shimakaze会进行两种操作：1、修改某个结点的食材的美味度。2...

2019-08-03 17:11:43 109

原创 2019牛客多校第三场 A Graph Games　（　分　块　）

题意：给你一张无向图，设s(x)为与x直接相连的点的集合，题目中有两种操作：1：1 l r 将读入的边的序列中第l个到第r个翻转状态（有这条边 -> 没这条边，没这条边 -> 有这条边）2：2 x y 询问s(x)和s(y)是否相等。题解：首先判断　s(x) 和　s(y) 是不是相等,这个我们给每个点一个随机的权值,然后把每个点所连的点的权值亦或起来,判...

2019-08-02 15:01:18 289

空空如也

空空如也