信息学奥赛-提高级 题库
作业调度方案
【问题描述】
我们现在要利用 m 台机器加工 n 个工件,每个工件都有 m 道工序,每道工序都在不同的指定的机器上完成。每个工件的每道工序都有指定的加工时间。
每个工件的每个工序称为一个操作,我们用记号 j-k 表示一个操作,其中 j 为 1 到 n 中的某个数字,为工件号;k 为 1 到 m 中的某个数字,为工序号,例如 2-4 表示第 2 个工件第 4 道工序的这个操作。在本题中,我们还给定对于各操作的一个安排顺序。
例如,当 n=3,m=2 时,“1-1,1-2,2-1,3-1,3-2,2-2”就是一个给定的安排顺序,即先安排第 1 个工件的第 1 个工序,再安排第 1 个工件的第 2 个工序,然后再安排第 2 个工件的第 1 个工序,等等。
一方面,每个操作的安排都要满足以下的两个约束条件。
(1) 对同一个工件,每道工序必须在它前面的工序完成后才能开始;
(2) 同一时刻每一台机器至多只能加工一个工件。
另一方面,在安排后面的操作时,不能改动前面已安排的操作的工作状态。
由于同一工件都是按工序的顺序安排的,因此,只按原顺序给出工件号,仍可得到同样的安排顺序,于是,在输入数据中,我们将这个安排顺序简写为“1 1 2 3 3 2”。
还要注意,“安排顺序”只要求按照给定的顺序安排每个操作。不一定是各机器上的实际操作顺序。在具体实施时,有可能排在后面的某个操作比前面的某个操作先完成。
例如,取 n=3,m=2,已知数据如下:

则对于安排顺序“1 1 2 3 3 2”,下图中的两个实施方案都是正确的。但所需要的总时间分别是10 与 12。

当一个操作插入到某台机器的某个空档时(机器上最后的尚未安排操作的部分也可以看作一个空档),可以靠前插入,也可以靠后或居中插入。为了使问题简单一些,我们约定:在保证约束条
件(1)(2)的条件下,尽量靠前插入。并且,我们还约定,如果有多个空档可以插入,就在保证约束条件(1)(2)的条件下,插入到最前面的一个空档。于是,在这些约定下,上例中的方案一是正确的,而方案二是不正确的。
显然,在这些约定下,对于给定的安排顺序,符合该安排顺序的实施方案是唯一的,请你计算出该方案完成全部任务所需的总时间。
【输入文件】
输入文件 jsp.in 的第 1 行为两个正整数,用一个空格隔开:m n
(其中 m(<20)表示机器数,n(<20)表示工件数)
第 2 行:m x n个用空格隔开的数,为给定的安排顺序。
接下来的 2n 行,每行都是用空格隔开的 m 个正整数,每个数不超过 20。
其中前 n 行依次表示每个工件的每个工序所使用的机器号,第 1 个数为第 1 个工序的机器号,第 2 个数为第 2 个工序机器号,等等。
后 n 行依次表示每个工件的每个工序的加工时间。
可以保证,以上各数据都是正确的,不必检验。
【输出文件】
输出文件 jsp.out 只有一个正整数,为最少的加工时间。
【输入样例】
2 3
1 1 2 3 3 2
1 2
1 2
2 1
3 2
2 5
2 4
【输出样例】
10
#include<bits/stdc++.h>
using namespace std;
int n,m;
int t[21][1001];//第i个机器在第j分钟是的状态,1:工作,2:空闲
int k[401];
int a[21][21],b[21][21];
int f[21],last[21];//记录第i个工件到了第f[i]个工序,这个工件上一次是什么时候做完的
int main(){
scanf("%d%d",&m,&n);
for(int i=1;i<=n*m;i++)
scanf("%d",&k[i]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&b[i][j]);
for(int i=1;i<=n*m;i++){
f[k[i]]++;//当前到了第几道工序
int j,sum;
for(j=last[k[i]]+1,sum=0;sum<b[k[i]][f[k[i]]];j++){
if(t[a[k[i]][f[k[i]]]][j]==0)sum++;//括号有点绕
else sum=0;
}
last[k[i]]=--j;//记录最后的时间
//注意要减掉1
for(int l=j-sum+1;l<=j;l++)
t[a[k[i]][f[k[i]]]][l]=1;//时间已经被占用
}
int ans=0;
for(int i=1;i<=n;i++)//答案就是各个工件最后一道工序的完成时间
ans=max(ans,last[i]);
printf("%d",ans);
return 0;
}
进制数
【问题描述】
设 r 是个
进制数,并满足以下条件:
(1)r 至少是个 2 位的
进制数
(2)作为
进制数除最后一位外,r 的每一位严格小于它右边相邻的那一位。
(3)将 r 转换为 2 进制数 q 后,则 q 的总位数不超过 w。
在这里,正整数 k(1≤k≤9)和 w(k<w≤30000)是事先给定的。
问:满足上述条件的不同的 r 共有多少个?
我们再从另一角度作些解释:设 S 是长度为 w 的 01 字符串(即字符串 S 由 w 个“0”或“1”组成),S 对应于上述条件(3)中的 q。将 S 从右起划分为若干个长度为 k 的段,每段对应一位
进制的数,如果 S 至少可分成 2 段,则 S 所对应的二进制数又可以转换为上述的
进制数 r。
例:设 k=3,w=7。则 r 是个八进制数(23=8)。由于 w=7,长度为 7 的 01 字符串按 3 位一段分,可分为 3 段(即 1,3,3,左边第一段只有一个二进制位),则满足条件的八进制数有:2 位数:高位为 1:6 个(即 12,13,14,15,16,17),高位为 2:5 个,„,高位为 6:1个(即 67)。共 6+5+„+1=21 个。3 位数:高位只能是 1,第 2 位为 2:5 个(即 123,124,125,126,127),第 2 位为 3:4 个,„,第 2 位为 6:1 个(即 167)。共 5+4+„+1=15 个。所以,满足要求的 r 共有 36 个。
【输入文件】
输入文件 digital.in 只有 1 行,为两个正整数,用一个空格隔开:
k W
【输出文件】
输出文件 digital.out 为 1 行,是一个正整数,为所求的计算结果,即满足条件的不同的 r 的个数(用十进制数表示),要求最高位不得为 0,各数字之间不得插入数字以外的其他字符(例如
空格、换行符、逗号等)。
(提示:作为结果的正整数可能很大,但不会超过 200 位)
【输入样例】
3 7
【输出样例】
36
1 #include<iostream>
2 using namespace std;
3
4 typedef long long LL;
5 const int maxn = 1000;
6 int C[maxn][maxn][300];
7 int ans[300];
8 int k,n;
9 void add(int *A,int* B,int *C) {
10 int len=max(A[0],B[0]); C[0]=len;
11 for(int i=1;i<=len;i++) {
12 C[i]+=A[i]+B[i];
13 C[i+1]+=C[i]/10;
14 C[i]%=10;
15 }
16 if(C[C[0]+1]) C[0]++;
17 }
18 void add(int* C,int* B) {
19 int len=max(C[0],B[0]); C[0]=len;
20 for(int i=1;i<=len;i++) {
21 C[i]+=B[i];
22 C[i+1]+=C[i]/10; //+=
23 C[i]%=10;
24 }
25 if(C[C[0]+1]) C[0]++;
26 }
27
28 int main() {
29 ios::sync_with_stdio(false);
30 cin>>k>>n;
31 int b_max=1<<(k),h_max=1<<(n%k);
32 C[0][0][0]=C[0][0][1]=1;
33 for(int i=1;i<b_max;i++)
34 for(int j=0;j<=i;j++){
35 if(j==0) C[i][j][1]=1;
36 else add(C[i-1][j-1],C[i-1][j],C[i][j]);
37 }
38 for(int i=2;i<=n/k&&i<b_max;i++) add(ans,C[b_max-1][i]);
39 for(int i=1;i<h_max&&n/k+i<b_max;i++) add(ans,C[b_max-i-1][n/k]);
40 for(int i=ans[0];i;i--) cout<<ans[i];
41 return 0;
42 }