5555,太堕落了,好久没有写博客了。 早就听说pb_ds这玩意了,有时候可以省很多东西。 好像最主要是为了替代set不能求第k大的问题。 感觉真的很方便啊~ //可并堆测试#include <ext/pb_ds/priority_queue.hpp>void ceshi_1() { //binary_heap_tag一般比std::priority_queue快 //pairing_heap_tag和std::priority_queue启发式合并时,速度差不多 __gnu_pbds::priority_queue<int, less<int>, __gnu_pbds::pairing_heap_tag> Q1, Q2; Q1.push(1); Q1.push(2); Q1.push(3); Q2.push(1); Q2.push(2); Q2.push(3); Q1.join(Q2);//pairing_heap_tag配对堆,zici O(1)合并 while(!Q1.empty()) { std::pr
发表于 2017-02-28 23:29:53 | 条评论 | 阅读次数:121
质数线性筛 O(1) gcd 可撤销的并查集 权值并查集 O(1)查询的lca 质数线性筛 复杂度:O(n)O(n)O(n) 以前没有深刻的理解这个,今天在看O(1)的gcd才发现这东西原来这么厉害。 每个数字只会被访问一次 每个合数可以拆分为 最小质数p*x 所以,我们要做到,筛数字的时候,只用那个最小的质数去筛,下面是代码: bool not_prime[MX];int prime[MX], prear;void prime_init() { prear = 0; not_prime[1] = 1; for(int i = 2; i < MX; i++) { if(!not_prime[i]) prime[++prear] = i; for(int j = 1; j <= prear && prime[j]*i < MX; j++) { not_prime[i * prime[j]] = 1; if(i % prime[j] == 0) break;
发表于 2017-02-13 18:22:41 | 条评论 | 阅读次数:300
Team Building Archery Training Shoot and kill Mr. Ant & His Problem The Chosen One How Many Answers Are Wrong Hill Climbing Drawing Circles is Fun Legen… Correct Bracket Sequence Editor Family Photos Racing Gems Factorial vs Power Menagerie Team Building 可以发现,可以考虑把两种年级合并成一种年级,那么问题就从3个年级变成了2个年级,然后考虑每次选人从一个年级选1人,另一个年级选2人。 之后很容易就能发现两个年级的做法。 #include <map>#include <set>#include <cmath>#include <ctime>#include <stack>#include <queue>#include <cstdio>
发表于 2017-02-13 14:14:40 | 条评论 | 阅读次数:97
并查集 简单图论概念 kruscal求最小生成树 并查集 基本作用:维护点之间的连通性,支持合并 通常用于一些点,然后可以把一些点和另一些点合并成一类,然后还能查询两个点是否连通。 引入问题 输入n,Q(1≤n,Q≤105)n,Q(1 \leq n,Q \leq 10^5)n,Q(1≤n,Q≤10​5​​),表示n个点,刚开始互相独立。 之后Q行,代表Q次操作。 1 u v,表示在u和v之间连接一条边 2 u v,表示查询,输出u是否和v通过边连通,连通输出YES反之输出NO 如果每次都去搜索,显然复杂度是承受不了的,我们考虑如何去优化 对于一个连通图,我们考虑用一棵有根树去表示它们的连通性。 用P[i]表示一棵树中,i的父节点为P[i],最刚开始时初始化P[i]=iP[i]=iP[i]=i 对操作1,我们就找到u节点所在的那棵树的根节点记为r1,以及找到v节点所在的那棵树的根节点记为r2。如下图1: r1等于r2时,表示现在u和v已经连通了,加了这条边对连通性没有任何影响,所以我们忽略这次操作。 如果r1不等于r2,我们就把P[r1]=r2P[r1]=r2P[r1]=r2当然也可以
发表于 2017-02-12 20:45:39 | 条评论 | 阅读次数:350
新年的第一周,决定尝试坚持把每日一题做完 那么问题来了,窝能坚持几天呢QAQ Alyona and Triangles Fibonotci Boxes Cleaning Valera and Number Tree Game Different Subsets For All Tuples Checking cubes Multipliers Eefun Guessing Words Bit Difference Decreasing Number of Visible Box Alyona and Triangles 找到面积最大的三角形面积。然后做A关于BC中心的对称点A’,同理做出B’,C’,那么A’B’C’构成的三角形会包含所有的点,且面积<=4S 找最大三角形面积,是一个经典的题,先求个凸包,然后在凸包上两点法就好了 #include <map>#include <set>#include <cmath>#include <ctime>#include <stack>#include <queu
发表于 2017-02-09 20:29:47 | 条评论 | 阅读次数:100
Mahmoud and Longest Uncommon Subsequence Mahmoud and a Triangle Mahmoud and a Message Mahmoud and a Dictionary Mahmoud and a xor trip Mahmoud and Longest Uncommon Subsequence 其实只要比较两个字符串是否相等就好了 #include <map>#include <set>#include <cmath>#include <ctime>#include <stack>#include <queue>#include <cstdio>#include <cctype>#include <bitset>#include <string>#include <vector>#include <climits>#include <cstring>#include <iostr
发表于 2017-02-09 20:19:01 | 条评论 | 阅读次数:157
前缀和 一维前缀和 问题1:静态区间求和 问题2:求是否有子区间之和%m等于x 问题3:n个数,选数字之和整除n 问题4:从两端延伸的问题 问题5:先区间更新,然后再区间查询 二维前缀和 问题1:静态子矩阵求和 问题2:先子矩阵更新,然后再子矩阵查询 取尺法 问题1:处理同一类连续区间 问题2:一类具有单调性的问题 前缀和 一维前缀和 定义pre[n]=∑ni=1A[i]pre[n] = \sum_n^{i=1}A[i]pre[n]=∑​n​i=1​​A[i] 问题1:静态区间求和 给定大小为n的数组(1≤n≤105)( 1 \leq n \leq 10^5)(1≤n≤10​5​​),接下来读入n个数字表示A[i](1≤A[i]≤109)A[i] (1 \leq A[i] \leq 10^9)A[i](1≤A[i]≤10​9​​) 接下来输入Q(1≤Q≤105)(1 \leq Q \leq 10^5)(1≤Q≤10​5​​),然后有Q行,表示Q次查询。 每次查询,输入l,r(1≤l≤r≤n)l, r(1 \leq l \leq r \leq n)l,r(1≤l≤r≤n)
发表于 2017-02-05 14:12:05 | 条评论 | 阅读次数:356
Copyright © 2017 - 2018 qwb's blog
blog.csustacm.com All Rights Reserved
Powered by qwb Contact me