算法训练 关联矩阵  
时间限制：1.0s   内存限制：512.0MB
   
问题描述
　　有一个n个结点m条边的有向图，请输出他的关联矩阵。
输入格式
　　第一行两个整数n、m，表示图中结点和边的数目。n<=100,m<=1000。
　　接下来m行，每行两个整数a、b，表示图中有(a,b)边。
　　注意图中可能含有重边，但不会有自环。
输出格式
　　输出该图的关联矩阵，注意请勿改变边和结点的顺序。
样例输入
5 9
1 2
3 1
1 5
2 5
2 3
2 3
3 2
4 3
5 4
样例输出
1 -1 1 0 0 0 0 0 0
-1 0 0 1 1 1 -1 0 0
0 1 0 0 -1 -1 1 -1 0
0 0 0 0 0 0 0 1 -1
0 0 -1 -1 0 0 0 0 1

  算法训练 送分啦   时间限制：1.0s   内存限制：512.0MB     问题描述　　这题想得分吗？想，请输出“yes”；不想，请输出“no”。输出格式　　输出包括一行，为“yes”或“no”。

  算法训练 操作格子  
时间限制：1.0s   内存限制：256.0MB
   
问题描述

有n个格子，从左到右放成一排，编号为1-n。

共有m次操作，有3种操作类型：

1.修改一个格子的权值，

2.求连续一段格子权值和，

3.求连续一段格子的最大值。

对于每个2、3操作输出你所求出的结果。
输入格式

第一行2个整数n，m。

接下来一行n个整数表示n个格子的初始权值。

接下来m行，每行3个整数p,x,y，p表示操作类型，p=1时表示修改格子x的权值为y，p=2时表示求区间[x,y]内格子权值和，p=3时表示求区间[x,y]内格子最大的权值。
输出格式

有若干行，行数等于p=2或3的操作总数。

每行1个整数，对应了每个p=2或3操作的结果。
样例输入
4 3
1 2 3 4
2 1 3
1 4 3
3 1 4
样例输出
6
3
数据规模与约定

对于20%的数据n <= 100，m <= 200。

对于50%的数据n <= 5000，m <= 5000。

对于100%的数据1 <= n <= 100000，m <= 100000，0 <= 格子权值 <= 10000。

  算法训练 逆序对   时间限制：1.0s   内存限制：256.0MB     问题描述 Alice是一个让人非常愉跃的人!他总是去学习一些他不懂的问题，然后再想出许多稀奇古怪的题目。这几天，Alice又沉浸在逆序对的快乐当中， 他已近学会了如何求逆序对对数，动态维护逆序对对数等等题目，他认为把这些题让你做简直是太没追求了，于是，经过一天的思考和完善，Alice终于拿出了 一道他认为差不多的题目：
有一颗2n-1个节点的二叉树，它有恰好n个叶子节点，每个节点上写了一个整数。如果将这棵树的所有叶子节点上的数从左到右写下来，便得到一个序列 a[1]…a[n]。现在想让这个序列中的逆序对数量最少，但唯一的操作就是选树上一个非叶子节点，将它的左右两颗子树交换。他可以做任意多次这个操作。 求在最优方案下，该序列的逆序对数最少有多少。
Alice自己已近想出了题目的正解，他打算拿来和你分享，他要求你在最短的时间内完成。
输入格式 第一行一个整数n。
下面每行，一个数x。
如果x=0，表示这个节点非叶子节点，递归地向下读入其左孩子和右孩子的信息，如果x≠0，表示这个节点是叶子节点，权值为x。
输出格式 输出一个整数，表示最少有多少逆序对。 样例输入 3
0
0
3
1
2 样例输出 1 数据规模与约定 对于20%的数据，n <= 5000。
对于100%的数据，1 <= n <= 200000，0 <= a[i]<2^31。

  算法训练 安慰奶牛   时间限制：1.0s   内存限制：256.0MB     问题描述 Farmer John变得非常懒，他不想再继续维护供奶牛之间供通行的道路。道路被用来连接N个牧场，牧场被连续地编号为1到N。每一个牧场都是一个奶牛的家。FJ计 划除去P条道路中尽可能多的道路，但是还要保持牧场之间 的连通性。你首先要决定那些道路是需要保留的N-1条道路。第j条双向道路连接了牧场Sj和Ej(1 <= Sj <= N; 1 <= Ej <= N; Sj != Ej)，而且走完它需要Lj的时间。没有两个牧场是被一条以上的道路所连接。奶牛们非常伤心，因为她们的交通系统被削减了。你需要到每一个奶牛的住处去安慰她们。每次你到达第i个牧场的时候(即使你已经到过)，你必须花去Ci的 时间和奶牛交谈。你每个晚上都会在同一个牧场(这是供你选择的)过夜，直到奶牛们都从悲伤中缓过神来。在早上 起来和晚上回去睡觉的时候，你都需要和在你睡觉的牧场的奶牛交谈一次。这样你才能完成你的 交谈任务。假设Farmer John采纳了你的建议，请计算出使所有奶牛都被安慰的最少时间。
输入格式 第1行包含两个整数N和P。
接下来N行，每行包含一个整数Ci。
接下来P行，每行包含三个整数Sj, Ej和Lj。
输出格式 输出一个整数, 所需要的总时间(包含和在你所在的牧场的奶牛的两次谈话时间)。 样例输入 5 7
10
10
20
6
30
1 2 5
2 3 5
2 4 12
3 4 17
2 5 15
3 5 6 样例输出 176 数据规模与约定 5 <= N <= 10000，N-1 <= P <= 100000，0 <= Lj <= 1000，1 <= Ci <= 1,000。

  算法训练 最短路   时间限制：1.0s   内存限制：256.0MB     问题描述 给定一个n个顶点，m条边的有向图（其中某些边权可能为负，但保证没有负环）。请你计算从1号点到其他点的最短路（顶点从1到n编号）。
输入格式 第一行两个整数n, m。
接下来的m行，每行有三个整数u, v, l，表示u到v有一条长度为l的边。
输出格式 共n-1行，第i行表示1号点到i+1号点的最短路。 样例输入 3 3
1 2 -1
2 3 -1
3 1 2 样例输出 -1
-2 数据规模与约定 对于10%的数据，n = 2，m = 2。
对于30%的数据，n <= 5，m <= 10。
对于100%的数据，1 <= n <= 20000，1 <= m <= 200000，-10000 <= l <= 10000，保证从任意顶点都能到达其他所有顶点。

  算法训练 结点选择   时间限制：1.0s   内存限制：256.0MB     问题描述 有一棵 n 个节点的树，树上每个节点都有一个正整数权值。如果一个点被选择了，那么在树上和它相邻的点都不能被选择。求选出的点的权值和最大是多少？
输入格式 第一行包含一个整数 n 。
接下来的一行包含 n 个正整数，第 i 个正整数代表点 i 的权值。
接下来一共 n-1 行，每行描述树上的一条边。
输出格式 输出一个整数，代表选出的点的权值和的最大值。 样例输入 5
1 2 3 4 5
1 2
1 3
2 4
2 5 样例输出 12 样例说明 选择3、4、5号点，权值和为 3+4+5 = 12 。 数据规模与约定 对于20%的数据， n <= 20。
对于50%的数据， n <= 1000。
对于100%的数据， n <= 100000。
权值均为不超过1000的正整数。

  算法训练 K好数   时间限制：1.0s   内存限制：256.0MB     问题描述 如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字，那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K = 4，L = 2的时候，所有K好数为11、13、20、22、30、31、33 共7个。由于这个数目很大，请你输出它对1000000007取模后的值。
输入格式 输入包含两个正整数，K和L。
输出格式 输出一个整数，表示答案对1000000007取模后的值。 样例输入 4 2 样例输出 7 数据规模与约定 对于30%的数据，KL <= 106；
对于50%的数据，K <= 16， L <= 10；
对于100%的数据，1 <= K,L <= 100。

  算法训练 最大最小公倍数   时间限制：1.0s   内存限制：256.0MB     问题描述 已知一个正整数N，问从1~N中任选出三个数，他们的最小公倍数最大可以为多少。
输入格式 输入一个正整数N。
输出格式 输出一个整数，表示你找到的最小公倍数。 样例输入 9 样例输出 504 数据规模与约定 1 <= N <= 106。

  算法训练 区间k大数查询   时间限制：1.0s   内存限制：256.0MB     问题描述 给定一个序列，每次询问序列中第l个数到第r个数中第K大的数是哪个。
输入格式 第一行包含一个数n，表示序列长度。
第二行包含n个正整数，表示给定的序列。
第三个包含一个正整数m，表示询问个数。
接下来m行，每行三个数l,r,K，表示询问序列从左往右第l个数到第r个数中，从大往小第K大的数是哪个。序列元素从1开始标号。
输出格式 总共输出m行，每行一个数，表示询问的答案。 样例输入 5
1 2 3 4 5
2
1 5 2
2 3 2 样例输出 4
2 数据规模与约定 对于30%的数据，n,m<=100；
对于100%的数据，n,m<=1000；
保证k<=(r-l+1)，序列中的数<=10^6。