题目描述 lxhgww最近接到了一个生成字符串的任务，任务需要他把n个1和m个0组成字符串，但是任务还要求在组成的字符串中，在任意的前k个字符中，1的个数不能少于0的个数。现在lxhgww想要知道满足要求的字符串共有多少个，聪明的程序员们，你们能帮助他吗？ 输入格式 输入数据是一行，包括2个数字n和m 输出格式 输出数据是一行，包括1个数字，表示满足要求的字符串数目，这个数可能会很大，只需输出这个数除以20100403的余数 题解：比较经典的卡特兰数，关于卡特兰数，我明天可能会补上讲解与练习（咕咕咕警告 #include <stdio.h> #define int long lon...

题目描述 小刚在玩JSOI提供的一个称之为“建筑抢修”的电脑游戏：经过了一场激烈的战斗，T部落消灭了所有z部落的入侵者。但是T部落的基地里已经有N个建筑设施受到了严重的损伤，如果不尽快修复的话，这些建筑设施将会完全毁坏。现在的情况是：T部落基地里只有一个修理工人，虽然他能瞬间到达任何一个建筑，但是修复每个建筑都需要一定的时间。同时，修理工人修理完一个建筑才能修理下一个建筑，不能同时修理多个建筑。如果某个建筑在一段时间之内没有完全修理完毕，这个建筑就报废了。你的任务是帮小刚合理的制订一个修理顺序，以抢修尽可能多的建筑。 输入格式 第一行是一个整数N，接下来N行每行两个整数T1,T2描述一个建筑：...

零 很长一段时间内，zhn_666每周会更一些之前的学过的算法，也会把曾经因为懒惰之类的原因没学的算法重新学一遍，这次会好好写博客，希望有缘人看到也能学到点东西 一 这周俺要复习的算法是有关最小生成树的 首先介绍一些关于图的定义 - 连通图：在一张无向图中，任意两点都联通，则称此无向图为连通图 - 强连通图:在一张有向图中，任意两点都联通，则称此有向图为强连通图 - 生成树：在有n个点连通图中，选n-1条边构成的连通子图，则为一棵生成树。 - 最小生成树：在生成树中，使得这n-1条边权值和最小，为最小生成树。 二 解决最小生成树类的问题有主要两种方法，第一种为Kruskal算法，第二种为pri...

kruskal #include <cstdio> #include <iostream> #include <algorithm> #define inf 2000000000 using namespace std; const int M=200004; const int N=5005; int n,m,tot; struct NODE{  int x,y,dis; bool operator < (const NODE &a){  return this->dis < a.dis; } }bian[M]; int fa[N...

题目描述 Farmer John had just acquired several new farms! He wants to connect the farms with roads so that he can travel from any farm to any other farm via a sequence of roads; roads already connect some of the farms. Each of the N (1 ≤ N ≤ 1,000) farms (conveniently numbered 1…N) is represented by a p...

题目背景 小杉坐在教室里，透过口袋一样的窗户看口袋一样的天空。 有很多云飘在那里，看起来很漂亮，小杉想摘下那样美的几朵云，做成棉花糖。 题目描述 给你云朵的个数N，再给你M个关系，表示哪些云朵可以连在一起。 现在小杉要把所有云朵连成K个棉花糖，一个棉花糖最少要用掉一朵云，小杉想知道他怎么连，花费的代价最小。 输入格式 每组测试数据的 第一行有三个数N,M,K(1 \le N \le 1000,1 \le M \le 10000,1 \le K \le 10)N,M,K(1≤N≤1000,1≤M≤10000,1≤K≤10) 接下来M个数每行三个数X,Y,LX,Y,L，表示X云和Y云可以通过L的代...

题目描述 又到了一年一度的明明生日了，明明想要买B样东西，巧的是，这BB样东西价格都是A元。 但是，商店老板说最近有促销活动，也就是： 如果你买了第II样东西，再买第JJ样，那么就可以只花K_{I,J}K ,J 元，更巧的是，K_{I,J}K I,J 竟然等于K_{J,I}K J,I ​  。 现在明明想知道，他最少要花多少钱。 输出格式 一个整数，为最小要花的钱数。 题解 考虑加一个超级点0，然后建树，边权为连到的下一个点的点权，然后跑kruskal即可 #include <cstdio> #include <iostream> #include <algori...

题目背景 还记得 NOIP 2011 提高组 Day1 中的铺地毯吗？时光飞逝，光阴荏苒，三年过去了。组织者精心准备的颁奖典礼早已结束，留下的则是被人们踩过的地毯。请你来解决类似于铺地毯的另一个问题。 题目描述 会场上有 n 个关键区域，不同的关键区域由 m 条无向地毯彼此连接。每条地毯可由三个整数 u、v、w 表示，其中 u 和 v 为地毯连接的两个关键区域编号，w 为这条地毯的美丽度。 由于颁奖典礼已经结束，铺过的地毯不得不拆除。为了贯彻勤俭节约的原则，组织者被要求只能保留 K 条地毯，且保留的地毯构成的图中，任意可互相到达的两点间只能有一种方式互相到达。换言之，组织者要求新图中不能有环。...

题目描述 聪聪研究发现，荒岛野人总是过着群居的生活，但是，并不是整个荒岛上的所有野人都属于同一个部落，野人们总是拉帮结派形成属于自己的部落，不同的部落之间则经常发生争斗。只是，这一切都成为谜团了——聪聪根本就不知道部落究竟是如何分布的。 不过好消息是，聪聪得到了一份荒岛的地图。地图上标注了 n 个野人居住的地点（可以看作是平面上的坐标）。我们知道，同一个部落的野人总是生活在附近。我们把两个部落的距离，定义为部落中距离最近的那两个居住点的距离。聪聪还获得了一个有意义的信息——这些野人总共被分为了 k 个部落！这真是个好消息。聪聪希望从这些信息里挖掘出所有部落的详细信息。他正在尝试这样一种算法： ...

题目背景 Imakf是一个小蒟蒻，他最近刚学了LCA，他在手机APP里看到一个游戏也叫做LCA就下载了下来。 题目描述 这个游戏会给出你一棵树，这棵树有NN个节点，根结点是RR，系统会选中MM个点P_1,P_2…P_M ，要Imakf回答有多少组点对(u_i,v_i)的最近公共祖先是P_i 。Imakf是个小蒟蒻，他就算学了LCA也做不出，于是只好求助您了。Imakf毕竟学过一点OI,所以他允许您把答案模 (10^9+7)( 9 +7) 输入格式 第一行 N , R , M 此后N-1行 每行两个数a,ba,b 表示a,ba,b之间有一条边 此后1行 M个数 表示P_i 输出格式 M行，每行一...

题目描述 A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。 现在有 q 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。 输入格式 第一行有两个用一个空格隔开的整数 n,m 表示 A 国有 n 座城市和 m 条道路。 接下来 m 行每行三个整数 x, y, z 每两个整数之间用一个空格隔开，表示从 x 号城市到 y 号城市有一条限重为 z 的道路。 注意：两座城市之间可能有多条道路 。 接下来一行有一个整数 q，表示有 q 辆货车需要运货。 接下来 q 行，每行两个整数 x,y，之间用一个空格隔开...

purfer 编码 purfer编码是一种无根树的表示方式，对于一棵无根树，有着为一的prufer编码。如何把一棵树转化成为purfer编码呢？我们用删点乱搞 的方式。在第i步时，移去所有叶子节点中标号最小的顶点和相连的边，并把与它相邻的点的编号加入Prufer序列中，重复以上步骤直到原图仅剩2个顶点。 将Prufer数列转化成树的方法： 设{a1,a2,…an-2}为一棵有n个节点的树的Prufer序列，另建一个集合G含有元素{1…n}，找出集合中最小的未在Prufer序列中出现过的数，将该点与Prufer序列中首项连一条边，并将该点和Prufer序列首项删除，重复操作n-2次，将集合中剩余...

题目描述 a180285 非常喜欢滑雪。他来到一座雪山，这里分布着 mm 条供滑行的轨道和 nn 个轨道之间的交点（同时也是景点），而且每个景点都有一编号 i\space (1 \le i \le n)i (1≤i≤n) 和一高度 h_ia180285 能从景点 i 滑到景点 j 当且仅当存在一条 i 和 j 之间的边，且 i 的高度不小于 j。与其他滑雪爱好者不同，a180285 喜欢用最短的滑行路径去访问尽量多的景点。如果仅仅访问一条路径上的景点，他会觉得数量太少。 于是 a18028 5拿出了他随身携带的时间胶囊。这是一种很神奇的药物，吃下之后可以立即回到上个经过的景点（不用移动也不被认...

题目描述 小C最近学了很多最小生成树的算法，Prim算法、Kurskal算法、消圈算法等等。正当小C洋洋得意之时，小P又来泼小C冷水了。小P说，让小C求出一个无向图的次小生成树，而且这个次小生成树还得是严格次小的，也就是说：如果最小生成树选择的边集是EM，严格次小生成树选择的边集是ES，那么需要满足：和严格小于 这下小 C 蒙了，他找到了你，希望你帮他解决这个问题。 输入格式 第一行包含两个整数N 和M，表示无向图的点数与边数。 接下来 M行，每行 3个数x y z 表示，点 x 和点y之间有一条边，边的权值为z。 输出格式 包含一行，仅一个数，表示严格次小生成树的边权和。(数据保证必定存在严...