首页 › 题库 › 信息学奥赛 › 9.1 线性动态规划

信息学奥赛-入门级 题库

共 11 道题 · 按题型筛选,点「查看答案」核对解析
章节 9.1 线性动态规划 清除
1 单选题 适中 信息学奥赛 ·信息学奥赛-入门级 · 9.1 线性动态规划

设某算法的计算时间表示为递推关系式T(n)=T(n-1)+n(n为正整数)及T(0)=1,则该算法的时间复杂度为( )。

A
O(logn)
B
O(nlogn)
C
O(n)
D
O(n2)
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
2 单选题 适中 信息学奥赛 ·信息学奥赛-入门级 · 9.1 线性动态规划

在一个无向图中,如果任意两点之间都存在路径相连, 则称其为连通图。下图是一个有4个顶点、6 条边的连通图。若要使它不再是连通图,至少要删去其中的( )条边。

A
1
B
2
C
3
D
4
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
3 判断题 偏易 信息学奥赛 ·信息学奥赛-入门级 · 9.1 线性动态规划

如果将 dp[i-1]改为 dp[i-3],程序可能会产生编译错误( )

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
4 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 9.1 线性动态规划
#include <algorithm>
#include <cstdio>
#include <cstring>
#define ll long long  

int f[5007][5007]; 
int a[5007], b[5007];  
int n; 

int main() {
    scanf("%d", &n); 
    
    // 读取第一个序列
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]); 
    }
    
    // 读取第二个序列
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &b[i]); 
    }
    
    // 动态规划计算最长公共子序列(LCS)
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            // 状态转移:取上方或左方的最大值
            f[i][j] = std::max(f[i-1][j], f[i][j-1]);
            // 若当前元素相等,则可以从左上角+1转移
            if (a[i] == b[j]) {
                f[i][j] = std::max(f[i][j], f[i-1][j-1] + 1);
            }
        }
    }
    
    printf("%d\n", f[n][n]);
    return 0;
}


答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
5 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 9.1 线性动态规划

阅读程序(2)

#include <iostream>
#include <vector>
using namespace std;
int compute(vector<int> &cost) {
    int n = cost.size();
    vector<int> dp(n + 1, 0);
    dp[1] = cost[0];
    for (int i = 2; i <= n; i++) {
      dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i - 1];
   }
   return min(dp[n], dp[n - 1]);
}
int main() {
    int n;
    cin >> n;
    vector<int> cost(n);
    for (int i = 0; i < n; i++) {
        cin >> cost[i];
    }
    cout << compute(cost) << endl;
    return 0;
}
答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
6 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 9.1 线性动态规划

(编辑距离)给定两个字符串,每次操作可以选择删除(Delete)、插入(Insert)、替换(Replace),一个字符,求将第一个字符串转换为第二个字符串所需要的最少操作次数。

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int min(int x,int y,int z){
return min(min(x,y),z);
}

int edit_dist_dp(string str1,string str2){
int m=str1.length();
int n=str2.length();
vector<vector<int>> dp(m+1,vector<int>(n+1));

for(int i=0;i<=m;i++){
for(int j=0;j<=n;j++){
if(i==0)
dp[i][j]=     ①     ;
else if(j==0)
dp[i][j]=     ②     ;
else if(     ③     )
dp[i][j]=     ④     ;
 else
 dp[i][j]=1+min(dp[i][j-1],dp[i-1][j],     ⑤     ); 
 }
 }
return dp[m][n];
}

int main(){
 string str1,str2;
 cin>>str1>>str2;
 cout<<"Mininum number of operation:"
 <<edit_dist_dp(str1,str2)<<endl;
 return 0; 
}


答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
7 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 9.1 线性动态规划

求和

【问题描述】

一条狭长的纸带被均匀划分出了 n 个格子,格子编号从 1 到 n。每个格子上都染了一种颜色colori(用[1,m]当中的一个整数表示),并且写了一个数字numberi。

定义一种特殊的三元组:(x, y, z),其中 x,y,z 都代表纸带上格子的编号,这里的三元组要求满足以下两个条件:

  1. x,y,z,都是整数, x< y < z, y − x = z − y

  2. colorx =colorz

满足上述条件的三元组的分数规定为(x + z) * (numberx +numberz)。整个纸带的分数规定为所有满足条件的三元组的分数的和。这个分数可能会很大,你只要输出整个纸带的分数除以 10,007 所得的余数即可。

【输入格式】

输入文件名为 sum.in。

第一行是用一个空格隔开的两个正整数n和m,n代表纸带上格子的个数,m代表纸带上颜色的种类数。

第二行有n个用空格隔开的正整数,第i个数字numberi代表纸带上编号为i的格子上面写的数字。

第三行有n个用空格隔开的正整数,第i个数字colori代表纸带上编号为i的格子染的颜色。

【输出格式】

输出文件名为 sum.out。

共一行,一个整数,表示所求的纸带分数除以 10,007 所得的余数。

【输入输出样例 1】

【输入输出样例 1 说明】

纸带如题目描述中的图所示。

所有满足条件的三元组为:(1, 3, 5), (4, 5, 6)。

所以纸带的分数为(1 + 5) *(5 + 2) + (4 + 6) * (2 + 2) = 42 + 40 = 82。

【输入输出样例 2】

【数据说明】

对于第 1 组至第 2 组数据,1 ≤ n ≤ 100, 1 ≤ m ≤ 5;

对于第 3 组至第 4 组数据,1 ≤ n ≤ 3000, 1 ≤ m ≤ 100;

对于第 5 组至第 6 组数据,1 ≤ n ≤ 100000, 1 ≤ m ≤ 100000,且不存在出现次数超过 20 的颜色;

对于全部 10 组 数 据 , 1 ≤ n ≤ 100000, 1 ≤m ≤ 100000, 1 ≤colori ≤ m, 1 ≤numberi ≤ 100000。

答案与解析
参考答案

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int maxj = 1e5+100,mod = 10007;

int a[maxj],c[maxj],cnt[maxj][3],sum[maxj][3],x[maxj];

int32_t main(){//前缀和,颜色相同,等差数列,公式推导

    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n,m;

    cin>>n>>m;

    for(int i=1;i<=n;++i){

        cin>>a[i];

    }

    for(int i=1;i<=n;++i){

        cin>>c[i];

        cnt[c[i]][i%2]++;

        sum[c[i]][i%2]=(sum[c[i]][i%2]+a[i])%mod;

    }

    int ans=0;

    for(int i = 1;i <=n;++i){

        ans = (ans + i*(a[i]*(cnt[c[i]][i%2]-2)%mod+sum[c[i]][i%2]))%mod;

    }

    cout<< ans <<'\n';

    return 0 ;

}

题目详情
8 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 9.1 线性动态规划

立体图

【问题描述】

小渊是个聪明的孩子,他经常会给周围的小朋友们讲些自己认为有趣的内容。最近,他准备给小朋友们讲解立体图,请你帮他画出立体图。

小渊有一块面积为m*n的矩形区域,上面有m*n个边长为1的格子,每个格子上堆了一些同样大小的吉姆(积木的长宽高都是1),小渊想请你打印出这些格子的立体图。我们定义每个积木为如下格式,并且不会做任何翻转旋转,只会严格以这一种形式摆放:

每个顶点用1个加号’+’表示,长用3个”-“表示,宽用1个”/”表示,高用两个”|”表示。字符’+’ ‘-‘’/’ ‘|’的ASCII码分别为43,45,47,124。字符’.’(ASCII码46)需要作为背景输出,即立体图里的空白部分需要用’.’代替。立体图的画法如下面的规则:

立体图中,定义位于第(m,1)的格子(即第m行第1列的格子)上面自底向上的第一块积木(即最下面的一块积木)的左下角顶点为整张图最左下角的点。

【输入】

输入文件drawing.in第一行有用空格隔开的两个整数m和n,表示有m*n个格子(1<=m,n<=50)。

接下来的m行,是一个m*n的矩阵,每行有n个用空格隔开的整数,其中第i行第j列上的整数表示第i行第j列的格子上摞有多少个积木(1<=每个格子上的积木数<=100)。

【输出】

输出文件drawing.out中包含题目要求的立体图,是一个K行L列的字符矩阵,其中K和L表示最少需要K行L列才能按规定输出立体图。

【输入输出样例】

答案与解析
参考答案

#include<bits/stdc++.h>

#define max(x,y) ((x)>(y)?(x):(y))

using namespace std;

int n,m,k,l;

int a[101][101];

char c[6][8]={

"  +---+",

" /   /|",

"+---+ |",

"|   | +",

"|   |/ ",

"+---+  "

},ans[1001][1001];

int start[6]={0,0,0,0,1,2},end[6]={5,6,7,7,7,7};//只能覆盖到这些区域,其他的不能覆盖

void add(int y,int x){

k=max(k,x+5);//如题

l=max(l,y+6);

for(int i=x;i<x+6;i++)

for(int j=y+start[i-x];j<y+end[i-x];j++)

ans[i][j]=c[x+5-i][j-y];//因为是倒着的要注意一下

}

int main(){

for(int i=0;i<999;i++)

for(int j=0;j<999;j++)

ans[i][j]='.';//初始值即为背景

scanf("%d%d",&n,&m);

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++)

    for(int h=1;h<=a[i][j];h++)

        add(2*(n-i)+4*(j-1),2*(n-i)+3*(h-1));//公式

for(int i=k;i>=0;i--){//倒着输出

for(int j=0;j<=l;j++)

    printf("%c",ans[i][j]);

printf("\n");//换行

}

    return 0;

}

题目详情
9 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 9.1 线性动态规划

Hanoi双塔问题

【问题描述】

给定A、B、C三根足够长的细柱,在A柱上放有2n个中间有孔的圆盘,共有n个不同的尺寸,每个尺寸都有两个相同的圆盘,注意这两个圆盘是不加区分的(下图为n=3的情形)。现要将这些圆盘移到C柱上,在移动过程中可放在B柱上暂存。要求:

(1)每次只能移动一个圆盘;

(2)A、B、C三根细柱上的圆盘都要保持上小下大的顺序;

任务:设An为2n个圆盘完成上述任务所需的最少移动次数,对于输入的n,输出An。

【输入】

输入文件hanoi.in为一个正整数n,表示在A柱上放有2n个圆盘。

【输出】

输出文件hanoi.out仅一行,包含一个正整数, 为完成上述任务所需的最少移动次数An。


【输入输出样例1】

【输入输出样例2】

【限制】

    对于50%的数据,1<=n<=25

    对于100%的数据,1<=n<=200

 

【提示】

    设法建立An与An-1的递推关系式。

答案与解析
参考答案

#include<bits/stdc++.h>

using namespace std;

 

int a[1000],len_a;

int main()

{

    int n,len;

    freopen("hanoi.in","r",stdin);

    freopen("hanoi.out","w",stdout);

cin>>n;

    a[1]=2; //第一个2次 

    len_a=1; //数字长度为1 

    for(int i=1;i<=n;i++) // 做n次*2的高精乘法 

    {

        

        for(int j=len_a;j>=1;j--) // 从高位做起 

        {

            a[j]=a[j]*2; //乘2 

            if(a[j]>=10)  //进位 

            {

                a[j+1]++;

                a[j]-=10;

            }

        }

        while(a[len_a+1]>0) len_a++; //进最高位 

    }

    a[1]=a[1]-2;  // 不能忘记-2 

    for(int i=len_a;i>=1;i--) //输出 

        cout<<a[i];

    fclose(stdin);

    fclose(stdout);

    return 0;

}

题目详情
10 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 9.1 线性动态规划

有2×n的一个长方形方格,用一个1×2的骨牌铺满方格。例如n=3时,为2×3方格。

  此时用一个1×2的骨牌铺满方格,共有3种铺法:

试对给出的任意一个n(n>0),求出铺法总数的递推公式。

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
11 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 9.1 线性动态规划

排水系统(water)

【题目描述】

对于一个城市来说,排水系统是极其重要的一个部分。有一天,小 C 拿到了某座城市排水系统的设计图。排水系统由 n 个排水结点(它们从 1 ∼ n 编号)和若干个单向排水管道构成。每一个排水结点有若干个管道用于汇集其他排水结点的污水(简称为该结点的汇集管道),也有若干个管道向其他的排水结点排出污水(简称为该结点的排出管道)。

排水系统的结点中有 m 个污水接收口,它们的编号分别为 1, 2, · · · , m,污水只能从这些接收口流入排水系统,并且这些结点没有汇集管道。排水系统中还有若干个最终排水口,它们将污水运送到污水处理厂,没有排出管道的结点便可视为一个最终排水口。

现在各个污水接收口分别都接收了 1 吨污水,污水进入每个结点后,会均等地从当前结点的每一个排出管道流向其他排水结点,而最终排水口将把污水排出系统。

现在小 C 想知道,在该城市的排水系统中,每个最终排水口会排出多少污水。该城市的排水系统设计科学,管道不会形成回路,即不会发生污水形成环流的情况。

【输入格式】

从文件 water.in 中读入数据。

第一个两个用单个空格分隔的整数 n,m。分别表示排水结点数与接收口数量。

接下来 n 行,第 i 行用于描述结点 i 的所有排出管道。其中每行第一个整数 di 表示其排出管道的数量,接下来 di 个用单个空格分隔的整数 a1, a2, · · · , adi 依次表示管道的目标排水结点。

保证不会出现两条起始结点与目标结点均相同的管道。

【输出格式】

输出到文件 water.out 中。

输出若干行,按照编号从小到大的顺序,给出每个最终排水口排出的污水体积。其中体积使用分数形式进行输出,即每行输出两个用单个空格分隔的整数 p,q,表示排出的污水体积为要求 p 与 q 互素,q = 1 时也需要输出 q。

【样例 1 输入】

5  1

3  2  3  5

2  4  5

2  5  4

0

0

【样例 1 输出】

1  3

2  3

【样例 1 解释】

【数据范围】

对于所有测试点,保证

数据保证,污水在从一个接收口流向一个最终排水口的过程中,不会经过超过 10个中间排水结点(即接收口和最终排水口不算在内)。

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情