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

信息学奥赛-提高级 题库

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

铺设道路

【问题描述】

春春是一名道路工程师,负责铺设一条长度为 n 的道路。

铺设道路的主要工作是填平下陷的地表。整段道路可以看作是 n 块首尾相连的区域,一开始,第 i 块区域下陷的深度为 di 。

春春每天可以选择一段连续区间 [L, R] ,填充这段区间中的每块区域,让其下陷深度减少 1。在选择区间时,需要保证,区间内的每块区域在填充前下陷深度均不为 0 。

春春希望你能帮他设计一种方案,可以在最短的时间内将整段道路的下陷深度都变为 0 。

【输入格式】

输入文件名为 road.in。

输入文件包含两行,第一行包含一个整数 n,表示道路的长度。

第二行包含 n 个整数,相邻两数间用一个空格隔开,第 i 个整数为 di 。

【输出格式】

输出文件名为 road.out。

输出文件仅包含一个整数,即最少需要多少天才能完成任务。

【输入输出样例 1】

【样例解释】

一种可行的最佳方案是,依次选择:

[1,6]、[1,6]、[1,2]、[1,1]、[4,6]、[4,4]、[4,4]、[6,6]、[6,6]。

【数据规模与约定】

对于 30% 的数据,1 ≤ n ≤ 10 ;

对于 70% 的数据,1 ≤ n ≤ 1000 ;

对于 100% 的数据,1 ≤ n ≤ 100000 ,0 ≤ di ≤ 10000 。

答案与解析
参考答案

#include <bits/stdc++.h>

#define inf 0x3f3f3f3f

using namespace std;

int ans,d[100001],N;

int partition1(int left, int right) //分治(实现这一片区域的操作)

{   int sum1=0;

if(left>=right) //当不能再分时返回

{  

if(left==right) //如果区域是单个数

{   int t=d[left];

d[left]=0; //清0

return t; //直接返回里面的值(它里面的值代表这个单个区域需要的天数)

}

else

return 0;

}   

int min1=inf,l=left;

for (int i=left; i<=right;i++) //求出这片区域的最小值

    min1=min(d[i],min1);

sum1+=min1;//先把最小值加上

for(int i=left; i<=right; i++)

{  d[i]-=min1; //每个都减去最小值

   if(d[i]==0&&d[i-1]!=0) //如果遇到0分界线

           {

   sum1+=partition1(l,i-1);//把之前的区域分治

   }

   if(d[i]!=0&&d[i-1]==0) l=i;//如果在0之后遇到新的左端点,更新

}

if(d[right]!=0)//不要忘掉最后一块区域

sum1+=partition1(l,right);

return sum1;

}

int main()

{

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

cin>>N;

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

cin>>d[i];

ans=partition1(1,N);

cout<<ans;

return 0;

 } 

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

货币系统

【问题描述】

在网友的国度中共有 n 种不同面额的货币,第 i 种货币的面额为 a[i],你可以假设每一种货币都有无穷多张。为了方便,我们把货币种数为 n、面额数组为 a[1..n]的货币系统记作 (n,a)。

在一个完善的货币系统中,每一个非负整数的金额 x 都应该可以被表示出,即对每一个非负整数 x,都存在 n 个非负整数 t[i] 满足 a[i]× t[i] 的和为 x。然而,在网友的国度中,货币系统可能是不完善的,即可能存在金额 x 不能被该货币系统表示出。例如在货币系统 n=3, a=[2,5,9] 中,金额 1,3 就无法被表示出来。

两个货币系统 (n,a) 和 (m,b) 是等价的,当且仅当对于任意非负整数 x,它要么均可以被两个货币系统表出,要么不能被其中任何一个表出。

现在网友们打算简化一下货币系统。他们希望找到一个货币系统 (m,b),满足(m,b) 与原来的货币系统 (n,a) 等价,且 m 尽可能的小。他们希望你来协助完成这个艰巨的任务:找到最小的 m。

【输入格式】

输入文件名为 money.in。

输入文件的第一行包含一个整数 T,表示数据的组数。接下来按照如下格式分别给出 T 组数据。

每组数据的第一行包含一个正整数 n。接下来一行包含 n 个由空格隔开的正整数a[i]。

【输出格式】

输出文件名为 money.out。

输出文件共有 T 行,对于每组数据,输出一行一个正整数,表示所有与 (n,a) 等价的货币系统 (m,b) 中,最小的 m。

【输入输出样例 1】

【输入输出样例 1 说明】

在第一组数据中,货币系统 (2, [3,10]) 和给出的货币系统 (n, a) 等价,并可以验证不存在 m < 2 的等价的货币系统,因此答案为 2。

在第二组数据中,可以验证不存在 m < n 的等价的货币系统,因此答案为 5。

【数据规模与约定】

对于 100% 的数据,满足 1 ≤ T ≤ 20, n,a[i] ≥ 1。

答案与解析
参考答案

#include<iostream>

#include<algorithm>

#include<cstring>

#define N 25005

using namespace std;

bool dp[N]={0};

int a[103]={0};

int T=0,n=0;

int ret=0;

int main()

{

    cin>>T;

    while(T--)

    {

        cin>>n;

        ret=0;

        memset(dp,0,sizeof(dp));

        dp[0]=1;

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

            cin>>a[i];

        sort(a+1,a+1+n);

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

        {

            if(dp[a[i]]) 

                continue;

            ret++;

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

            {

                dp[j]|=dp[j-a[i]];

            }

        }

        cout<<ret<<endl;

    }

    return 0;

}

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

赛道修建

【问题描述】

C 城将要举办一系列的赛车比赛。在比赛前,需要在城内修建m 条赛道。

C 城一共有 n 个路口,这些路口编号为 1,2, … , n,有 n − 1 条适合于修建赛道的双向通行的道路,每条道路连接着两个路口。其中,第 i 条道路连接的两个路口编号为 ai和 bi,该道路的长度为 li。借助这 n − 1 条道路,从任何一个路口出发都能到达其他所有的路口。

一条赛道是一组互不相同的道路 e1, e2, … , ek,满足可以从某个路口出发,依次经过道路 e1, e2, … , ek(每条道路经过一次,不允许调头)到达另一个路口。一条赛道的长度等于经过的各道路的长度之和。为保证安全,要求每条道路至多被一条赛道经过。

目前赛道修建的方案尚未确定。你的任务是设计一种赛道修建的方案,使得修建的m条赛道中长度最小的赛道长度最大(即m条赛道中最短赛道的长度尽可能大)。

【输入格式】

输入文件名为 track.in。

输入文件第一行包含两个由空格分隔的正整数 n, m,分别表示路口数及需要修建的赛道数。

接下来 n − 1 行,第 i 行包含三个正整数 ai, bi, li,表示第 i 条适合于修建赛道的道路连接的两个路口编号及道路长度。保证任意两个路口均可通过这 n − 1 条道路相互到达。每行中相邻两数之间均由一个空格分隔。

【输出格式】

输出文件名为 track.out。

输出共一行,包含一个整数,表示长度最小的赛道长度的最大值。

【输入输出样例 1】

【输入输出样例 1 说明】

所有路口及适合于修建赛道的道路如下图所示:

道路旁括号内的数字表示道路的编号,非括号内的数字表示道路长度。

需要修建 1 条赛道。可以修建经过第 3,1,2,6 条道路的赛道(从路口 4 到路口 7),则该赛道的长度为 9 + 10 + 5 + 7 = 31,为所有方案中的最大值。

【输入输出样例 2】

【输入输出样例 2 说明】

所有路口及适合于修建赛道的道路如下图所示:

需要修建 3 条赛道。可以修建如下 3 条赛道:

1. 经过第 1,6 条道路的赛道(从路口 1 到路口 7),长度为 6 + 9 = 15;

2. 经过第 5,2,3,8 条道路的赛道(从路口 6 到路口 9),长度为 4 + 3 + 5 + 4 = 16;

3. 经过第 7,4 条道路的赛道(从路口 8 到路口 5),长度为 7 + 10 = 17。

长度最小的赛道长度为 15,为所有方案中的最大值。

【数据规模与约定】

所有测试数据的范围和特点如下表所示

其中,“分支不超过 3”的含义为:每个路口至多有 3 条道路与其相连。对于所有的数据,2 ≤ n≤ 50,000,1 ≤ m ≤ n − 1,1 ≤ ai, bi ≤ n,1 ≤ li ≤ 10,000。

答案与解析
参考答案

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <set>

#include <vector>

using namespace std;


int head[50100],to[100100],nex[100100],val[100100];

int n,waysnumber,m,edges;


multiset <int> :: iterator it;


int dfs(int now,int father,int x){

multiset <int> son;

for (int v = head[now]; v ; v = nex[v])

if (to[v] != father){

int tmpways = dfs(to[v],now,x) + val[v];

if (tmpways >= x) ++waysnumber;

else son.insert(tmpways);

}

//对当前点now的所有子路径进行组合,用刚好能满足≥x的最小的边组合

//并返回所有儿子中最长的无法被组合成满足条件路的点 

int maxwaylen = 0;

while (son.size() > 1){

it = son.lower_bound(x - *son.begin());

if (it == son.begin()) it++; //若最短的边≥x的时候,则用最短的两条边组合 

if (it == son.end()){        //当前最短的边没办法找到够长的边组合出满足条件的路 

//挑一条最长的子边返回 

maxwaylen = max(maxwaylen,*son.begin());

son.erase(son.begin());

}

else{

//成功组合出了满足条件的边 

++waysnumber;

son.erase(it);

son.erase(son.begin());

}

}

if (son.size() == 1) maxwaylen = max(maxwaylen,*son.begin());

return maxwaylen;

}

 

bool check(int x){

waysnumber = 0;

dfs(1,0,x);

if (waysnumber >= m) return true;

else return false;

}


void addedge(int u,int v,int c){

    nex[++edges] = head[u], head[u] = edges, to[edges] = v, val[edges] = c;

}


int main()

{

edges = 0;

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

long long all = 0;

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

int a,b,c;scanf("%d%d%d",&a,&b,&c);

addedge(a,b,c);

addedge(b,a,c);

all += c;

}

int l = 0 , r = all / m,mid,ans;   //这里存在一个坑,对于ai = 1的图,如果这里的 r 使用极大值500000000,就会超时

while (l <= r){

mid = (l + r) >> 1;

if (check(mid)) ans = mid,l = mid + 1;

else r = mid - 1;

}

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

return 0;

} 

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

旅行

【问题描述】

小 Y 是一个爱好旅行的 OIer。她来到 X 国,打算将各个城市都玩一遍。

小 Y 了解到,X 国的n 个城市之间有 m 条双向道路。每条双向道路连接两个城市。不存在两条连接同一对城市的道路,也不存在一条连接一个城市和它本身的道路。并且,从任意一个城市出发,通过这些道路都可以到达任意一个其他城市。小 Y 只能通过这些道路从一个城市前往另一个城市。

小 Y 的旅行方案是这样的:任意选定一个城市作为起点,然后从起点开始,每次可以选择一条与当前城市相连的道路,走向一个没有去过的城市,或者沿着第一次访问该城市时经过的道路后退到上一个城市。当小 Y 回到起点时,她可以选择结束这次旅行或继续旅行。需要注意的是,小 Y 要求在旅行方案中,每个城市都被访问到。

为了让自己的旅行更有意义,小 Y 决定在每到达一个新的城市(包括起点)时,将它的编号记录下来。她知道这样会形成一个长度为n 的序列。她希望这个序列的字典序最小,你能帮帮她吗?

对于两个长度均为 n 的序列 A 和 B,当且仅当存在一个正整数 x,满足以下条件时,我们说序列 A 的字典序小于 B。

⚫ 对于任意正整数 1 ≤ i < x,序列 A 的第 i 个元素 Ai 和序列 B 的第 i 个元素Bi 相同。

⚫ 序列 A 的第 x 个元素的值小于序列 B 的第 x 个元素的值。

【输入格式】

输入文件名为 travel.in。

输入文件共 m + 1 行。第一行包含两个整数 n, m(m ≤ n) ,中间用一个空格分隔。

接下来 m 行,每行包含两个整数 u, v (1 ≤ u, v ≤ n) ,表示编号为 u 和 v 的城市之间有一条道路,两个整数之间用一个空格分隔。

【输出格式】

输出文件名为 travel.out。

输出文件包含一行,n 个整数,表示字典序最小的序列。相邻两个整数之间用一个空格分隔。

【输入输出样例 1】

【输入输出样例 2】

【数据规模与约定】

对于 100% 的数据和所有样例,1 ≤ n ≤ 5000 且 m = n − 1 或 m = n 。

对于不同的测试点,我们约定数据的规模如下:

答案与解析
参考答案

#include<bits/stdc++.h>

#define maxn 50500

using namespace std;

inline int read() {

int x=0;char c=getchar();

while(!isdigit(c)) c=getchar();

while(isdigit(c)) x=(x<<3)+(x<<1)+c-48,c=getchar();return x;

}


int n,m,cnt,del;

int ans[maxn],start[maxn],to[maxn],cur[maxn];

vector<int> v[maxn];


inline bool check() {

if(cnt != n) return false;

for(int i=1;i<=n;i++) if(cur[i]!=ans[i]) return ans[i]>cur[i];

}

void dfs(int u,int f) {

if(cnt>n) return ;

cur[++cnt]=u;

for(int i=0;i<v[u].size();i++) {

if(v[u][i]==f || (u==start[del]&&v[u][i]==to[del]) || (v[u][i]==start[del]&&u==to[del])) continue;

dfs(v[u][i],u);

}

}

int main() {

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

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

memset(ans,64,sizeof(ans));

n=read(),m=read();

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

int x=read(),y=read();

v[x].push_back(y);

v[y].push_back(x);

start[i]=x;to[i]=y;

}

for(int i=1;i<=n;i++) sort(v[i].begin(),v[i].end());

if(m==n-1) {

del=0;cnt=0;

dfs(1,0);

memcpy(ans,cur,sizeof(cur));

} else {

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

memset(cur,0,sizeof(cur));

del=i;cnt=0;

dfs(1,0);

if(check() ) {

memcpy(ans,cur,sizeof(cur));

}

}

}

for(int i=1;i<=n;i++) printf("%d ",ans[i]);

return 0;

}

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

 填数游戏

【问题描述】

小 D 特别喜欢玩游戏。这一天,他在玩一款填数游戏。

这个填数游戏的棋盘是一个n × m的矩形表格。玩家需要在表格的每个格子中填入一个数字(数字 0 或者数字 1),填数时需要满足一些限制。

下面我们来具体描述这些限制。

为了方便描述,我们先给出一些定义:

• 我们用每个格子的行列坐标来表示一个格子,即(行坐标,列坐标)。(注意:行列坐标均从 0 开始编号)

• 合法路径 P:一条路径是合法的当且仅当:

1. 这条路径从矩形表格的左上角的格子(0,0)出发,到矩形的右下角格子(n − 1, m − 1)结束;

2. 在这条路径中,每次只能从当前的格子移动到右边与它相邻的格子,或者从当前格子移动到下面与它相邻的格子。

例如:在下面这个矩形中,只有两条路径是合法的,它们分别是p1:(0,0) → (0,1) →(1,1)和p2:(0,0) → (1,0) → (1,1)。

对于一条合法的路径 P,我们可以用一个字符串w(P)来表示,该字符串的长度为n +m − 2,其中只包含字符“R”或者字符“D”,第 i 个字符记录了路径 P 中第 i 步的移动方法,“R”表示移动到当前格子右边与它相邻的格子,“D”表示移动到当前格子下面与它相邻的格子。例如,上图中对于路径p1,有w(P1) = "RD";而对于另一条路径p2,有w(P2) = "DR"。

同时,将每条合法路径 P 经过的每个格子上填入的数字依次连接后,会得到一个长度为n + m − 1的 01 字符串,记为 s(P)。例如,如果我们在格子(0,0)和(1,0)上填入数字0,在格子(0,1)和(1,1)上填入数字 1(见上图红色数字)。那么对于路径p1,我们可以得到s(P1) = "011",对于路径p2,有s(P2) = "001"。

游戏要求小 D 找到一种填数字 0、1 的方法,使得对于两条路径p1,P2,如果w(P1) >w(P2),那么必须s(P1) ≤ s(P2)。我们说字符串 a 比字符串 b 小,当且仅当字符串 a 的字典序小于字符串 b 的字典序,字典序的定义详见第一题。但是仅仅是找一种方法无法满足小 D 的好奇心,小 D 更想知道这个游戏有多少种玩法,也就是说,有多少种填数字的方法满足游戏的要求?

小 D 能力有限,希望你帮助他解决这个问题,即有多少种填 0、1 的方法能满足题目要求。由于答案可能很大,你需要输出答案对109 + 7取模的结果。

【输入格式】

输入文件名为 game.in。

输入文件共一行,包含两个正整数 n、m,由一个空格分隔,表示矩形的大小。其中 n 表示矩形表格的行数,m 表示矩形表格的列数。

【输出格式】

输出文件名为 game.out。

输出共一行,包含一个正整数,表示有多少种填 0、1 的方法能满足游戏的要求。

注意:输出答案对 10^9+7 取模的结果。

【输入输出样例 1】

【样例解释】

对于2 × 2棋盘,有上图所示的 12 种填数方法满足要求。

【输入输出样例 2】

【输入输出样例 3】

【数据规模与约定】

答案与解析
参考答案

#include<cstdio>

#include<cstring>

#include<algorithm>

#define P 1000000007

using namespace std;

int n,m,inv128=570312504,inv384=190104168;

int add(int x,int y)  {return x+y>=P?x+y-P:x+y;}

int dec(int x,int y)  {return x-y< 0?x-y+P:x-y;}

int mul(int x,int y)  {return 1ll*x*y%P;}

int power(int a,int b){

int ans=1;

for(;b;b>>=1,a=mul(a,a))  if(b&1)  ans=mul(ans,a);

return ans;

}

int main(){

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

if(n>m)  swap(n,m);

if(n==1)  printf("%d\n",power(2,m));

else  if(n==2)  printf("%d\n",mul(4,power(3,m-1)));

else  if(n==3)  printf("%d\n",mul(112,power(3,m-3)));

else{

if(m==n)  printf("%d\n",(83ll*power(8,n)%P+5ll*power(2,n+7)%P)*inv384%P);

else  printf("%d\n",(83ll*power(8,n)%P+power(2,n+8))*power(3,m-n-1)%P*inv128%P);

}

return 0;

}

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

下列关于图灵奖的说法中,正确的有( )。

答案与解析
正确答案:B,C,D
这道题暂未补解析。
题目详情
87 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.2 图

奶酪

【问题描述】

现有一块大奶酪,它的高度为 h,它的长度和宽度我们可以认为是无限大的,奶酪中间有许多半径相同的球形空洞。我们可以在这块奶酪中建立空间坐标系,在坐标系中,奶酪的下表面为z = 0,奶酪的上表面为z = h。

现在,奶酪的下表面有一只小老鼠 Jerry,它知道奶酪中所有空洞的球心所在的坐标。如果两个空洞相切或是相交,则 Jerry 可以从其中一个空洞跑到另一个空洞,特别地,如果一个空洞与下表面相切或是相交,Jerry 则可以从奶酪下表面跑进空洞;如果一个空洞与上表面相切或是相交,Jerry 则可以从空洞跑到奶酪上表面。

位于奶酪下表面的 Jerry 想知道,在不破坏奶酪的情况下,能否利用已有的空洞跑到奶酪的上表面去?

【输入格式】

输入文件名为 cheese.in。

每个输入文件包含多组数据。

输入文件的第一行,包含一个正整数 T,代表该输入文件中所含的数据组数。

接下来是 T 组数据,每组数据的格式如下:

第一行包含三个正整数 n,h 和 r,两个数之间以一个空格分开,分别代表奶酪中空洞的数量,奶酪的高度和空洞的半径。

接下来的 n 行,每行包含三个整数 x、y、z,两个数之间以一个空格分开,表示空洞球心坐标为(x, y, z)。

【输出格式】

输出文件名为 cheese.out。

输出文件包含 T 行,分别对应 T 组数据的答案,如果在第 i 组数据中,Jerry 能从下

表面跑到上表面,则输出“Yes”,如果不能,则输出“No”(均不包含引号)。

【输入输出样例 1】

【输入输出样例 1 说明】

【数据规模与约定】

对于 20%的数据,n = 1,1 ≤ h , r ≤ 10,000,坐标的绝对值不超过 10,000。

对于 40%的数据,1 ≤ n ≤ 8, 1 ≤ h , r ≤ 10,000,坐标的绝对值不超过 10,000。

对于 80%的数据,1 ≤ n ≤ 1,000,1 ≤ h , r ≤ 10,000,坐标的绝对值不超过 10,000。

对于 100%的数据,1 ≤ n ≤ 1,000,1 ≤ h , r ≤ 1,000,000,000,T ≤ 20,坐标的绝对值不超过 1,000,000,000。

答案与解析
参考答案

#include<bits/stdc++.h>

#define rg register int

using namespace std;

long long T, n, h, r, x[1005], y[1005], z[1005], f[1005][1005], bz[1005], ans;

int dist(int i, int j) {

double s = sqrt((x[i] - x[j]) * 1.0 * (x[i] -x [j])*1.0 + (y[i] - y[j]) * 1.0 * (y[i] - y[j])*1.0 + (z[i] - z[j]) * 1.0 * (z[i] -z [j]) * 1.0) * 1.0;

if (s > (int)s) s++;

return s;

}

void dfs(int x) {

if (x == n + 1) {

ans = 1;

return;

}

bz[x] = 1;

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

if (f[x][i] && (!bz[i])) {

dfs(i);

if (ans == 1)

return;

}

}

int main() {

scanf("%lld", &T);

while (T--) {

scanf("%lld%lld%lld", &n, &h, &r), ans = 0;

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

scanf("%lld%lld%lld", &x[i], &y[i], &z[i]);

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

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

f[i][j] = f[j][i] = 0;

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

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

if (dist(i,j) <= r * 2) f[i][j] = f[j][i] = 1;

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

bz[i] = 0;

if (h - z[i] <= r) f[i][n + 1] = f[n + 1][i] = 1;

if (z[i] <= r) f[i][0] = f[0][i] = 1;

}

dfs(0);

if (ans) printf("Yes\n");

else printf("No\n");

}

return 0;

}

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

列队

【问题描述】

Sylvia 是一个热爱学习的女孩子。

前段时间,Sylvia 参加了学校的军训。众所周知,军训的时候需要站方阵。Sylvia所在的方阵中有n × m名学生,方阵的行数为 n,列数为 m。

为了便于管理,教官在训练开始时,按照从前到后,从左到右的顺序给方阵中的学生从 1 到 n × m 编上了号码(参见后面的样例)。

即:初始时,第 i 行第 j 列的学生的编号是(i − 1) × m + j。

然而在练习方阵的时候,经常会有学生因为各种各样的事情需要离队。在一天中,一共发生了 q 件这样的离队事件。每一次离队事件可以用数对(x, y) (1≤x≤n, 1≤y≤m)描述,表示第 x 行第 y 列的学生离队。

在有学生离队后,队伍中出现了一个空位。为了队伍的整齐,教官会依次下达这样的两条指令:

1. 向左看齐。这时第一列保持不动,所有学生向左填补空缺。不难发现在这条指令之后,空位在第 x 行第 m 列。

2. 向前看齐。这时第一行保持不动,所有学生向前填补空缺。不难发现在这条指令之后,空位在第 n 行第 m 列。

教官规定不能有两个或更多学生同时离队。即在前一个离队的学生归队之后,下一个学生才能离队。因此在每一个离队的学生要归队时,队伍中有且仅有第 n 行第 m 列一个空位,这时这个学生会自然地填补到这个位置。

因为站方阵真的很无聊,所以 Sylvia 想要计算每一次离队事件中,离队的同学的编号是多少。

注意:每一个同学的编号不会随着离队事件的发生而改变,在发生离队事件后方阵中同学的编号可能是乱序的。

【输入格式】

输入文件名为 phalanx.in。

输入共 q+1 行。

第 1 行包含 3 个用空格分隔的正整数 n, m, q,表示方阵大小是 n 行 m 列,一共发生了 q 次事件。

接下来 q 行按照事件发生顺序描述了 q 件事件。每一行是两个整数 x, y,用一个空格分隔,表示这个离队事件中离队的学生当时排在第 x 行第 y 列。

【输出格式】

输出文件名为 phalanx.out。

按照事件输入的顺序,每一个事件输出一行一个整数,表示这个离队事件中离队学生的编号。

【输入输出样例 1】

【输入输出样例 1 说明】

列队的过程如上图所示,每一行描述了一个事件。

在第一个事件中,编号为 1 的同学离队,这时空位在第一行第一列。接着所有同学向左标齐,这时编号为 2 的同学向左移动一步,空位移动到第一行第二列。然后所有同学向上标齐,这时编号为 4 的同学向上一步,这时空位移动到第二行第二列。最后编号为 1 的同学返回填补到空位中。

【数据规模与约定】

数据保证每一个事件满足 1≤x≤n,1≤y≤m。

答案与解析
参考答案

#pragma GCC optimize(3)

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int Max=300005;

int n,m,q,sum,tot;

int tree[Max*20],lc[Max*20],rc[Max*20],rt[Max];

vector<ll>num[Max];

inline int get_int()

{

int x=0;char c;

for(c=getchar();!isdigit(c);c=getchar());

for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^48);

return x;

}

inline void print(ll x)

{

if(x>9) print(x/10);

putchar('0'+x%10);

}

 

inline void add(int &now,int l,int r,int pos)

{

if(!now) now=++tot;tree[now]++;

if(l==r) return;

int mid=(l+r)>>1;

if(pos<=mid) add(lc[now],l,mid,pos);

else add(rc[now],mid+1,r,pos);

}

inline int Q(int root,int l,int r,int k)

{

if(l==r) return l;

int mid=(l+r)>>1,sum=(mid-l+1)-tree[lc[root]];

if(sum>=k) Q(lc[root],l,mid,k);

else Q(rc[root],mid+1,r,k-sum);

}

inline ll Qr(int x,ll v)

{

int pos=Q(rt[n+1],1,sum,x);add(rt[n+1],1,sum,pos);

ll ans=pos<=n?(ll)m*pos:num[n+1][pos-n-1];

return num[n+1].push_back(v?v:ans),ans;

}

inline ll Ql(int x,int y)

{

int pos=Q(rt[x],1,sum,y);add(rt[x],1,sum,pos);

ll ans=pos<m?(ll)(x-1)*m+pos:num[x][pos-m];

return num[x].push_back(Qr(x,ans)),ans;

}

 

int main()

{

  n=get_int(),m=get_int(),q=get_int(),sum=max(n,m)+q;

while(q--)

{

  int x=get_int(),y=get_int();

  if(y==m) print(Qr(x,0)),putchar('\n');

  else print(Ql(x,y)),putchar('\n');

}

return 0;

}

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

信息传递

【问题描述】

有 n 个同学(编号为 1 到 n)正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象,其中,编号为 i 的同学的信息传递对象是编号为Ti的同学。

游戏开始时,每人都只知道自己的生日。之后每一轮中,所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象(注意:可能有人可以从若干人那里获取信息,但是每人只会把信息告诉一个人,即自己的信息传递对象)。当有人从别人口中得知自己的生日时,游戏结束。请问该游戏一共可以进行几轮?

【输入格式】

输入文件名为 message.in。

输入共 2 行。

第 1 行包含 1 个正整数 n,表示 n 个人。

第 2 行包含 n 个用空格隔开的正整数 T1, T2, … … , Tn,其中第i 个整数Ti表示编号为 i

的同学的信息传递对象是编号为 Ti 的同学, Ti ≤ n 且 Ti ≠ i。

数据保证游戏一定会结束。

【输出格式】

输出文件名为 message.out。

输出共 1 行,包含 1 个整数,表示游戏一共可以进行多少轮。

【输入输出样例 1】

【输入输出样例 1 说明】

游戏的流程如图所示。当进行完第 3 轮游戏后,4 号玩家会听到 2 号玩家告诉他自己的生日,所以答案为 3。当然,第 3 轮游戏后,2 号玩家、3 号玩家都能从自己的消息来源得知自己的生日,同样符合游戏结束的条件。

【数据规模与约定】

对于 30%的数据,n ≤ 200;

对于 60%的数据,n ≤ 2500;

对于 100%的数据,n ≤ 200000。

答案与解析
参考答案

#include <bits/stdc++.h>

using namespace std;

const int maxn=200010;

int n, fa[maxn],ans=0x3f3f3f3f;

int get(int x, int &cnt){

    cnt++;

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

    else return get(fa[x], cnt);

}

int main () {

    cin>>n;

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

        fa[i]=i;

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

        int cnt=0,f;

        cin>>f;

        if(get(f,cnt)==i){

            ans=min(ans,cnt); 

        }else{

        fa[i]=f;

        }

    }

    cout<<ans;

    return 0;

}

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

跳石头

【问题描述】

一年一度的“跳石头”比赛又要开始了!这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间,有 N 块岩石(不含起点和终点的岩石)。在比赛过程中,选手们将从起点出发,每一步跳向相邻的岩石,直至到达终点。

为了提高比赛难度,组委会计划移走一些岩石,使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制,组委会至多从起点和终点之间移走 M 块岩石(不能移走起点和终点的岩石)。

【输入格式】

输入文件名为 stone.in。

输入文件第一行包含三个整数 L,N,M,分别表示起点到终点的距离,起点和终点之间的岩石数,以及组委会至多移走的岩石数。

接下来 N 行,每行一个整数,第 i 行的整数 Di(0 < Di < L)表示第 i 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出,且不会有两个岩石出现在同一个位置。

【输出格式】

输出文件名为 stone.out。

输出文件只包含一个整数,即最短跳跃距离的最大值。

【输入输出样例 1】

【输入输出样例 1 说明】

将与起点距离为 2 和 14 的两个岩石移走后,最短的跳跃距离为 4(从与起点距离17 的岩石跳到距离 21 的岩石,或者从距离 21 的岩石跳到终点)。

【数据规模与约定】

对于 20%的数据,0 ≤ M ≤ N ≤ 10。

对于 50%的数据,0 ≤ M ≤ N ≤ 100。

对于 100%的数据,0 ≤ M ≤ N ≤ 50,000,1 ≤ L ≤ 1,000,000,000。

答案与解析
参考答案

#include<bits/stdc++.h>

using namespace std;      //本题数据量大,采用二分法来减少复杂度,避免超时。先把所有的石头点存入数组a

int l,n,m;     //包括起始点0和终点l。这题使用二分答案的思想,顾名思义就是采用二分法查找答案(最短跳跃距离最大值)

int a[100000];  //我们知道,最短跳跃距离必在0-l之间,0和l一开始作为上下界,对于a[mid]用judge进行判断

bool judge(int k){    //如果要达到mid对应最短跳跃距离需要移开石头数count>原有的m,说明实际的答案会比mid小

    int count=0,now=0;    //就把有边界左移,反之,说明可以达到这个最短跳跃距离,是暂时的最优答案,先保存

    for(int i=1;i<n+2;i++){    //然后把左边界右移,试试有没有更优的解,直到上下边界互相跨越

        if(a[i]-a[now]<k){

            count++;

        }else{

            now=i;        //now是现在脚底下的石头,如果不移石头直接过去要更新

        }

    }

    if(count>m){

        return false;

    }else{

        return true;

    }

}

int main(){

    cin>>l>>n>>m;

    a[0]=0;

    a[n+1]=l;

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

        cin>>a[i];

    }

    int left=0,right=l,mid,ans;

    while(left<=right){       //二分法

        mid=(left+right)/2;

        if(judge(mid)){

            left=mid+1;

            ans=mid;

        }else{

            right=mid-1;

        }

    }

    cout<<ans;

    //system("pause");

    return 0;

}

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

运输计划

【问题描述】

公元 2044 年,人类进入了宇宙纪元。

L 国有 n 个星球,还有 n-1 条双向航道,每条航道建立在两个星球之间,这 n-1 条航道连通了 L 国的所有星球。小 P 掌管一家物流公司,该公司有很多个运输计划,每个运输计划形如:有一艘物流飞船需要从 ui号星球沿最快的宇航路径飞行到 vi号星球去。显然,飞船驶过一条航道是需要时间的,对于航道 j,任意飞船驶过它所花费的时间为 tj,并且任意两艘飞船之间不会产生任何干扰。

为了鼓励科技创新,L 国国王同意小 P 的物流公司参与 L 国的航道建设,即允许小P 把某一条航道改造成虫洞,飞船驶过虫洞不消耗时间。

在虫洞的建设完成前小 P 的物流公司就预接了 m 个运输计划。在虫洞建设完成后,这 m 个运输计划会同时开始,所有飞船一起出发。当这 m 个运输计划都完成时,小 P 的物流公司的阶段性工作就完成了。

如果小 P 可以自由选择将哪一条航道改造成虫洞,试求出小 P 的物流公司完成阶段性工作所需要的最短时间是多少?

【输入格式】

输入文件名为 transport.in。

第一行包括两个正整数 n、m,表示 L 国中星球的数量及小 P 公司预接的运输计划的数量,星球从 1 到 n 编号。

接下来 n-1 行描述航道的建设情况,其中第 i 行包含三个整数 ai, bi和 ti,表示第i 条双向航道修建在 ai与 bi两个星球之间,任意飞船驶过它所花费的时间为 ti。

接下来 m 行描述运输计划的情况,其中第 j 行包含两个正整数 uj和 vj,表示第 j 个运输计划是从 uj号星球飞往 vj号星球。

【输出格式】

输出文件名为 transport.out。

共 1 行,包含 1 个整数,表示小 P 的物流公司完成阶段性工作所需要的最短时间。

【输入输出样例 1】

【输入输出样例 1 说明】

将第 1 条航道改造成虫洞:则三个计划耗时分别为:11、12、11,故需要花费的时间为 12。

将第 2 条航道改造成虫洞:则三个计划耗时分别为:7、15、11,故需要花费的时间为 15。

将第 3 条航道改造成虫洞:则三个计划耗时分别为:4、8、11,故需要花费的时间为 11。

将第 4 条航道改造成虫洞:则三个计划耗时分别为:11、15、5,故需要花费的时间为 15。

将第 5 条航道改造成虫洞:则三个计划耗时分别为:11、10、6,故需要花费的时间为 11。

故将第 3 条或第 5 条航道改造成虫洞均可使得完成阶段性工作的耗时最短,需要花费的时间为 11。

【数据规模与约定】

所有测试数据的范围和特点如下表所示

请注意常数因子带来的程序效率上的影响。

答案与解析
参考答案

#include <bits/stdc++.h>

using namespace std;

 

const int Max=300005;

int n,m,s,ans,tot,l,r,mid;

int first[Max],son[Max],pos[Max],top[Max],depth[Max],father[Max],size[Max],dis[Max],num[Max],len[Max],val[Max],v[Max];

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

struct bian{int x,y,len;}d[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,int z){edge[++s].next=first[x],first[x]=s,edge[s].to=y,edge[s].len=z;}

inline void dfs1(int point,int fa)

{

size[point]=1,father[point]=fa,depth[point]=depth[fa]+1;

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

{

  int to=edge[u].to;

  if(to==fa) continue;

  val[to]=edge[u].len,dis[to]=dis[point]+edge[u].len;

  dfs1(to,point);

  size[point]+=size[to];

  if(size[to] > size[son[point]]) son[point]=to;

}

}

inline void dfs2(int point,int fa)

{

if(son[point])

{

  pos[son[point]]=++tot,len[tot]=val[son[point]],top[son[point]]=top[point];

  dfs2(son[point],point);

}

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

{

  int to=edge[u].to;

  if(top[to]) continue;

  pos[to]=++tot,top[to]=to;

  dfs2(to,point);

}

}

inline int LCA(int x,int y)

{

while(top[x]!=top[y])

{

  if(depth[top[x]] < depth[top[y]]) x^=y,y^=x,x^=y;

  x=father[top[x]];

}

if(depth[x] > depth[y]) swap(x,y);

return x;

}

inline bool comp(const bian &a,const bian &b){return a.len>b.len;}

inline void solve(int x,int y)

{

while(top[x]!=top[y])

{

  if(depth[top[x]] < depth[top[y]]) x^=y,y^=x,x^=y;

  num[pos[top[x]]+1]++,num[pos[x]+1]--;

  x=father[top[x]];

}

if(x==y) return;

if(depth[x] > depth[y]) x^=y,y^=x,x^=y;

num[pos[x]+1]++,num[pos[y]+1]--;

}

inline int mx(int x,int y){return x < y ? y : x;}

inline int check(int mid)

{

int k=0,x=0,sum=0;

while(d[k+1].len>mid) k++;

if(v[k]) return v[k];

memset(num,0,sizeof(num));

for(int i=1;i<=k;i++) solve(d[i].x,d[i].y);

for(int i=1;i<=n;i++){sum+=num[i];if(sum == k) x=mx(x,len[i]);}

v[k]=x;

return x;

}

inline void print(int x){if(x>9) print(x/10);putchar('0'+x%10);}

int main()

{

n=get_int(),m=get_int();

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

{

  int x=get_int(),y=get_int(),z=get_int();

  build(x,y,z),build(y,x,z);

}

top[1]=tot=pos[1]=1;

dfs1(1,0),dfs2(1,0);

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

{

  d[i].x=get_int(),d[i].y=get_int();

  d[i].len=dis[d[i].x]+dis[d[i].y]-2*dis[LCA(d[i].x,d[i].y)];

}

sort(d+1,d+m+1,comp);

l=0,r=d[1].len;

while(l<r)

{

  mid=(l+r)>>1;

  (d[1].len - check(mid) <= mid) ? r=mid : l=mid+1;

}

print(r);

return 0;

}

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

生活大爆炸版石头剪刀布

【问题描述】

石头剪刀布是常见的猜拳游戏:石头胜剪刀,剪刀胜布,布胜石头。如果两个人出拳一样,则不分胜负。在《生活大爆炸》第二季第 8 集中出现了一种石头剪刀布的升级版游戏。升级版游戏在传统的石头剪刀布游戏的基础上,增加了两个新手势:

斯波克:《星际迷航》主角之一。

蜥蜴人:《星际迷航》中的反面角色。

这五种手势的胜负关系如表一所示,表中列出的是甲对乙的游戏结果。

现在,小 A 和小 B 尝试玩这种升级版的猜拳游戏。已知他们的出拳都是有周期性规律的,但周期长度不一定相等。例如:如果小 A 以“石头-布-石头-剪刀-蜥蜴人-斯波克”长度为 6 的周期出拳,那么他的出拳序列就是“石头-布-石头-剪刀-蜥蜴人-斯波克-石头-布-石头-剪刀-蜥蜴人-斯波克-……”,而如果小 B 以“剪刀-石头-布-斯波克-蜥蜴人”长度为 5 的周期出拳,那么他出拳的序列就是“剪刀-石头-布-斯波克-蜥蜴人-剪刀-石头-布-斯波克-蜥蜴人-……”

已知小 A 和小 B 一共进行 N 次猜拳。每一次赢的人得 1 分,输的得 0 分;平局两人都得 0 分。现请你统计 N 次猜拳结束之后两人的得分。

【输入】

输入文件名为 rps.in。

第一行包含三个整数:N,NA,NB,分别表示共进行 N 次猜拳、小 A 出拳的周期长度,小 B 出拳的周期长度。数与数之间以一个空格分隔。

第二行包含 NA 个整数,表示小 A 出拳的规律,第三行包含 NB 个整数,表示小 B 出拳的规律。其中,0 表示“剪刀”,1 表示“石头”,2 表示“布”,3 表示“蜥蜴人”, 4 表示“斯波克”。数与数之间以一个空格分隔。

【输出】

输出文件名为 rps.out。

输出一行, 包含两个整数,以一个空格分隔,分别表示小 A、小 B 的得分。

【输入输出样例 1】

【输入输出样例 2】

【数据说明】

对于 100%的数据,0 < N ≤ 200,0 < NA ≤ 200, 0 < NB ≤ 200。

答案与解析
参考答案

#include<bits/stdc++.h>

using namespace std;

int n , a , b , arr[205] , brr[205] , x , y;

int main(){

scanf("%d %d %d" , &n , &a , &b);

for(int i = 0 ; i < a ; i++) cin >> arr[i];

for(int i = 0 ; i < b ; i++) cin >> brr[i];

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

if(arr[i % a] == 0 && brr[i % b] == 2 ||

   arr[i % a] == 0 && brr[i % b] == 3 ||

   arr[i % a] == 1 && brr[i % b] == 0 ||

   arr[i % a] == 1 && brr[i % b] == 3 ||

   arr[i % a] == 2 && brr[i % b] == 1 ||

   arr[i % a] == 2 && brr[i % b] == 4 ||

   arr[i % a] == 3 && brr[i % b] == 2 ||

   arr[i % a] == 3 && brr[i % b] == 4 ||

   arr[i % a] == 4 && brr[i % b] == 0 ||

   arr[i % a] == 4 && brr[i % b] == 1)

   x++;

else if(arr[i % a] == brr[i % b]) continue;

else y++; 

} 

cout << x << " " << y;

return 0;

} 

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

联合权值

【问题描述】

无向连通图 G 有 n 个点,n-1 条边。点从 1 到 n 依次编号,编号为 i 的点的权值为 Wi ,每条边的长度均为 1。图上两点(u, v)的距离定义为 u 点到 v 点的最短距离。对于图 G 上的点对(u, v),若它们的距离为 2,则它们之间会产生的联合权值。

请问图 G 上所有可产生联合权值的有序点对中,联合权值最大的是多少?所有联合权值之和是多少?

【输入】

输入文件名为 link.in。

第一行包含 1 个整数 n。

接下来 n-1 行,每行包含 2 个用空格隔开的正整数 u、v,表示编号为 u 和编号为 v 的点之间有边相连。

最后 1 行,包含 n 个正整数,每两个正整数之间用一个空格隔开,其中第 i 个整数表示图 G 上编号为 i 的点的权值为 Wi。

【输出】

输出文件名为 link.out。

输出共 1 行,包含 2 个整数,之间用一个空格隔开,依次为图 G 上联合权值的最大值和所有联合权值之和。由于所有联合权值之和可能很大,输出它时要对 10007 取余。

【输入输出样例】

【样例说明】

 本例输入的图如上所示,距离为 2 的有序点对有(1,3)、(2,4)、(3,1)、(3,5)、(4,2)、(5,3)。

其联合权值分别为 2、15、2、20、15、20。其中最大的是 20,总和为 74。

【数据说明】

答案与解析
参考答案

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

long long n,x,y,v[500001],head[500001],nxt[500001],cnt,w[200001];

long long sum,maxx;

void add(int a,int b)//链式前向星存边,效率高,在图论中有很重要的作用 

{

    v[++cnt]=b;//v[cnt]表示编号为cnt的边的终点 

    nxt[cnt]=head[a];//nxt[cnt]表示第cnt条边下一条边是head[a] 

    head[a]=cnt;//插入链表头部 

}

int main()

{

    scanf("%lld",&n);

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

    {

        scanf("%lld%lld",&x,&y);

        add(x,y);//无向边存两次 

        add(y,x);

    }

    for(int i=1;i<=n;i++)scanf("%lld",&w[i]);

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

    {

    long long fix=0,maxn=0;

    for(int j=head[i];j;j=nxt[j])

    {

    sum+=(fix*w[v[j]])%10007;//和之前的数每个相乘再相加,只需加他们的和就好了。 

    fix+=w[v[j]];//根据乘法分配律,打前缀和 

    maxx=max(maxx,maxn*w[v[j]]);//打擂台取最大值 

    maxn=max(maxn,w[v[j]]);

}

}

    cout<<maxx<<" "<<sum*2%10007;

    return 0;

}

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

飞扬的小鸟

【问题描述】

Flappy Bird 是一款风靡一时的休闲手机游戏。玩家需要不断控制点击手机屏幕的频率来调节小鸟的飞行高度,让小鸟顺利通过画面右方的管道缝隙。如果小鸟一不小心撞到了水管或者掉在地上的话,便宣告失败。

为了简化问题,我们对游戏规则进行了简化和改编:

1. 游戏界面是一个长为 n,高为 m 的二维平面,其中有k 个管道(忽略管道的宽度)。

2. 小鸟始终在游戏界面内移动。小鸟从游戏界面最左边任意整数高度位置出发,到达游戏界面最右边时,游戏完成。

3. 小鸟每个单位时间沿横坐标方向右移的距离为 1,竖直移动的距离由玩家控制。如果点击屏幕,小鸟就会上升一定高度 X,每个单位时间可以点击多次,效果叠加;如果不点击屏幕,小鸟就会下降一定高度 Y。小鸟位于横坐标方向不同位置时,上升的高度 X 和下降的高度 Y 可能互不相同。

4. 小鸟高度等于 0 或者小鸟碰到管道时,游戏失败。小鸟高度为 m 时,无法再上升。

现在,请你判断是否可以完成游戏。如果可以,输出最少点击屏幕数;否则,输出小鸟最多可以通过多少个管道缝隙。

【输入】

输入文件名为 bird.in。

第 1 行有 3 个整数 n,m,k,分别表示游戏界面的长度,高度和水管的数量,每两个整数之间用一个空格隔开;

接下来的 n 行,每行 2 个用一个空格隔开的整数 X 和 Y,依次表示在横坐标位置 0~n-1上玩家点击屏幕后,小鸟在下一位置上升的高度 X,以及在这个位置上玩家不点击屏幕时,小鸟在下一位置下降的高度 Y。

接下来 k 行,每行 3 个整数 P,L,H,每两个整数之间用一个空格隔开。每行表示一个管道,其中 P 表示管道的横坐标,L 表示此管道缝隙的下边沿高度为 L,H 表示管道缝隙上边沿的高度(输入数据保证 P 各不相同,但不保证按照大小顺序给出)。

【输出】

输出文件名为 bird.out。

共两行。

第一行,包含一个整数,如果可以成功完成游戏,则输出 1,否则输出 0。

第二行,包含一个整数,如果第一行为 1,则输出成功完成游戏需要最少点击屏幕数,否则,输出小鸟最多可以通过多少个管道缝隙。

【输入输出样例 1】

【输入输出样例 2】

【输入输出样例说明】

如下图所示,蓝色直线表示小鸟的飞行轨迹,红色直线表示管道。

【数据范围】

对于 30%的数据:5≤n≤10,5≤m≤10,k=0,保证存在一组最优解使得同一单位时间最多点击屏幕 3 次;

对于 50%的数据:5≤n≤20,5≤m≤10,保证存在一组最优解使得同一单位时间最多点击屏幕 3 次;

对于 70%的数据:5≤n≤1000,5≤m≤100;

对于 100%的数据:5≤n≤10000,5≤m≤1000,0≤k<n,0<X<m,0<Y<m,0<P<n,0≤L<H ≤m,L+1<H。

答案与解析
参考答案

#include <bits/stdc++.h>

using namespace std;

#define me(a, b) memset(a, b, sizeof(a))

#define IOS() ios::sync_with_stdio(false), cin.tie(0)

#define endl '\n'


typedef long long ll;

typedef pair<ll, ll> pll;

typedef pair<int, int> pii;

const int INF = 0x3f3f3f3f;

const int maxn = 1e4 + 5;

const ll mod = 1e9 + 7;


int dp[maxn][2005]; // dp[i][j] 表示到 i,j的最小操作

int x[maxn], y[maxn]; // 上升 和 下降

pii lim[maxn]; // 每列的范围

bool vis[maxn]; // 是不是管道


bool check(int i, int x) // 检查 x 是否在 第 i 行范围中

{

    return x >= lim[i].first && x <= lim[i].second;

}


int main()

{

    IOS();

    int n, m, k;

    cin >> n >> m >> k;

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

        cin >> x[i] >> y[i];

        lim[i].first = 1;

        lim[i].second = m;

    }

    lim[0].first = 0;

    lim[n].first = 1;

    lim[n].second = m;

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

        int p, l, r;

        cin >> p >> l >> r;

        vis[p] = true;

        lim[p].first = l + 1;

        lim[p].second = r - 1;

    }

    me(dp, 0x3f);

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

        dp[0][i] = 0;

    

    int p = 0;

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

        // 上升完全背包

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

            // 这里其实是做 01 背包,所以必须要从合法位置转移

            if(check(i-1, j-x[i-1]))

                dp[i][j] = min(dp[i][j], dp[i-1][j-x[i-1]] + 1);

            // 这里才是完全背包,就不需要检查范围

            dp[i][j] = min(dp[i][j], dp[i][j-x[i-1]] + 1);

        }

        // 特判 上届的情况

        if(m == lim[i].second) {

            for(int j = m-x[i-1]+1; j <= m; ++j) {

                if(check(i-1, j))

                    dp[i][m] = min(dp[i][m], dp[i-1][j] + 1);

                if(check(i, j))

                    dp[i][m] = min(dp[i][m], dp[i][j] + 1);

            }

        }


        // 下降01背包

        for(int j = lim[i].first; j <= lim[i].second; ++j) {

            if(check(i-1, j+y[i-1]))

                dp[i][j] = min(dp[i][j], dp[i-1][j+y[i-1]]);

            if(dp[i][j] != INF)

                p = i;

        }

    }

    int ans = INF;

    for(int i = lim[n].first; i <= lim[n].second; ++i) {

        ans = min(ans, dp[n][i]);

    }

    if(ans != INF) {

        cout << "1\n" << ans << endl;

    }

    else {

        int cnt = 0;

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

            if(vis[i]) ++cnt;

        cout << "0\n" << cnt << endl;

    }


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

    //     for(int j = 0; j <= m; ++j) {

    //         cout << (dp[i][j]==INF?-1:dp[i][j]) << " ";

    //     }

    //     cout << endl;

    // }


    return 0;

}

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

无线网络发射器选址

【问题描述】

随着智能手机的日益普及,人们对无线网的需求日益增大。某城市决定对城市内的公共场所覆盖无线网。

假设该城市的布局为由严格平行的129条东西向街道和129条南北向街道所形成的网格状,并且相邻的平行街道之间的距离都是恒定值 1。东西向街道从北到南依次编号为0,1,2…128,南北向街道从西到东依次编号为 0,1,2…128。

东西向街道和南北向街道相交形成路口,规定编号为 x 的南北向街道和编号为 y 的东西向街道形成的路口的坐标是(x, y)。在某些路口存在一定数量的公共场所。

由于政府财政问题,只能安装一个大型无线网络发射器。该无线网络发射器的传播范围是一个以该点为中心,边长为 2*d 的正方形。传播范围包括正方形边界。

例如下图是一个 d = 1 的无线网络发射器的覆盖范围示意图。

现在政府有关部门准备安装一个传播参数为 d 的无线网络发射器,希望你帮助他们在城市内找出合适的安装地点,使得覆盖的公共场所最多。

【输入】

输入文件名为 wireless.in。

第一行包含一个整数 d,表示无线网络发射器的传播距离。

第二行包含一个整数 n,表示有公共场所的路口数目。

接下来 n 行,每行给出三个整数 x, y, k, 中间用一个空格隔开,分别代表路口的坐标(x, y)以及该路口公共场所的数量。同一坐标只会给出一次。

【输出】

输出文件名为 wireless.out。

输出一行,包含两个整数,用一个空格隔开,分别表示能覆盖最多公共场所的安装地点方案数,以及能覆盖的最多公共场所的数量。

【输入输出样例】

【数据说明】

对于 100%的数据,1 ≤ d ≤ 20,1 ≤ n ≤ 20, 0 ≤ x ≤ 128, 0 ≤ y ≤ 128, 0 < k ≤1,000,000。

答案与解析
参考答案

#include<cstdio>

#include<cstdlib>

int main(){

    int ans=0,d,n,x,y,k[129][129],jc=0,sum=0,m1,m2,n1,n2;

    bool city[129][129];

    scanf("%d",&d);

    scanf("%d",&n);

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

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

                            scanf("%d",&k[x][y]);

                            city[x][y]=true;

                            }          

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

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

            n1=i-d;n2=i+d;m1=j-d;m2=j+d;

                     if (n1<0) n1=0;if (n2>128) n2=128;

                     if (m1<0) m1=0;if (m2>128) m2=128;

            for (int q=n1;q<=n2;q++)

                 for (int p=m1;p<=m2;p++)

                             if (city[q][p]) ans=ans+k[q][p];  

            if (ans>jc) {jc=ans;

                         sum=1;}

            else if (ans==jc) sum++;

            ans=0;

                                 }

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

    //system("pause");                           

    return 0;   

}

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

火柴排队

【问题描述】

涵涵有两盒火柴,每盒装有 n 根火柴,每根火柴都有一个高度。现在将每盒中的火柴各自排成一列,同一列火柴的高度互不相同,两列火柴之间的距离定义为:

其中 ai表示第一列火柴中第 i 个火柴的高度,bi表示第二列火柴中第 i 个火柴的高度。

每列火柴中相邻两根火柴的位置都可以交换,请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离,最少需要交换多少次?如果这个数字太大,请输出这个最小交换次数对 99,999,997 取模的结果。

【输入】

输入文件为 match.in。

共三行,第一行包含一个整数 n,表示每盒中火柴的数目。

第二行有 n 个整数,每两个整数之间用一个空格隔开,表示第一列火柴的高度。

第三行有 n 个整数,每两个整数之间用一个空格隔开,表示第二列火柴的高度。

【输出】

输出文件为 match.out。

输出共一行,包含一个整数,表示最少交换次数对 99,999,997 取模的结果。

【输入输出样例 1】

【输入输出样例说明】

最小距离是 0,最少需要交换 1 次,比如:交换第 1 列的前 2 根火柴或者交换第 2 列的前 2 根火柴。

【输入输出样例 2】

【输入输出样例说明】

最小距离是 10,最少需要交换 2 次,比如:交换第 1 列的中间 2 根火柴的位置,再交

换第 2 列中后 2 根火柴的位置。

【数据范围】

对于 10%的数据, 1 ≤ n ≤ 10;

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

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

对于 100%的数据,1 ≤ n ≤ 100,000,0 ≤火柴高度≤

答案与解析
参考答案

#include <bits/stdc++.h>

using namespace std;

 

const int mod=99999997;

const int Max=100005;

int n,m,tot,ans;

int sum[Max],c[Max<<1],num[Max];

struct shu{int num,id;};

shu a[Max],b[Max];

 

inline int get_int()

{

int x=0,f=1;

char c;

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

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

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

return x*f;

}

 

inline bool comp(const shu &a,const shu &b){return a.num<b.num;}

 

inline void pre()

{ 

sort(c+1,c+tot+1);

m=unique(c+1,c+tot+1)-c-1;

for(int i=1;i<=n;i++) a[i].num=lower_bound(c+1,c+m+1,a[i].num)-c;

for(int i=1;i<=n;i++) b[i].num=lower_bound(c+1,c+m+1,b[i].num)-c;

}

 

inline void add(int num)

{

for(int i=num;i<=100000;i+=i&(-i)) sum[i]++;

}

 

inline int Q(int num)

{

int ans=0;

for(int i=num;i;i-=i&(-i)) ans+=sum[i];

return ans;

}

 

inline void solve()

{

for(int i=1;i<=n;i++) add(num[i]),ans=(ans+i-Q(num[i]))%mod;

cout<<ans<<"\n";

}

 

int main()

{

n=get_int();

for(int i=1;i<=n;i++) c[++tot]=a[i].num=get_int(),a[i].id=i;

for(int i=1;i<=n;i++) c[++tot]=b[i].num=get_int(),b[i].id=i;

pre();

sort(a+1,a+n+1,comp),sort(b+1,b+n+1,comp);

for(int i=1;i<=n;i++) num[a[i].id]=b[i].id;

solve();

return 0;

}

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

积木大赛

【题目描述】

春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为n的大厦,大厦可以看成由n块宽度为1的积木组成,第i块积木的最终高度需要是hi。

在搭建开始之前,没有任何积木(可以看成n块高度为 0 的积木)。接下来每次操作,小朋友们可以选择一段连续区间[L,R],然后将第L块到第R块之间(含第 L 块和第 R 块)所有积木的高度分别增加1。

小M是个聪明的小朋友,她很快想出了建造大厦的最佳策略,使得建造所需的操作次数最少。但她不是一个勤于动手的孩子,所以想请你帮忙实现这个策略,并求出最少的操作次数。

【输入】

输入文件为 block.in

输入包含两行,第一行包含一个整数n,表示大厦的宽度。

第二行包含n个整数,第i个整数为hi。

【输出】

输出文件为 block.out

仅一行,即建造所需的最少操作数。

【输入输出样例】

【样例解释】

其中一种可行的最佳方案,依次选择[1,5] [1,3] [2,3] [3,3] [5,5]

【数据范围】

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

对于 70%的数据,有1 ≤ n ≤ 1000;

对于 100%的数据,有1 ≤ n ≤ 100000,0 ≤ hi ≤ 10000。

答案与解析
参考答案

#include <iostream>

#include <algorithm>


using namespace std;


const int N = 100010;


int n;

int h[N];


int main()

{

    scanf("%d", &n);

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


    int res = 0;

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

     if(h[i]-h[i-1]>0)res+=h[i]-h[i-1];

}

    cout << res << endl;


    return 0;

}

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

花匠

【问题描述】

花匠栋栋种了一排花,每株花都有自己的高度。花儿越长越大,也越来越挤。栋栋决定把这排中的一部分花移走,将剩下的留在原地,使得剩下的花能有空间长大,同时,栋栋希望剩下的花排列得比较别致。

具体而言,栋栋的花的高度可以看成一列整数h1, h2, … , hn。设当一部分花被移走后,剩下的花的高度依次为g1, g2, … , gm,则栋栋希望下面两个条件中至少有一个满足:

条件 A:对于所有的i,g2i > g2i−1,且g2i > g2i+1;

条件 B:对于所有的i,g2i < g2i−1,且g2i < g2i+1。

注意上面两个条件在m = 1时同时满足,当m > 1时最多有一个能满足。

请问,栋栋最多能将多少株花留在原地。

【输入】

输入文件为 flower.in。

输入的第一行包含一个整数n,表示开始时花的株数。

第二行包含n个整数,依次为h1, h2,… , hn,表示每株花的高度。

【输出】

输出文件为 flower.out。

输出一行,包含一个整数m,表示最多能留在原地的花的株数。

【输入输出样例】

【输入输出样例说明】

有多种方法可以正好保留 3 株花,例如,留下第 1、4、5 株,高度分别为 5、1、2,满足条件 B。

【数据范围】

对于 20%的数据,n ≤ 10;

对于 30%的数据,n ≤ 25;

对于 70%的数据,n ≤ 1000,0 ≤ hi ≤ 1000;

对于 100%的数据,1 ≤ n ≤ 100,000,0 ≤ hi ≤ 1,000,000,所有的hi随机生成,所有随机数服从某区间内的均匀分布。

答案与解析
参考答案

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n,a[N],ans;

int f[N][2];


int main()

{

scanf("%d",&n);

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

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

f[1][0] = f[1][1] = 1;

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

{

if(a[i] > a[i - 1])

f[i][1] = max(f[i - 1][1],f[i - 1][0] + 1);

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

if(a[i] < a[i - 1])

f[i][0] = max(f[i - 1][0],f[i - 1][1] + 1);

else f[i][0] = f[i - 1][0];

}

printf("%d",max(f[n][0],f[n][1]));

return 0;

}

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

华容道

【问题描述】

小 B 最近迷上了华容道,可是他总是要花很长的时间才能完成一次。于是,他想到用编程来完成华容道:给定一种局面,华容道是否根本就无法完成,如果能完成,最少需要多少时间。

小 B 玩的华容道与经典的华容道游戏略有不同,游戏规则是这样的:

1. 在一个 n*m 棋盘上有 n*m 个格子,其中有且只有一个格子是空白的,其余 n*m-1个格子上每个格子上有一个棋子,每个棋子的大小都是 1*1 的;

2. 有些棋子是固定的,有些棋子则是可以移动的;

3. 任何与空白的格子相邻(有公共的边)的格子上的棋子都可以移动到空白格子上。游戏的目的是把某个指定位置可以活动的棋子移动到目标位置。

给定一个棋盘,游戏可以玩 q 次,当然,每次棋盘上固定的格子是不会变的,但是棋盘上空白的格子的初始位置、指定的可移动的棋子的初始位置和目标位置却可能不同。第 i 次玩的时候,空白的格子在第 EXi行第 EYi列,指定的可移动棋子的初始位置为第 SXi行第 SYi列,目标位置为第 TXi行第 TYi列。

假设小 B 每秒钟能进行一次移动棋子的操作,而其他操作的时间都可以忽略不计。请你告诉小 B 每一次游戏所需要的最少时间,或者告诉他不可能完成游戏。

【输入】

输入文件为 puzzle.in。

第一行有 3 个整数,每两个整数之间用一个空格隔开,依次表示 n、m 和 q;

接下来的 n 行描述一个 n*m 的棋盘,每行有 m 个整数,每两个整数之间用一个空格隔开,每个整数描述棋盘上一个格子的状态,0 表示该格子上的棋子是固定的,1 表示该格子上的棋子可以移动或者该格子是空白的。

接下来的 q 行,每行包含 6 个整数依次是 EXi、EYi、SXi、SYi、TXi、TYi,每两个整数之间用一个空格隔开,表示每次游戏空白格子的位置,指定棋子的初始位置和目标位置。

【输出】

输出文件名为 puzzle.out。

输出有 q 行,每行包含 1 个整数,表示每次游戏所需要的最少时间,如果某次游戏无法完成目标则输出−1。

【输入输出样例】

【输入输出样例说明】

棋盘上划叉的格子是固定的,红色格子是目标位置,圆圈表示棋子,其中绿色圆圈表示目标棋子。

1. 第一次游戏,空白格子的初始位置是 (3, 2)(图中空白所示),游戏的目标是将初始位置在(1, 2)上的棋子(图中绿色圆圈所代表的棋子)移动到目标位置(2, 2)(图中红色的格子)上。

2. 第二次游戏,空白格子的初始位置是(1, 2)(图中空白所示),游戏的目标是将初始位置在(2, 2)上的棋子(图中绿色圆圈所示)移动到目标位置 (3, 2)上。

要将指定块移入目标位置,必须先将空白块移入目标位置,空白块要移动到目标位置,

必然是从位置(2,2)上与当前图中目标位置上的棋子交换位置,之后能与空白块交换位置

的只有当前图中目标位置上的那个棋子,因此目标棋子永远无法走到它的目标位置,游戏无

法完成。

【数据范围】

对于 30%的数据,1 ≤ n, m ≤ 10,q = 1;

对于 60%的数据,1 ≤ n, m ≤ 30,q ≤ 10;

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

答案与解析
参考答案

#include <bits/stdc++.h> 

using namespace std;

 

const int Max=35;

const int fx[5]={0,1,0,-1};

const int fy[5]={1,0,-1,0};

int n,m,q,head,tail,tot,ans;

int num[Max][Max],dis[Max][Max][5],move[Max][Max][5][5];

bool vis[Max][Max],v[Max][Max][5];

int p[1000000][5],d[1000000][5];

 

inline void bfs(int x,int y,int k1,int k2)

{

int sx=x+fx[k1],sy=y+fy[k1],tx=x+fx[k2],ty=y+fy[k2];

if((!num[sx][sy])||(!num[tx][ty])) return;

head=0,tail=1;

p[1][1]=sx,p[1][2]=sy;

memset(vis,0,sizeof(vis));

vis[x][y]=vis[sx][sy]=1;

while(head<tail)

{

  head++;

  int xx=p[head][1],yy=p[head][2];

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

  {

  int x1=xx+fx[i],y1=yy+fy[i];

  if(!vis[x1][y1] && num[x1][y1])

  {

   vis[x1][y1]=1;

     p[++tail][1]=x1,p[tail][2]=y1,p[tail][0]=p[head][0]+1;

     if(x1==tx&&y1==ty) {move[x][y][k1][k2]=p[tail][0];return;}

  }

  }

}

}

 

inline void pre()

{

memset(move,43,sizeof(move));

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

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

    if(num[i][j])

      for(int k=0;k<=3;k++)

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

          if(l==k) move[i][j][k][l]=0;

          else bfs(i,j,k,l);

}

 

inline void calc(int x,int y,int sx,int sy)

{

head=0,tail=1,tot=0;

p[1][1]=x,p[1][2]=y,p[1][0]=0;

memset(vis,0,sizeof(vis));

vis[x][y]=vis[sx][sy]=1;

while(head<tail)

{

  head++;

  int xx=p[head][1],yy=p[head][2];

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

  {

  int x1=xx+fx[i],y1=yy+fy[i];

  if(num[x1][y1]&&!vis[x1][y1])

  {

    vis[x1][y1]=1;

    p[++tail][0]=p[head][0]+1;

    p[tail][1]=x1,p[tail][2]=y1;

  }

  else if(x1==sx&&y1==sy) d[++tot][1]=x1,d[tot][2]=y1,d[tot][0]=p[head][0],d[tot][3]=(i+2)%4;

  }

}

}

 

inline void SPFA()

{

memset(v,0,sizeof(v));

for(int i=1;i<=tot;i++) dis[d[i][1]][d[i][2]][d[i][3]]=d[i][0],v[d[i][1]][d[i][2]][d[i][3]]=1;

head=0,tail=tot;

while(head<tail)

{

  head++;

  int x=d[head][1],y=d[head][2];

  v[x][y][d[head][3]]=0;

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

  {

  int x1=x+fx[i],y1=y+fy[i];

  if(dis[x1][y1][(i+2)%4] > dis[x][y][d[head][3]]+move[x][y][d[head][3]][i]+1)

  {

  dis[x1][y1][(i+2)%4]=dis[x][y][d[head][3]]+move[x][y][d[head][3]][i]+1;

  if(!v[x1][y1][(i+2)%4])

  {

  tail++;

  d[tail][1]=x1,d[tail][2]=y1,d[tail][3]=(i+2)%4;

  v[x1][y1][(i+2)%4]=1;

  }

} 

  }

}

}

 

int main()

{

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

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

  for(int j=1;j<=m;j++) scanf("%d",&num[i][j]);

pre();

while(q--)

{

  int x,y,sx,sy,tx,ty;

  scanf("%d%d%d%d%d%d",&x,&y,&sx,&sy,&tx,&ty);

  if(sx==tx&&sy==ty) {cout<<"0\n";continue;}

  memset(dis,43,sizeof(dis));

  calc(x,y,sx,sy);

  SPFA();

  ans=dis[0][0][0];

  for(int i=0;i<=3;i++) ans=min(ans,dis[tx][ty][i]);

  if(ans==dis[0][0][0]) cout<<"-1\n";

  else cout<<ans<<"\n";

}

return 0;

}

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

Vigenère 密码

【问题描述】

16 世纪法国外交家 Blaise de Vigenère 设计了一种多表密码加密算法——Vigenère 密码。Vigenère 密码的加密解密算法简单易用,且破译难度比较高,曾在美国南北战争中为南军所广泛使用。

在密码学中,我们称需要加密的信息为明文,用 M 表示;称加密后的信息为密文,用C 表示;而密钥是一种参数,是将明文转换为密文或将密文转换为明文的算法中输入的数据,记为 k。 在 Vigenère 密码中,密钥 k 是一个字母串,k=k1k2…kn。当明文 M=m1m2…mn时,得到的密文 C=c1c2…cn,其中 ci=mi®ki,运算®的规则如下表所示:

Vigenère 加密在操作时需要注意:

1. ®运算忽略参与运算的字母的大小写,并保持字母在明文 M 中的大小写形式;

2. 当明文 M 的长度大于密钥 k 的长度时,将密钥 k 重复使用。

例如,明文 M=Helloworld,密钥 k=abc 时,密文 C=Hfnlpyosnd。

【输入】

输入文件名为 vigenere.in。

输入共 2 行。

第一行为一个字符串,表示密钥 k,长度不超过 100,其中仅包含大小写字母。第二行为一个字符串,表示经加密后的密文,长度不超过 1000,其中仅包含大小写字母。

【输出】

输出文件名为 vigenere.out。

输出共 1 行,一个字符串,表示输入密钥和密文所对应的明文。

【输入输出样例】

【数据说明】

对于 100%的数据,输入的密钥的长度不超过 100,输入的密文的长度不超过 1000,且都仅包含英文字母。

答案与解析
参考答案

#include <cstdio>


#include <iostream>


#include <cstring>


using namespace std;


int len1, len2;


char s1[10001];                                         // 秘钥字符串


char s2[10001];                                          // 密文字符串


void turn(char &x) {

     if ('a'<=x && x<='z') {                            // 将小写字母转为大写字母


         x -= 'a'-'A';                                        // 等同于 x-=32


     }


}


int main() {

     scanf("%s", s1);                                   // 输入秘钥字符串


     len1 = strlen(s1);


     for (int i=0; i<len1; i++) {                      // 等同于 strupr(s1); 将秘钥转为大写字母


         turn(s1[i]);      


     } 


     scanf("%s", s2);                                    // 输入密文字符串


     len2 = strlen(s2);


     int j = 0;                                                 // 秘钥从头开始解密


     for (int i=0; i<len2; i++) {                       // 密文的每个字符


         if (s2[i] <= 'Z') {                                 // 如果密文字符是大写(已知输入密文字符串仅包含大小写字母)


              s2[i] -= (s1[j] - 'A');


              j++;


              if (s2[i] < 'A') {                             // 若明文小于'A',就从字母表倒叙转换


                   s2[i] = 'Z' - ('A' - s2[i]) + 1;


              }


         } else {                                             // 如果密文字符是小写


              s2[i] -= s1[j]-'A';


              j++;


              if (s2[i] < 'a') {

                   s2[i] = 'z' - ('a' - s2[i]) + 1;       // 若明文小于'a',就从字母表倒叙转换


              }


         }


         if (j > len1-1) {                                   // 若明文长度大于秘钥长度,重复使用秘钥


              j = 0;


         }       


     }


     cout << s2;


     return 0;


}

题目详情