洛谷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表示正面朝上...
p3302 [SDOI2013]森林（树上主席树+启发式合并）
对着题目yy了一天加上看了一中午题解，终于搞明白了我太弱了连边就是合并线段树，把小的集合合并到大的上，可以保证规模至少增加一半，复杂度可以是\(O(logn)\)合并的时候暴力dfs修改倍增数组和维护主席树即可然后树上主席树就是维护节点到根节点的信息即可，询问链上的第k大时，画图后可以发现维护一个r...
【BZOJ2242】【SDoi2011】计算器 快速幂+EXGCD+BSGS
Description你被要求设计一个计算器完成以下三项任务：1、给定y,z,p,计算Y^Z Mod P 的值；2、给定y,z,p，计算满足xy≡ Z ( mod P )的最小非负整数；3、给定y,z,p，计算满足Y^x ≡ Z ( mod P)的最小非负整数。Input输入包含多组数据。第一行包含...
P2484 [SDOI2011]打地鼠
差分代码：#include <bits/stdc++.h>using namespace std;#define INF 1999999999int n,m,sum,a[][],b[][],c[][];int main(){ int minn=INF; cin>>n&...
P3784 [SDOI2017]遗忘的集合
非常神仙的一道题！题意：给出某n个数字跑完全背包m容量的dp数组，求满足要求的字典序最小的n个元素，不知道n是多少。首先考虑付公主的背包这个题。对dp数组求一个ln，设它为F。已知 e^(G1+G2+G3)=e^F，其中Gi是第i个物品的生成函数求ln。（重量为i的物品的Gi=∑ 1/i ✖ x^v...
【bzoj2281】[Sdoi2011]黑白棋
博弈论---Nimk问题。 dp再搞搞。很容易看出，该游戏的终态是每两个棋子都紧靠着。当一颗棋子移动，另一方与该棋子对应的那一刻可以立即追上，使得仍旧紧靠，最终棋子动弹不得，游戏结束。还能看出，对于白色棋子（先手），往左走没有意义。因为黑子（后手）可以紧随其上使得两者距离不变。同理黑子只往左走。（黄...
bzoj 3202: [Sdoi2013]项链
Description项链是人体的装饰品之一，是最早出现的首饰。项链除了具有装饰功能之外，有些项 链还具有特殊显示作用，如天主教徒的十字架链和佛教徒的念珠。 从古至今人们为了美化人体本身，也美 化环境，制造了各种不同风格，不同特点、不同式样的项链，满足了不同肤色、不同民族、不同审美观的人的审美需要。...
BZOJ3202 [Sdoi2013]项链
Problem E: [Sdoi2013]项链Time Limit: 30 Sec Memory Limit: 512 MBSubmit: 427 Solved: 146[Submit][Status][Discuss]Description项链是人体的装饰品之一，是最早出现的首饰。项链除了具有...
BZOJ1878[SDOI2009]HH的项链
DescriptionHH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步 完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH不断地收集新的贝壳，因此， 他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同 的贝壳？这个问题很难回答。。...