1 CCF之任务调度：
| 试题编号： | 201403-5 |
| 试题名称： | 任务调度 |
| 时间限制： | 1.0s |
| 内存限制： | 256.0MB |
| 问题描述： |
问题描述
有若干个任务需要在一台机器上运行。它们之间没有依赖关系,因此 可以被按照任意顺序执行。
该机器有两个 CPU 和一个 GPU。对于每个任务,你可以为它分配不 同的硬件资源: 1. 在单个 CPU 上运行。 2. 在两个 CPU 上同时运行。 3. 在单个 CPU 和 GPU 上同时运行。 4. 在两个 CPU 和 GPU 上同时运行。 一个任务开始执行以后,将会独占它所用到的所有硬件资源,不得中 断,直到执行结束为止。第 i 个任务用单个 CPU,两个 CPU,单个 CPU 加 GPU,两个 CPU 加 GPU 运行所消耗的时间分别为 a i,b i,c i 和 d i。 现在需要你计算出至少需要花多少时间可以把所有给定的任务完成。
输入格式
输入的第一行只有一个正整数 n(1 ≤ n ≤ 40), 是总共需要执行的任 务个数。
接下来的 n 行每行有四个正整数 a i, b i, c i, d i(a i, b i, c i, d i 均不超过 10), 以空格隔开。
输出格式
输出只有一个整数,即完成给定的所有任务所需的最少时间。
样例输入
3
4 4 2 2 7 4 7 4 3 3 3 3
样例输出
7
样例说明
有很多种调度方案可以在 7 个时间单位里完成给定的三个任务,以下是其中的一种方案:
同时运行第一个任务(单 CPU 加上 GPU)和第三个任务(单 CPU), 它们分别在时刻 2 和时刻 3 完成。在时刻 3 开始双 CPU 运行任务 2,在 时刻 7 完成。 |
| 试题编号： | 201409-5 |
| 试题名称： | 拼图 |
| 时间限制： | 3.0s |
| 内存限制： | 256.0MB |
| 问题描述： |
问题描述
给出一个n×m的方格图，现在要用如下L型的积木拼到这个图中，使得方格图正好被拼满，请问总共有多少种拼法。其中，方格图的每一个方格正好能放积木中的一块。积木可以任意旋转。
输入格式
输入的第一行包含两个整数n, m，表示方格图的大小。
输出格式
输出一行，表示可以放的方案数，由于方案数可能很多，所以请输出方案数除以1,000,000,007的余数。
样例输入
6 2
样例输出
4
样例说明
四种拼法如下图所示：
评测用例规模与约定
在评测时将使用10个评测用例对你的程序进行评测。
评测用例1和2满足：1<=n<=30，m=2。 评测用例3和4满足：1<=n, m<=6。 评测用例5满足：1<=n<=100，1<=m<=6。 评测用例6和7满足：1<=n<=1000，1<=m<=6。 评测用例8、9和10满足：1<=n<=10^15，1<=m<=7。 |
3 CCF之货物调度：
| 试题编号： | 201412-5 |
| 试题名称： | 货物调度 |
| 时间限制： | 1.0s |
| 内存限制： | 256.0MB |
| 问题描述： |
问题描述
某公司要处理一个周期性的物流问题。
有n个城市，第i个城市在每周的第j(1≤j≤7) 天会生产a ij吨某种货物，同时需要消耗b ij吨该种货物。已知每周的产量等于消耗量（即a ij之和等于b ij之和）。 城市之间有m条道路，第k条道路连接了城市s k和t k。一条道路上运输1吨货物有一个固定的成本c k。道路都可以双向使用。每天运输的货物量没有限制。城市之间的距离并不远，货物可以从任意一个城市运输到任意另一个城市并且在当天到达。 货物如果在当天没有被消耗掉，就需要存放在仓库里过夜。第i个城市的仓库容量为v i，存放1 吨货物过一夜所需的成本是w i。 请你计算该公司如果每周循环性地按照一个固定的流程调度货物的话，该公司在最优方案下每周需要为货物的运输和存储消耗多少成本。
输入格式
输入的第一行有两个正整数n和m，即城市的个数和道路的条数。
接下来有n行，每行包含16个整数，用以描述第i个城市的相关数据。其中第i行包含的数为a i1, a i2, a i3, a i4, a i5, a i6, a i7, b i1, b i2, b i3, b i4, b i5, b i6, b i7, v i, w i。 接下来有m行，每行包含3个整数，用以描述一条道路的相关数据。其中第k行包含的数为s k, t k和c k。 输入数据中城市的编号均为1到n之间。输入数据的每行的行首行尾均保证没有空格，两个数之间恰好被一个空格隔开。
输出格式
你只需要输出一个数，即最优方案下每周的支出。
样例输入
3 3
0 0 0 0 5 0 0 0 0 0 0 0 0 0 2 4 0 0 0 0 0 0 0 2 0 0 0 0 0 0 2 1 0 0 0 0 0 0 0 0 0 3 0 0 0 0 2 5 1 2 1 1 3 5 2 3 1
样例输出
67
样例说明
城市1 每周五生产5 吨货物，把其中2 吨运到存储费用低廉的城市2 存储，把1 吨运到城市3 存储，剩下的2 吨留在城市1。
在次周一的时候城市2 会消耗掉存放在那里的2 吨货物。为了节约存储成本，将囤放在城市1 的货物运到城市2 存放。周三再将所有货物运到城市3 以满足该城市的需求。 在此方案下，每周的运输成本为8，每周的存储成本为59，因此每周的总支出为67。
评测用例规模与约定
对于100%的数据，1≤n≤100，1≤m≤500，0≤a
ij,b
ij,v
i≤100，1≤w
i,c
k≤100。
|
4 CCF之最小花费：
| 试题编号： | 201503-5 |
| 试题名称： | 最小花费 |
| 时间限制： | 4.0s |
| 内存限制： | 256.0MB |
| 问题描述： |
问题描述
C国共有n个城市。有n-1条双向道路，每条道路连接两个城市，任意两个城市之间能互相到达。小R来到C国旅行，他共规划了m条旅行的路线，第i条旅行路线的起点是s
i，终点是t
i。在旅行过程中，小R每行走一单位长度的路需要吃一单位的食物。C国的食物只能在各个城市中买到，而且不同城市的食物价格可能不同。
然而，小R不希望在旅行中为了购买较低价的粮食而绕远路，因此他总会选择最近的路走。现在，请你计算小R规划的每条旅行路线的最小花费是多少。
输入格式
第一行包含2个整数n和m。
第二行包含n个整数。第i个整数w i表示城市i的食物价格。 接下来n-1行，每行包括3个整数u, v, e，表示城市u和城市v之间有一条长为e的双向道路。 接下来m行，每行包含2个整数s i和t i，分别表示一条旅行路线的起点和终点。
输出格式
输出m行，分别代表每一条旅行方案的最小花费。
样例输入
6 4
1 7 3 2 5 6 1 2 4 1 3 5 2 4 1 3 5 2 3 6 1 2 5 4 6 6 4 5 6
样例输出
35
16 26 13
样例说明
对于第一条路线，小R会经过2->1->3->5。其中在城市2处以7的价格购买4单位粮食，到城市1时全部吃完，并用1的价格购买7单位粮食，然后到达终点。
评测用例规模与约定
前10%的评测用例满足：n, m ≤ 20, w
i ≤ 20；
前30%的评测用例满足：n, m ≤ 200； 另有40%的评测用例满足：一个城市至多与其它两个城市相连。 所有评测用例都满足：1 ≤ n, m ≤ 10 5，1 ≤ w i ≤ 10 6，1 ≤ e ≤ 10000。 |
| 试题编号： | 201604-5 | ||||||||||||||||||||||||||||||||||||||||||||
| 试题名称： | 网络连接 | ||||||||||||||||||||||||||||||||||||||||||||
| 时间限制： | 5.0s | ||||||||||||||||||||||||||||||||||||||||||||
| 内存限制： | 256.0MB | ||||||||||||||||||||||||||||||||||||||||||||
| 问题描述： |
问题描述
某校新建的大楼中有n台设备，学校需要利用这些设备搭建一个网络。我们用1到n的整数给这些设备编号。
这些设备之间一共可以建立m条连线，建立每条连线会消耗一定的费用。连接建立后两台设备就可以相互通信了。两台设备可以借助其他设备进行通信，即通信关系可传递：如果设备A和设备B都能与设备C相互通信，那么设备A和设备B也能相互通信。 由于大楼的拓扑结构所限，可以建立连线的两台设备，一定满足其编号之差的绝对值不超过p。 这n台设备中的一部分属于用户设备。学校要求在最终的网络中，用户设备必须两两能够相互通信，其他设备则可以根据需要选择连线或不连线。 现在问要达到学校的要求最少要消耗多少的费用。
输入格式
输入的第一行包含一个正整数T，表示数据的组数，保证T=5。接下来依次描述每组数据。
每组数据的第一行包含3个正整数n, m, p，表示设备的总数，可以建立的连线数量和拓扑结构的参数。 第二行包含一个长度为n的01字符串，依次表示这n台设备是否为用户设备；为1表示是，为0表示不是。相邻字符之间无空格隔开，保证不会出现除了0和1之外的字符。保证至少有2个设备是用户设备。 接下来m行，每行包含3个非负整数u, v, w，表示设备u和设备v可以消耗w的费用建立连线。其中0 < u < v ≤ n，v – u ≤ p，w ≤ 10 6。 除第二行外，所有的数之间用一个空格隔开。 保证两台设备之间最多只有一条可以建立的连线，保证至少存在一种方案能够满足学校的要求。
输出格式
对于每组数据，输出一行一个整数，表示能达到要求所需的最少费用。
样例输入
1
20 11 6 10000100001100000000 1 6 300 1 3 100 3 6 100 4 10 100 4 6 100 6 10 400 10 15 100 11 15 100 10 11 500 12 15 100 15 20 100
样例输出
700
样例说明
用户设备分别是1、6、11、12。最优的方案需要选择以下连线：设备1和3，费用100；设备3和6，费用100；设备4和6，费用100；设备4和10，费用100；设备10和15，费用100；设备11和15，费用100；设备12和15，费用100。共计700。
子任务
每个测试点的每组数据分别都满足以下限制（其中c表示用户设备总数）：
样例输入
5
20 93 6 11111111111111111111 1 2 727765 2 3 263881 1 4 514909 2 4 131844 3 4 933178 1 5 438613 2 5 603733 3 5 859906 4 5 38725 1 6 599082 2 6 225184 3 6 365575 4 6 126126 5 6 25505 2 7 546601 3 7 63931 4 7 419406 5 7 531790 6 7 265271 2 8 724126 3 8 163879 4 8 59317 5 8 545880 6 8 126779 7 8 938859 4 9 387231 5 9 600880 6 9 927742 7 9 56690 8 9 987324 4 10 23106 5 10 328383 6 10 757082 7 10 787341 8 10 218539 9 10 282814 5 11 506005 6 11 257575 7 11 524808 8 11 223439 9 11 402018 10 11 580131 6 12 711292 7 12 314072 8 12 752595 9 12 141042 10 12 339498 11 12 321201 7 13 100337 8 13 969444 9 13 683912 10 13 973527 11 13 776443 12 13 436444 8 14 826460 9 14 453950 10 14 231374 11 14 667343 13 14 754318 10 15 46540 11 15 741941 12 15 909374 13 15 901791 14 15 246817 10 16 34192 11 16 866848 12 16 488324 13 16 824636 14 16 319615 15 16 472537 11 17 661823 12 17 595773 13 17 912773 14 17 674733 15 17 880787 16 17 168668 12 18 621903 13 18 894662 14 18 994829 15 18 80344 16 18 343121 17 18 697098 13 19 569872 14 19 599332 15 19 417377 16 19 837022 18 19 270641 14 20 748579 15 20 724926 16 20 367572 17 20 103857 18 20 443540 19 20 932348 20 92 6 00000010000000001000 1 2 113099 1 3 587351 2 3 209419 1 4 412024 2 4 526550 3 4 74575 1 5 627809 2 5 488889 3 5 78667 4 5 853953 1 6 914999 2 6 60305 3 6 52666 4 6 39394 5 6 243622 1 7 843636 2 7 752452 3 7 206953 4 7 209536 5 7 105503 6 7 179097 2 8 938375 3 8 449664 4 8 464591 5 8 312120 6 8 943383 7 8 798642 3 9 759837 4 9 655902 5 9 367024 6 9 560174 7 9 421235 8 9 552637 4 10 251605 5 10 453809 6 10 942947 7 10 378285 8 10 944748 9 10 761726 5 11 7926 6 11 237034 8 11 860297 9 11 224152 10 11 62671 7 12 518894 9 12 265459 10 12 399585 11 12 16993 7 13 935813 8 13 675125 9 13 986248 10 13 801332 11 13 775825 12 13 483974 8 14 879925 9 14 568657 10 14 539371 11 14 392819 12 14 673171 13 14 593981 9 15 893512 10 15 459005 11 15 935151 13 15 984026 14 15 352506 10 16 847405 11 16 902823 12 16 924659 14 16 31185 15 16 83802 11 17 225697 12 17 697702 13 17 431672 14 17 934227 15 17 64055 16 17 714592 12 18 429691 13 18 69217 16 18 916446 17 18 859123 13 19 675753 14 19 427831 15 19 3386 16 19 179655 17 19 148897 18 19 307554 14 20 291004 15 20 497622 16 20 669001 17 20 742221 18 20 662204 19 20 966218 20 93 6 00000101001110000010 1 2 710445 1 3 390108 2 3 871795 1 4 323940 2 4 1557 3 4 853515 1 5 987497 2 5 791951 3 5 565856 4 5 401932 1 6 49223 2 6 59889 3 6 300678 4 6 123895 5 6 160344 1 7 196308 3 7 787087 5 7 224478 6 7 104395 3 8 344509 4 8 173377 5 8 100930 7 8 544113 3 9 475119 4 9 673881 5 9 234187 6 9 191885 7 9 35559 8 9 872991 4 10 339910 5 10 624600 6 10 442925 7 10 821981 8 10 805172 9 10 463188 5 11 745511 6 11 444346 7 11 856170 8 11 10706 9 11 582739 10 11 666926 6 12 838187 7 12 711050 8 12 386931 9 12 886249 10 12 356669 11 12 14156 7 13 339092 8 13 578454 9 13 195419 10 13 600017 11 13 504670 12 13 753722 8 14 219160 9 14 281523 10 14 730539 11 14 890253 12 14 789909 13 14 995665 9 15 227552 10 15 125146 11 15 737706 12 15 697809 13 15 753633 14 15 248107 10 16 15962 11 16 178154 12 16 586355 13 16 32073 14 16 912542 15 16 913266 11 17 158548 12 17 35601 14 17 818081 15 17 39970 16 17 330500 12 18 207654 13 18 729538 14 18 642935 15 18 73734 16 18 676418 17 18 455930 13 19 945333 15 19 723755 16 19 67978 17 19 128589 18 19 647790 14 20 294150 15 20 681124 16 20 749167 17 20 480962 18 20 133266 19 20 928077 20 34 2 10000111010111001100 1 2 175025 1 3 372293 2 3 723523 2 4 828462 3 4 96614 3 5 496039 4 5 435856 4 6 728072 5 6 26736 5 7 658831 6 7 294479 6 8 971178 7 8 755365 7 9 467364 8 9 912893 8 10 88692 9 10 132051 9 11 939008 10 11 986048 11 12 676052 11 13 287187 12 13 304051 13 14 305223 14 15 610873 14 16 540274 15 16 494014 15 17 90777 16 17 157248 16 18 211384 17 18 718096 17 19 822166 18 19 366585 18 20 250962 19 20 231236 20 89 6 00110010100101111001 1 2 758268 1 3 205716 2 3 295263 1 4 207862 2 4 69876 3 4 179798 2 5 479889 3 5 953848 4 5 68337 1 6 833892 2 6 234107 4 6 772558 5 6 675566 2 7 942986 3 7 253909 4 7 95158 5 7 119424 6 7 316766 2 8 477692 3 8 406515 4 8 987774 5 8 808702 6 8 184409 7 8 500278 3 9 887393 4 9 469162 6 9 293078 7 9 205359 8 9 777079 5 10 313301 6 10 636761 7 10 846529 8 10 315392 9 10 477016 5 11 29206 6 11 840608 7 11 151527 8 11 877001 9 11 439665 10 11 907197 7 12 815137 8 12 530916 9 12 922868 11 12 827381 7 13 887939 8 13 638323 9 13 311582 10 13 169399 11 13 763999 12 13 695711 8 14 686748 9 14 400272 10 14 39935 11 14 528026 12 14 776064 13 14 965438 10 15 457267 12 15 318406 13 15 3489 14 15 217063 11 16 763755 12 16 711741 13 16 617167 14 16 469274 15 16 845875 11 17 776936 12 17 464487 13 17 682511 14 17 11831 15 17 447702 16 17 10247 12 18 10991 13 18 388512 14 18 312431 15 18 427326 16 18 846191 17 18 977005 13 19 941472 14 19 709497 15 19 343667 16 19 346238 17 19 777055 18 19 703066 14 20 779760 15 20 559561 16 20 810681 17 20 436275 18 20 371192 19 20 42384
样例输出
2402044
339126 523926 4622029 1721412 |
| 试题编号： | 201609-5 |
| 试题名称： | 祭坛 |
| 时间限制： | 2.0s |
| 内存限制： | 256.0MB |
| 问题描述： |
问题描述
在遥远的Dgeak大陆，生活着一种叫做Dar-dzo-nye的怪物。每当这种怪物降临，人们必须整夜对抗怪物而不能安睡。为了乞求这种怪物不再降临，人们决定建造祭坛。
Dgeak大陆可以看成一个用平面直角坐标系表示的巨大平面。在这个平面上，有 n 个Swaryea水晶柱，每个水晶柱可以用一个点表示。 如果 4 个水晶柱依次相连可以构成一个四边形，满足其两条对角线分别平行于 x 轴和 y 轴，并且对角线的交点位于四边形内部（不包括边界），那么这 4 个水晶柱就可以建立一个结界。其中，对角线的交点称作这个结界的中心。 例如下左图中，水晶柱 ABCD 可以建立一个结界，其中心为 O。 为了起到抵御Dar-dzo-nye的最佳效果，人们会把祭坛修建在最多层结界的保护中。其中不同层的结界必须有共同的中心，这些结界的边界不能有任何公共点，并且中心处也不能有水晶柱。这里共同中心的结界数量叫做结界的层数。 为了达成这个目的，人们要先利用现有的水晶柱建立若干个结界，然后在某些结界的中心建立祭坛。 例如上右图中，黑色的点表示水晶柱（注意 P 和 O 点不是水晶柱）。祭坛的一个最佳位置为 O 点，可以建立在 3 层结界中，其结界的具体方案见下左图。当然，建立祭坛的最佳位置不一定是唯一，在上右图中，O 点左侧 1 单位的点 P 也可以建立一个在 3 层结界中的祭坛，见下右图。 现在人们想知道： 1. 祭坛最佳选址地点所在的结界层数； 2. 祭坛最佳的选址地点共有多少个。
输入格式
输入的第一行包含两个正整数 n,q，表示水晶柱的个数和问题的种类。保证 q=1 或 2，其意义见输出格式。
接下来 n 行，每行包含两个非负整数 x,y，表示每个水晶柱的坐标。保证相同的坐标不会重复出现。
输出格式
若 q=1，输出一行一个整数，表示祭坛最多可以位于多少个结界的中心；若 q=2，输出一行一个整数，表示结界数最多的方案有多少种。
样例1输入
26 1
0 5 1 1 1 5 1 9 3 5 3 10 4 0 4 1 4 2 4 4 4 6 4 9 4 11 5 0 5 2 5 4 5 8 5 9 5 10 5 11 6 5 7 5 8 5 9 10 10 2 10 5
样例1输出
3
样例2输入
26 2
0 5 1 1 1 5 1 9 3 5 3 10 4 0 4 1 4 2 4 4 4 6 4 9 4 11 5 0 5 2 5 4 5 8 5 9 5 10 5 11 6 5 7 5 8 5 9 10 10 2 10 5
样例2输出
2
样例说明
样例即为题目描述中的例子，两个样例数据相同，分别询问最多的结界数量和达到最多结界数量的方案数。
其中图片的左下角为原点，右和上分别是 x 轴和 y 轴的正方向，一个格子的长度为单位长度。 以图中的 O 点建立祭坛，祭坛最多可以位于 3 个结界的中心。不存在更多结界的方案，因此样例1的答案为 3。 在 O 点左侧 1 单位的点 (4,5) 也可以建立一个在 3 个结界中的祭坛，因此样例2的答案为 2。
评测用例规模与约定
对于所有的数据，保证存在至少一种方案，使得祭坛建造在至少一层结界中，即不存在无论如何祭坛都无法建造在结界中的情况。
数据分为 8 类，各类之间互相没有交集，分别有以下特点： 1. 占数据的 10%，n=200，x,y≤n； 2. 占数据的 10%，n=200，x,y≤10 9； 3. 占数据的 10%，n=1000，x,y≤n； 4. 占数据的 10%，n=1000，x,y≤10 9； 5. 占数据的 10%，n=5000，x,y≤n； 6. 占数据的 10%，n=5000，x,y≤10 9； 7. 占数据的 20%，n=300000，x,y≤n； 8. 占数据的 20%，n=300000，x,y≤10 9。 此外，每类数据中，q=1 与 q=2 各占恰好一半。 |
各位大神帮帮忙，毫无头绪
