首页 › 题库 › 信息学奥赛 › 1 数据结构进阶

信息学奥赛-提高级 题库

共 682 道题 ,第 35 / 35 页 · 按题型筛选,点「查看答案」核对解析
章节 1 数据结构进阶 清除
681 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.2 图

作业调度方案

【问题描述】

我们现在要利用 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;

}

题目详情
682 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.2 图

进制数

【问题描述】

设 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 }

题目详情