Dispwnl

Crazy Up

[LOJ6494]LJJ 的字符串

题目题解跟这道题差不多一个处理方法，枚举$x=j-i$，每隔$x$距离放一个标志，求相邻标志的$LCP$和$LCS$（最长公共后缀），建两个后缀数组就可以处理每次更新答案就是对于一段区间加三部分答案，二维差分即可$O(1)$维护代码 # include<iostream> # include<cstring> # include<cstdio&...

Posted by Dispwnl on April 18, 2019

[JLOI2015]骗我呢

题目题解 yyb 代码 # include<iostream> # include<cstring> # include<cstdio> # include<algorithm> using namespace std; const int MAX=4e6+5,mod=1e9+7; int n,m; int fac[MAX],inv[...

Posted by Dispwnl on April 18, 2019

[JOI 2019 Final]独特的城市

题目题解首先发现可能能计入贡献的点都在直径上所以先$dfs$两遍把直径搞出来，然后从直径两端分别$dfs$，只统计祖先部分（链上部分）是否有贡献，用子树中的最深点把距离重复的祖先去除掉，发现这个东西可以用单调栈维护两遍求答案取最大值即可代码 # include<iostream> # include<cstring> # include<...

Posted by Dispwnl on April 17, 2019

[JOI 2018 Final]毒蛇越狱

题目题解考虑暴力，用$N_c$表示字符$c$在询问字符串中出现的次数可以$O(2^{N_?})$枚举$?$选什么可以处理出来每个状态的超集的毒性和，然后可以$O(N_02^{N_0})$处理出来$F_i$，表示至少有$i$个$0$的毒性和，容斥即可可以处理出来每个状态的子集的毒性和，然后可以$O(N_12^{N_1})$处理出来$G_i$，表示至多有$i$个$1...

Posted by Dispwnl on April 17, 2019

[CEOI2017]Building Bridges

题目题解首先先推出$O(n^2)dp$，设$f_i$表示连通$1\sim i$需要的最小代价 $f_i=\min(f_j+(h_i-h_j)^2+\sum_{k=j}^{i-1}w_k),j<i$ 发现似乎可以斜率优化！拆开式子，$sum$为$w$的前缀和 $f_i=f_j+{h_i}^2+{h_j}^2-2h_ih_j+sum_{i-1}-sum_j$ $f_i-su...

Posted by Dispwnl on April 17, 2019

[SDWC2018]网格

题目搞题面太烦啦就不整了OAO 题解首先考虑没有$k$的限制怎么做发现二维可以分开搞，设${f_x}(i,n,R)$表示横坐标要跳$R$步跳到$n$上至少有$i$次坐标变化超过$M_x$的方案数，则有 ${f_x}(i,n,R)=C_{R}^{i}C_{n-i(M_x+1)+R-1}^{R-1}$ 后面那部分就是先确定$i$个$M_x+1$后随便选，即用$...

Posted by Dispwnl on April 16, 2019

[LOJ6073]距离

题目题解设$d_x$表示$x$到根的距离，对于每个询问，可以把它拆成 $\sum_{i\in path(u,v)}d_k+d_{p_i}-2d_{LCA(k,p_i)}$ 第一个直接$d_k$乘路径长度，第二个可以处理出来$dfs$序上的前缀和，然后跳链统计即可第三个的统计和这道题差不多对于一个点$x$，把$P_x$到根都打上标记（边权），这样查询$d_{LCA(k,P...

Posted by Dispwnl on April 16, 2019

[CF1140G]Double Tree

题目题目大意给出一个$2N$个点、$3N-2$条边的无向图，边有边权。这张图满足以下性质： ①对于图上的一条边$(u,v)(2 \vert u , 2 \vert v)$，一定存在边$(u+1,v+1)$，反之亦然； ②图上存在边$(u,u+1)$ 可以知道编号为偶数的点的导出子图和编号为奇数的点的导出子图都是一棵树，且它们同构。现在给出$Q$组询问，每组询问询问两个点$...

Posted by Dispwnl on April 15, 2019

[SDOI2016]模式字符串

题目题目描述给出n个结点的树结构T，其中每一个结点上有一个字符，这里我们所说的字符只考虑大写字母A到Z，再给出长度为m的模式串s，其中每一位仍然是A到z的大写字母。 Alice希望知道，有多少对结点<u，v>满足T上从u到V的最短路径形成的字符串可以由模式串S重复若干次得到？这里结点对<u，v>是有序的，也就是说<u，v>和<v，u&g...

Posted by Dispwnl on April 14, 2019

[CF1119F]Niyaz and Small Degrees

题目题目大意给定一棵$n$个节点的树，每条边有一个权值，求出使每个点度数不超过$0\sim n-1$删掉的边的权值和最小是多少 Examples input 5 1 2 1 1 3 2 1 4 3 1 5 4 output 10 6 3 1 0 input 5 1 2 1 2 3 2 3 4 5 4 5 14 output 22 6 0 0 0 题解...

Posted by Dispwnl on April 14, 2019