3 xgc_woker

尚未进行身份认证

一名热爱看番的OIer, 热爱OI, 热爱二次元, 热爱这个世界。

等级
TA的排名 3w+

THUWC2020题解

我去了P营,但隔壁好像很有意思,于是我也来更题解辣!/se题面来自xht。DAY1T1这道题简单。T2这道题比较难写,我觉得如果是我可能就跳了。大概是一个基环树+LCT,怪恶心的。T3这道题稍微有意思一点,感觉区分度主要在这道题上面。容易发现,你如果求一个最小生成树的话,那么答案就是大于XXX的边加一。那么我们考虑这样子求,按照深度排序,每个点按顺序加进来,往前面连边,这个...

2020-01-07 20:20:02

PKUWC2020游记+题解

有点小难受这次打的。DAY0来到了北京有点小冷。去报到的时候看到了疑似北大集训的讲题现场。晚上颓废。DAY1这一天没有上百,因此我也不说具体分数是多少了。最主要是我的心路历程。开场看了一会儿T1没有思路。看T2很快就会做了,写了一个小时发现过不去样例,非常难受,当时写了一个暴力发现也过不去样例,于是我去求助当时的监考,回答是no response,然而我也很智障,当时只是疯狂...

2019-12-25 15:40:35

子喔解少

高二OIer,想变成现充的宅男

2019-08-13 09:31:58

CSP-S2019游记

最后一次csp了吧。进行了很多思考。

2019-11-17 20:33:09

数学笔记

求极限:关于求00\frac 0000​形:上下两个式子取次数最小的,然后化简。不可搞的一般求泰勒展开,取泰勒展开中最小的项来搞。记一些基本的泰勒展开:一般要能求导才行,所以不是很能求导的东西我不是很会。泰勒展开的主要思想就是希望一阶导在某个位置求的值相同,二阶导在某个位置求的值相同…,nnn阶导在某个位置求的值相同。比如exe^xex,一般选择在x=0x=0x=0的位置进行泰勒展开...

2019-10-24 15:44:35

【清华集训2017】生成树计数 pufer序+分治NTT优化DP

Description在一个sss个点的图中,存在s−ns−ns−n条边,使图中形成了nnn个连通块,第iii个连通块中有aia_iai​个点。现在我们需要再连接n−1n−1n−1条边,使该图变成一棵树。对一种连边方案,设原图中第iii个连通块连出了did_idi​条边,那么这棵树TTT的价值为:val(T)=(∏i=1ndim)(∑i=1ndim)val(T)=(\prod_{i=1}^n...

2019-08-05 22:26:33

PKUSC2019真游记

我来北京旅游了!!!北京让我充分感受到了骑自行车的快感!DAY0坐飞机来到了北京,一路上被去隔壁sc的roseD的体无完肤。感觉首都机场并没有想象中那种人山人海的感觉。住酒店什么的搞了半天,终于可以去北大辣!下午的时候约上了之前的师兄cjj,请他带我们逛北大,看了看湖塔图,并没有找到翘尾石鱼???然后看了看沿路的建筑,果然北大真的挺漂亮的。然后就一起去勺园餐厅二楼吃饭,吃了听说是北...

2019-05-28 09:19:50

GDSOI2019爆蛋记

因为有人催,所以写了这篇东西,真的没脸写,考得太差了。。。DAY0去到酒店发现非常豪华,这应该是我出来比赛住过最好的酒店了吧。跟rose一个房,这谁顶得住啊。DAY1昨天晚上睡得很好,不知道考试怎么样。进考场之前遇到了和蔼可亲的麦老大,与他交流了一下。进考场,打了几个板子后发了密码条:zhuwo51kuaile(中间省略乱七八糟的东西看了一下这个T1T1T1,我会个5亿5亿5亿...

2019-05-20 20:15:34

Atcoder做题记录

ARC101E - Ribbons on Tree容斥树形dpdpdp,设f[x][k]f[x][k]f[x][k]为以xxx为根的子树,上面大小为kkk的连通块没有匹配。首先一个大小为nnn的子树的自由完全匹配方案我们先预处理出来。转移的话对于一个xxx考虑那些边是一定不选的的,不选的边的边数为TTT的话,容斥系数为−1∣T∣-1^{|T|}−1∣T∣对于一个xxx的子节点yyy,那么...

2019-04-18 20:19:22

Codeforces 1119FNiyaz and Small Degrees 树形DP+堆优化

Description现在给你一颗树,边有边权,回答nnn个询问,分别是对于x=0,1,2..(n−1)x=0,1,2..(n−1)x=0,1,2..(n−1),使得每个点的度数都不超过xxx,最小化删掉的权值。Sample Input51 2 11 3 21 4 31 5 4Sample Output10 6 3 1 0先来考虑一个给定一个xxx的做法。设f[x][0...

2019-04-09 19:48:38

SDOI2017题解

round1round1round1就不贴代码了。。。放个R2R2R2代码。数字表格写过了树点涂色又写过了序列计数预处理质数模PPP意义下的个数,以及和数模PPP意义下的个数,设f[i][j]f[i][j]f[i][j]为iii表示是否出现过质数,jjj表示当前的和在模PPP意义下的值。矩乘即可。新生舞会分数规划,跑个费用流。(为什么我的KM跑不过。。。硬币游...

2019-03-12 11:05:19

[SDOI2017]硬币游戏 Hash+高斯消元

Description给你一个字符串集,构造一个串每个位置等概率的插入。问字符串集中每个字符串最先出现在构造的串中的概率。Sample Input3 3THTTTHHTTSample Output0.33333333330.25000000000.4166666667首先这道题有弱化版,就是JSOI2009奇怪的游戏JSOI2009奇怪的游戏JSOI2009奇怪的游戏...

2019-03-07 20:02:46

HAOI2018题解

这一年搞了我好久。。。但还都是比较可做的。奇怪的背包对于每一个物品iii,他能拼出的物品ddd满足d∣gcd(P,V[i])d|gcd(P,V[i])d∣gcd(P,V[i]),所以一个物品只需要对PPP去gcdgcdgcd即可。根据蜚蜀定理你一堆物品能拼出的物品为这堆物品的gcdgcdgcd的倍数。然后你做一个dpdpdp表示,f[i][j]f[i][j]f[i][j]表示前iii个...

2019-03-05 17:02:30

JSOI2016部分题题解

边做边更吧。。。独特的树叶判断两棵树是否相同可以使用树HashHashHash,我用的HashHashHash方式是按照子树大小来HashHashHash。然后你搞一个换根DPDPDP判一下即可。。。#include <map>#include <ctime>

2019-03-02 19:05:15

BZOJ2671: Calc 莫比乌斯反演

Description给出NNN,统计满足下面条件的数对(a,b)(a,b)(a,b)的个数:1.1<=a<b<=N1.1<=a<b<=N1.1<=a<b<=N2.a+b整除a∗b2.a+b整除a*b2.a+b整除a∗bSample Input15Sample Output4...

2019-03-02 09:20:51

PAM学习笔记

Manacher按照惯例,先放上manachermanachermanacher(其实是为了给自己看。。。首先为了处理奇数串和偶数串的问题,我们可以给两个字符之间插入一些特殊字符。设p[i]p[i]p[i]为以iii为中心最长回文串长度。设mxmxmx为当前i+p[i]i+p[i]i+p[i]的最大值,ididid为mxmxmx的iii。假设当前加入一个新节点iii,如果i&lt...

2019-03-01 10:18:12

BZOJ1396: 识别子串 SAM+线段树

Description对于一个字符串SSS,一个位置xxx的识别子串T=S(i,j)T=S(i,j)T=S(i,j)为:1.i<=x<=j1.i<=x<=j1.i<=x<=j2.T只在S中出现过一次2.T只在S中出现过一次2.T只在S中出现过一次对每个位置求出识别子串的长度。Sample Inputagoodcook...

2019-03-01 08:38:50

JXOI2018题解

排列问题比较明显的贪心吧,就先让排名最小的增加到排名第二的权值,再让排名第二的权值增加到排名第三的权值,sortsortsort完之后按顺序搞就好了,模数搞错弄了半天。。。#include <ctime>#include <cmath>#include <cstdio>#include <cstring>#include <cst...

2019-02-28 19:45:56

BZOJ2589: Spoj 10707 Count on a tree II 树上分块+可持久化块状数组

Description给定一棵NNN个节点的树,每个点有一个权值,对于MMM个询问(u,v)(u,v)(u,v),你需要回答uxorlastansu xor lastansuxorlastans和vvv这两个节点间有多少种不同的点权。其中lastanslastanslastans是上一个询问的答案,初始为000,即第一个询问的uuu是明文。Sample Input8 2105 2 9 3...

2019-02-28 11:35:30

[Jsoi2018]军训列队 主席树

Description一共有nnn个学生,第iii个学生的休息位置是a[i]a[i]a[i]。每一次命令,教官会指定一个区间[l,r][l, r][l,r]和集合点kkk,所有编号在[l,r][l, r][l,r]内的学生都必须赶到集合点列队。在列队时,每一个学生需要选择[k,k+r−l][k, k+r-l][k,k+r−l]中的一个整数坐标站定且不能有任何两个学生选择的坐标相同。学生从坐标xx...

2019-02-28 07:13:12

查看更多

勋章 我的勋章
  • 专栏达人
    专栏达人
    授予成功创建个人博客专栏的用户。专栏中添加五篇以上博文即可点亮!撰写博客专栏浓缩技术精华,专栏达人就是你!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv1
    勤写标兵Lv1
    授予每个自然周发布1篇到3篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。