[SDOI]消耗战
link题目大意:若有一颗带边权的树，且每次询问$k$个节点，问$k$个节点均不与1号节点相连的最小边权。试题分析考虑暴力$dp$,设$dp_i$为处理好i的子树的最小边权，我们定义$val_i$为从$i$到根的最小边权，则$dp_i=min(\sum dp_v,val_i)$。但是发现其实有一些节...
BZOJ3129: [Sdoi2013]方程
拓展Lucas+容斥原理 #include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #include<vector> #include<cmath...
SDOI2013直径（树的直径）
题目描述：点这里题目大意：就是在一个树上找其直径的长度是多少，以及有多少条边满足所有的直径都经过该边。题解：首先，第一问很好求，两边dfs就行了，第一次从任一点找距它最远的点，再从这个点找距它的最远点，后两个点就是树的直径的两个端点，证明就不赘述了，有兴趣可以自己证一证玩一玩。那第二问怎么办呢？假设...
【bzoj4516】 Sdoi2016—生成魔咒
http://www.lydsy.com/JudgeOnline/problem.php?id=4516 (题目链接)题意依次向字符串末尾加上一个字符，每次求不同子串个数。Solution如果不是字符的范围太大，这道题就是个板子题。。所以我们把后缀自动机上的边用map存下就好了。伦说hash可以做，...
BZOJ4513: [Sdoi2016]储能表
Description有一个 n 行 m 列的表格，行从 0 到 n−1 编号，列从 0 到 m−1 编号。每个格子都储存着能量。最初，第 i 行第 j 列的格子储存着 (i xor j) 点能量。所以，整个表格储存的总能量是，随着时间的推移，格子中的能量会渐渐减少。一个时间单位，每个格子中的能量都...
bzoj 3130 [Sdoi2013]费用流（二分，最大流）
DescriptionAlice和Bob在图论课程上学习了最大流和最小费用最大流的相关知识。 最大流问题：给定一张有向图表示运输网络，一个源点S和一个汇点T，每条边都有最大流量。一个合法的网络流方案必须满足：(1)每条边的实际流量都不超过其最大流量且非负；(2)除了源点S和汇点T之外，对于其余...
bzoj2242: [SDOI2011]计算器 BSGS+exgcd
你被要求设计一个计算器完成以下三项任务：1、给定y,z,p,计算Y^Z Mod P 的值；（快速幂）2、给定y,z,p，计算满足xy≡ Z ( mod P )的最小非负整数；（exgcd）3、给定y,z,p，计算满足Y^x ≡ Z ( mod P)的最小非负整数。（BSGS）/***********...
BZOJ3530[Sdoi2014]数数——AC自动机+数位DP
题目描述我们称一个正整数N是幸运数，当且仅当它的十进制表示中不包含数字串集合S中任意一个元素作为其子串。例如当S=(22，333，0233)时，233是幸运数，2333、20233、3223不是幸运数。 给定N和S，计算不大于N的幸运数个数。输入输入的第一行包含整数N。 接下来一行一个整...
洛谷P2158 [SDOI2008]仪仗队
题目描述作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。 现在，C君希望你告诉他队伍整齐时能看到的学生人数。输入输出格式输入格式：共一个数N输出格式：共一...
BZOJ 1228: [SDOI2009]E&D(SG定理)
这道嘛，很容易就看出是个nim和，然后问题就是怎么算子问题的sg函数了先暴力个表看下规律，很容易就找出来了~~~（百度空间又渣了，图贴不出来= =）320 1 0 2 0 1 0 3 0 1 0 2 0 1 0 4 0 1 0 2 0 1 0 3 0 1 0 2 0 1 0 51 1 2 2 1 1...
【SDOI2009】解题汇总
又开了波专题，感觉就和炉石开冒险一样...（说的好像我有金币开冒险似的）/—————————————————————————————————————————————/ BZOJ-1226 【SDOI2009】学校食堂Dining 状态压缩DPf【i】【j】【k】表示前i-1人都吃过饭，j表示i与i之...
[SDOI2016]生成魔咒(后缀自动机)
/*水题， 根据性质做就行， nq不会对答案产生贡献， 那么只算p的贡献就好了*/#include<cstdio>#include<algorithm>#include<cstring>#include<queue>#include<map>...
[bzoj4821][Sdoi2017]相关分析
来自FallDream的博客，未经允许，请勿转载，谢谢。Frank对天文学非常感兴趣，他经常用望远镜看星星，同时记录下它们的信息，比如亮度、颜色等等，进而估算出星星的距离，半径等等。Frank不仅喜欢观测，还喜欢分析观测到的数据。他经常分析两个参数之间（比如亮度和半径）是否存在某种关系。现在Fran...
【LOJ】#2269. 「SDOI2017」切树游戏
题解把所有的数组一开始就FWT好然后再IFWT回去可以减小常数从13s跑到0.7s……可以参照immortalCO的论文，感受一下毒瘤的动态动态DP就是用数据结构维护线性递推的矩阵的乘积由于所有轻儿子\(F(z) + z^{0}\)的乘积做除法太麻烦，我们用一个线段树维护每个点所有的轻儿子即可代码#...
bzoj千题计划268：bzoj3131: [Sdoi2013]淘金
http://www.lydsy.com/JudgeOnline/problem.php?id=3131如果已知 s[i]=j 表示有j个<=n数的数码乘积=i那么就会有 s[a1]*s[a2] 个数 在一阵风之后到（a1，a2）位置把所有的j用一个数组b存起来，从大到小排序开始把（1,1）存...
BZOJ.5329.[SDOI2018]战略游戏(圆方树 虚树)
题目链接显然先建圆方树，方点权值为0圆点权值为1，两点间的答案就是路径权值和减去起点终点。对于询问，显然可以建虚树。但是只需要计算两关键点间路径权值，所以不需要建出虚树。统计DFS序相邻的两关键点间路径权值，最后除以2就好了。因为这个前缀和统计不到根节点，所以要加上当前虚树的根节点的权值，即(LCA...
bzoj2241: [SDOI2011]打地鼠
暴力。O(n^6)暴力卡过，72ms。莫名其妙做这道题时感觉十分烦躁，难受，只能这样了。O(n^4)的方法是这样差分一下。判断的时候tmp=t[i][j],t[i][j]-=tmp,t[i+r][j]+=tmp,t[i][j+c]+=tmp,t[i+r][j+c]-=tmp,同时查看是否合法。还有一...
BZOJ5329:[SDOI2018]战略游戏(圆方树,虚树)
Description省选临近，放飞自我的小Q无心刷题，于是怂恿小C和他一起颓废，玩起了一款战略游戏。这款战略游戏的地图由n个城市以及m条连接这些城市的双向道路构成，并且从任意一个城市出发总能沿着道路走到任意其他城市。现在小C已经占领了其中至少两个城市，小Q可以摧毁一个小C没占领的城市，同时摧毁所有...
BZOJ1975 [Sdoi2010]魔法猪学院
本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。本文作者：ljh2000 作者博客：http://www.cnblogs.com/ljh2000-jump/转载请注明出处，侵权必究，保留最终解释权！DescriptioniPig在假期来到了传说中的魔法猪学院...
[bzoj4820][Sdoi2017]硬币游戏
来自FallDream的博客，未经允许，请勿转载，谢谢。周末同学们非常无聊，有人提议，咱们扔硬币玩吧，谁扔的硬币正面次数多谁胜利。大家纷纷觉得这个游戏非常符合同学们的特色，但只是扔硬币实在是太单调了。同学们觉得要加强趣味性，所以要找一个同学扔很多很多次硬币，其他同学记录下正反面情况。用H表示正面朝上...