- 博客(298)
- 收藏
- 关注
RSS订阅
原创 友链
g19:%%%金牌爷DZYO%%%%%%北大学姐lyw%%%%%%清华学长gyr%%%%%%SC状元zjj%%%g21:萌妹一只：%%%ldx%%%%%%zxy%%%tql至强之王♂：%%%cyk%%%%%%gsj%%%%%%osy%%%%%%xly%%%%%%wcr%%%%%%glf%%%%%%rhj%%%%%%lsr%%%菜鸡g22:%%%fsy%%%%%...
2019-08-09 13:38:56
403
原创 About romiqi
事情是这样的这里是romiqi的新博客romiqi的那个博客因为各种原因停更了很久又因为各种原因登不上去了所以这里就是romiqi的新博客啦
2018-10-06 21:33:40
241
1
原创 [2-sat][POI2001]和平委员会
根据宪法，Byteland民主共和国的公众和平委员会应该在国会中通过立法程序来创立。不幸的是，由于某些党派代表之间的不和睦而使得这件事存在障碍。此委员会必须满足下列条件：每个党派都在委员会中恰有1个代表，如果2个代表彼此厌恶，则他们不能都属于委员会。每个党在议会中有2个代表。代表从1编号到2n。 编号为2i-1和2i的代表属于第i个党派。任务：写一程序读入党派的数量和关系不友好的代表对...
2019-11-12 21:37:39
755
原创 191106CSP（NOI？）模拟及NOI（CSP？）模拟题解
CSP模拟：T1：求∑i=1n∑j=1mCgcd(i,j)B%mod\sum_{i=1}^n\sum_{j=1}^mC_{gcd(i,j)}^B \%mod∑i=1n∑j=1mCgcd(i,j)B%modn,m≤1e10,B≤mod=9990017n,m\le1e10,B\le mod=9990017n,m≤1e10,B≤mod=9990017莫比乌斯反演，设f(i)f(i)f(i)表...
2019-11-06 19:04:24
444
2
原创 191101CSP模拟题解
T1：给定n,k,ln,k,ln,k,l，求nnn个数每个取值[0,l][0,l][0,l]，其一个子序列和为kkk的方案数，n,k≤20n,k\le 20n,k≤20补集转化，是个背包，然后状压算方案，dp of dpCode：#include<bits/stdc++.h>#define ll long long#define mod 998244353using nam...
2019-11-01 17:07:40
284
原创 191026考试题解
T1：求一个网格图从原点出发走n步，每步等概率往上下左右走，最终到达的点和原点之间的欧氏距离的期望打个表可以发现是n，完了具体证明可以推式子或者三角函数#include<bits/stdc++.h>#define mod 998244353#define pii pair<int,int>#define pb push_back#define mp make_...
2019-10-26 17:02:14
207
原创 191024省选测试题解
T1：有n个不相交矩形障碍，求从原点走到某个目标点的最短路，目标点在x轴上显然矩形的右端点是没用的，我们保留左边即可显然不会往左走，dp一下是n2n^2n2的，用扫描线优化一下即可#include<bits/stdc++.h>#define pb push_back#define ll long long using namespace std;inline int re...
2019-10-24 16:29:35
177
原创 [LOJ2339][虚树][边分治][树形DP]WC2018：通道
LOJ233944pts暴力就不用讲了两棵树的做法似乎是个套路？先拆距离变成dep1[x]+dep1[y]−2∗dep1[lca1(x,y)]+dis2(x,y)dep1[x]+dep1[y]-2*dep1[lca1(x,y)]+dis2(x,y)dep1[x]+dep1[y]−2∗dep1[lca1(x,y)]+dis2(x,y)，然后就可以在第一棵树上从下到上枚举lca，消去lca的影响，...
2019-10-21 17:56:01
159
原创 191015NOI模拟总结
T1：CF643D解法：是一道模拟题。。。我们可以用一个set维护全局最大值，然后再用n个set维护所有当前点的ans，用这n个set更新全局set即可完成3操作考虑修改的影响，会影响到它和其原来父亲，并且父亲的E会改变从而导致父亲的父亲的答案也改变，新的父亲也是一样的，更新全局答案时注意处理三个点的环的情况，然后就是模拟了Code：#include<bits/stdc++.h&g...
2019-10-16 10:21:20
188
原创 191012CSP-J模拟题解
T2算答案加成了矩阵的一行然后调了我2个小时T1：求图的仅在一个简单环中的边显然点双Code：#include<bits/stdc++.h>#define pb push_back#define fi first#define se secondusing namespace std;inline int read(){ int res=0,f=1;char ch...
2019-10-12 13:51:04
1285
原创 191007CSP-S模拟题解
博主来口胡联赛组巨佬们的考试题辣T1：给一个序列，保证只有两个数出现了奇数次，求出这两个数数据范围只允许O(n)O(n)O(n)显然考虑出现奇数次的数字和出现偶数次的有什么不同，当然是全部异或起来后出现偶数次的全没了所以先全部异或起来得到两个所求数的异或值，这个异或值某一位为1表示某个数这一位为1而另一个数这一位为0，那就把这一位为1的数再全部异或一遍就完了Code：太傻逼不想写T2：...
2019-10-11 20:13:46
355
原创 191009NOI模拟题解
T1:给你一个长为n的数组，下标从0开始，每个数都是0…9，你需要回答Q个询问：给出li,ri，求区间[li,ri]中所有数的乘积模10的结果。小A轻松地解决了这道题，现在她想知道：给出n,Q,li,ri，以及每组询问的答案ansi，求原数组有多少种不同的情况？n,q≤100n,q\le100n,q≤100先用中国剩余定理转化为%2和%5的情况，然后分别统计，最后乘起来考虑一个点为0的情...
2019-10-10 11:08:24
583
原创 [CF1137F][LCT][树状数组]Matches Are Not a Child's Play
CF1137FLCT神题。。。首先三操作显然就是两个二操作然后我们考虑一操作会造成什么影响我们将权值最大的那个点看作根，一个点进行一操作后，他到根节点这条路径就会最后被删除，其他的点删除顺序不变，这很显然考虑这段链，一定是从原来的最大值那一头删到当前最大值这一头，那我们就把新的最大值作为根，这就很像LCT了所以我们把会从下到上按顺序删除的链看成实链，那么不同链之间的影响只与链上最大值有...
2019-10-06 17:07:58
190
原创 191005CSP模拟题解
T1：对于每条边，求删了这条边原图能否成为二分图，点边规模2e6解法：首先判掉无奇环和一个奇环的情况一条边合法当且仅当其属于所有奇环的交集且不属于任何一个偶环（会构成新的奇环）那就弄个dfs树，对于每条返祖边树上差分一下，奇环+1偶环-1，最后看差分值是否为奇环个数即可Code：#include<bits/stdc++.h>using namespace std;inli...
2019-10-05 17:16:26
169
原创 191003NOI模拟题解
T1：题目大意：给你一张图，每条边有边权，要求保留边权和尽量大的边使得每个点至多有一条出边和至多一条入边，点数200，边数5000解法：显然的二分图最小费用流，可行流即可不需要最大流Code：#include<bits/stdc++.h>#define ll long longusing namespace std;inline int read(){ int res=...
2019-10-05 17:05:53
310
原创 190930模拟题解
T1：你在跟朋友玩一个记忆游戏。朋友首先给你看了n个长度相同的串，然后从中等概率随机选择了一个串。每一轮你可以询问一个位置上的正确字符，如果能够凭借已有的信息确定出朋友所选的串，那么游戏就结束了，你的成绩就是所用的轮数。由于你实在太笨，不会任何策略，因此你采用一种方法，每次等概率随机询问一个未询问过的位置的字符。现在你想知道，在这种情况下，你猜出结果所需的期望次数。状压DP，预处理一个f...
2019-10-02 17:21:21
154
原创 [LOJ2197][线段树][凸包][三分]SDOI2014：向量集
LOJ2197和UOJ191unknown类似我们知道点积等于一个向量的长度乘以另一个向量在这个向量上的投影的长度那么如果我们把范围限制在180°内，则这个函数是单峰的，那就可以线段树维护上下凸壳，查找的时候三分但是直接维护会T飞，因为需要合并，复杂度很高换一种方法，我们是从左到右依次加入的，那就意味着如果我们要查询线段树的一个节点的话，那这个节点对应的区间一定被填满了，所以我们可以在填...
2019-09-29 23:28:19
163
原创 [BZOJ3203][凸包][三分]SDOI2013：保护出题人
OJ挂，链自找由题目的特性可知，我们可以把血量求前缀和，然后视为同时攻击则每次的yiy_iyi可以表示为sum[i]−sum[j−1]x[i]−(i−j)∗d(1≤j≤i−1)\frac{sum[i]-sum[j-1]}{x[i]-(i-j)*d}(1\le j\le i-1)x[i]−(i−j)∗dsum[i]−sum[j−1](1≤j≤i−1)直接求就是n2n^2n2考虑优化，发现...
2019-09-29 22:11:19
109
原创 [BZOJ1074][计算几何][搜索]SCOI2017：折纸
OJ挂，链自找一直在想正做的做法，然后当场去世反着做就好做多了，对于每个询问点，我们找出其被翻回去后处于哪个位置，然后从这两个点递归下去继续找，需要及时判断合法性，即一个点是否处于当前直线的右侧，如果在显然不行，因为右边的会被往左边翻，所以这个位置实际上最后是空的点的对称就利用直线垂直：k1∗k2=−1k1*k2=-1k1∗k2=−1搞即可Code：#include<bits/st...
2019-09-29 22:01:59
113
原创 [BZOJ3199][半平面交][最短路]SDOI2013：逃考
BZOJ挂，链自找很容易发现两个点连线的中垂线就是划分两个点控制区域的直线那对于每个点处理处它与其他所有点的连线的中垂线，加上边界四条线做半平面交即可知道这个点的控制区域然后这个点与所有剩下的直线所代表的点连边，跑最短路即可Code：#include<bits/stdc++.h>#define eps 1e-9#define db double#define mp ma...
2019-09-29 21:56:57
86
原创 [LOJ2008][半平面交]SCOI2015：小凸想跑步
LOJ2008把每个三角形的面积用叉积表示，每个三角形和0,1,p0,1,p0,1,p组成的三角形组合可以列出n−1n-1n−1个不等式，然后把不等式转成直线做半平面交即可Code：#include<bits/stdc++.h>#define db long doubleusing namespace std;inline int read(){ int res=0,f=...
2019-09-29 21:52:52
116
原创 [LOJ2056][CDQ][树状数组]TJOI / HEOI2016：序列
LOJ2056设一个位置的数的最大可能值为mxmxmx，最小为mnmnmn，原本值为valvalvalDP时显然需要满足以下条件：j<ij<ij<ivalj<mnival_j<mn_ivalj<mnimxj<valimx_j<val_imxj<vali显然三维偏序，CDQ+树状数组Code：#include<bit...
2019-09-27 22:00:30
101
原创 [BZOJ3730][点分树]震波
链接自己找，BZOJ还没开也很显然是点分树维护，对每个点开两个树状数组，维护点分树上子树之和，然后修改询问仍然暴力爬树，询问也是用两个树状数组作差消掉当前子树影响Code：#include<bits/stdc++.h>using namespace std;inline int read(){ int res=0,f=1;char ch=getchar(); while(...
2019-09-26 22:06:58
117
原创 [LOJ2135][点分树]ZJOI2015：幻想乡战略游戏
LOJ2135显然点分树维护，维护一个点在点分树上的子树权值和，子树到它的代价和，子树到它父亲的代价和，用加减消掉询问时当前子树的影响，这些都是点分树的套路修改暴力爬树然后询问先从点分树根节点开始，算一次根节点的答案，然后和各个儿子的答案比较一下，如果某个儿子比它优，就进这个儿子找这样询问的正确性：如果这个儿子里面没有答案，那这个儿子肯定比根节点差如果这个儿子里面有答案，那这个儿子肯定比...
2019-09-26 22:02:36
118
原创 [BZOJ1146][树套树][树链剖分]CTSC2008：网络管理
链接自己找，BZOJ还没开题意：求树上路径第k大，单点修改，可离线考虑树剖维护，内层主席树外层套个树状数组就完了（时空和代码长度都全方位被整体二分吊打）也可以整体二分Code：#include<bits/stdc++.h>using namespace std;inline int read(){ int res=0,f=1;char ch=getchar(); wh...
2019-09-26 21:52:58
119
原创 [LOJ2174][主席树]FJOI2016：神秘数
LOJ2174假设当前的神秘数为xxx，我们加入一个数yyy后新的神秘数是什么？显然如果y>xy\gt xy>x，则xxx依然是神秘数否则我们本来能够表示出[1,x−1][1,x-1][1,x−1]的数，则现在我们可以表示出[1,x−1+y][1,x-1+y][1,x−1+y]的数，那新的神秘数就是x+yx+yx+y我们首先假设当前神秘数为ggg，初始g=1g=1g=1，然后每...
2019-09-26 21:48:00
197
原创 [LOJ2011][主席树]SCOI2015：情报传递
LOJ2011经过分析，设某个点的起始时间为ttt，当前时间为iii，则对答案有贡献的点需满足i−t>Ci-t>Ci−t>C，即i−C>ti-C>ti−C>t当然把简单路径拆成到根节点的四条路径，那么修改一个点会对它子树产生影响，就可以按当前时间建主席树搞一搞了Code：#include<bits/stdc++.h>using namesp...
2019-09-25 22:01:02
107
原创 [LOJ3021][树状数组][扫描线]CQOI2017：老C的任务
LOJ3021这扫描线敢不敢再水一点好像没法更水了Code：#include<bits/stdc++.h>#define ll long longusing namespace std;inline ll read(){ ll res=0,f=1;char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') f=-f;ch=g...
2019-09-25 21:54:57
96
原创 [BZOJ1009][KMP][矩阵快速幂]HNOI2008：GT考试
BZOJ1009建出KMP自动机，要求走n步不能到达m点的方案数，矩阵快速幂即可Code：#include<bits/stdc++.h>using namespace std;inline int read(){ int res=0,f=1;char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') f=-f;ch=getcha...
2019-09-23 13:01:04
78
原创 190921CSP-S模拟题解
T1：lcm求给定的数集的任意非空子集的lcm之和数集大小2000，元素大小200要求lcm，那显然唯一分解然后很容易发现200以内的所有素数中，在某个合数的分解中对应幂次大于1的只有200\sqrt{200}200级别，即2,3,5,7,11,132,3,5,7,11,132,3,5,7,11,13所以我们可以把这些素数出现的状态压缩一下，然后每个合数除掉这些素数之后剩下的一定只剩下...
2019-09-23 09:00:59
275
原创 [BZOJ3659][矩阵树定理][Best定理]Which Dreamed It
BZOJ3659这个Best定理的名字似乎是四个人的姓的首字母拼起来的我还以为是最好的定理的意思前置技能：矩阵树定理（Matrix-tree）无向图的生成树个数即基尔霍夫矩阵的行列式有向图的生成树有两种：外向的和内向的外向树即所有边从根节点指出去内向树即所有边指向根节点外向生成树的基尔霍夫矩阵为入度矩阵-度数矩阵内向生成树的基尔霍夫矩阵为出度矩阵-度数矩阵有向生成树个数为其基尔...
2019-09-19 18:00:32
306
原创 [LOJ3083][单调栈]GXOI/GZOI2019：与或和
LOJ3083很显然是拆位那么对于and，就是统计这个01矩阵中的全1子矩阵个数对于or，就是统计这个01矩阵中的全0子矩阵个数，再用全集减去它统计01矩阵的全1子矩阵个数就直接上单调栈即可大致做法：记录矩阵内每一个点上方的连续1有多少个（包括自身）扫描每一行，求出以每个点为右下角的矩阵的个数，可以用单调栈弹掉不合法的答案Code：#include<bits/stdc++....
2019-09-19 13:02:43
110
原创 20190918CSP-S模拟题解
T1：一张n个点的无向图，求出经过每个点的最小环n≤300n\le300n≤300 m≤40000m\le40000m≤40000暴力是拆边然后跑dij，正解就是拆点可以枚举每个点，做一个最短路树，然后枚举非树边更新答案就过了。。。std是分治Floyd，就在每次分治的时候暴力向Floyd矩阵里插...
2019-09-19 08:17:25
530
原创 [最短路][位运算优化建图]walk
无来源对于所有数据，n≤2e5,m≤3e5,1≤vali<220n≤2e5,m≤3e5,1≤val_i<2^{20}n≤2e5,m≤3e5,1≤vali<220位运算优化建图是我瞎取的名字考虑新建点来表示val，每个点向val连边权为1的边，每个val向对应点连边权为0的边然后重点是考虑val之间的连边：每个val向二进制位下1的个数比自己少一个的点连边权为0的边，这...
2019-09-17 22:08:43
106
原创 [LOJ3096][数学]SNOI2019：数论
LOJ3096实际上是要求一个方程ai+Pk1=bj+Qk2a_i+Pk_1=b_j+Qk_2ai+Pk1=bj+Qk2，可以发现不断增加p的时候左边的取值modQmodQmodQ会成一个环，那就把这个环搞出来，把对应的所有b标上去，然后枚举a，先算一下最多走多少步，然后求个环上前缀和就完了Code：#include<bits/stdc++.h>#define pb p...
2019-09-17 22:02:05
127
原创 [LOJ3098][矩阵快速幂]SNOI2019：纸牌
LOJ3098这种数据范围不是推式子然后lucas就是矩阵快速幂了在一副王牌中，任意连续三个数构成的顺子的出现次数显然只用考虑0，1，2，否则我们直接弄三个刻子效果是一样的考虑转移，先考虑非初始牌的转移，设当前为第iii位，则我们转移到第i+1i+1i+1需要知道第i−1i-1i−1位和第iii位的信息，即以这两个位开头的顺子的个数，那么我们可以用一个3∗33*33∗3的状态表示这个东西，然...
2019-09-17 21:54:08
182
原创 [luogu4389][生成函数][NTT]付公主的背包
luogu4389考虑OGF，ans=[xn]∏i=1n(11−xi)aians=[x^n]\prod_{i=1}^n(\frac{1}{1-x^i})^{a_i}ans=[xn]∏i=1n(1−xi1)ai，其中aia_iai表示大小为iii的物品的个数看到这种一般想到用exp：∏i=1n(11−xi)ai\prod_{i=1}^n(\frac{1}{1-x^i})^{a_i}i=...
2019-09-17 21:45:27
162
原创 [BZOJ4888][树状数组]TJOI2017：异或和
BZOJ4888可以枚举二进制每一位，看看哪些对它有贡献先弄成前缀和，然后增量构造如果当前前缀和的当前这一位为1，那么要满足它减去之前的一个前缀和之后这一位仍然为1，就是要求减去的那个前缀和的小于枚举的这一位的部分小于当前前缀和的这一部分，这样减掉才不会退位如果当前这一位为0，那就是要大于才能退位退到这一位上来分别用树状数组维护即可Code：#include<bits/stdc...
2019-09-16 23:57:36
182
原创 [BZOJ4890][树形DP]TJOI2017：城市
BZOJ4890看到题还以为要二分，结果连二分都不用枚举断边，计算两个子树直径，更新答案，没了Code：#include<bits/stdc++.h>using namespace std;inline int read(){ int res=0,f=1;char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') ...
2019-09-16 23:51:48
104
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人