2018年新生个人训练赛第十一场(第27届宁波市信息学竞赛小学组,初中组)

第一批乘客发出请求到离开电梯所需时间：3*2+6+3*11+6=51 从前一批乘客离开电梯到第二批乘客离开电梯所需时间：3*6+6+3*4+6=42 第三批乘客从出发地出发到离开电梯所需时间：
3*8+6=30（由于出发地与前一批乘客目的地相同，所以上下客时间不必再加 6） 从前一批乘客离开电梯到第四批乘客离开电梯所需时间：3+6+3*8+6=39 总花费时间：51+42+30+39=162

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
typedef struct point{int num,t,s,f;
}p;
p a[110];
int cmp(p x,p y){return x.t<y.t;
}
int main()
{int x,n,c=3,ans=0,time=2020;scanf("%d%d",&x,&n);for(int i=0;i<n;i++){scanf("%d%d%d",&a[i].t,&a[i].s,&a[i].f);a[i].num=i;time=min(time,a[i].t);}sort(a,a+n,cmp);ans=0;ans=ans+abs(a[0].s-x)*3;ans+=6;ans=ans+abs(a[0].f-a[0].s)*3;if(a[0].f!=a[1].s){ans+=6;}for(int i=1;i<n;i++){ans=max(a[i].t,ans);ans=ans+abs(a[i-1].f-a[i].s)*3;if(a[i-1].f!=a[i].s){ans+=6;}ans=ans+abs(a[i].s-a[i].f)*3;if(a[i].f!=a[i].s){ans+=6;}}printf("%d\n",ans);return 0;
}

题目描述

输入

输出

样例输入

4 3
1024
010

样例输出

1124

提示

#include<stdio.h>
#include<algorithm>
using namespace std;
int main()
{int str[11]={0},n,m;char a[100050],b[100050];scanf("%d %d\n",&n,&m);scanf("%s",a);scanf("%s",b);for(int i=0;i<m;i++){str[b[i]-'0']++;}for(int i=0;i<n;i++){for(int j=9;j>=0;j--){if(a[i]<(j+'0')&&str[j]){a[i]=(j+'0');str[j]--;break;}}}printf("%s\n",a);return 0;
}

题目描述

味味妈妈有一串珠子串成的项链，这个项链中的珠子最多有 3 种颜色（红、蓝、白， 分别用 r、b、w 表示）。某天，味味想从妈妈项链中取出一些珠子来玩，妈妈虽然答应了， 但提出了以下条件：
（1）只能在项链中选择一个地方剪断，然后从断开的两端开始依次取出珠子；
（2）每一端取珠子时，如果珠子颜色与该端第一颗珠子颜色相同则可以连续取下去， 直到出现一颗与该端第一颗颜色不同的珠子。如果遇到白色珠子则可根据需要看做蓝色或者 红色。

 

味味对于颜色并没有特殊要求，但她想得到尽可能多的珠子。
为方便表示，我们给项链中的珠子按顺时针方向编号，如图-1 和图-2 所示为两种可能的项链情况（珠子都有 11 颗）。
对于图-1 来说，如果在 1 和 2 号珠子之间剪断，则味味可以取到共 2 颗珠子。而如果 在 6 和 7 号珠子之间剪断，则味味可以取到共 5 颗珠子（左边取 3 颗红色 r，右边取 2 颗 蓝色 b），而 5 颗珠子也是味味从这串项链中最多可以取到的珠子数量。
对于图-2 中的项链来说，如果在 1 和 2 号珠子之间剪断，则共可取走 4 颗珠子（将 1 号珠子当做蓝色，这样左边可取 3 颗，右边可取 1 颗蓝色 b）。而如果在 2 和 3 号之间剪断， 则共可取走 6 颗珠子（将 1 号珠子当做蓝色，这样左边可取 4 颗蓝色 b，右边可取 2 颗红 色 r）。

输入

输出

样例输入

11
wbrrbbwbrbb

样例输出

6

提示

#include<stdio.h>
#include<algorithm>
using namespace std;
int main()
{int n,ans=0;char a[10000];scanf("%d",&n);scanf("%s",a);for(int i=0;i<n;i++){a[i+n]=a[i];a[i+2*n]=a[i];}a[n*3]='\0';for(int i=n;i<=2*n;i++){char ch1=a[i],ch2=a[i+1];int l=1,r=1;for(int j=i-1;j>=0;j--){if(a[j]=='w'){l++;}else if(ch1==a[j]){l++;}else{if(ch1=='w'){ch1=a[j];l++;}else{break;}}}for(int j=i+2;j<=3*n;j++){if(a[j]=='w'){r++;}else if(ch2==a[j]){r++;}else{if(ch2=='w'){r++;ch2=a[j];}else{break;}}}ans=max(r+l,ans);}ans=min(ans,n);printf("%d\n",ans);return 0;
}

题目描述

输入

输出

样例输入

2
90

样例输出

09

提示

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
long long tmp[20];
long long first[20];
long long remain;
int n;
void init()
{tmp[1]=1;for (int i=2; i<=12; ++i)tmp[i]=tmp[i-1]*10+1;cin >> n;cin >> remain;for (int i=0; i<=9; ++i)first[i]=i*tmp[n];
}
void print(long long x,long long y,long long z)
{for (int i=1; i<=n-1; ++i)y*=i;long long k1=0,k2=1;for (int i=1; i<=n; ++i){k1+=k2*y;k2*=10;}if (k1-x!=remain) return;int c[20];int pos=0;memset(c,0,sizeof(c));while (x>0){c[pos++]=x%10;x/=10;}for (int i=n-1; i>=0; --i)cout << c[i];cout << endl;exit(0);
}
void solve()
{int ll=1;for (int i=1; i<=n-1; ++i) ll*=i;for (int i=0; i<=n*9; ++i){for (int j=0; j<=9; ++j){long long second=first[j]*i*ll;long long third=second-remain;long long w = third;int x=0;while (w>0){x+=w%10;w/=10;}if (x==i && third>0) print(third,i,j);}}
}
int main()
{init();solve();
}

题目描述

Windows 中的扫雷游戏是大家都熟悉的小游戏，今天，味味也设计了一个简易的扫雷游戏。味 味设计的扫雷游戏功能如下：
1.程序一开始会读入扫雷区域大小 n，表示游戏区域有 n*n 个小方格组成，接下来会读入 n 行 信息，每行有 n 个整数（每个整数可能是 0，也可能是 1），每两个整数之间用一个空格分隔。其中 0 所在位置表示该小方格内没有地雷，1 所在位置表示该小方格内有地雷（游戏开始时，扫雷区域 中必定包含至少一个地雷）。 
接下来每行输入两个用空格分开的正整数 i 和 j，每一行的一对 i 和 j 表示用户用鼠标单击扫 雷区域中第 i 行第 j 列位置上的小方格（就象我们使用 Windows 中扫雷游戏一样），i 和 j 表示的 位置必定在扫雷区域内。程序每输入一对 i 和 j，就马上进行相应的处理（就象我们在 Windows 中 鼠标单击某个小方块就会出现结果一样）。 
2.程序将根据读入的一组 i 和 j 的值来对扫雷区域作相应处理，具体的处理规则如下： 
（1）如果 i 和 j 表示的小方格内没有地雷、而且也没有被处理过（就是第 i 行第 j 列的数值 是 0），那么将以该小方格为中心的一个正方形区域内所有没有地雷的小方格都赋值为-1（表示该 区域的地砖已经被掀开了）。如果在当前正方形区域内有一个位置号为 i1 和 j1（注意：i1<>i 并且 j1<>j）的小方格内恰好有地雷，则此地雷就被顺利扫除，将该位置标记为-2。如果该正方形区域 内某些小方格已经被处理过，则对这些小方格不再做任何处理。 
举个例子来说明一下，假如输入信息如下左边所示，那么处理结果就如下右边所示： 

（2）如果 i 和 j 表示的小方格已经被处理过（就是第 i 行第 j 列的数值是-1 或者是-2），那 么不作任何处理，继续去读取下一行的 i 和 j 的值。 
（3）如果 i 和 j 表示的小方格刚好有地雷，并且该小方格没有被处理过（就是第 i 行第 j 列
的数值是 1），那么表示用户触雷，马上输出信息“GAME  OVER!”,程序结束。 
3.如果在读入 i 和 j 的过程中一直没有触雷，那么就一直按照位置信息处理下去，直到满足下 列条件之一，就输出相应信息并结束程序： 
（1）读入的 i 和 j 的值都是 0（表示用户不再在某个小方格内单击鼠标右键了），则输出处理 后整个扫雷区域的状态（就是输出 n 行 n 列的方阵，每行中两个整数之间用一个空格分隔，末尾没 有多余空格），然后程序结束。 
（2）如果某次处理完后，游戏区域内所有的地雷都被扫除了，那么不必再读入下一行的信息， 输出信息“YOU ARE WINNER!”,程序结束。 

输入

输出

样例输入

6
0 0 0 0 0 0
0 0 1 0 0 0
1 0 0 0 1 0
0 0 0 0 0 0
0 1 0 0 0 1
0 0 0 0 0 0
1 1
3 4
5 5
4 6
2 3
0 0

样例输出

-1 -1 0 0 0 0
-1 -1 -2 -1 -1 0
1 0 -1 -1 -2 0
0 0 -1 -1 -1 -1
0 1 0 -1 -1 -2
0 0 0 -1 -1 -1

模拟即可。

#include<stdio.h>
#include<string.h>
int G[55][55],a[55][55],vis[55][55],flag=1,cnt1,cnt2,n;
void tu(int x,int y){if(x<=0||x>n||y<=0||y>n){return ;}if(vis[x][y]==0&&a[x][y]==1){vis[x][y]=1;cnt2++;}if(a[x][y]==1){G[x][y]=-2;}else{G[x][y]=-1;}
}
int check(int x,int y){int ans=0;for(int i=x-1;i<=x+1;i++){for(int j=y-1;j<=y+1;j++){tu(i,j);}}
}
int ck(int x,int y){if(a[x][y]==1){return 0;}else if(a[x][y]==0&&G[x][y]==0)check(x,y);else{return 1;}
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){scanf("%d",&a[i][j]);if(a[i][j]==1){cnt1++;}}}int tx,ty;while(~scanf("%d%d",&tx,&ty),(tx||ty)){if(G[tx][ty]==-1||G[tx][ty]==-2){continue;}if(ck(tx,ty)==0){printf("GAME OVER!\n");return 0;}if(cnt2==cnt1){printf("YOU ARE WINNER!\n");return 0;}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(G[i][j]==0&&a[i][j]==1){G[i][j]=1;}printf("%d%c",G[i][j],j==n?'\n':' ');}}return 0;
}

题目描述

输入

输出

样例输入

3
1 2
2 3

样例输出

3
2
3

提示

#include<bits/stdc++.h>
using namespace std;
int n,g[2000],tot,depth[2000],MAX;
struct tree{int t,next;
}e[500000];
void addedge(int a,int b){e[++tot].t=b;e[tot].next=g[a];g[a]=tot;
}
void dfs(int x,int father){depth[x]=depth[father]+1;MAX=max(MAX,depth[x]);for(int i=g[x];i;i=e[i].next){if(e[i].t!=father){dfs(e[i].t,x);}}
}
int main()
{scanf("%d",&n);for(int i=1;i<n;i++){int x,y;scanf("%d%d",&x,&y);addedge(x,y);addedge(y,x);}for(int i=1;i<=n;i++){MAX=0;dfs(i,0);printf("%d\n",MAX);memset(depth,0,sizeof(depth));}return 0;
}

题目描述

输入

输出

样例输入

4

样例输出

28 41

提示

#include<stdio.h>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
int main()
{ll n,cnt=0;scanf("%lld",&n);ll a[100000];for(int i=1;i*i<=n;i++){if(n%i==0){a[cnt++]=i;a[cnt++]=n/i;}}sort(a,a+cnt);map<ll,ll>my;for(int i=0;i<cnt;i++){my[a[i]]=1;}ll ans1=0x3f3f3f3f,ans2=-1;for(int i=0;i<cnt;i++){if((n%a[i]==0)&&(my[n/a[i]]==1))for(int j=0;j<cnt;j++){if(((n/a[i])%a[j]==0)&&(my[(n/a[i])/a[j]]==1))for(int k=0;k<cnt;k++){if(a[i]*a[j]*a[k]==n){ans1=min((a[i]+1)*(a[j]+2)*(a[k]+2)-n,ans1);ans2=max((a[i]+1)*(a[j]+2)*(a[k]+2)-n,ans2);}}}}printf("%lld %lld\n",ans1,ans2);return 0;
}

题目描述

输入

输出

样例输入

2 7

样例输出

33

提示

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll luck[10000];
int cnt;
int a[2]={4,7};
typedef struct point{ll x,step;
}p;
void bfs(){queue<p>q;p first={0,0};q.push(first);while(!q.empty()){p cur=q.front();q.pop();p next;if(cur.step==11){return ;}for(int i=0;i<2;i++){next.x=cur.x*10+a[i];next.step=cur.step+1;q.push(next);luck[++cnt]=next.x;}}
}
int main()
{bfs();ll L,R,ans=0;int k=0;scanf("%lld %lld",&L,&R);for(int i=0;i<=1024;i++){if(luck[i]>=L){k=i;break;}}for(int i=L;i<=R;i++){if(i>luck[k]){k++;}ans+=luck[k];}printf("%lld\n",ans);return 0;
}

题目描述

输入

输出

样例输入

3 3
1 2 3
1 2
2 3
3 1

样例输出

6

提示

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;ll n,m,price[1100];int main()
{ll ans=99999999;int G[110][110]={0},l,r;scanf("%lld%lld",&n,&m);for(int i=1;i<=n;i++){scanf("%lld",&price[i]);}for(int i=1;i<=m;i++){scanf("%d%d",&l,&r);G[l][r]=G[r][l]=1;}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){for(int k=1;k<=n;k++){if(G[i][j]+G[i][k]+G[k][j]==3){ans=min(ans,price[i]+price[j]+price[k]);}}}}if(ans==99999999){printf("-1\n");}else{printf("%lld\n",ans);}return 0;
}

题目描述

输入

输出

样例输入

991

样例输出

3

提示

#include<stdio.h>
#include<string.h>
typedef long long ll;
int main()
{char str[1005000],a[1000002];scanf("%s",str);ll t=0,ans=1;int len=strlen(str);for(int i=0;i<len;i++){t+=(str[i]-'0');}if(t<10&&len<2){printf("0");return 0;}for(;;){if(t<10){printf("%lld\n",ans);break;}ans++;sprintf(a,"%lld",t);//printf("%s\n",a);t=0,len=strlen(a);for(int i=0;i<len;i++){t+=(a[i]-'0');}}return 0;
}

#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;char str[1000000];int f(int p) {return (p == 0) ? 0 : (p%10 + f(p/10));
}int main(void) {scanf("%s", str);if (strlen(str) == 1) {printf("0\n");return 0;}int cnt = 0;for (char *i = str; *i; i++) {cnt += (*i - '0');}int res = 1;while (cnt >= 10) {cnt = f(cnt);++res;}printf("%d\n", res);return 0;
}