3 xyz32768

尚未进行身份认证

菜鸡菜鸡菜**

等级
TA的排名 1w+

博客搬家

博客搬迁至 https://www.cnblogs.com/xyz32768

2019-12-07 15:02:08

[题解]CSP2019 Solution - Part B

orz\text{orz}orz 一波现场 A\text{A}A 掉 D1T3\text{D1T3}D1T3 的神仙D2T3 centroidSolution考虑每个点 uuu 作为重心的贡献假设以 uuu 为根时,存在 uuu 的一个子节点 vvv现在要在 vvv 的子树内删掉一个子树,使得 uuu 成为重心考虑删子树之后,vvv 的子树大小需要满足什么条件设 uuu 除 v...

2019-11-20 22:56:54

[题解]CSP2019 Solution - Part A

至于为什么是 Part A\text{Part A}Part A 而不是 Day 1\text{Day 1}Day 1那是因为 Day1 T3 还没改(那这六题的 solution\text{solution}solution 就按难度顺序写吧)感觉今年的画风和 NOIP 2016\text{NOIP 2016}NOIP 2016...

2019-11-20 20:28:28

[Other]CSP2019 游记

一些有趣的事情Day 0上午颓废,下午到宾馆15:4015:4015:40 左右去试机试机题是 A+B Problem\text{A+B Problem}A+B Problem ,发现是个线段树模板题,直接码上某初二学弟写了主席树回到宾馆颓了一段时间之后去外面吃饭再次回来之后继续颓颓颓10:0010:0010:00 要睡觉突然被叫起来(老董开会)开完会...

2019-11-17 22:00:55

[LOJ#3177][IOI2019]矩形区域(分治 + 单调栈)

AddressLOJ #3177Solution首先有一个性质对于长度为 nnn 的数组 a1...na_{1...n}a1...n​满足对于所有 l≤i≤rl\le i\le rl≤i≤r 都有 al−1>ai,ar+1>aia_{l-1}>a_i,a_{r+1}>a_ial−1​>ai​,ar+1​>ai​ 的...

2019-08-18 15:23:40

[LOJ#2320][UOJ#335][清华集训2017]生成树计数(prufer序列 + 生成函数)

Address洛谷 P4002BZOJ 5119UOJ #335LOJ #2320Solution我们知道,一棵 nnn 个节点的无根树对应一个长度为 n−2n-2n−2 的 prufer 序列且 prufer 序列中 uuu 的出现次数为树上 uuu 的度数 dud_udu​ 减 111而在原题中,一个节点 uuu 本质上是一个大小为 aua_uau​ 的连通块故如果 d...

2019-08-12 20:31:55

[题解][LOJ #3156~#3161]NOI2019 简要题解集合

AddressD1T1 :洛谷 P5468 / LOJ #3156D1T2:洛谷 P5469 / LOJ #3157D1T3 :洛谷 P5470 / LOJ #3158D2T1:洛谷 P5471 / LOJ #3159D2T2:洛谷 P5472 / LOJ #3160D2T3 :洛谷 P5473 / LOJ #3161...

2019-08-04 14:41:50

[UOJ#346][清华集训2017]某位歌姬的故事(DP)

Address洛谷 P4229UOJ #346LOJ #2331Solutionorz 讲课现场切掉此题的神仙 Lagoon可以发现,如果一个限制为 max⁡i=lrhi=x\max_{i=l}^rh_i=xmaxi=lr​hi​=x ,另一个限制为 max⁡i=abhi=y\max_{i=a}^bh_i=ymaxi=ab​hi​=y 且 y<xy<x...

2019-08-03 18:03:06

[LOJ#3124][CTS2019]氪金手游(概率 + 树形 DP + 容斥)

Address洛谷 P5405LOJ #3124Solution先考虑如果以某个点(下面定为 111 )为根时,如果所有的限制二元组 (u,v)(u,v)(u,v) 都满足 uuu 是 vvv 的父亲(即 uuu 向 vvv 连边构成外向树)怎么做显然,对于任意一个点 uuu , uuu 必须是在 uuu 的子树内第一个被翻到的如果每个点的 WWW 已经确定,则这个概率就等于∏...

2019-06-28 17:59:52

[题解][Codeforces 1172A~1172D]Codeforces Round #564 (Div. 1) 前四题题解

中国场,最后两题为毒瘤数据结构题,还未写,见谅Address洛谷 RemoteJudgeABCDEFCodeforcesABC1C2DEFAMeaning两个序列 aaa 和 bbb ,长度为 nnn ,每个数均为 000 或者 111 到 nnn 之间的整数,且 111 到 nnn 的每个数出现且仅出现一次每次操作可以在第一个序列里抽走一个数...

2019-06-11 20:19:14

[LOJ#6617][THUPC2019]摆家具(矩阵乘法 + 子集和变换)

AddressLOJ #6617SolutionTask 1先解决一个小问题如何求 TTT 次操作之后,对于所有的 0≤i≤k0\le i\le k0≤i≤k ,求出最后恰好有 iii 个家具不在原来的房间内的方案数容易设计一个 DPf[i][j]f[i][j]f[i][j] 表示 iii 次操作之后,恰好有 jjj 个家具不在原来的房间内的方案数转移(自行理解)f[0][...

2019-06-07 18:00:58

[UOJ#461]新年的Dog划分(交互 | DFS + 二分)

AddressUOJ #461Solution看到题目只需要求二分图的两个点集而不需要求所有的边我们可以想到求出二分图的一棵生成树而这棵生成树就能唯一确定二分图的两个点集看到操作次数限制,我们可以猜测需要使用的操作次数为 O(nlog⁡n)O(n\log n)O(nlogn)考虑钦定一个生成树的根每次把根 uuu 删掉,对剩下的每个连通块各找一个点 vvv 满足边 (u,v)...

2019-06-04 19:46:04

[LOJ#3119][CTS2019]随机立方体(容斥)

Address洛谷 P5400LOJ #3119Solution考虑容斥具体地,用「选出 kkk 个格子,这 kkk 个格子极大的概率之和」×Ckk\times C_k^k×Ckk​减去「选出 k+1k+1k+1 个格子,这 k+1k+1k+1 个格子极大的概率之和」×Ck+1k\times C_{k+1}^k×Ck+1k​再加上「选出 k+2k+2k+2 个格子,这 k+2k...

2019-06-02 21:54:26

[题解]一道 DP 思路好题

Description数轴上对于所有的 1≤i≤n1\le i\le n1≤i≤n ,点 iii 上有一个物品,价值为 aia_iai​从 000 开始走路,每次可以向左或向右走如果点 iii 上有一个没有取过的物品,则可以取之但初始你有 xxx 点能量在任何时候,如果你身上的物品价值总和为 aaa ,则走一个单位距离要消耗 a+1a+1a+1 点能量求在回到起点 000 时剩余能量...

2019-05-18 10:49:08

[日常训练]Hard(组合数学 + FMT)

Meaning有一棵 nnn 个点的树,根结点为 111 号结点,初始时每个结点有一个值 aia_iai​每一轮,你需要从根结点开始,将每个结点的权值更新为它子树中所有结点上一轮结束后权值的异或和有 qqq 个询问,每个询问给定轮数 TTT ,你需要输出 TTT 轮后根结点的值0≤T,ai≤1018,1≤n,q≤1060\le T,a_i\le10^{18},1\le n,q\le10^...

2019-04-21 15:43:56

[题解][Codeforces 1137A~1137F]Codeforces Round #545 (Div. 1) 简要题解

第一次打 Div. 1 ,感觉题目质量还是比较好的然后就把我这个菜鸡选手区分到了榜末题目洛谷 RemoteJudgeABCDEFCodeforcesABCDEFA题意一个 n×mn\times mn×m 矩阵 aaa定义 f(x,y)f(x,y)f(x,y) 表示在矩阵中取出第 xxx 行和第 yyy 列设一个新矩阵 bbb ,这个矩阵只有第...

2019-04-01 21:47:47

[BZOJ4651][Noi2016]网格(Tarjan 求割点)

Address洛谷 P1173BZOJ 4651UOJ #220LOJ #2084Solution下面把跳蚤视为白点,蛐蛐视为黑点可以发现答案只可能是 −1-1−1 、 000 、 111 、 222 四种然后随机输出一个,你可以以 1 / (4 ^ T) 的高概率通过此题易得, 如果没有黑点,则有三种情况(1) n×m≤2n\times m\le 2n×m≤2 : −1...

2019-04-01 16:43:14

[题解][Codeforces 1139A~1139F]Codeforces Round #548 (Div. 2) 简要题解

终于 rank < 10 了题目洛谷 RemoteJudgeABCDEFCodeforcesABCDEFA题意一个长度为 nnn 的数字串 sss求 sss 有多少个子串,满足子串内的数字顺次连接后得到的数是偶数1≤n≤650001\le n\le 650001≤n≤65000 且 sss 不包含 000题解∑i=1ni[s[i]...

2019-03-26 21:47:17

[Codeforces 1098C]Construct a tree(二分 + 构造)

Address洛谷 RemoteJudgeCodeforces 1098CSolution看到要最小化每个点子节点个数的最大值,想到二分答案 midmidmid考虑通过构造进行判断首先要知道:所有节点的子树大小之和,等于所有节点的深度之和所以在此题中,一棵树可以被量化成一个数组 d[]d[]d[] ,其中 d[i]d[i]d[i] 表示深度为 iii 的点数然后尝试分析一下每...

2019-03-14 20:52:32

[Codeforces 1097F]Alex and a TV Show(bitset + 莫比乌斯反演)

Address洛谷 RemoteJudgeCodeforces 1097FSolution发现我们要查询的是某集合内某数的出现次数模 222 的结果可以对于每个可重集维护一个 bitset ,第 iii 个集合的 bitset 第 jjj 位表示第 iii 个集合中 jjj 的出现次数的奇偶性但我们发现这样做无法解决第 333 种操作我们不妨把维护的东西换一下A[i][j]A...

2019-03-09 11:06:17

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv1
    勤写标兵Lv1
    授予每个自然周发布1篇到3篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。