Dispwnl

Crazy Up

常见错误

# define max(x,y) ((x)>(y)?(x):(y)) # define max(x,y) ((x)>(y)?(x):(y))尽量少用（尤其是数据结构），可能把函数放里面调用多次然后就被锤成弟弟了…… 写最短路（$SPFA$或$Dijkstra$）注意每次用队列里的点更新下一个点而不是起点也就我错这种sb错误了还是define，注意如果# defi...

Posted by Dispwnl on December 31, 2022

Hello World

“It’s a beginning” 在xm和Cansult的帮助下blog终于搞的比较像样了… 感谢Wzhqwq的大力帮助如你所见博主因为太弱了没有多少人来看欢迎加友链qwq $Q:$跟你加友链有什么好处呢毕竟你这么弱 $A:$您能得到双份的快乐就多了个人来表现您的强了啊QAQ $Q:$有道理就这样开始吧qwq 小建议：如果您想要有更...

Posted by Dispwnl on March 13, 2022

[HDU6959]zoto

题目题解考试的时候想到了莫队套数据结构维护，但是没想到分块…… 首先可以把题目简化成二维矩阵的查询，如果去掉查询中$y$坐标的限制，即查询一段区间内不同数的个数，这个显然是可以用莫队搞的；而对于加上$y$的限制，考虑能否用数据结构维护莫队每一步移动对于$y$值域的贡献以及查询如果用树状数组等数据结构维护，可以做到$O(logM)$的修改和查询，但是这样复杂度就为$O((n\sqr...

Posted by Dispwnl on July 21, 2021

END

本来预计的是等高考完就来更博客，但是刚考完根本没心情……出了成绩又懒得更，于是鸽到了现在不装弱了发一下真实所想高考刚考完以为自己考得很差，自己估了一下大概640差不多？然后对着答案估了一下大概650左右中间还发生了很让人啼笑皆非的事：我刚考完物理，记不起来自己涂没涂答题卡是不是很搞笑，但是当时我冷汗直接就下来了于是后几天一直在回想到底有没有涂卡……（...

Posted by Dispwnl on August 3, 2020

退役啦

如题意料之中又在情理之中不过文化课的生活真的养老啊(｡･∀･)ﾉﾞ

Posted by Dispwnl on June 13, 2019

[SDOI2018]荣誉称号

题目题解可以发现题目中给定的是个完全二叉树的形式，然后题目给定的限制可以转换成树上每一条长度为$k+1$的链$a$值和$\%m=0$ 发现深度为$x(x> k+1)$的点的值$a_1$与它深度为$x-k-1$祖先的值$a_2$满足$a_1\equiv a_2(\bmod m)$，这样只用确定前$k+1$层的值即可，把下面的信息都压到前 $k+1$层即可处理出点$t$的$a...

Posted by Dispwnl on May 3, 2019

[SDOI2018]战略游戏

题目题解很明显题目要求的就是两个点之间的割点数量，先建出圆方树，然后就是两两路径上圆点个数可以建出虚树来求，也可以直接按$dfs$序排序，每个点和下一个点（$\vert S\vert$点的下一个点是$1$号点）求出路径圆点个数，然后除以$2$就是答案了代码 # include<iostream> # include<cstring> # includ...

Posted by Dispwnl on May 3, 2019

[CF487E]Tourists

题目题目大意给定一张无向图，每个点有一个权值，求两个点之间所有简单路径上最小值的最小值，要求支持单点修改 Examples input 3 3 3 1 2 3 1 2 2 3 1 3 A 2 3 C 1 5 A 2 3 output 1 2 input 7 9 4 1 2 3 4 5 6 7 1 2 2 5 1 5 2 3 3 4 2 4 5 6 6 7 5 7 A...

Posted by Dispwnl on May 3, 2019

[PKUWC2018]随机游走

题目题解一脸min-max容斥的样子，设$f_{i,S}$表示起点为$i$，要求遍历的集合为 $S$，第一次遍历到集合中的点的期望最早时间，分情况讨论：设现在遍历到的点为$x$，如果$x\in S$，那么$f_{x,S}$且$x$的子树不会产生贡献如果$x \not \in S$，那么有转移$f_{x,S}=\frac{1}{du_x}(f_{fa_x,S}+1)+...

Posted by Dispwnl on April 29, 2019

[HAOI2017]方案数

题目题解先考虑没有障碍的情况设$f_{i,j,k}$为第一维二进制下有$i$个$1$，第二维二进制下有$j$个$1$，第三维二进制下有$k$个$1$的方案数，每次就从$f_{i-l,j,k},f_{i,j-l,k},f_{i,j,k-l}$转移过来即可设$F_i$表示经过第$i$个障碍，但是不经过前$i-1$个障碍的方案数，容斥即可代码 # include<ios...

Posted by Dispwnl on April 28, 2019