yfzcsc-CSDN博客

原创 NOI2018 游记

NOI2018 游记Day -1听说要出发了，所以用十几分钟扔了一些东西到行李箱里，然后就到机场在机场打了半小时的summer pockets，没想到这个东西竟然耗了40%的电。。。晚上在网吧越坐越觉得困倦，于是回到寝室洗洗就睡了Day 0以为笔试什么时候都可以去，于是就在床上咕到9点钟。结果9点07分下去时发现蔺老一副惊慌的样子，这才发现笔试好像早就开始了于是...

2018-07-23 11:40:11 4493 1

原创 Codeforces 493 Div1题解

Problem A. 发现可以用xxx次翻转操作替换xxx次反转操作。做完了。 Problem B. 发现n≥50n≥50n\geq 50时变成等差数列。（实际上是n≥12n≥12n\geq 12）所以小范围大暴力，然后O(1)O(1)O(1)计算。 Problem C. 发现答案的式子为： −2×∑i=1n(ni)3(n−i)n+i(−1)i−∑i=1n∑j=1n(ni)(nj)...

2018-07-02 21:51:15 676

好吧，老师让我们vp了一把ZJOI2018爽爽。。。结果5h用了4h做t2，最后没时间推t1了，110滚粗（现场赛有debuff分数肯定比这个低），然后那个冒金光的wxh 2h秒了t2，最后得分190ZJOI2018 Problem B.历史想了半天这个序列应该有啥性质，后来才发现应该对每个点考虑。这样就简单多了，对于每个点，答案就是∑sum[u]−1−max(0,mx[u]−1−(sum[u]−m

2018-03-24 20:41:03 1464 2

原创 WXHRound#13 场外被虐记

WXH太神了！T1还是找规律找出来的。。。T_T Problem C.多项式求∑mi=1xi≤S,∀1≤i≤nxi≤T,∀xi≥0\sum_{i=1}^m x_i \leq S,\forall_{1\leq i \leq n} x_i\leq T,\forall x_i\geq 0的解数T,n,m≤109,n×T≤S,m−n≤1000T,n,m\leq 10^9,n\times T\leq S,m

2018-03-08 21:15:40 901

原创 bzoj4314 倍数？倍数！加强版

问题：求[1,n][1,n]中选mm个互不相同的数使得他们的和膜nn等于kk的方案数Joker\texttt{Joker}太神了！题解：如果没有mm的限制，实际上相当于求∏ni=1(1+xi)\prod_{i=1}^n (1+x^i)所有次数是膜nn为kk的项的系数和考虑用单位根来计算这个可以发现，设F(x)=∏ni=1(1+xi)F(x)=\prod_{i=1}^n (1+x^i)，则答案为

2018-03-08 21:00:40 668 1

原创 Atcoder Grand Contest 021 题解

Problem A. （此处省略）反正怎么搞都行了。。。Problem B. 对于每个点，枚举其他点，那么选的点一定是在垂直平分线的一侧。由于R 特别大，所以可以把这个垂直平分线移到这个点上，就相当于一堆可行极角区间求交也可以O(nlogn)O(nlogn)，大概是把凸包搞出来然后答案就出来了。。。#include<bits/stdc++.h>#define maxn 110using name

2018-02-26 18:12:54 515

原创 WC2018游记

WC游记前几天的课，就觉得猫锟和杜教的课学的挺多的，杜教的Surreal Number看来又要出一堆毒瘤题了吉司机的PA介绍（PA2017全题解）太可怕了，快跑猫的那个矩阵还是挺好玩的WC考试开局先看3题，发现好像都挺可做然后先做t2,刚了2h+写了个玄学O(n^2*2^n*X)(X然后打t3,t1

2018-02-09 00:02:44 1386 1

原创 UNR#2 梦中的题面 HDU6056

这题口胡起来真简单。。。先来考虑∑mi=1xi≤n,xi≥0\sum_{i=1}^{m} x_i\leq n,x_i\geq 0的整数{xi}\{x_i\}个数这可以用插板法证明是(n+mm)n+m \choose m对于原问题，一个经典做法是容斥，每次枚举一些数一定超过上界，其他数任意。所以答案可以表示为：∑S∈U(−1)|S|(n+c∗|S|−|S|−∑x∈sbx+mm)\sum_{S \i

2018-01-25 21:27:13 709

原创 bzoj5145 [Ynoi2018]未来日记 (多校第4场1013 Yuno and Claris)

2018目标：让nzhtl1477nzhtl1477打通罚抄！这题其实不难写，就是我写完后MLEMLE了。。。对权值和序列都分块，假设nn和值域同阶记b[i][j]b[i][j]表示前ii块，权值在第jj块的有几个记c[i][j]c[i][j]表示前ii块，权值为jj的有几个预处理这个是O(nn√)O(n\sqrt{n})对于查询：直接暴力每块，O(n√)O(\sqrt{n})对于修改：两边的块暴力

2018-01-23 21:34:14 2406

原创 bzoj5144 [Ynoi2018]末日时在做什么？有没有空？可以来拯救吗？

这个死宅题面就不吐槽了。。。2018目标：一定要让nzhtl1477" role="presentation" style="position: relative;">nzhtl1477nzhtl1477nzhtl1477把罚抄打通！这题当然是O(nn+nlogn)" role="presentation" style="position: relative;">O(nn−−√+nlogn

2018-01-23 21:17:45 28490 32

原创 SWERC 2017 H Kabobs

这题就是暴力暴力暴力。。。暴力记每个规则匹配到哪里可以脑补一下为什么正确：1.x60x+2\texttt{1.}x^{\frac{60}{x+2}}在x=4x=4时取到max=1048576max = 10485762.\texttt{2.}一旦失配立刻就跳回去，所以除了x=2x=2，其他时候根本卡不满直接预处理状态及转移然后暴力暴力暴力就过了#include<bits/stdc++.h>#def

2018-01-23 20:49:14 603

原创 BZOJ4081 [WF2014]Skiing

显然可以发现一个dp(i,j)dp(i,j)表示现在在ii，速度是jj，然后答案是什么可以得到这个dpdp是单峰的所以每个答案最多只会有两个可行区间于是用dp(i,j)dp(i,j)表示现在在ii，答案是jj时的可行区间，对于每个点区间总数是O(n)O(n)的。所以现在考虑如何从[L,R]→[L′,R′][L,R]\to [L',R']如果要得到R′R'，显然要先−a-a再aa设时间为tt，初始速度

2018-01-23 20:39:04 373

原创 BZOJ3970 WF2013 G Map Tiles

想象一个框把这个多边形框住，如果知道这个框的左上角的确切位置就能知道答案。可以发现，这个位置有如下4种情况：1.\texttt{1.} 一个顶点在水平线上，一个顶点在竖直线上2.\texttt{2.} 一个顶点在水平线上，一个网格点在多边形边上3.\texttt{3.} 一个顶点在竖直线上，一个网格点在多边形边上4.\texttt{4.} 两个网格点在多边形边上这样理论的点数有O(102n2)O(1

2018-01-16 21:42:19 348

原创高中数学题

Problem A. 已知n∈[0,1018],b,k∈[1,105]n \in [0,10^{18}],b,k\in [1,10^5]，求∑ni=1(ik)bi\sum_{i=1}^n {i \choose k}b^i令Sk=∑ni=1(ik)biS_{k}=\sum_{i=1}^n {i \choose k}b^i则bSk=∑n+1i=2(i−1k)bibS_{k}=\sum_{i=2}^{n

2018-01-02 17:20:38 468

原创记点笔记

NN天前修习了一下多项式，就简要记录一下好了多项式求逆：对于A(x)A(x)，求出一个B(x)B(x)使得A(x)B(x)=1(modA(x)B(x)=1(mod xn)x^n)当n=1n=1时B(x)B(x)就是A(x)A(x)常数项的逆元当n>1n>1时，考虑倍增令A(x)Bk(x)=1(modA(x)B_{k}(x)=1(mod xk)x^k)假设已知B⌈n2⌉B_{\l

2018-01-01 20:47:51 272

原创 CodeFestival 2017 Final 题解

Problem A.(…)#include<bits/stdc++.h>using namespace std;void dfs(int x,string a,string b,string c){ if(x==a.length()){ if(b==c){puts("YES");exit(0);} else return ; } if(a[

2017-11-28 21:27:05 510

原创没听清楚出处的题

T1(好像是TCO 500分题)题意:给你个DAG,要你选择一个拓扑序使得最大子段和最大,n题解:一个拓扑序可以分成三部分,假设把这三部分的点标一个标号(0/1/2),即000001111122222如果a->b有边,那么val[a]S->i(0),i+n->T(0),i->i+n(-val[i])a[i]->b[i](inf),a[i]+n->b[i]+n(i

2017-11-14 08:21:05 289

原创 BZOJ4256 推箱子

首先将空地与空地之间连边，转化为一个无向图。令dp[i][j][0/1/2/3]表示箱子在(i,j),人在箱子旁4个方向中的一个时是否存在方案(和NOIP2013华容道类似)则有2种转移：dp[i][j][k]->dp[i][j][l](从方向k可以不通过(i,j)到方向l) dp[i][j][k]->dp[i'][j'][k](人推动箱子)最后答案就是枚举所有的(i,

2017-11-07 20:57:24 492 1

原创深入理解LCT

以前做LCT基本上都是拿来当模板用,于是总是会出各种错误,乱搞半天才过...随着玄妙的LCT题的增多,总算渐渐理解了LCT的本质,就记一下好了定义一下:fa[x]是splay中的父亲,splay的根的fa是另一颗splay中的一个点,即special father一定要牢记:LCT的splay是按深度为关键字排序,每个splay维护的是一条奇怪的链.access操作:从

2017-08-29 21:31:03 727

原创如何卡SPFA

由于一个校内最短路题数据太水,于是就和司机一起研究如何卡SPFA...卡SPFA的基本思路是弄一个网格图,然后这个网格图行比列小得多,比如10*10000之类的...然后对于竖着的边边权就设多么小,然后横着的边权就设多么大(比如1和rand()%10000+10)还可以在图里随机加一些奇怪的边.然后对于点个数1e5,边个数2e5的有向图,随机或随机+SLF的SPFA就被卡到了入队1

2017-08-27 21:43:50 9940 4

原创关于联通块DP的一些问题(to be continued)

记一下这种奇妙的思路。。。Example I:HDU 6157题意就是给一些点(数轴上),然后你要选出其中的m个点,重新安排它们的顺序,假设为P1...Pm.若令P0=Pm,Pm+1=P1(其实就是在一个环上)那么这个排列的权值就是dist(P1,P2)+...+dist(Pm,P1)+(满足Pi-1Pi+1或Pi-1>Pi思路:dp[i][j][k]表示到第i

2017-08-27 21:32:19 543

原创 WXH♂Round

这几个是YJQ（搬）的题，补补题解好了T1:WXH要表演，每天可以倒立表演或正常表演，倒立表演有Ai的收益，正常有Bi的收益，要求每连续K天必须有P个倒立，Q个正常网络流，相当于必须[Q,K-P]个正常表演，设为[l,r]，先假设都是倒立表演建图如下：每一天建一个点，先给前K天r个,表示只能改r个.i天向i+k天连边,花费Bi-Ai,流量1,表示这一天可以换成正常,但要到i+k天才

2017-08-14 00:27:53 630

原创百度之星2017初赛题解（A）

T1:简单数论，问满足（a0+a1*B+...+an*B^n）=a0+a1+...+an（mod P）的P的个数即满足P|(B-1)a1+(B^2-1)a2+(B^3-1)a3+...,即P|B-1的P的个数sqrt(B-1)暴力枚举B-1约数即可T2:现在给若干个条件，xi=xj或xi≠xj,要你将它们划分成若干组，满足每个组除去最后一个条件时成立，否则不成立。拿并查集将

2017-08-13 21:14:42 1241

原创 WXHRound#14被虐记

T2：无标号有根仙人掌计数，不会倒是搞懂了O(n^2log n)无标号无根树计数先考虑无标号有根树的计数记dp[k]为当我dp到i时用1~i大小的树可以凑出k的方案数则每次就拿dp[i]去更新dp[k],dp[k]+=[t=1...k/i]C(t,t+dp[i]-1)*dp[k-i*t]解释：大小为i的树有dp[i]种，相当于求每个元素∈[1,dp[i]]的长为t的非降序列个数

2017-08-08 21:03:05 695

原创 SW算法？！bzoj3345

SW算法是一种求全局最小割的算法，复杂度为O(|V||E|+|V|^2log|V|)算法类似于Prim算法：每次从1节点开始,初始集合为{1}每个节点的权值为他对于这个集合每个有边直接相连的顶点边权之和,设为dis[u]每次找dis最大的点加入这个集合设最后加的点为s,倒数第二加的点为t,那么dis[t]就是s-t的最小割,更新答案。将t缩到s里面，再来一次（缩就是类似强连

2017-08-06 17:26:23 1246

原创 WXHRound#13被虐记

T1:▸给定一个大小为 n 的有根树。有 Q个询问，每次给出一个 k，求至少用多少条长度不超过 k 的祖先-后代链可以覆盖树上的所有点？▸n, Q 算法一：不同答案只有sqrt(n)种，拿分治弄一下就是O(nsqrt(n)log(n))算法二：（本来已经想到这个东西了的。。。）答案一定小于t+(n-t)/k+1（t为叶子数），故可以O(答案-t)的去算每个k。具体算法如下：

2017-08-03 22:58:05 482

原创 LOJ #6077. 「2017 山东一轮集训 Day7」逆序对

这题（BZOJ2431的加强版）厉害了。。。考虑从小到大加入数，则i就可以让逆序对数+[0,i-1]问题就变为了现在有一个不定方程:x1+..+xn=m,且0考虑用容斥，于是要计算F(i,j)表示[1,n]选i个数和为j的方案数则最终答案为sum{(F(0,j)-F(1,j)+F(2,j)-...)*(和为m-j有n个变量的不定方程解的个数)}(j=0..m)如何计算F

2017-07-17 20:48:07 1418

原创 Codeforces Round#419 (div.1)

Problem B.点击打开链接这个题找规律真是Excited...找出来是这样的:#include#define mod 1000000007#define maxn 200100using namespace std;int fac[maxn],inv[maxn],n,a[maxn],ans;int C(int x,int y){return 1ll*fac[y]*i

2017-06-18 16:56:24 408

原创 [THUWC]菜鸡旅游记

Day 0跟司机等人来到了HangZhou，飞机上打了一会bzoj4605后发现平衡树并不用删除。。。(IQ--)跟司机游览西湖时很不高兴，不过一回到宾馆后两人立即活跃起来，就出了一道Spfa Killer。。。顺便随手把没打的pyoj比赛AK了(要是参加了，wxh010910又会加一波rating)晚上时赶在Water Closet的人来之前去了学军新校区，报名处的小哥好像很高兴

2017-02-19 01:03:31 1048

原创 [FR#12]被虐赛

A题题意：有一个序列a1...an,您需要回答m个询问,每个询问给一个b,使删除尽量少的数使得任意时刻前缀和都>=b(m由于FLOJ跑的太快了，导致没有数据可以卡掉O(mnlogn)我倒是写了一个整体二分求ans[i]表示需要删i个数时的最小b，O(nlogn*30+mlogn)?正解:dp[i][j]表示a1..ai中删j个数时的最小前缀和，询问时二分,O(mlogn+n^2)

2017-02-18 23:19:50 367

原创动态点分治:bzoj 3730,bzoj 1095

总结一下动态点分治的模板。。。对于一个树，把它点分的同时记录每个点的所有父亲（logn个）并记录点距其父亲的距离。具体实现就是dfs的时候fa[x][++dep[x]]=u,dis[x][dep[x]]=d;BZOJ1095:您需要写一个程序支持反转点的颜色，求距离最远的黑色点对的距离。解析：在每个点u存一个堆st记录该子树（分治中的）中点到fa[u]的距离再存一个堆son

2017-02-17 22:57:34 449

转载 bzoj2839

转载自：iamxym http://blog.csdn.net/xym_csdn/article/details/54177123传送门(权限题)题面：一个有N个元素的集合有2^N个不同子集（包含空集），现在要在这2^N个集合中取出若干集合（至少一个），使得它们的交集的元素个数为K，求取法的方案数，答案模1000000007。吐槽一下，不知道为什么网上的题解都没有超

2017-02-05 13:05:47 652

原创 bzoj2594

这题好坑。。。离线然后用LCT倒着维护最大生成树，这个是一眼但是注意：边权是用多加一个点（类似kruskal同构树）来实现，实际上点有m+n个，注意数组不要开小，不然会TLE。。。附数据生成器（但是如果造小数据，每个AC程序输出都可能不一样；大数据没事）#include#includeusing namespace std;typedef pair data;int dx[

2017-01-30 10:41:21 255

原创 bzoj2959

用LCT+并查集缩点，记两个并查集，一个是实际在树中的编号，一个是普通的并查集注意：access中要更新father的编号，修改点值要把点splay上去再修改#include#include#include#include#define maxn 160100using namespace std;int sum[maxn],fa[maxn],tag[maxn],ch[maxn

2017-01-29 10:53:53 432

原创 bzoj2631

不知道为什么我的lct巨慢没加zigzag30004ms，加了zigzag19000ms。。。#include#include#include#include#define mod 51061#define maxn 100100#define inf (1<<30)using namespace std;typedef unsigned int ll;ll sum[ma

2017-01-29 09:48:17 256

原创 bzoj3065

再次写丑的我。。。（刚开始写了个线段树合并+fhq treap完TLE+MLE）换成替罪羊+可持久化线段树合并之后随机数据1s+，不知道vfk搞得什么新闻，bzoj运行37s+刚开始题意读错调了1h+我好菜#include#include#include#include#define Sum(x) ((x)?(x)->sum:0)#define Key(x) ((x)?(

2017-01-24 22:18:10 457

原创 BZOJ4552

O(nlogn),可分裂合并的线段树嗨呀,写死我了#include#include#include#include#include#define Sum(a) ((a)?(a)->sum:0)using namespace std;struct tree{ tree* l,* r; int sum; tree(){l=r=0;sum=0;} v

2017-01-18 20:36:00 401

原创记一次考试(GT Practice #1)

t1,t2 SB题,t3虽然是费用流,但是我不会写,于是就写了一个贪心dinic(神TM)结果比大佬的分还多。。。PS:eps=1e-5,1e-8都可以过,eps=1e-6,1e-7不能过...感到畏惧#include#include#include#include#include#define maxn 2100#define maxm 550000#define yjq

2017-01-17 19:24:40 407

原创 bzoj3451

这个题其实就是求为什么呢?考虑一个点i,枚举每一个j,他对答案贡献的条件是在j作为点分树根即i到j之间上没有点被选为点分树根于是就点分,这个东西就是一个卷积,用fft即可为什么我一写就是第一页...#include#include#include#include#include#define inf (1<<30)#define

2017-01-16 21:26:01 570

WC2019课件

空空如也