信息学奥赛-入门级 题库
共 127 道题
,第 3 / 7 页
· 按题型筛选,点「查看答案」核对解析
47
简答题
偏难
字符串解码
“行程长度编码”(Run-Length Encoding)是一种无损压缩算法,常用于压缩重复字符较多的数据,以减少存储空间。假设原始字符串不包含数字字符,压缩规则如下:
①如果原始字符串中一个字符连续出现N次(N≥2),在压缩字符串中表示为“字符+数字N”。例如,编码“A12”代表12个连续的字符A。
②如果原始字符串中一个字符只出现1次,在压缩字符串中表示为该字符本身。例如,编码“B”代表1个字符B。
以下程序实现读取压缩字符串并输出其原始的、解压后的形式,试补全程序。
答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
48
简答题
偏难
上升点列(point)


答案与解析
参考答案
//参考代码1
#include<bits/stdc++.h>
using namespace std;
struct node{
int x,y;
//重载运算符,按x从小到大排序,x相同,则按y从小到大排序
friend bool operator<(const node &a1,const node &a2){
if(a1.x!=a2.x)return a1.x<a2.x;
return a1.y<a2.y;
}
}a[505];//记录500个点
int f[505][105],n,m,ans;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
sort(a+1,a+1+n);//排序
for(int k=0;k<=m;k++){//枚举使用0到K个点的情况
for(int i=1;i<=n;i++){//枚举每一个点
f[i][k]=k+1;//初始化第i个点用掉K个添加点后的最长距离
for(int j=1;j<i;j++){//循环这个点之前的点
if(a[j].y>a[i].y)continue;//如果之前的点Y坐标大,则忽略
int dist=a[i].x-a[j].x+a[i].y-a[j].y;//计算距离
if(dist-1>k)continue;//如果距离大,添加的点不够用,则忽略
f[i][k]=max(f[i][k],f[j][k-dist+1]+dist);//看下现在的大还是换成之前的点大
}
ans=max(ans,f[i][k]+m-k);//跟最大值比较
}
}
cout<<ans;
return 0;
}//参考代码2
#include<bits/stdc++.h>
using namespace std;
int n,k;
struct points
{
int x,y;
} p[510];
bool cmp(const points a,const points b)
{
if(a.x==b.x) return a.y<b.y;
else return a.x<b.x;
}
int f[510][110];//以i点为终点,再添加上j个点的情况下最大序列长度
int main()
{
//打开输入文件,输出文件
freopen("point.in","r",stdin);
freopen("point.out","w",stdout);
scanf("%d %d",&n,&k);
for(int i=1; i<=n; i++)
{
scanf("%d %d",&p[i].x,&p[i].y);
}
sort(p+1,p+1+n,cmp);
int ans=0;
for(int i=1; i<=n; i++)
{//以i为终点
for(int j=0; j<=k; j++)
{//添加j个点
f[i][j]=j+1;//以i为终点,后续添加j个点最短的长度
for(int l=1; l<i; l++)
{ //l为i的前一个点
if(p[l].x<=p[i].x&&p[l].y<=p[i].y)
{//横坐标、纵坐标值均单调不减
int t=p[i].x-p[l].x+p[i].y-p[l].y-1;//需要添加的点数量
if(j>=t) f[i][j]=max(f[i][j],f[l][j-t]+t+1);
//cout<<p[i].x<<p[l].x<<p[i].y<<p[l].y<<t<<endl;
}
//cout<<"i="<<i<<" j="<<j<<" l="<<l<<" f="<<f[i][j]<<endl;
}
ans=max(ans,f[i][j]);
}
}
printf("%d",ans);
//关闭输入文件输出文件
fclose(stdin);
fclose(stdout);
return 0;
}
51
简答题
偏难
完善程序(1)
(判断平方数) 问题:给定一个正整数 n,判断这个数 是不是完全平方数,即存在一个正整数 x 使得 x 的平方等于 n。试补全程序。
答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。