Ren_Ivan-CSDN博客

原创通知

鉴于csdn不能加密博文，现暂时转至cnblogs www.cnblogs.com/Ren-Ivan 然而依旧没人看。

2017-10-26 07:53:52 539 1

原创 10.2晚模拟继续

100+100+80=280 rank 3 神tm卡常 T1:打表找规律，T2:简单的树规 T3:调了好久，结果蜜汁被卡常，文艺平衡树+乱搞 T1#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<cmath>using namespace std;#define mod 1

2017-10-03 07:26:30 634

原创 10.2 考试

100*3=300 rank 1 好久没进前三了，被wq和std压了这么久终于翻身一天了，然而总分还差30(无奈前几天挂的惨) T1，每一个点向两边拓展至(x-w,x+w)的线段，找最多条不相交的线段就好了。 T2裸线段树 T3，发现答案是连续的一段，二分左右端点暴力计算，又发现对于每个数的答案就是它每一个是一的位那一行的杨辉三角摞起来。 T1#include<cstdio>#inclu

2017-10-02 13:08:05 449 1

原创 10.1 国庆考试

100+10+20=130 rank 7 考试时T1先推了30+30的暴力高精，后来瞎代式子，发现答案就是Cmn+m−Cm−1n+mC_{n+m}^{m}-C_{n+m}^{m-1} T2情况太多了，脑子特别乱，照着3个样例调过了3个样例就WA了。。正解又是欧拉图上各种乱搞。 T3没想到状压深度，20分暴力，正解树上的状压dp T1#include<cstdio>#include<cs

2017-10-02 06:27:14 432

原创爆零专场

总分 60+15+0=75 rank5 T1想主席树套树状数组，死活调不出来，后来发现内存炸了交的30暴力+30静态主席树 T2暴力O(n4)O(n^4)加减枝 15 T3 真心不会目前只改了T1 正解：因为异或了opt，所以反解答案。。。#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>

2017-10-01 21:47:35 522

原创 bzoj 4501 旅行

01分数规划+最大权闭合子图倒拓扑序处理每个节点 f[x]=∑f[v]n+1f[x]=\frac{\sum{f[v]}}{n}+1 二分答案 val 只需要判断是否存在 ∑f[v]+1−val>0\sum{f[v]+1-val}>0即可点权下放给边，限制{x,y}即为若边x存在，则边y存在建图，跑网络流即可#include<cstdio>#include<cstring>#in

2017-09-26 19:52:56 409

原创 bzoj 4556 字符串

后缀数组，暴力硬跑贼快#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<cmath>#define MAXN 100005using namespace std;int buc[MAXN],wa[MAXN],wb[MAXN];int r[MAXN],sa[MAXN],ran

2017-09-26 17:48:08 296

原创 9.25+9.27 联考

第一次和某二中学联考，达哥出题，翻车十分惨烈考试时上来10分钟搞定T1，看T2，没思路，二维莫队？好像和图论有点关系，有点乱，先弃坑，看T3，发现只需要处理前a个，后面都是等差数列，但是需要记录一大堆东西，手玩了一下，发现有戏，搞出来，发现只能过前两个点，后面的起点都不在a内，特判，乱搞了好长时间，最后5个样例都过了，但是时间只剩下30min左右了，觉得可能还有别的情况，但弃了，搞T2，把20分

2017-09-26 09:42:12 310

原创 9.22

100+30+70=200 T1水题，单调队列#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>#include<cmath>#define N 2005using namespace std;int n,m,ans,a[N],f[N][N],l[N],r[N],q[N];int main()

2017-09-26 09:28:32 285

原创普通平衡树

SPLAY#include<cstdio>#include<iostream>#include<cstring>#define N 1000005using namespace std;int ch[N][2],f[N],size[N],cnt[N],key[N],root,sz;inline void clear(int x){ ch[x][0]=ch[x][1]=f[x]=siz

2017-09-24 14:48:30 314

原创 bzoj 3126 单调队列优化dp

能转移的最左是其左边完整区间的最右左端点，最右是能覆盖它的最左左端点-1#pragma GCC optimize ("O3")#include#include#include#include#include#define N 200005using namespace std;int l[N],r[N],n,m,f[N],q[N];int read(){ int a=0;c

2017-09-24 07:48:54 357

原创 9.20...

40+0+30=70 rank10 这都前十…… T1，考试时就想斜率dp了，结果推出来的式子没法搞，又推了一些没用的性质，最后放弃了打了40分暴力。正解根号算法，转移时包含的颜色最多有n√\sqrt{n}个，记录每个位置的上一个和下一个相同颜色的位置，转移时，pos[j]表示pos[j]+1~i中有不超过j种颜色，当i++时，要巧妙的转移(详见代码)，总复杂度O(nn√)O(n\sqrt{n

2017-09-21 21:26:29 239

原创 9.18 题解？

100+100+10=210 rank 1 T1，醉了，考试时对拍平均1分钟一个错，真爽……暴力枚举约数判断就好了，从根dfs，当∑size[v]modD\sum{size[v] mod D }+1>D时 return;#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<cmath>

2017-09-19 13:38:59 427

原创 [SCOI2005]栅栏二分+dfs

这个题真的是太nb了，各种骚二分答案，肯定要减最小的mid个，从大往小搜每一个木板，从大往小枚举所用的木材当当前木材比最短的木板还短，就扔到垃圾堆里，并记录waste，当 waste+sum>tot 时，return#include#include#include#include#include#define N 2005using namespace std;int n

2017-09-17 15:21:36 333

原创守规矩题解

上课闲的没事想到的题，挺水的。。。只需要计算出每个数被除了多少次，就是优先级的最长下降子序列#include#include#include#include#include#define N 5000005using namespace std;int n,a[N],q[N],top,ans[N],t;int read(){ int a=0;char ch=getchar

2017-09-17 08:32:54 488 1

原创 9.10+9.14+9.16

9.10 40+0+60=100 rank 16 T1 裸的exgcd，然而不会求解的个数了，用解析几何搞的，考试时一堆问题都没调出来。。。 T2树形dp，f[i][j]表示i这颗子树里选j个黑点的最大收益，像背包一样转移就好了，考试打的暴力，还tm翻车了(0x7f) T3神题，至今没改，留个坑以后填吧。。。 T1#include<cstdio>#include<cstring>#in

2017-09-17 07:06:41 325 1

原创 9.5题解

总分201，rank3 T2图上的简单题，但调了好久，T3暴力分很足，st表加减枝91，T1嘛，卡读题啊，QAQ…… 先说坑爹的T1: 先是没看见每种喜悦值只能获得一次，改的时候又发现一次只可以买一个，233 状压每个状态表示每种物品是否被买，转移时可能转移到自己或新的状态，导一下式子倒推就好了。#include<cstdio>#include<cstring>#include<iost

2017-09-09 10:43:49 293

原创 9.2题解

总分122，rank 10. T1 找硬币 bzoj3233 考试时打的暴力，深搜，一点剪枝都没有，22分。后来还是用深搜改的。对于每一层，枚举素数p，每一个兔子可以表示为ki*p+mi的形式，因为后面的硬币一定都是p的倍数，所以mi部分一定要用1填，∑mi\sum{mi} 就是这一层一定要用的，当这个数加上之前的sum>当前最优解时continue;注意，当当前数列中的max < p时

2017-09-03 21:50:07 297

原创 8.27 题解

先%一发达哥 T1,其实不难,就是一个简单的dp+矩阵快速幂加个原根优化,其实是模意义之前没做过题,有点懵,一开始思路也光想数学了,就gg了…… 模意义下所有运算都和正常运算一样,只是除变成了乘逆元!! 定义状态数组f[i][j]表示第i步转移后模数为j的概率,矩阵乘优化,可得80分,正解是把每个数转化为p原根的i次方,别的都一样,会发现这样出来的是循环矩阵,复杂度降为O(logm*mod^2

2017-08-29 16:51:52 377

原创 8.27考试小结

好久不考试了...一开始没有考试的感觉，一直在想第一题，无果，打了个不知道是什么的暴力大概还剩不到两个小时了，发现T2,T3都没看。。洗了把脸，清醒了一下。看T2，想了一会，感觉60分应该可以，打了个dfs+高斯消元，又过了1h。急忙去看第三题，觉得应该是卡特兰枢加一些奇奇怪怪的东西，但卡特兰数不太记得了，觉得4种情况也来不及推了，最后20min就滚动数组打了65分暴力.

2017-08-28 16:29:54 415

原创 bzoj2326 [HNOI2011]数学作业

矩阵乘，按位搞两个矩阵，分别为 ans00i00100\begin{matrix} ans & i & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{matrix} 10k11011001\begin{matrix} 10^k &0 & 0 \\ 1 & 1 & 0 \

2017-08-26 12:07:25 254

原创 [Poi2012]Festival 差分约束+tarjan

差分约束建图，发现要在每个联通块里求最长路，600，直接O(n3) floyed#include#include#include#include#include#define N 650#define M 100050using namespace std;int g[N][N],n,m1,m2,f[N],ans;int e=1,head[N];struct edge{

2017-08-24 16:47:56 303

原创 [Usaco2005 dec]Layout 排队布局差分约束

填坑… 差分约束一般是搞一个不等式组，求xn-x1的最大最小值什么的，求最大值就转化成xa<=xb+w这样的，然后建图跑最短路(这才是最终约束的)，举个例子 x1<=x0+2x2<=x0+7x3<=x0+8x2<=x1+3x3<=x2+2 \begin{matrix} x1<=x0+2 \\ x2<=x0+7 \\ x3<=x0+8

2017-08-23 15:34:01 499

原创 bzoj3631[JLOI2014 松鼠的新家倍增lca+差分

裸的树上差分+倍增lca每次从起点到终点左闭右开，这就有一个小技巧，要找到右端点向左端点走的第一步，然后差分就好了#include#include#include#include#include#define N 300005using namespace std;int fa[N][20],dep[N],f[N],g[N],n,l[N];int e=1,head[N];

2017-08-22 16:37:45 325

原创 [HNOI2015]菜肴制作拓扑序

逆序最大字典序拓扑序反向建边，逆序字典序最大。。#include#include#include#include#include#include#define N 1000005using namespace std;priority_queue q;int e=1,head[N],T,n,m,in[N],now,ans[N];struct edge{int v,nex

2017-08-21 17:12:59 330

原创 [POI2007]洪水pow bfs

发现：只在所有自己的城市建水泵一定是最优解。所以对自己的城市按高度排序，该城市不用建的前提是从他出发经过一条高度都小于等于他的路径能到达一个已经修建水泵的sort+bfs......#include#include#include#include#include#define N 1005using namespace std;int dx[4]={-1,1,0,0},d

2017-08-21 15:59:17 317

原创 bzoj1059 [ZJOI2007]矩阵游戏

二分图匹配。发现：无论怎么交换，同一行的还是同一行，同一列的还是同一列的。所以直接建图，跑匈牙利就好了#include#include#include#include#include#define N 205using namespace std;int pp[N],n,T,g[N][N],cnt;bool bo[N];bool find(int x){ fo

2017-08-20 19:36:38 307

原创 bzoj2730 [HNOI2012] 矿场搭建

tarjan跑出来所有的割点dfs搞每一个点双和几个割点相连，0个就要建两个，因为建一个的话，那个地方没了就死了，1个就要建一个，因为如果割点断了，需要内部供给，2个就不用建，任意一个断都可以从另一边过#include#include#include#include#include#define N 1500using namespace std;int n,m,cnt,nu

2017-08-20 18:08:30 364

原创 NOIP2013华容道大爆搜

预处理出每个点周围四个点互相到达的最短路，再在整个图上跑SPFA，要记录路径#include#include#include#include#include#include#define N 32using namespace std;int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};int n,m,g[N][N],dis[N][N][5][5],f

2017-08-20 17:43:59 344

原创便加权并查集

题目发现每一行，列的差都相等 ⎡⎣⎢124235346⎤⎦⎥ \begin{bmatrix} 1 & 2&3 \\ 2&3 & 4 \\ 4&5&6\\\end{bmatrix} 行 1-2=2-3=3-4 2-4=3-5=4-6 列 1-2=2-3=4-5 2-3=3-4=5-6 再发现了这个神奇的规律后，就可以用带权并查集维护了。#include <cstdio>#inc

2017-08-15 20:59:56 528

原创 bzoj 4565 状压区间dp

我还以为我状压很好。。。。。。噗！！！果然我区间很差。。。 f[i][j][s]表示i~j段，合并后的状态为s所得的最大收益枚举i,j,k,s. f[i][j][s<<1]=max(f[i][j][s<<1],f[i][k−1][s]+f[k][j][0]) f[i][j][s<<1|1]=max(f[i][j][s<<1|1],f[i][k−1][s]+f[k][j][1])

2017-08-15 17:32:51 381

原创 bzoj 2242 [SDOI2011]计算器快速幂+扩展欧几里得+BSGS

1：快速幂 2：exgcd 3：exbsgs，题里说是素数，但我打的普通bsgs就wa，exbsgs就A了......(map就是慢).....#include#include#include#include#include#include#define LL long longusing namespace std;map pp;map bo;LL a,b,c;

2017-08-15 06:30:22 481

原创 poj 3243 扩展BSGS

每次把gcd(a,c)提到前面，知道a,c互质，然后就是普通BSGS了#include#include#include#include#include#define LL long longusing namespace std;struct hashtable{ static const int N=577399; int tot,hash[N+10],key[N+5

2017-08-14 21:18:29 430

原创 bzoj 3239 poj 2417 BSGS

BSGS算法，预处理出ϕ(c)−−−−√\sqrt{\phi(c)}内的a的幂，每次再一块一块的往上找，转移时将b乘上逆元，哈希表里O(1)查询即可#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<cmath>#include<map>#define LL long longlo

2017-08-14 10:42:52 269

原创 51nod 1135 原根就是原根...

%%% dalao Orz ,筛素数到sqrt(n),分解ϕ(p)\phi(p)，依次枚举判断就好了#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<cmath>#define N 100000#define LL long longusing namespace std;LL

2017-08-14 08:44:13 341

原创 bzoj 2005 能量采集莫比乌斯反演

我们要求的是∑ni=1∑mj=1(2×gcd(i,j)−1)\sum_{i=1}^{n}\sum_{j=1}^{m}{(2\times gcd(i,j)-1)} 化简得2×∑ni=1∑mj=1gcd(i,j)−n×m2\times\sum_{i=1}^{n}\sum_{j=1}^{m}{gcd(i,j)}-n\times m 所以我们现在只需要求出∑ni=1∑mj=1gcd(i,j)\sum_{

2017-08-13 15:15:04 308

原创约会倍增lca

题意：一棵树，给两个点，求树上有多少点到他俩距离相等倍增lca，分好多情况讨论。。#include#include#include#include#include#define N 100500using namespace std;int e=1,head[N];struct edge{ int u,v,next;}ed[2*N];void add(int u

2017-08-13 13:59:50 279

原创 bzoj 2186 [Sdoi2008]沙拉公主的困惑欧拉函数

n>=m,所以就变成了求ϕ(m!)∗n!/m!\phi(m!)*n!/m! 而ϕ(m!)=m!∗(p−1)/p......\phi(m!)=m!*(p-1)/p......p为m!的素因子,即为m内的所有素数,问题就转化为了求n!∗(p−1)/p......n!*(p-1)/p...... 只需要预处理出素数，阶乘，逆元即可#include<cstdio>#include<cstring>#

2017-08-13 07:21:50 221

原创 bzoj 2822 [AHOI2012]树屋阶梯卡特兰数

因为规定n层的阶梯只能用n块木板那么就需要考虑，多出来的一块木板往哪里放考虑往直角处放置新的木板不管怎样，只有多的木板一直扩展到斜边表面，才会是合法的新状态，发现，这样之后，整个n层阶梯就被分成了i层和n-1-i层的阶梯，即 f(n)=∑i=0n−1f(i)×f(n−1−i)f(n)=\sum_{i=0}^{n-1}{f(i)\times f(n-1-i)} 就是卡特兰数！！！，需要

2017-08-12 20:38:49 357

原创 bzoj 1485 [HNOI2009]有趣的数列卡特兰数

把排好序的序列看成一对对括号，要把他们往原数列里塞，所以就是括号序合法方案数即为卡特兰数 f(n)=Cn2nn+1f(n)=\frac{C_{2n}^n}{n+1} 求的时候为避免除法，可以O(n)计算每个素数出现次数，最后乘起来，打完之后发现其实根本不用快速幂……#include<cstdio>#include<cstring>#include<iostream>#include<a

2017-08-12 20:31:08 282

空空如也

空空如也