输入格式
输入的第一行为一个正整数n（1<=n<=10^5）——车的个数。 接下来n行，每行四个整数，第i行的数字: vi, ci,li ,ri ,（1<=vi<=10^4 , 1<=ci<=10^5,0<=li,ri<=10^5），车子们从1开始编号，从车队的最前头开始算起。 输出格式
第一行输出一个数k：会继续在这车队里的车的总数（注意我们的目标是让价值最大）。 第二行k个数，递增输出继续在车队里的车的编号。
请留心你不允许改变车的次序。如果答案不唯一，输出任意一个。 样例输入 5
1 1 0 3 1 1 1 2 1 1 2 1 1 1 3 0 2 1 3 0 样例输出 4
1 2 3 5 样例输入 5
1 1 0 3 10 1 2 1 2 2 1 1 10 1 1 2 3 1 3 0 样例输出 3
1 3 5 数据规模和约定
对于20%的数据，n<=100 对于50%的数据，n<=1000 对于100%的数据，n<=100000
对于100%的数据，1<=vi<=10^4 , 1<=ci<=10^5,0<=li,ri<=10^5
40. 算法训练 Maze
时间限制：1.0s 内存限制：256.0MB
31
问题描述
一个含有n个点的迷宫是一棵树（一个任意两点之间都恰好有一条路径的无向图）。每个点都有一定的概率成为这个迷宫的入口和出口。
从这个迷宫走出去的方法是从入口开始进行深度优先搜索。如果当前有多个移动方案，那么等概率的选择移动方案中的一个。DFS的过程为以下的伪代码： DFS(x)
if x == exit vertex then finish search flag[x] <- TRUE
random shuffle the vertices' order in V(x) // here all permutations have equal probability to be chosen for i <- 1 to length[V] do if flag[V[i]] = FALSE then count++; DFS(y);
count++;
V(x)是与x点相邻的点的序列。Flag数组初始时是全部为FALSE的。DFS 初始时从入口开始。当搜索结束时，变量count将会统计移动的次数。
你的任务是统计一个人从这个迷宫的入口走到出口步数的数学期望值。 输入格式
第一行一个数n，表示这个图的节点数。。
下面n-1行，每行包括两个数ai,bi，表示一条连接ai和bi的边。 保证给出的图是一棵树。
下面n行，每行包括两个非负整数xi,yi，表示选择i为入口的可能性和出口的可能性。
选择i为入口的概率和选择i为出口的概率分别为xi/sumx和yi/sumy，sumx表示x的总和，sumy表示y的总和。sumx以及sumy均为正数且不超过10^6。 输出格式
输出期望的步数，要求误差不超过10^-9。 样例输入 输入格式 2 1 2 0 1 1 0 输入格式
32
3 1 2 1 3 1 0 0 2 0 3 输入格式 7 1 2 1 3 2 4 2 5 3 6 3 7 1 1 1 1 1 1 1 1 1 1 1 1 1 1 样例输出 输出格式
1.00000000000000000000 输出格式
2.00000000000000000000 输出格式
4.04081632653 样例说明
第一个样例中，入口总是1，出口总是2。
第二个样例的入口总是1且出口有2/5的概率是2，3/5的概率是3。对于出口为2和3的数学期望是相同的（对称的情况），第一步有0.5的概率直接到达出口，0.5的概率走错到另一个点（然后再走两步到终点）。所以数学期望等于2/5*(1*0.5+3*0.5)+3/5*(1*0.5+3*0.5) = 2。
数据规模和约定
33
20% 的数据n <= 100 50% 的数据n <= 1000 70% 的数据n <= 10000 100%的数据n <= 100000
41. 算法训练 Entertaining Geodetics
时间限制：2.0s 内存限制：256.0MB
问题描述
在此游戏中地图被分为了许多叫作Geo格的正方形方格，其中一些被涂上色，假设没有涂色的为透明色。
地图中还有些Geo符号，它们样子像不同颜色的金字塔（包括透明Geo符号）。每个Geo符号都坐落在Geo格上，每个Geo格上最多一个Geo符号。
Geo符号可以被消除。为了更好地理解Geo符号在消除时发生了什么，这里引入把刚消除的Geo符号放入的队列。
从队列中取出Geo符号，观察包含Geo符号的Geo格的颜色，如果它不是透明的且颜色不同于Geo符号，则把所有这个颜色的Geo格重新涂为Geo符号的颜色（透明的Geo符号则为透明色）。重涂色是在一个无限大的区域从那个有符号的Geo格子开始螺旋状进行的。
.
换句话说，我们选择所有需要重涂色的方格找到它们在以有符号格为中心的无限螺旋表格中所对应的数字。此后按数字的增加顺序我们对其重染色。
如果在重染色时遇到一个格子包含另一个Geo符号的情况则将Geo符号移出并放置在队列尾部。
当重染色结束后Geo符号彻底消失，并且队列中下一个Geo符号（如果有）将取出，重复此操作直至队列为空。 为了更好地理解请看一个例子。
你知道所有格子的颜色、所有符号的位置。计算出队列里符号彻底消失时所造成的重染色次数。
推荐使用I64d输出。 输入格式
34
第一行包含两个数n，m(1<=n，m<=300)—地图的高和宽。 接下来n行每行m个数—格子的颜色。
接下来n行每行m个数—对符号的描述，-1表示没有符号，否则数字代表符号的颜色。 所有颜色都是属于0到10^9的整数，0表示透明。
最后一行两个数x，y(1<=x<=n，1<=y<=m)—需要消除的Geo符号的行和列位置。行从上到下标记，列从左往右标记，从1开始。保证位置(x，y)包含一个符号。 输出格式
一行一个数—符号消除时重染色次数。 样例输入
5 5
9 0 1 1 0 0 0 3 2 0 1 1 1 3 0 1 1 1 3 0 0 1 2 0 3 -1 1 -1 3 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 2 3 -1 -1 -1 -1 -1 -1 2 4 2 样例输出 35 样例说明
42. 算法训练特殊的数字四十
时间限制：1.0s 内存限制：256.0MB
特殊的数字四十
35