题目描述 Description#

有一位使者要游历各国，他每到一个国家，都能学到一种文化，但他不愿意学习任何一种文化超过一次（即如果他学习了某种文化，则他就不能到达其他有这种文化的国家）。不同的国家可能有相同的文化。不同文化的国家对其他文化的看法不同，有些文化会排斥外来文化（即如果他学习了某种文化，则他不能到达排斥这种文化的其他国家）。

现给定各个国家间的地理关系，各个国家的文化，每种文化对其他文化的看法，以及这位使者游历的起点和终点（在起点和终点也会学习当地的文化），国家间的道路距离，试求从起点到终点最少需走多少路。

输入描述 Input Description#

第一行为五个整数$N$，$K$，$M$，$S$，$T$，每两个整数之间用一个空格隔开，依次代表国家个数（国家编号为$1$到$N$），文化种数（文化编号为$1$到$K$），道路的条数，以及起点和终点的编号（保证$S$不等于$T$）；

第二行为$N$个整数，每两个整数之间用一个空格隔开，其中第$i$个数$C_i$，表示国家 i 的文化为$C_i$。

接下来的$K$行，每行$K$个整数，每两个整数之间用一个空格隔开，记第 i 行的第 j 个数为$a_i,j$，$a_i,j = 1$表示文化$i$排斥外来文化$j$（$i$等于$j$时表示排斥相同文化的外来人），$a_i,j = 0$表示不排斥（注意$i$排斥$j$并不保证$j$一定也排斥 i）。

接下来的$M$行，每行三个整数$u$，$v$，$d$，每两个整数之间用一个空格隔开，表示国家 u 与国家 v 有一条距离为$d$的可双向通行的道路（保证$u$不等于$v$，两个国家之间可能有多条道路）。

输出描述 Output Description#

输出只有一行，一个整数，表示使者从起点国家到达终点国家最少需要走的距离数（如果无解则输出$-1$）。

样例输入 Sample Input#

1
2 2 1 1 2
2
1 2 0 1 1 0 1 2 10

1
2 2 1 1 2
2
1 2 0 1 0 0 1 2 10

样例输出 Sample Output#

1
-1

1
10

数据范围及提示 Data Size & Hint#

【问题描述】#

每天，农夫约翰的$N$（$1\le N\le 50000$）头奶牛总是按同一顺序排好队，有一天，约翰决定让一些牛玩一场飞盘游戏（Ultimate Frisbee），他决定在队列里选择一群位置连续的奶牛进行比赛，为了避免比赛结果过于悬殊，要求挑出的奶牛身高不要相差太大。

约翰准备了$Q$（$1\le Q\le 200000$）组奶牛选择，并告诉你所有奶牛的身高$H_i$（$1\le H_i\le 10^6$）。他想知道每组里最高的奶牛和最矮的奶牛身高差是多少。

注意：在最大的数据上，输入输出将占据大部分时间。

【输入】#

第一行，两个用空格隔开的整数$N$和$Q$。

第$2$到第$N+1$行，每行一个整数，第$i+1$行表示第$i$头奶牛的身高$H_i$

第$N+2$到第$N+Q+1$行，每行两个用空格隔开的整数$A$和$B$，表示选择从$A$到$B$的所有牛（$1 \le A \le B \le N$）

【输出】#

共$Q$行，每行一个整数，代表每个询问的答案。

1
6 3
2
1
3
7
4
3
5
4
6
2
7
5
8
1 5
9
4 6
10
2 2

1
6
2
3
3
0

1
for (int i = 1; i <= q; i++)
2
{
3
  scanf("%d%d", &a, &b);
4
  int min = INT_MAX, max = INT_MIN;
5
  for (int i = a; i <= b; i++)
6
  {
7
    if (h[i] < min)
8
      min = h[i];
9
    if (h[i] > max)
10
      max = h[i];
11
  }
12
  printf("%d\n", max - min);
13
}

题目描述 Description#

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

输入描述 Input Description#

输入第一行有两个整数 T（1<=T<=1000）和 M（1<=M<=100），用一个空格隔开，T 代表总共能够用来采药的时间，M 代表山洞里的草药的数目。接下来的 M 行每行包括两个在 1 到 100 之间（包括 1 和 100）的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出描述 Output Description#

输出包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

样例输入 Sample Input#

1
70 3
2
71 100
3
69 1
4
1 2

样例输出 Sample Output#

1
3

数据范围及提示 Data Size & Hint#

对于$30\%$的数据，$M\le 10$；

对于全部的数据，$M\le 100$。

这题的方法很简单。我们瞄准$30\%$的数据来做，可以用 DFS 枚举方案，然后模拟计算出最优解。附一个大致的代码：

1
void DFS(int d, int c)
2
{
3
  if (d == n)
4
  {
5
    if (c > ans)
6
      ans = c;
7
    return;
8
  }
9
  DFS(d + 1, c + w[i]);
10
  DFS(d + 1, c);
11
}

【问题描述】#

皇军侵占了通往招远的黄金要道。为了保护渤海通道的安全，使得黄金能够顺利地运送到敌后战略总指挥地延安，从而购买战需武器，所以我们要通过你的程序确定这条战略走廊是否安全。

已知我们有$N$座小岛，只有使得每一个小岛都能与其他任意一个小岛联通才能保证走廊的安全。每个小岛之间只能通过若干双向联通的桥保持联系，已知有$M$座桥($A_i$,$B_i$)表示第 i 座桥连接了$A_i$与$B_i$这两座城市。

现在，敌人的炸药只能炸毁其中一座桥，请问在仅仅炸毁这一座桥的情况下，能否保证所有岛屿安全，都能联通起来。

现在给出$Q$个询问$C_i$，其中$C_i$表示桥梁编号，桥梁的编号按照输入顺序编号。每个询问表示在仅仅炸毁第$C_i$座桥的情况下能否保证所有岛屿安全。如果可以，在输出文件当中，对应输入顺序输出yes，否则输出no（输出为半角英文单词，区分大小写，默认为小写，不含任何小写符号，每行输出一个空格，忽略文末空格）。

【输入格式】#

第一行 三个整数$N$，$M$，$Q$，分别表示岛屿的个数，桥梁的个数和询问的个数。

第二行到第$M+1$行 每行两个整数。第$i+1$行有两个整数$A_i$，$B_i$表示这个桥梁的属性。

第$M+2$行 有$Q$个整数$Ci$表示查询。

【输出格式】#

$Q$行，表示查询结果。

1
2 1 1
2
1
3
2
4
1

1
no

题目描述 Description#

栈是计算机中经典的数据结构，简单的说，栈就是限制在一端进行插入删除操作的线性表。

栈有两种最重要的操作，即 pop（从栈顶弹出一个元素）和 push（将一个元素进栈）。

栈的重要性不言自明，任何一门数据结构的课程都会介绍栈。宁宁同学在复习栈的基本概念时，想到了一个书上没有讲过的问题，而他自己无法给出答案，所以需要你的帮忙

宁宁考虑的是这样一个问题：一个操作数序列，从 1，2，一直到 n（图示为 1 到 3 的情况），栈 A 的深度大于 n。

现在可以进行两种操作，

1.将一个数，从操作数序列的头端移到栈的头端（对应数据结构栈的 push 操作）

将一个数，从栈的头端移到输出序列的尾端（对应数据结构栈的 pop 操作） 使用这两种操作，由一个操作数序列就可以得到一系列的输出序列，下图所示为由 1 2 3 生成序列 2 3 1 的过程。（原始状态如上图所示） 。

你的程序将对给定的 n，计算并输出由操作数序列 1，2，…，n 经过操作可能得到的输出序列的总数。

输入描述 Input Description#

输入文件只含一个整数 n（1≤n≤18）

输出描述 Output Description#

输出文件只有一行，即可能输出序列的总数目

样例输入 Sample Input#

3 样例输出 Sample Output#

5

这题看似复杂，但数据范围太小，N<=18。所以，骗分程序就好写了：

int a[18]={1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845,35357670,129644790,477638700};

scanf(“%d”,&n):

printf(“%d”,ans[n-1]);

测试结果不言而喻，AC 了。

学完这一章，你已基本掌握了骗分技巧。下面的内容涉及一点算法知识，难度有所增加。蒟蒻中的蒟蒻可以止步于此了。

【问题描述】#

2013 年的 NOIP 结束后， Smart 发现自己又被题目碾压了，心里非常地不爽，于是

暗下决心疯狂地刷数学题目，做到天昏地暗、废寝忘食，准备在今年的中考中大展身手。

有一天，他在做题时发现了一个有趣的问题：

给定 n 个二元组(ai, bi) i)，记函数：

y=100*sigma(ai)/sigma(bi);

将函数 y 的值四舍五入取整。

现将 n 个二元组去掉其中的 k 个计算一个新的 y 值（也四舍五入取整），均能满足：y <= z ，求出最小的 z 值。Smart 想让你帮他一起找出最小的 z 值。

【输入格式】#

输入包含多组测试数据。每组测试数据第一行两个整数：n 和 k；第二行为 n 个数：

a1 a2 …… an；第三行为；n 个数： b1 b2 …… bn。

输入数据当 n、k 均为 0 时结束。

【输出格式】#

对于每组测试数据输出一行，即找出的最小的冘值。

注意：为避免精度四舍五入出现误差，测试点保证每个函数值与最终结果的差值至

少为 0.001 。

【样例】#

math.in

3 1 5 0 1 5 1 6 4 2 1 2 7 9

5 6 7 9

0 0 math. out

83 100 【数据范围】#

对于 40% 的数据： n≤20；

对于 70% 的数据： n≤1000；

对于 100% 的数据： n≤10000，ai,bi 都在 int 范围内。

这题让人望而生畏，但我们有贪心的手段。每个二元组的 a 值是乘到答案中的，所以 a 越大越好，那么只要选择出最小的 k 个去掉即可。代码就不写了，因为这个设计到下一章的内容：排序。

此代码得$20$分。