sdoi2010专题

P2446 [SDOI2010]大陆争霸（dijkstra）

题目：https://www.luogu.org/problem/P2446 Description：带限制的最短路，途中一些点被其他点限制，当限制该点的点都被到达后方可通过该点。你可以释放无限多个机器人替你跑路。 Solution：情景一：当前到达的点没有被保护 => 可以直接通过情景二：当前到达的点被保护，不能通过 => 在门口等着，直到保护这个点的点都被到达,限制

P2483 【模板】k 短路 / [SDOI2010] 魔法猪学院

题目：题目背景注：对于 kk 短路问题，A* 算法的最坏时间复杂度是 O(nk \log n)O(nklogn) 的。虽然 A* 算法可以通过本题原版数据，但可以构造数据，使得 A* 算法在原题的数据范围内无法通过。事实上，存在使用可持久化可并堆的算法可以做到在 O((n+m) \log n + k \log k)O((n+m)logn+klogk) 的时间复杂度解决 kk 短路问题。详情见

[SDOI2010]地精部落解题报告

这道题是我看了题解以后才做出来的，真是一道神题，但是写题解的大神都不愿解释得太详细，所以我想了很久才想明白。。看了题解以后真的觉得很像数的划分、约瑟夫问题还有国王游戏，代码出奇地简洁，但是思维量相当地高。主要思路：离散。三个引理： ①在n->n-1的转化过程中，我们删除了一个点后，我们可以将n-1个点视为仍是1~n-1的排列。 ②在若排列Pn为一个合法抖动子序列，则交换i∈[1,n

[SDOI2010星际竞速]解题报告

用这道题学了最小费用最大流，明白了一些建模的思路。我们必须要让一个合法解与一个割集的对应。拿此题来说，原命题可以转换为要让所有点进且仅进一次，至多出一次；分别限制即可。进且仅进一次意味着开一条边容量为1而存在一条路径从源到汇使得有且仅有这条边容量为正无穷；至多出一次意味着开一条边，这条边到源点的流至多为1. #include<cstdio>#include<cstring>#in

[SDOI2010]猪国杀解题报告

这道题作为一道省选题，质量真是差到了极点！！强烈建议千万不要去做！首先，这题意与数据不合，而样例怎么看都是错的，反猪明明有6张无懈！题意与数据之龃龉： ①题目中n<=5,而实际上n<=10. ②题目中明确指出不会出现牌不够用的情况，而实际上你需要不断地抽最后一张牌。也就是说，如果你按照题目要求写的话，你的最终得分将是：30分。。。(←_←这种题考场上能有人A才怪。) 而

【BZOJ 1951】 [Sdoi2010]古代猪文|数论|中国剩余定理|Lucas

搞清楚费马小定理的适用条件 #include <cmath>#include <cstdio>#include <iostream>#include <algorithm>using namespace std;#define LL long longconst int MO = 999911659;const int MO1= 999911658; int t[5]={0

【bzoj1926】【sdoi2010】【粟粟的书架】【二分+主席树】

Description Input 第一行是三个正整数R, C, M。接下来是一个 R行C 列的矩阵，从上到下、从左向右依次给出了每本书的页数Pi,j。接下来 M行，第 i 行给出正整数x1i, y1i, x2i, y2i, Hi，表示第i 天的指定区域是﹙x1i, y1i﹚与﹙x2i, y2i﹚间的矩形，总页数之和要求不低于 Hi。保证 1≤x1i≤x2i≤R，1≤y1i

【模板】k 短路 / [SDOI2010] 魔法猪学院

题目背景注：对于 k k k 短路问题，A* 算法的最坏时间复杂度是 O ( n k log ⁡ n ) O(nk \log n) O(nklogn) 的。虽然 A* 算法可以通过本题原版数据，但可以构造数据，使得 A* 算法在原题的数据范围内无法通过。事实上，存在使用可持久化可并堆的算法可以做到在 O ( ( n + m ) log ⁡ n + k log ⁡ k ) O((n+m)

【蓝桥杯冲冲冲】k 短路 / [SDOI2010] 魔法猪学院

蓝桥杯备赛 | 洛谷做题打卡day33 文章目录蓝桥杯备赛 | 洛谷做题打卡day33题目背景题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示数据规模数据更新日志题解代码我的一些话【模板】k 短路 / [SDOI2010] 魔法猪学院题目背景注：对于 k k k 短路问题，A* 算法的最坏时间复杂度是 O ( n k log ⁡ n )

BZOJ 1923 [Sdoi2010]外星千足虫

Description Input 第一行是两个正整数 N, M。接下来 M行，按顺序给出 Charles 这M次使用“点足机”的统计结果。每行包含一个“01”串和一个数字，用一个空格隔开。“01”串按位依次表示每只虫子是否被放入机器：如果第 i 个字符是“0”则代表编号为 i 的虫子未被放入，“1” 则代表已被放入。后面跟的数字是统计的昆虫足数 mod 2 的结果。由于 NASA

[SDOI2010]魔法猪学院[k短路][A*]

题目描述 iPig在假期来到了传说中的魔法猪学院，开始为期两个月的魔法猪训练。经过了一周理论知识和一周基本魔法的学习之后，iPig对猪世界的世界本原有了很多的了解：众所周知，世界是由元素构成的；元素与元素之间可以互相转换；能量守恒……。能量守恒……iPig 今天就在进行一个麻烦的测验。iPig 在之前的学习中已经知道了很多种元素，并学会了可以转化这些元素的魔法，每种魔法需要消耗 iPig 一

[BZOJ 1951][Sdoi2010]古代猪文：Lucas定理|中国剩余定理|费马小定理|扩展欧几里得

点击这里查看原题一道综合了各种数论的神题。其实不难，主要是需要组合在一起运用。 1.费马小定理：求G^P时使用，因为G^(mod-1)%mod=1，所以需要P%=mod-1 2.Lucas定理&中国剩余定理：计算组合数取模时使用，但是本题中mod-1不为素数，因此需要结合中国剩余定理使用（即扩展Lucas定理） 3.扩展欧几里得：中国剩余定理要求逆元 /*User:SmallLan

「SDOI2010」古代猪文 - Lucas定理+CRT

题目描述 Luogu2480 题意简述：给定 n , G n,G n,G，求 G ∑ d ∣ n C n d mod 999911659 G^{\sum\limits_{d|n}C_n^d}\text{mod}\ 999911659 Gd∣n∑Cndmod 999911659 分析若 G mod 999911659 = 0 G\ \text{mod}\ 999911659=0

Bzoj 1927: [Sdoi2010]星际竞速(网络流)

1927: [Sdoi2010]星际竞速 Time Limit: 20 Sec Memory Limit: 259 MB Description 　　10年一度的银河系赛车大赛又要开始了。作为全银河最盛大的活动之一，夺得这个项目的冠军无疑是很多人的梦想，来自杰森座α星的悠悠也是其中之一。赛车大赛的赛场由N颗行星和M条双向星际航路构成，其中每颗行星都有一个不同的引力值。大赛要求车手们

SDOI2010 魔法猪学院

题目描述题解：明显的$k$短路问题，这里提供两种方法。 1.$A$*算法 $A$*可以解决一般的$k$短路问题，但是并不如可持久化可并堆优秀。 $A$*的本质是$f+g$，而估价函数可以用终止节点到终点的最短路表示。所以先反向建图$dij$，然后小根堆跑$A$*即可。优化一下，总代价/起点终点最短路就是每个点经过的最大次数。代码： #include<queue>#includ

【SDOI2010】bzoj1941 Hide and Seek

Description 小猪iPig在PKU刚上完了无聊的猪性代数课，天资聪慧的iPig被这门对他来说无比简单的课弄得非常寂寞，为了消除寂寞感，他决定和他的好朋友giPi（鸡皮）玩一个更加寂寞的游戏—捉迷藏。但是，他们觉得，玩普通的捉迷藏没什么意思，还是不够寂寞，于是，他们决定玩寂寞无比的螃蟹版捉迷藏，顾名思义，就是说他们在玩游戏的时候只能沿水平或垂直方向走。一番寂寞的剪刀石头布后，他们决定

Luogu 2467[SDOI2010]地精部落 - DP

Solution 这题真秒啊，我眼瞎没有看到这是个排列很显然，有一条性质：　　第一个是山峰和第一个是山谷的情况是一一对应的，只需要把每个数 $x$ 变成 $n-x+1$ 然后窝萌定义数组 $f[ i ][ j ]$ 表示有 $i$ 座山，且第一座山是山谷(即开头上升) 且高度 $<= j$ 时的方案数。然后考虑如何转移。 1：当第一位 $!=j$ 时，即第一位 $ <=