首页 › 题库 › 信息学奥赛 › 1.2 图

信息学奥赛-提高级 题库

共 117 道题 ,第 6 / 6 页 · 按题型筛选,点「查看答案」核对解析
101 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.2 图

开车旅行

【问题描述】

小 A 和小 B 决定利用假期外出旅行,他们将想去的城市从 1 到 N 编号,且编号较小的城市在编号较大的城市的西边,已知各个城市的海拔高度互不相同,记城市 i 的海拔高度为Hi,城市 i 和城市 j 之间的距离 d[i,j]恰好是这两个城市海拔高度之差的绝对值,即d[i, j] = |Hi − Hj|。

旅行过程中,小 A 和小 B 轮流开车,第一天小 A 开车,之后每天轮换一次。他们计划选择一个城市 S 作为起点,一直向东行驶,并且最多行驶 X 公里就结束旅行。小 A 和小 B的驾驶风格不同,小 B 总是沿着前进方向选择一个最近的城市作为目的地,而小 A 总是沿着前进方向选择第二近的城市作为目的地(注意:本题中如果当前城市到两个城市的距离相同,则认为离海拔低的那个城市更近)。如果其中任何一人无法按照自己的原则选择目的城市,或者到达目的地会使行驶的总距离超出 X 公里,他们就会结束旅行。

在启程之前,小 A 想知道两个问题:

1.对于一个给定的 X=X0,从哪一个城市出发,小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值最小(如果小 B 的行驶路程为 0,此时的比值可视为无穷大,且两个无穷大视为相等)。如果从多个城市出发,小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值都最小,则输出海拔最高的那个城市。

2. 对任意给定的 X=Xi和出发城市 Si,小 A 开车行驶的路程总数以及小 B 行驶的路程总数。

【输入】

输入文件为 drive.in。

第一行包含一个整数 N,表示城市的数目。

第二行有 N 个整数,每两个整数之间用一个空格隔开,依次表示城市 1 到城市 N 的海拔高度,即 H1,H2,……,Hn,且每个 Hi都是不同的。

第三行包含一个整数 X0。

第四行为一个整数 M,表示给定 M 组 Si和 Xi。

接下来的 M 行,每行包含 2 个整数 Si和 Xi,表示从城市 Si出发,最多行驶 Xi公里。

【输出】

输出文件为 drive.out。

输出共 M+1 行。

第一行包含一个整数 S0,表示对于给定的 X0,从编号为 S0 的城市出发,小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值最小。

接下来的 M 行,每行包含 2 个整数,之间用一个空格隔开,依次表示在给定的 Si 和Xi下小 A 行驶的里程总数和小 B 行驶的里程总数。

【输入输出样例 1】

【输入输出样例 1 说明】

各个城市的海拔高度以及两个城市间的距离如上图所示。

如果从城市 1 出发,可以到达的城市为 2,3,4,这几个城市与城市 1 的距离分别为 1,1,2,但是由于城市 3 的海拔高度低于城市 2,所以我们认为城市 3 离城市 1 最近,城市 2 离城市1 第二近,所以小 A 会走到城市 2。到达城市 2 后,前面可以到达的城市为 3,4,这两个城市与城市 2 的距离分别为 2,1,所以城市 4 离城市 2 最近,因此小 B 会走到城市 4。到达城市 4 后,前面已没有可到达的城市,所以旅行结束。

如果从城市 2 出发,可以到达的城市为 3,4,这两个城市与城市 2 的距离分别为 2,1,由于城市 3 离城市 2 第二近,所以小 A 会走到城市 3。到达城市 3 后,前面尚未旅行的城市为4,所以城市 4 离城市 3 最近,但是如果要到达城市 4,则总路程为 2+3=5>3,所以小 B 会直接在城市 3 结束旅行。

如果从城市 3 出发,可以到达的城市为 4,由于没有离城市 3 第二近的城市,因此旅行还未开始就结束了。

如果从城市 4 出发,没有可以到达的城市,因此旅行还未开始就结束了。

【输入输出样例 2】

【输入输出样例 2 说明】

当 X=7 时,

如果从城市 1 出发,则路线为 1 -> 2 -> 3 -> 8 -> 9,小 A 走的距离为 1+2=3,小 B 走的距离为 1+1=2。(在城市 1 时,距离小 A 最近的城市是 2 和 6,但是城市 2 的海拔更高,视为与城市 1 第二近的城市,所以小 A 最终选择城市 2;走到 9 后,小 A 只有城市 10 可以走,没有第 2 选择可以选,所以没法做出选择,结束旅行)

如果从城市 2 出发,则路线为 2 -> 6 -> 7 ,小 A 和小 B 走的距离分别为 2,4。

如果从城市 3 出发,则路线为 3 -> 8 -> 9,小 A 和小 B 走的距离分别为 2,1。

如果从城市 4 出发,则路线为 4 -> 6 -> 7,小 A 和小 B 走的距离分别为 2,4。

如果从城市 5 出发,则路线为 5 -> 7 -> 8 ,小 A 和小 B 走的距离分别为 5,1。

如果从城市 6 出发,则路线为 6 -> 8 -> 9,小 A 和小 B 走的距离分别为 5,1。

如果从城市 7 出发,则路线为 7 -> 9 -> 10,小 A 和小 B 走的距离分别为 2,1。

如果从城市 8 出发,则路线为 8 -> 10,小 A 和小 B 走的距离分别为 2,0。

如果从城市 9 出发,则路线为 9,小 A 和小 B 走的距离分别为 0,0(旅行一开始就结束了)。

如果从城市 10 出发,则路线为 10,小 A 和小 B 走的距离分别为 0,0。

从城市 2 或者城市 4 出发小 A 行驶的路程总数与小 B 行驶的路程总数的比值都最小,但是城市 2 的海拔更高,所以输出第一行为 2。

【数据范围】

对于 30%的数据,有 1≤N≤20,1≤M≤20;

对于 40%的数据,有 1≤N≤100,1≤M≤100;

对于 50%的数据,有 1≤N≤100,1≤M≤1,000;

对于 70%的数据,有 1≤N≤1,000,1≤M≤10,000;

对于 100%的数据,有 1≤N≤100,000,1≤M≤10,000,-1,000,000,000≤Hi≤1,000,000,000,

0≤X0≤1,000,000,000,1≤Si≤N,0≤Xi≤1,000,000,000,数据保证 Hi互不相同。

答案与解析
参考答案

#include<cstdio>

#include<cstring>

#include<algorithm>

#define inf 2147483647

#define ld long double 

#define ll long long

#define N 100010

using namespace std;

int n,m,x,sa,sb,hs,st,nx[N],ls[N],a[N],b[N],c[N],s[N],f[N][19];

ll pra[N][19],prb[N][19];

struct node{int v,id;}h[N];

ld ans=(ld)inf,t;

bool cmp(node x,node y){return x.v<y.v;}

int dis(int x,int y){return abs(h[x].v-h[y].v);}

void get(int x){

b[x]=(ls[x]&&(dis(x,ls[x])<=dis(x,nx[x])||!nx[x]))?ls[x]:nx[x];

if(b[x]==ls[x]){

a[x]=(ls[b[x]]&&(dis(x,ls[b[x]])<=dis(x,nx[x])||!nx[x]))?ls[b[x]]:nx[x];}

else{

a[x]=(ls[x]&&(dis(x,ls[x])<=dis(x,nx[b[x]])||!nx[b[x]]))?ls[x]:nx[b[x]];

}

nx[ls[x]]=nx[x];ls[nx[x]]=ls[x];

}

void work(int s,int x){

sa=sb=0;

for(int i=18;i>=0;i--){

if(x>=pra[s][i]+prb[s][i]){

x-=pra[s][i];x-=prb[s][i];

sa+=pra[s][i];sb+=prb[s][i];

s=f[s][i];

}

}

if(x>=pra[s][0]){x-=pra[s][0];sa+=pra[s][0];}

}

int main(){

scanf("%d",&n);

for(int i=1;i<=n;i++) scanf("%d",&h[i].v),h[i].id=i,s[i]=h[i].v;

sort(h+1,h+1+n,cmp);

for(int i=1;i<=n;i++){c[h[i].id]=i;ls[i]=i-1;nx[i]=i+1;}

nx[n]=0;

for(int i=1;i<=n;i++) get(c[i]);

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

int x=c[i];

if(b[a[x]]&&a[x])prb[i][0]=abs(h[a[x]].v-h[b[a[x]]].v);

if(a[x]) pra[i][0]=abs(h[x].v-h[a[x]].v);

f[i][0]=h[b[a[x]]].id;

}

for(int j=1;j<=18;j++){

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

f[i][j]=f[f[i][j-1]][j-1];

pra[i][j]=pra[i][j-1]+pra[f[i][j-1]][j-1];

prb[i][j]=prb[i][j-1]+prb[f[i][j-1]][j-1];

}

}

scanf("%d",&x);

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

work(i,x);

if(!sb) continue;else t=(ld)sa/sb;

if(ans>t||(ans==t&&s[i]>s[hs])){ans=t;hs=i;}

}

printf("%d\n",hs);

scanf("%d",&m);

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

scanf("%d%d",&st,&x);

work(st,x);

printf("%d %d\n",sa,sb);

}

return 0;

}

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

铺地毯

【问题描述】

为了准备一个独特的颁奖典礼,组织者在会场的一片矩形区域(可看做是平面直角坐标系的第一象限)铺上一些矩形地毯。一共有 n 张地毯,编号从 1 到 n。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设,后铺的地毯覆盖在前面已经铺好的地毯之上。地毯铺设完成后,组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意:在矩形地毯边界和四个顶点上的点也算被地毯覆盖。

【输入】

输入文件名为 carpet.in。

输入共 n+2 行。

第一行,一个整数 n,表示总共有 n 张地毯。

接下来的 n 行中,第 i+1 行表示编号 i 的地毯的信息,包含四个正整数 a,b,g,k,每两个整数之间用一个空格隔开,分别表示铺设地毯的左下角的坐标(a,b)以及地毯在 x轴和 y 轴方向的长度。

第 n+2 行包含两个正整数 x 和 y,表示所求的地面的点的坐标(x,y)。

【输出】

输出文件名为 carpet.out。

输出共 1 行,一个整数,表示所求的地毯的编号;若此处没有被地毯覆盖则输出-1。

【输入输出样例 1】

【输入输出样例说明】

如下图,1 号地毯用实线表示,2 号地毯用虚线表示,3 号用双实线表示,覆盖点(2,2)的最上面一张地毯是 3 号地毯。

【输入输出样例 2】

【输入输出样例说明】

如上图,1 号地毯用实线表示,2 号地毯用虚线表示,3 号用双实线表示,点(4,5)没有被地毯覆盖,所以输出-1。

【数据范围】

对于 30%的数据,有 n≤2;

对于 50%的数据,0≤a, b, g, k≤100;

对于 100%的数据,有 0≤n≤10,000,0≤a, b, g, k≤100,000。

答案与解析
参考答案

#include<iostream>

using namespace std;

int ditan[1000005][5];

int main()

{

    int n;

    cin>>n;

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

    {

        for(int j=1;j<=4;j++)

        {

            cin>>ditan[i][j];

        }

    }

    int x,y,flag=0;

    cin>>x>>y;

    for(int i=n;i>=1;i--)

    {

        if(ditan[i][1]<=x&&ditan[i][1]+ditan[i][3]>=x&&ditan[i][2]<=y&&ditan[i][2]+ditan[i][4]>=y)//判断是否覆盖此点

        {

            cout<<i<<endl;

            flag=1;

            break;

        }

    }

    if(!flag) cout<<"-1"<<endl;

    return 0;

}

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

选择客栈

【问题描述】

丽江河边有 n 家很有特色的客栈,客栈按照其位置顺序从 1 到 n 编号。每家客栈都按照某一种色调进行装饰(总共 k 种,用整数 0 ~ k-1 表示),且每家客栈都设有一家咖啡店,每家咖啡店均有各自的最低消费。

两位游客一起去丽江旅游,他们喜欢相同的色调,又想尝试两个不同的客栈,因此决定分别住在色调相同的两家客栈中。晚上,他们打算选择一家咖啡店喝咖啡,要求咖啡店位于两人住的两家客栈之间(包括他们住的客栈),且咖啡店的最低消费不超过 p。

他们想知道总共有多少种选择住宿的方案,保证晚上可以找到一家最低消费不超过 p元的咖啡店小聚。

【输入】

输入文件 hotel.in,共 n+1 行。

第一行三个整数 n,k,p,每两个整数之间用一个空格隔开,分别表示客栈的个数,色调的数目和能接受的最低消费的最高值;

接下来的 n 行,第 i+1 行两个整数,之间用一个空格隔开,分别表示 i 号客栈的装饰色调和 i 号客栈的咖啡店的最低消费。

【输出】

输出文件名为 hotel.out。

输出只有一行,一个整数,表示可选的住宿方案的总数。

【输入输出样例 1】

【输入输出样例说明】

2 人要住同样色调的客栈,所有可选的住宿方案包括:住客栈①③,②④,②⑤,④⑤,

但是若选择住 4、5 号客栈的话,4、5 号客栈之间的咖啡店的最低消费是 4,而两人能承受的最低消费是 3 元,所以不满足要求。因此只有前 3 种方案可选。

【数据范围】

对于 30%的数据,有 n≤100;

对于 50%的数据,有 n≤1,000;

对于 100%的数据,有 2≤n≤200,000,0<k≤50,0≤p≤100, 0≤最低消费≤100。

答案与解析
参考答案

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 const int maxn=2e6+10;

 4 const int maxc=55;

 5 int n,k,p;

 6 long long ans;

 7 int clo[maxn],val[maxn];

 8 int closum[maxc],last[maxn];

 9 int main()

10 {

11     scanf("%d%d%d",&n,&k,&p);

12     for(int i=1;i<=n;++i)scanf("%d%d",clo+i,val+i);

13     last[n+1]=0x7fffffff;

14     for(int i=n;i>0;--i)last[i]=val[i]<=p?i:last[i+1];

15     int cur=n;

16     for(int i=n-1;i>=1;--i)

17     {

18         while(cur>=last[i]&&cur>i)

19         {

20             closum[clo[cur]]++;

21             --cur;

22         }

23         ans+=closum[clo[i]];

24         

25     }

26     cout<<ans;

27     return 0;

28 }

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

Mayan 游戏

【问题描述】

Mayan puzzle 是最近流行起来的一个游戏。游戏界面是一个 7 行 5 列的棋盘,上面堆放着一些方块,方块不能悬空堆放,即方块必须放在最下面一行,或者放在其他方块之上。游戏通关是指在规定的步数内消除所有的方块,消除方块的规则如下:

1、 每步移动可以且仅可以沿横向(即向左或向右)拖动某一方块一格:当拖动这一方块时,如果拖动后到达的位置(以下称目标位置)也有方块,那么这两个方块将交换位置(参见输入输出样例说明中的图 6 到图 7);如果目标位置上没有方块,那么被拖动的方块将从原来的竖列中抽出,并从目标位置上掉落(直到不悬空,参见下面图 1 和图 2);

2、 任一时刻,如果在一横行或者竖列上有连续三个或者三个以上相同颜色的方块,则它们将立即被消除(参见图 1 到图 3)。

注意:

a) 如果同时有多组方块满足消除条件,几组方块会同时被消除(例如下面图 4,三个颜色为 1 的方块和三个颜色为 2 的方块会同时被消除,最后剩下一个颜色为 2 的方块)。

b) 当出现行和列都满足消除条件且行列共享某个方块时,行和列上满足消除条件的所有方块会被同时消除(例如下面图 5 所示的情形,5 个方块会同时被消除)。

 

3、 方块消除之后,消除位置之上的方块将掉落,掉落后可能会引起新的方块消除。注意:掉落的过程中将不会有方块的消除。

上面图 1 到图 3 给出了在棋盘上移动一块方块之后棋盘的变化。棋盘的左下角方块的坐标为(0, 0),将位于(3, 3)的方块向左移动之后,游戏界面从图 1 变成图 2 所示的状态,此时在一竖列上有连续三块颜色为 4 的方块,满足消除条件,消除连续 3 块颜色为 4 的方块后,上方的颜色为 3 的方块掉落,形成图 3 所示的局面。 

【输入】

输入文件 mayan.in,共 6 行。

第一行为一个正整数 n,表示要求游戏通关的步数。

接下来的 5 行,描述 7*5 的游戏界面。每行若干个整数,每两个整数之间用一个空格隔开,每行以一个 0 结束,自下向上表示每竖列方块的颜色编号(颜色不多于 10 种,从 1 开始顺序编号,相同数字表示相同颜色)。

输入数据保证初始棋盘中没有可以消除的方块。

【输出】

输出文件名为 mayan.out。

如果有解决方案,输出 n 行,每行包含 3 个整数 x,y,g,表示一次移动,每两个整数之间用一个空格隔开,其中(x,y)表示要移动的方块的坐标,g 表示移动的方向,1 表示向右移动,-1 表示向左移动。注意:多组解时,按照 x 为第一关健字,y 为第二关健字,1优先于-1,给出一组字典序最小的解。游戏界面左下角的坐标为(0,0)。

如果没有解决方案,输出一行,包含一个整数-1。

【输入输出样例 1】

【输入输出样例说明】

按箭头方向的顺序分别为图 6 到图 11 

样例输入的游戏局面如上面第一个图片所示,依次移动的三步是:(2,1)处的方格向右移动,(3,1)处的方格向右移动,(3,0)处的方格向右移动,最后可以将棋盘上所有方块消除。

【数据范围】

对于 30%的数据,初始棋盘上的方块都在棋盘的最下面一行;

对于 100%的数据,0 < n≤5。

答案与解析
参考答案

int main()

{

    //freopen("mayan.in","r",stdin);

    //freopen("mayan.out","w",stdout);

    scanf("%d",&n);

    for(int i=1;i<=5;i++)

    {

        for(int j=1;j<=8;j++)

        {

            int x;scanf("%d",&x);

            if(x==0)break;//毒瘤出题人弄我输入我去

            map[i][j]=x;

        }

    }

    memset(ans,-1,sizeof(ans));

    dfs(1);

    printf("-1\n");//没有解输出-1.直接输出只能有20分

    return 0;

}

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

机器翻译 

【问题描述】

小晨的电脑上安装了一个机器翻译软件,他经常用这个软件来翻译英语文章。

这个翻译软件的原理很简单,它只是从头到尾,依次将每个英文单词用对应的中文含义来替换。对于每个英文单词,软件会先在内存中查找这个单词的中文含义,如果内存中有,软件就会用它进行翻译;如果内存中没有,软件就会在外存中的词典内查找,查出单词的中文含义然后翻译,并将这个单词和译义放入内存,以备后续的查找和翻译。

假设内存中有 M 个单元,每单元能存放一个单词和译义。每当软件将一个新单词存入内存前,如果当前内存中已存入的单词数不超过 M−1,软件会将新单词存入一个未使用的内存单元;若内存中已存入 M 个单词,软件会清空最早进入内存的那个单词,腾出单元来,存放新单词。

假设一篇英语文章的长度为 N 个单词。给定这篇待译文章,翻译软件需要去外存查找多少次词典?假设在翻译开始前,内存中没有任何单词。

【输入】

输入文件名为 translate.in,输入文件共 2 行。每行中两个数之间用一个空格隔开。

第一行为两个正整数 M 和 N,代表内存容量和文章的长度。

第二行为 N 个非负整数,按照文章的顺序,每个数(大小不超过 1000)代表一个英文单词。文章中两个单词是同一个单词,当且仅当它们对应的非负整数相同。

【输出】

输出文件 translate.out 共 1 行,包含一个整数,为软件需要查词典的次数。

【输入输出样例 1】

【输入输出样例 1 说明】

整个查字典过程如下:每行表示一个单词的翻译,冒号前为本次翻译后的内存状况:

空:内存初始状态为空。

1. 1:查找单词 1 并调入内存。

2. 1 2:查找单词 2 并调入内存。

3. 1 2:在内存中找到单词 1。

4. 1 2 5:查找单词 5 并调入内存。

5. 2 5 4:查找单词 4 并调入内存替代单词 1。

6. 2 5 4:在内存中找到单词 4。

7. 5 4 1:查找单词 1 并调入内存替代单词 2。

共计查了 5 次词典。

【输入输出样例 2】

【数据范围】

对于 10%的数据有 M=1,N ≤ 5。

对于 100%的数据有 0<M ≤ 100,0<N ≤ 1000。

答案与解析
参考答案

#include<bits/stdc++.h>

using namespace std;

int main()

{

    int a,b;

    cin>>a>>b;

    int c[a],d[b];

    int ans=0;

    for (int i=0;i<a;i++)//将内存赋值为-1(因为为非负整数)

        c[i]=-1;

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

        cin>>d[i];

    if (a==0)//恒为0的时候直接输出

        cout<<b;

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

    {

        int k=0;

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

        {

            if (d[i]!=c[j])

                continue;

            else k=1;//进行标记

        }

        if (k==0)

        {

            int s=ans%a;//取余能够删除元素

            c[s]=d[i];

            ans++;

        }

    }

    cout<<ans<<endl;

}

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

关押罪犯

【问题描述】

S 城现有两座监狱,一共关押着 N 名罪犯,编号分别为 1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久,如果客观条件具备则随时可能爆发冲突。我们用“怨气值”(一个正整数值)来表示某两名罪犯之间的仇恨程度,怨气值越大,则这两名罪犯之间的积怨越多。如果两名怨气值为 c 的罪犯被关押在同一监狱,他们俩之间会发生摩擦,并造成影响力为 c 的冲突事件。

每年年末,警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表,然后上报到 S 城 Z 市长那里。公务繁忙的 Z 市长只会去看列表中的第一个事件的影响力,如果影响很坏,他就会考虑撤换警察局长。

在详细考察了 N 名罪犯间的矛盾关系后,警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配,以求产生的冲突事件影响力都较小,从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨,那么他们一定会在每年的某个时候发生摩擦。那么,应如何分配罪犯,才能使 Z 市长看到的那个冲突事件的影响力最小?这个最小值是多少? 

【输入】

输入文件名为 prison.in。输入文件的每行中两个数之间用一个空格隔开。

第一行为两个正整数 N 和 M,分别表示罪犯的数目以及存在仇恨的罪犯对数。

接下来的 M 行每行为三个正整数 aj,bj,cj,表示 aj号和 bj号罪犯之间存在仇恨,其怨气值为 cj。数据保证1 ≤ a j < bj ≤ N ,0 < c j ≤ 1,000,000,000 ,且每对罪犯组合只出现一次。

【输出】

输出文件 prison.out 共 1 行,为 Z 市长看到的那个冲突事件的影响力。如果本年内监狱中未发生任何冲突事件,请输出 0。

【输入输出样例】

【输入输出样例说明】

罪犯之间的怨气值如下面左图所示,右图所示为罪犯的分配方法,市长看到的冲突事件影响力是 3512(由 2 号和 3 号罪犯引发)。其他任何分法都不会比这个分法更优。

【数据范围】

对于 30%的数据有 N ≤ 15。

对于 70%的数据有 N ≤ 2000,M ≤ 50000。

对于 100%的数据有 N ≤ 20000,M ≤ 100000。

答案与解析
参考答案

#include<cstdio>

#include<algorithm>

using namespace std;

const int N = 100100;

int n,m;

int par[N];

struct Node{

    int a,b,c;

    bool operator < (const Node &B) const{

        return c > B.c;

    }

} nodes[N];

int Find(int x){

    if(x == par[x]) return x;

    return par[x] = Find(par[x]);

}

void Merge(int x,int y){

    par[Find(x)] = Find(y);

}

int main(){

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

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

        scanf("%d%d%d",&nodes[i].a,&nodes[i].b,&nodes[i].c);

        par[i] = i;

    }

    sort(nodes+1,nodes+1+m);

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

        int x = nodes[i].a,y = nodes[i].b,d = nodes[i].c;

        int x_en = x+n, y_en = y+n;

        if(Find(x) == Find(y)){

            printf("%d\n",d);

            return 0;

        }

        Merge(x,y_en);Merge(x_en,y);

    }

    printf("0");

    return 0;

}

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

引水入城

【问题描述】

在一个遥远的国度,一侧是风景秀美的湖泊,另一侧则是漫无边际的沙漠。该国的行政区划十分特殊,刚好构成一个 N 行 M 列的矩形,如上图所示,其中每个格子都代表一座城市,每座城市都有一个海拔高度。

为了使居民们都尽可能饮用到清澈的湖水,现在要在某些城市建造水利设施。水利设施有两种,分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的蓄水池中。因此,只有与湖泊毗邻的第 1 行的城市可以建造蓄水厂。而输水站的功能则是通过输水管线利用高度落差,将湖水从高处向低处输送。故一座城市能建造输水站的前提,是存在比它海拔更高且拥有公共边的相邻城市,已经建有水利设施。

由于第 N 行的城市靠近沙漠,是该国的干旱区,所以要求其中的每座城市都建有水利设施。那么,这个要求能否满足呢?如果能,请计算最少建造几个蓄水厂;如果不能,求干旱区中不可能建有水利设施的城市数目。

【输入】

输入文件名为 flow.in。输入文件的每行中两个数之间用一个空格隔开。

输入的第一行是两个正整数 N 和 M,表示矩形的规模。

接下来 N 行,每行 M 个正整数,依次代表每座城市的海拔高度。

【输出】

输出文件名为 flow.out。

输出有两行。如果能满足要求,输出的第一行是整数 1,第二行是一个整数,代表最少建造几个蓄水厂;如果不能满足要求,输出的第一行是整数 0,第二行是一个整数,代表有几座干旱区中的城市不可能建有水利设施。

【输入输出样例 1】

【样例 1 说明】

只需要在海拔为 9 的那座城市中建造蓄水厂,即可满足要求。

【输入输出样例 2】

【样例 2 说明】

上图中,在 3 个粗线框出的城市中建造蓄水厂,可以满足要求。以这 3 个蓄水厂为源头

在干旱区中建造的输水站分别用 3 种颜色标出。当然,建造方法可能不唯一。

【数据范围】

本题共有 10 个测试数据,每个数据的范围如下表所示:

对于所有的 10 个数据,每座城市的海拔高度都不超过

答案与解析
参考答案

#include<bits/stdc++.h>

#define il inline

#define ll long long

#define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)

#define Bor(i,a,b) for(int (i)=(b);(i)>=(a);(i)--)

#define Max(a,b) ((a)>(b)?(a):(b))

#define Min(a,b) ((a)>(b)?(b):(a))

using namespace std;

const int N=505,dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};

int mp[N][N],l[N][N],r[N][N],n,m,tot;

bool vis[N][N],f;


il int gi(){

    int a=0;char x=getchar();bool f=0;

    while((x<'0'||x>'9')&&x!='-')x=getchar();

    if(x=='-')x=getchar(),f=1;

    while(x>='0'&&x<='9')a=(a<<3)+(a<<1)+x-48,x=getchar();

    return f?-a:a;

}


il void dfs(int x,int y){

    vis[x][y]=1;

    For(i,0,3){

        int xx=x+dx[i],yy=y+dy[i];

        if(xx<1||yy<1||xx>n||yy>m)continue;

        if(mp[xx][yy]<mp[x][y]){

            if(!vis[xx][yy])dfs(xx,yy);

            l[x][y]=min(l[x][y],l[xx][yy]);

            r[x][y]=max(r[x][y],r[xx][yy]);

        }

    }

}


int main(){

    ios::sync_with_stdio(0);

    n=gi(),m=gi();

    memset(l,0x3f,sizeof(l));

    For(i,1,m) l[n][i]=r[n][i]=i;

    For(i,1,n) For(j,1,m) mp[i][j]=gi();

    For(i,1,m) if(!vis[1][i]) dfs(1,i);

    For(i,1,m) if(!vis[n][i]) tot++,f=1;

    if(f)cout<<0<<endl<<tot;

    else {

        int pos=1,lp=1;

        while(pos<=m){

            For(i,1,m)

                if(l[1][i]<=lp) pos=max(pos,r[1][i]);

            pos++;tot++;lp=pos;

        }

        cout<<1<<endl<<tot;

    }

    return 0;

}

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

潜伏者

【问题描述】

R 国和 S 国正陷入战火之中,双方都互派间谍,潜入对方内部,伺机行动。

历尽艰险后,潜伏于 S 国的 R 国间谍小 C 终于摸清了 S 国军用密码的编码规则:

1. S 国军方内部欲发送的原信息经过加密后在网络上发送,原信息的内容与加密后所得的内容均由大写字母‘A’-‘Z’构成(无空格等其他字符)。

2. S 国对于每个字母规定了对应的“密字”。加密的过程就是将原信息中的所有字母替换为其对应的“密字”。

3. 每个字母只对应一个唯一的“密字”,不同的字母对应不同的“密字”。“密字”可以和原字母相同。

例如,若规定‘A’的密字为‘A’,‘B’的密字为‘C’(其他字母及密字略),则原信息“ABA”被加密为“ACA”。

现在,小 C 通过内线掌握了 S 国网络上发送的一条加密信息及其对应的原信息。小 C希望能通过这条信息,破译 S 国的军用密码。小 C 的破译过程是这样的:扫描原信息,对于原信息中的字母 x(代表任一大写字母),找到其在加密信息中的对应大写字母 y,并认为在密码里 y 是 x 的密字。如此进行下去直到停止于如下的某个状态: 

1. 所有信息扫描完毕,‘A’-‘Z’ 所有 26 个字母在原信息中均出现过并获得了相应的“密字”。

2. 所有信息扫描完毕,但发现存在某个(或某些)字母在原信息中没有出现。

3. 扫描中发现掌握的信息里有明显的自相矛盾或错误(违反 S 国密码的编码规则)。

例如某条信息“XYZ”被翻译为“ABA”就违反了“不同字母对应不同密字”的规则。

在小 C 忙得头昏脑涨之际,R 国司令部又发来电报,要求他翻译另外一条从 S 国刚刚截取到的加密信息。现在请你帮助小 C:通过内线掌握的信息,尝试破译密码。然后利用破译的密码,翻译电报中的加密信息。

【输入】

输入文件名为 spy.in,共 3 行,每行为一个长度在 1 到 100 之间的字符串。

第 1 行为小 C 掌握的一条加密信息。

第 2 行为第 1 行的加密信息所对应的原信息。

第 3 行为 R 国司令部要求小 C 翻译的加密信息。

输入数据保证所有字符串仅由大写字母‘A’-‘Z’构成,且第 1 行长度与第 2 行相等。

【输出】

输出文件 spy.out 共 1 行。

若破译密码停止时出现 2,3 两种情况,请你输出“Failed”(不含引号,注意首字母大写,其它小写)。

否则请输出利用密码翻译电报中加密信息后得到的原信息。

【输入输出样例 1】

【输入输出样例 1 说明】

原信息中的字母‘A’和‘B’对应相同的密字,输出“Failed”。

【输入输出样例 2】

【输入输出样例 2 说明】

字母‘Z’在原信息中没有出现,输出“Failed”。

【输入输出样例 3】

答案与解析
参考答案

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

string s1,s2,s;

int t[27];

int main()

{

cin>>s1>>s2>>s;

int l=s1.size(),l2=s.size();

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

t[s1[i]-64]++;

for(int i=1;i<26;i++)

if(t[i]==0)

{

printf("Failed");

return 0;

}

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

for(int j=i+1;j<1;j++)

if(s1[j]==s1[i]&&s2[j]!=s2[i])

{

printf("Failed");

return 0;

}

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

for(int j=i+i;j<1;j++)

{

printf("Failed");

return 0;

}

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

cout<<s2[s1.find(s[i])];

return 0;

}

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

最优贸易

【问题描述】

C 国有 n 个大城市和 m 条道路,每条道路连接这 n 个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 m 条道路中有一部分为单向通行的道路,一部分为双向通行的道路,双向通行的道路在统计条数时也计为 1 条。

C 国幅员辽阔,各地的资源分布情况各不相同,这就导致了同一种商品在不同城市的价格不一定相同。但是,同一种商品在同一个城市的买入价和卖出价始终是相同的。

商人阿龙来到 C 国旅游。当他得知同一种商品在不同城市的价格可能会不同这一信息之后,便决定在旅游的同时,利用商品在不同城市中的差价赚回一点旅费。设 C 国 n 个城市的标号从 1~ n,阿龙决定从 1 号城市出发,并最终在 n 号城市结束自己的旅行。在旅游的过程中,任何城市可以重复经过多次,但不要求经过所有 n 个城市。阿龙通过这样的贸易方式赚取旅费:他会选择一个经过的城市买入他最喜欢的商品——水晶球,并在之后经过的另一个城市卖出这个水晶球,用赚取的差价当做旅费。由于阿龙主要是来 C 国旅游,他决定这个贸易只进行最多一次,当然,在赚不到差价的情况下他就无需进行贸易。

假设 C 国有 5 个大城市,城市的编号和道路连接情况如下图,单向箭头表示这条道路为单向通行,双向箭头表示这条道路为双向通行。

假设 1~n 号城市的水晶球价格分别为 4,3,5,6,1。

阿龙可以选择如下一条线路:1->2->3->5,并在 2 号城市以 3 的价格买入水晶球,在 3号城市以 5 的价格卖出水晶球,赚取的旅费数为 2。

阿龙也可以选择如下一条线路 1->4->5->4->5,并在第 1 次到达 5 号城市时以 1 的价格买入水晶球,在第 2 次到达 4 号城市时以 6 的价格卖出水晶球,赚取的旅费数为 5。

现在给出 n 个城市的水晶球价格,m 条道路的信息(每条道路所连接的两个城市的编号以及该条道路的通行情况)。请你告诉阿龙,他最多能赚取多少旅费。

【输入】

输入文件名为 trade.in。

第一行包含 2 个正整数 n 和 m,中间用一个空格隔开,分别表示城市的数目和道路的数目。

第二行 n 个正整数,每两个整数之间用一个空格隔开,按标号顺序分别表示这 n 个城市的商品价格。

接下来 m 行,每行有 3 个正整数,x,y,z,每两个整数之间用一个空格隔开。如果 z=1,表示这条道路是城市 x 到城市 y 之间的单向道路;如果 z=2,表示这条道路为城市 x 和城市

y 之间的双向道路。

【输出】

输出文件 trade.out 共 1 行,包含 1 个整数,表示最多能赚取的旅费。如果没有进行贸易,则输出 0。

【输入输出样例】

【数据范围】

输入数据保证 1 号城市可以到达 n 号城市。

对于 10%的数据,1≤n≤6。

对于 30%的数据,1≤n≤100。

对于 50%的数据,不存在一条旅游路线,可以从一个城市出发,再回到这个城市。

对于 100%的数据,1≤n≤100000,1≤m≤500000,1≤x,y≤n,1≤z≤2,1≤各城市水晶球价格≤100。

答案与解析
参考答案

#include<iostream>

#include<cstring>

#include<queue>

using namespace std;

const int maxn=1000001;

struct node

{

    int to;

    int from;

    int next1;

    int next2;

}e[maxn];

queue<int> q;

int n,m,ans,cnt,v[maxn],head1[maxn],head2[maxn];

int maxx[maxn],minx[maxn];

bool flag[maxn];

void edd_edge(int u,int v)

{

    cnt++;

    e[cnt].to=v;e[cnt].from=u;

    e[cnt].next1=head1[u];

    e[cnt].next2=head2[v];

    head1[u]=head2[v]=cnt;

}

void spfa1()

{

    memset(minx,1,sizeof(minx));

    q.push(1);

    flag[1]=1;

    minx[1]=v[1];

    while(!q.empty())

    {

        int t=q.front();

        q.pop();

        for(int i=head1[t];i;i=e[i].next1)

        {

            int u=e[i].to;

            minx[u]=min(minx[t],min(minx[u],v[u]));

            if(!flag[u])

            {

                q.push(u);

                flag[u]=1;

            }

        }

    }

}

void spfa2()

{

    memset(maxx,0,sizeof(maxx));

    memset(flag,0,sizeof(flag));

    q.push(n);

    flag[n]=1;

    maxx[n]=v[n];

    while(!q.empty())

    {

        int t=q.front();

        q.pop();

        for(int i=head2[t];i;i=e[i].next2)

        {

            int u=e[i].from;

            maxx[u]=max(maxx[t],max(maxx[u],v[u]));

            if(!flag[u])

            {

                q.push(u);

                flag[u]=1;

            }

        }

    }

}

int main()

{

    cin>>n>>m;

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

    cin>>v[i];

    int x,y,z;

    for(int i=1;i<=m;i++)

    {

        cin>>x>>y>>z;

        edd_edge(x,y);

        if(z==2)

        edd_edge(y,x);

    }

    spfa1();

    spfa2();

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

    ans=max(ans,maxx[i]-minx[i]);

    cout<<ans;

    return 0;

}

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

靶形数独

【问题描述】

小城和小华都是热爱数学的好学生,最近,他们不约而同地迷上了数独游戏,好胜的他们想用数独来一比高低。但普通的数独对他们来说都过于简单了,于是他们向 Z 博士请教,Z 博士拿出了他最近发明的“靶形数独”,作为这两个孩子比试的题目。

靶形数独的方格同普通数独一样,在 9 格宽×9 格高的大九宫格中有 9 个 3 格宽×3 格高的小九宫格(用粗黑色线隔开的)。在这个大九宫格中,有一些数字是已知的,根据这些数字,利用逻辑推理,在其他的空格上填入 1 到 9 的数字。每个数字在每个小九宫格内不能重复出现,每个数字在每行、每列也不能重复出现。但靶形数独有一点和普通数独不同,即每一个方格都有一个分值,而且如同一个靶子一样,离中心越近则分值越高。(如图)

上图具体的分值分布是:最里面一格(黄色区域)为 10 分,黄色区域外面的一圈(红色区域)每个格子为 9 分,再外面一圈(蓝色区域)每个格子为 8 分,蓝色区域外面一圈(棕色区域)每个格子为 7 分,最外面一圈(白色区域)每个格子为 6 分,如上图所示。比赛的要求是:每个人必须完成一个给定的数独(每个给定数独可能有不同的填法),而且要争取更高的总分数。而这个总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和。如图,在以下的这个已经填完数字的靶形数独游戏中,总分数为 2829。游戏规定,将以总分数的高低决出胜负。

由于求胜心切,小城找到了善于编程的你,让你帮他求出,对于给定的靶形数独,能够得到的最高分数。

【输入】

输入文件名为 sudoku.in。

一共 9 行。每行 9 个整数(每个数都在 0—9 的范围内),表示一个尚未填满的数独方格,未填的空格用“0”表示。每两个数字之间用一个空格隔开。

【输出】

输出文件 sudoku.out 共 1 行。

输出可以得到的靶形数独的最高分数。如果这个数独无解,则输出整数-1。

【输入输出样例 1】

【输入输出样例 2】

【数据范围】

40%的数据,数独中非 0 数的个数不少于 30。

80%的数据,数独中非 0 数的个数不少于 26。

100%的数据,数独中非 0 数的个数不少于 24。

答案与解析
参考答案

#include<bits/stdc++.h>

using namespace std;

int a[20][20],b[20][20],hang[20][20],lie[20][20];

int check(int x,int k,int j)

{

if(b[(x-1)/3*3+(k-1)/3][j]==0&&hang[x][j]==0&&lie[k][j]==0)

{

return 1;

}

return 0;

}

struct nomd

{

int i,sum;

}p[20];

int cmp(nomd a,nomd b)

{

return a.sum<b.sum;

}

int ans=0,maxn=0;

int e[9][9]={//*权值

6,6,6,6,6,6,6,6,6,

6,7,7,7,7,7,7,7,6,

6,7,8,8,8,8,8,7,6,

6,7,8,9,9,9,8,7,6,

6,7,8,9,10,9,8,7,6,

6,7,8,9,9,9,8,7,6,

6,7,8,8,8,8,8,7,6,

6,7,7,7,7,7,7,7,6,

6,6,6,6,6,6,6,6,6

};

void dfs(int w,int k)

{

if(w==9&&k==10)

{

for(int i=1;i<=9;i++)

{

for(int j=1;j<=9;j++)

{

ans+=a[i][j]*e[i-1][j-1];

}

}

if(ans>maxn)

maxn=ans;

ans=0;

return;

}

if(k==10)

{

dfs(w+1,1);

return;

}

if(a[p[w].i][k]==0)

{

for(int j=9;j>=1;j--)

{

if(check(p[w].i,k,j))

{

a[p[w].i][k]=j;

b[(p[w].i-1)/3*3+(k-1)/3][j]=1;

hang[p[w].i][j]=1;

lie[k][j]=1;

dfs(w,k+1);

a[p[w].i][k]=0;

b[(p[w].i-1)/3*3+(k-1)/3][j]=0;

hang[p[w].i][j]=0;

lie[k][j]=0;

}

}

return;

}

else

{

dfs(w,k+1);

}

return; 

}

int main()

{

for(int i=1;i<=9;i++)

{

p[i].i=i;

for(int j=1;j<=9;j++)

{

scanf("%d",&a[i][j]);

if(a[i][j]==0)

{

p[i].sum++;

}

b[(i-1)/3*3+(j-1)/3][a[i][j]]=1;

hang[i][a[i][j]]=1;

lie[j][a[i][j]]=1;

}

} 

sort(p+1,p+9,cmp);

 

dfs(1,1);

 

if(maxn==0)

printf("-1\n");

else

printf("%d\n",maxn);

return 0;

 } 

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

火柴棒等式

【问题描述】

给你 n 根火柴棍,你可以拼出多少个形如“A+B=C”的等式?等式中的 A、B、C 是用火柴棍拼出的整数(若该数非零,则最高位不能是 0)。用火柴棍拼数字 0-9 的拼法如图所示:

注意:

1. 加号与等号各自需要两根火柴棍

2. 如果 A≠B,则 A+B=C 与 B+A=C 视为不同的等式(A、B、C>=0)

3. n 根火柴棍必须全部用上

【输入】

输入文件 matches.in 共一行,又一个整数 n(n<=24)。

【输出】

输出文件 matches.out 共一行,表示能拼成的不同等式的数目。

【输入输出样例 1】

【输入输出样例 1 解释】

2 个等式为 0+1=1 和 1+0=1。 

【输入输出样例 2】

【输入输出样例 2 解释】

9 个等式为:

0+4=4

0+11=11

1+10=11

2+2=4

2+7=9

4+0=4

7+2=9

10+1=11

11+0=11

答案与解析
参考答案

#include<bits/stdc++.h>

using namespace std;

int a[10]={6,2,5,5,4,5,6,3,7,6};

int s[2010]={6}; 

int main(){

int n;

scanf("%d",&n);

int sum=0;

for(int i=0;i<=2000;i++){

int t=i;

while(t){

s[i]+=a[t%10];

t/=10;

}

}

for(int i=0;i<=1000;i++){

for(int j=0;j<=1000;j++){

if(s[i]+s[j]+s[i+j]+4==n) sum++;

}

}

printf("%d\n",sum); 

return 0;

} 

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

传纸条

【问题描述】

小渊和小轩是好朋友也是同班同学,他们在一起总有谈不完的话题。一次素质拓展活动中,班上同学安排做成一个 m 行 n 列的矩阵,而小渊和小轩被安排在矩阵对角线的两端,因此,他们就无法直接交谈了。幸运的是,他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里,小渊坐在矩阵的左上角,坐标(1,1),小轩坐在矩阵的右下角,坐标(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递,从小轩传给小渊的纸条只可以向上或者向左传递。

在活动进行中,小渊希望给小轩传递一张纸条,同时希望小轩给他回复。班里每个同学都可以帮他们传递,但只会帮他们一次,也就是说如果此人在小渊递给小轩纸条的时候帮忙,那么在小轩递给小渊的时候就不会再帮忙。反之亦然。

还有一件事情需要注意,全班每个同学愿意帮忙的好感度有高有低(注意:小渊和小轩的好心程度没有定义,输入时用 0 表示),可以用一个 0-100 的自然数来表示,数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条,即找到来回两条传递路径,使得这两条路径上同学的好心程度只和最大。现在,请你帮助小渊和小轩找到这样的两条路径。

【输入】

输入文件 message.in 的第一行有 2 个用空格隔开的整数 m 和 n,表示班里有 m 行 n 列(1<=m,n<=50)。

接下来的 m 行是一个 m*n 的矩阵,矩阵中第 i 行 j 列的整数表示坐在第 i 行 j 列的学生的好心程度。每行的 n 个整数之间用空格隔开。

【输出】

输出文件 message.out 共一行,包含一个整数,表示来回两条路上参与传递纸条的学生的好心程度之和的最大值。

【输入输出样例】

【限制】

30%的数据满足:1<=m,n<=10

100%的数据满足:1<=m,n<=50

答案与解析
参考答案

#include <bits/stdc++.h>

 

int n,m,s[101][101],dp[101][101][101];

 

int main(){

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

    freopen("message.ans","w",stdout);

    std::cin>>n>>m;

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

        for(int j=1;j<=m;j++)   

            std::cin>>s[i][j];

    for(int i=3;i<=m+n;i++)

        for(int j=1;j<=std::min(i-1,n);j++)

            for(int k=1;k<=std::min(i-1,n);k++){

                if(i<m+n&&j==k)continue;

                dp[i][j][k]=std::max(dp[i-1][j][k],dp[i-1][j-1][k-1]);

                if(j-1!=k)dp[i][j][k]=std::max(dp[i][j][k],dp[i-1][j-1][k]);

                if(k-1!=j)dp[i][j][k]=std::max(dp[i][j][k],dp[i-1][j][k-1]);

                dp[i][j][k]+=s[j][i-j]+s[k][i-k];

            }

    std::cout<<dp[m+n][n][n]<<std::endl;

    return 0;

}

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

双栈排序

【问题描述】

Tom 最近在研究一个有趣的排序问题。如图所示,通过 2 个栈 S1 和 S2,Tom 希望借助以下 4 种操作实现将输入序列升序排序。

操作 d

如果栈 S2 不为空,将 S2 栈顶元素弹出至输出序列

如果一个 1~n 的排列 P 可以通过一系列操作使得输出序列为 1,2,…,(n-1),n,Tom就称 P 是一个“可双栈排序排列”。例如(1,3,2,4)就是一个“可双栈排序序列”,而(2,3,4,1)不是。下图描述了一个将(1,3,2,4)排序的操作序列:<a,c,c,b,a,d,d,b>

当然,这样的操作序列有可能有几个,对于上例(1,3,2,4),<a,c,c,b,a,d,d,b>是另外一个可行的操作序列。Tom 希望知道其中字典序最小的操作序列是什么。

【输入】

输入文件 twostack.in 的第一行是一个整数 n。

第二行有 n 个用空格隔开的正整数,构成一个 1~n 的排列。

【输出】

输出文件 twostack.out 共一行,如果输入的排列不是“可双栈排序排列”,输出数字 0;

否则输出字典序最小的操作序列,每两个操作之间用空格隔开,行尾没有空格。

【输入输出样例 1】

【输入输出样例 2】

【输入输出样例 3】

【限制】

30%的数据满足: n<=10

50%的数据满足: n<=50

100%的数据满足: n<=1000

答案与解析
参考答案

#include <bits/stdc++.h>

using namespace std;

 

const int Max=1010;

int n,m=1,size,tot1,tot2,p1[Max],p2[Max];

int first[Max],f[Max],num[Max],vis[Max];

struct shu{int to,next,len;}edge[Max*Max];

 

inline int get_int()

{

int x=0,f=1;

char c;

for(c=getchar();(!isdigit(c))&&(c!='-');c=getchar());

if(c=='-') f=-1,c=getchar();

for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';

return x*f;

}

 

inline void build(int x,int y)

{

edge[++size].next=first[x],first[x]=size,edge[size].to=y;

edge[++size].next=first[y],first[y]=size,edge[size].to=x;

}

 

inline void pre()

{

f[n]=num[n];

for(int i=n-1;i>=1;i--) f[i]=min(f[i+1],num[i]);

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

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

    if(f[j]<num[i]&&num[i]<num[j]) build(i,j);

}

 

inline bool dfs(int p,int color)

{

vis[p]=color;

for(int u=first[p];u;u=edge[u].next)

{

  int to=edge[u].to;

  if(!vis[to]) dfs(to,3-color);

  else if(color==vis[to]) return 0;

}

return 1;

}

 

int main()

{

n=get_int();

for(int i=1;i<=n;i++) num[i]=get_int();

pre();

for(int i=1;i<=n;i++) if(!vis[i]&&!dfs(i,1)) {puts("0");return 0;}

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

{

  if(vis[i]==1)p1[++tot1]=num[i],printf("a ");

  else p2[++tot2]=num[i],printf("c ");

  while(m==p1[tot1]||m==p2[tot2])

  {

  if(m==p1[tot1]) tot1--,printf("b ");

  else tot2--,printf("d ");

  m++;

  }

}

return 0;

}

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

字符串的展开

【问题描述】

在初赛普及组的“阅读程序写结果”的问题中,我们曾给出一个字符串展开的例子:如果在输入的字符串中,含有类似于“d-h”或“4-8”的子串,我们就把它当作一种简写,输出时,用连续递增的字母或数字串替代其中的减号,即,将上面两个子串分别输出为“defgh”和“45678”。在本题中,我们通过增加一些参数的设置,使字符串的展开更为灵活。具体约定如下:

(1)遇到下面的情况需要做字符串的展开:在输入的字符串中,出现了减号“-”,减号两侧同为小写字母或同为数字,且按照 ASCII 码的顺序,减号右边的字符严格大于左边的字符。

(2)参数 p1:展开方式。p1=1 时,对于字母子串,填充小写字母;p1=2 时,对于字母子串,填充大写字母。这两种情况下数字子串的填充方式相同。p1=3 时,不论是字母子串还是数字子串,都用与要填充的字母个数相同的星号“*”来填充。

(3)参数 p2:填充字符的重复个数。p2=k 表示同一个字符要连续填充 k 个。例如,当 p2=3时,子串“d-h”应扩展为“deeefffgggh”。减号两侧的字符不变。

(4)参数 p3:是否改为逆序:p3=1 表示维持原有顺序,p3=2 表示采用逆序输出,注意这时仍然不包括减号两端的字符。例如当 p1=1、p2=2、p3=2 时,子串“d-h”应扩展为“dggffeeh”。

(5)如果减号右边的字符恰好是左边字符的后继,只删除中间的减号,例如:“d-e”应输出为“de”,“3-4”应输出为“34”。如果减号右边的字符按照 ASCII 码的顺序小于或等于左边字符,输出时,要保留中间的减号,例如:“d-d”应输出为“d-d”,“3-1”应输出为“3-1”。

【输入】

输入文件 expand.in 包括两行:

第 1 行为用空格隔开的 3 个正整数,依次表示参数 p1,p2,p3。

第 2 行为一行字符串,仅由数字、小写字母和减号“-”组成。行首和行末均无空格。

【输出】

输出文件 expand.out 只有一行,为展开后的字符串。

【输入输出样例 1】

【输入输出样例 2】

【输入输出样例 3】

【限制】

 40%的数据满足:字符串长度不超过 5

 100%的数据满足:1<=p1<=3, 1<=p2<=8, 1<=p3<=2。字符串长度不超过 100

答案与解析
参考答案

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e6+7;

int main()

{

int p1,p2,p3,n;

char a[maxn],b[maxn];

cin>>p1>>p2>>p3>>a;

n=strlen(a);

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

{

if(a[i]=='-'&&i&&i<=n-2)

{

if(a[i-1]=='-'||a[i+1]=='-')cout<<'-';//这些是只能打印-号的情况

else if(a[i-1]+1==a[i+1])continue;//这些是只能打印-号的情况,或者不能打印

else if(a[i-1]>=a[i+1]||(a[i-1]<='9'&&a[i+1]>='A'))cout<<'-';//这些是只能打印-号的情况

else

{    int l=0;

if(p1==1)

{

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

{

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

b[l++]=tolower((char)j);

}

}

else if(p1==2)

{

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

{

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

b[l++]=toupper((char)j);

}

}

else

{

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

{

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

b[l++]='*';

}

}

if(p3==2)

{

reverse(b,b+l);

}

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

{

cout<<b[i];

}

}

}

else 

cout<<a[i];

}

 

}

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

金明的预算方案

【问题描述】

金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过 N 元钱就行”。今天一早,金明就开始做预算了,他把想买的物品分为两类:主件与附件,附件是从属于某个主件的,下表就是一些主件与附件的例子:

如果要买归类为附件的物品,必须先买该附件所属的主件。每个主件可以有 0 个、1 个或 2个附件。附件不再有从属于自己的附件。金明想买的东西很多,肯定会超过妈妈限定的 N 元。于是,他把每件物品规定了一个重要度,分为 5 等:用整数 1~5 表示,第 5 等最重要。他还从因特网上查到了每件物品的价格(都是 10 元的整数倍)。他希望在不超过 N 元(可以等于 N 元)的前提下,使每件物品的价格与重要度的乘积的总和最大。

设第 j 件物品的价格为 v[j],重要度为 w[j],共选中了 k 件物品,编号依次为 j1,j2,„„,jk,则所求的总和为:

v[j1]*w[j1]+v[j2]*w[j2]+ „+v[jk]*w[jk]。(其中*为乘号)

请你帮助金明设计一个满足要求的购物单。

【输入文件】

输入文件 budget.in 的第 1 行,为两个正整数,用一个空格隔开:

N m

(其中 N(<32000)表示总钱数,m(<60)为希望购买物品的个数。)

从第 2 行到第 m+1 行,第 j 行给出了编号为 j-1 的物品的基本数据,每行有 3 个非负整数v p q

(其中 v 表示该物品的价格(v<10000),p 表示该物品的重要度(1~5),q 表示该物品是主件还是附件。如果 q=0,表示该物品为主件,如果 q>0,表示该物品为附件,q 是所属主件的编号)

【输出文件】

输出文件 budget.out 只有一个正整数,为不超过总钱数的物品的价格与重要度乘积的总和的最大值(<200000)。

【输入样例】

1000 5

800 2 0

400 5 1

300 5 1

400 3 0

500 2 0

【输出样例】

2200

答案与解析
参考答案

#include<iostream>

#include<algorithm>

using namespace std;

int n,m,f[30010];

struct node

{

int v,p;

}a[30];

bool cmp(node x,node y)

{

if(x.p!=y.p)

return x.p>y.p;

}

int main()

{

cin>>n>>m;

for(int i=1;i<=m;i++)

{

cin>>a[i].v>>a[i].p;

}

sort(a+1,a+m+1,cmp);

for(int i=1;i<=m;i++)

{

for(int j=n;j>=a[i].v;j--)

{

f[j]=max(f[j],f[j-a[i].v]+a[i].v*a[i].p);

}

}

cout<<f[n];

return 0;

}

题目详情
116 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 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;

}

题目详情
117 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 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 }

题目详情