Dispwnl

Crazy Up

[HAOI2018]染色

题目题目描述为了报答小 C 的苹果, 小 G 打算送给热爱美术的小 C 一块画布, 这块画布可以抽象为一个长度为 $N$ 的序列, 每个位置都可以被染成 $M$ 种颜色中的某一种. 然而小 C 只关心序列的 $N$ 个位置中出现次数恰好为 $S$ 的颜色种数, 如果恰好出现了 $S$ 次的颜色有 $K$ 种, 则小C会产生 $W_k$ 的愉悦度. 小 C 希望知道对于所有可能的染...

Posted by Dispwnl on March 1, 2019

[BZOJ3160]万径人踪灭

题目题目描述图片不放了烦死给定一个只含$a,b$的字符串，在其中选取一个子序列，使得：位置和字符都关于某条对称轴对称不能是连续的一段输入输出样例输入样例#1： abaabaa 输出样例#1： 14 输入样例#2： aaabbbaaa 输出样例#2： 44 输入样例#3： aaaaaaaa 输出样例#3： 53 题解发现要...

Posted by Dispwnl on March 1, 2019

[BZOJ1458]士兵占领

题目 Description 有一个M * N的棋盘，有的格子是障碍。现在你要选择一些格子来放置一些士兵，一个格子里最多可以放置一个士兵，障碍格里不能放置士兵。我们称这些士兵占领了整个棋盘当满足第i行至少放置了Li个士兵, 第j列至少放置了Cj个士兵。现在你的任务是要求使用最少个数的士兵来占领整个棋盘。 Input 第一行两个数M, N, K分别表示棋盘的行数，列数以及障碍的个数。 ...

Posted by Dispwnl on March 1, 2019

[HDU5909]Tree Cutting

题目题目大意给定一棵树，定义一棵树的权值为每个节点权值的异或和，求这棵树所有子图的权值，输出每种权值的出现次数 Sample Input 2 4 4 2 0 1 3 1 2 1 3 1 4 4 4 0 1 3 1 1 2 1 3 1 4 Sample Output 3 3 2 3 2 4 2 3 题解假设$f_{i,j}$表示以$i$为根的子树包含$i$的子图权值为...

Posted by Dispwnl on February 28, 2019

[CSU1911]Card Game

题目题目大意给定两个长度为$n$的序列，求从这两个序列中各选出一个数使得它们的异或和为$x$的方案数，多组询问 Sample Input 1 4 4 1001 11 1100 1000 1110 1001 10 100 2 1100 111 Sample Output Case #1: 2 1 题解用$FWT$板子充数的我真是嗨到不行啊代码 # include...

Posted by Dispwnl on February 28, 2019

[CF995F]Cowmpany Cowmpensation

题目题目大意给定一棵树，每个点要确定一个$[1,D]$之间的权值，要求每个点（除$1$节点，即根）的权值不大于它的父亲求分配方案数 Examples Input 3 2 1 1 Output 5 Input 3 3 1 2 Output 10 Input 2 5 1 Output 15 题解如果$D$很小的话简单$dp$，设$f_{i,...

Posted by Dispwnl on February 28, 2019

[BZOJ2655]calc

题目 Description 一个序列a1,…,an是合法的，当且仅当：长度为给定的n。 a1,…,an都是[1,A]中的整数。 a1,…,an互不相等。一个序列的值定义为它里面所有数的乘积，即a1a2…an。求所有不同合法序列的值的和。两个序列不同当且仅当他们任意一位不一样。输出答案对一个数mod取余的结果。 Input 一行3个数，A，n，mod。意义为上面所...

Posted by Dispwnl on February 28, 2019

[CF954I]Yet Another String Matching Problem

题目题目大意两个相同长度的字符串，每次选择一种字符$c$，把两个字符串中所有的字符$c$变成另一种字符，定义两个字符串之间的值为通过以上操作把两个字符串变成一样的最少操作次数给定字符串$S,T(\vert S\vert\ge\vert T\vert)$，求$S$中每个$\vert T\vert $长度的子串和$T$的值是多少 Example input abcdefa dd...

Posted by Dispwnl on February 27, 2019

[CF1045G]AI robots

题目题目大意给定$n$个一维数轴上的点，每个点有两个值$r_i,q_i$，位于$x_i$，定义两个点$i,j$能匹配为$x_i-r_i\le x_j\le x_i+r_i,x_j-r_j\le x_i\le x_j+r_j$，且$\vert q_i-q_j\vert\le k$，$k$为给定的值求有多少对点可以匹配 Example input 3 2 3 6 1 7 3 1...

Posted by Dispwnl on February 27, 2019

后缀自动机略解

$SAM$学过一段时间了，本来想写一点总结的，结果一直咕咕咕咕咕咕咕咕咕到了现在…… 概念和构造关于$right$集合 $right$集合是指结束位置相同的一堆子串结束位置形成的集合，像字符串$aabaaabba$，子串$aab,ab$是$right$集合相同的，因为它们的结束位置都是${3,7}$（从$1$开始标号） $right$集合相同的两个子串，...

Posted by Dispwnl on February 26, 2019