信息学奥赛-入门级 题库
设某算法的计算时间表示为递推关系式T(n)=T(n-1)+n(n为正整数)及T(0)=1,则该算法的时间复杂度为( )。
在一个无向图中,如果任意两点之间都存在路径相连, 则称其为连通图。下图是一个有4个顶点、6 条边的连通图。若要使它不再是连通图,至少要删去其中的( )条边。

(编辑距离)给定两个字符串,每次操作可以选择删除(Delete)、插入(Insert)、替换(Replace),一个字符,求将第一个字符串转换为第二个字符串所需要的最少操作次数。
求和
【问题描述】
一条狭长的纸带被均匀划分出了 n 个格子,格子编号从 1 到 n。每个格子上都染了一种颜色colori(用[1,m]当中的一个整数表示),并且写了一个数字numberi。

定义一种特殊的三元组:(x, y, z),其中 x,y,z 都代表纸带上格子的编号,这里的三元组要求满足以下两个条件:
x,y,z,都是整数, x< y < z, y − x = z − y
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 ;
}
立体图
【问题描述】
小渊是个聪明的孩子,他经常会给周围的小朋友们讲些自己认为有趣的内容。最近,他准备给小朋友们讲解立体图,请你帮他画出立体图。
小渊有一块面积为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;
}
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;
}
有2×n的一个长方形方格,用一个1×2的骨牌铺满方格。例如n=3时,为2×3方格。
此时用一个1×2的骨牌铺满方格,共有3种铺法:

试对给出的任意一个n(n>0),求出铺法总数的递推公式。
排水系统(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个中间排水结点(即接收口和最终排水口不算在内)。