17.2.12 听说二区又考试了

NOIP模拟题

题目名称	远征	化简	生产
源程序名	expedition	simplify	production
输入文件	expedition.in	simplify.in	production.in
输出文件	expedition.out	simplify.out	production.out
时间限制	1s	1s	1s
内存限制	128MB	128MB	24MB

2017年2月12日 8:00 – 11:15

说明：

1.考试时间为 3 小时 15 分钟

2.评测在Windows下进行

3.评测时不打开任何优化开关

远征

【题目描述】

寒枫将军将要带领他的部队去圣雪山消灭那里的冰龙。

部队分成了若干个小队，属于同一个小队的人兵种相同。寒枫将军有着杰出的指挥能力，在战斗的时候，寒枫将军能够让所有相同兵种的人互相配合，使t个相同兵种的人发挥出t²的战斗力；寒枫将军还能让不同兵种的人互相配合，使整个部队的战斗力是所有兵种战斗力的和。

例如，部队中有3个小队，分别是5个人的步兵小队，3个人的步兵小队，3个人的骑兵小队。那么步兵战斗力为64，骑兵战斗力为9，部队总战斗力为73。

寒枫将军需要知道他的部队的战斗力是多少。

【输入格式】

第一行一个整数n，表示小队数。接下来n行，第i行有两个整数a_i、b_i，表示这个小队有a_i个人，兵种为b_i。

【输出格式】

一行一个整数，部队的战斗力。

【样例输入】

5 1

3 1

3 2

【样例输出】

【数据规模与约定】

10%的数据，n=1

30%的数据，n≤1000

另有20%的数据，a_i=1

另有30%的数据，b_i≤1000

100%的数据，1≤n≤100000，1≤a_i≤10000，1≤b_i≤1,000,000,000

统计、相乘、求和、没毛病

化简

【题目描述】

给出一个表达式，包含数字、未知数x、“+”、“-”、“*”和括号。把它化简成a₀x⁰+a₁x¹+a₂x²+……+a_nxⁿ的形式。

【输入格式】

一行一个字符串，即表达式。

【输出格式】

第一行一个非负整数n，接下来n+1个数，其中第i行为a_i-1。由于a_i可能很大，对10007取模后输出。

若有多个n满足条件，输出最小的n。

【样例输入】

(x-2)*3+x

【样例输出】

10001

【数据规模与约定】

测试点	输入长度不超过	对于乘号	对于括号	对于未知数x
0	3		没有	没有
1	100		没有括号套括号的情况	没有
2	100	没有		没有
3	100			没有
4	1000			没有
5	1000	没有	没有
6	1000		没有
7	1000	没有
8	100		没有括号套括号的情况
9	1000

上表中没有填写的格子，表示数据在那一方面没有特殊限制。

保证输入的表达式合法。

保证表达式中出现的数字小于10007。

表达式中没有“6x”这种形式。即数字和未知数之间至少存在一个符号。

恶心、恶心、恶心，重要的事情说三遍

生产

【题目描述】

工厂为了生产一种复杂的产品，给各个生产部门制定了详细的生产计划。那么，就经常会有生产部门要把产品送到另一个生产部门作为原料。这是一个注重产品质量的工厂，所以每当有产品要从A部门运到B部门时，都要先从A部门送到质量检验处，检验合格后再从质量检验处运到B部门。

有些部门之间有传送带连接，厂长想知道每次将产品从一个部门运送到另一个部门最少需要多长时间。

【输入格式】

第一行两个整数n、m，n表示部门数量，m表示传送带数量。出于方便，1号部门是质量检验处。

接下来m行，每行三个整数u、v、w，表示有一条从u部门到v部门的传送带，传送过去需要w个单位时间。注意传送带是单向的。

接下来一个整数q，表示有q次运送。

接下来q行，每行两个数a、b，表示这一次要将产品从a部门运送到b部门。

【输出格式】

输出q行，每行一个整数，表示这次运送最少需要的时间。若没有传送方案，输出-1。

【样例输入】

5 5

1 2 3

1 3 5

4 1 7

5 4 1

5 3 1

4 2

5 3

2 3

【样例输出】

-1

【数据规模与约定】

30%的数据，n≤100，m≤500，w=1

60%的数据，n≤100，m≤5000

另20%的数据，q=1

100%的数据，2≤n≤3000，m≤100000，2≤a,b≤n，

q≤100000，1≤u,v≤n，1≤w≤10000

有些部门之间可能有多条传送带。

工厂的员工都非常尽职尽责，他们的认真和热情决定了产品的完美，所以不必考虑产品不合格的情况。

正边反边、两遍SPFA，O（1）查询没毛病