青藤编程营Day7信心赛赛后总结

藤编程营Day7信心赛赛后总结"/>

青藤编程营Day7信心赛赛后总结

青藤编程营Day7信心赛赛后总结

T1 麦当劳(mdl.cpp)

题目描述

近日，麦当劳的老板和老板娘因为改名问题吵了起来，老板想把名
字改为“金拱门”，他觉得比较接地气，而老板娘喜欢洋气点的名
字，她坚持原来的名字。眼看着越吵越凶，藤藤决定挺身而出，为他
们想一个解决方法：让老板和老板娘各投三次骰子来决定胜负，如果
老板三次的数字都比老板娘投出来的大，则取名为“金拱门”，否则
取名为“麦当劳”，现在给出他们各投三次之后出来的数字，你能帮
藤藤判断一下最终结果吗？

输入文件

输入文件mdl.in第1行为老板分别投三次骰子的数字; 第2行为老板娘分别投三次骰子的数字。(1<=数字<=6)

输出文件

输出文件mdl.out如果老板赢了，则输出“Golden Arch!”,否则输出“McDonald!”

输入样例

1 1 1
1 1 1

输出样例

McDonald!

思路

水题，没有数据范围和scanf的阻挠，直接一个一个判断即可

比赛代码(AC)

#include<bits/stdc++.h>
using namespace std;
int a[10],b;
int main(){freopen("mdl.in","r",stdin);freopen("mdl.out","w",stdout);for(int i=1;i<=3;i++){cin>>a[i];}for(int i=1;i<=3;i++){cin>>b;if(a[i]<=b){cout<<"McDonald!";return 0;}}cout<<"Golden Arch!";fclose(stdin);fclose(stdout);return 0;
}

T2 肯德基(kdj.cpp)

题目描述

大家都知道，肯德基里面量大又好吃的东西是薯条和鸡米花，于是
藤藤点了一份薯条和一份鸡米花，由于来吃肯德基的小朋友特别多，
服务员忙不过来，他直接把薯条和鸡米花一盘端给了藤藤，薯条和鸡
米花都是带有数字的，每一根薯条上的数字都是奇数，而鸡米花上的
数字都是偶数，藤藤是个有强迫症的吃货，他见不得薯条里混有鸡米
花，你能帮他分开一下吗？

输入文件

输入文件kdj.in第1行为整数n(1<=n<=1000)，代表薯条和鸡米花的总数量; 第2行为n个整数，表示薯条或者鸡米花上的数字(1<=a[i]<=1000)。

输出文件

输出文件kdj.out输出4行. 第1行输出薯条的数量s,
第2行按顺序输出薯条代表的数字(如果s为0 则第2行不输出)，用
空格隔开，行末无空格。
第3行输出鸡米花的数量j,
第4行按顺序输出鸡米花代表的数字(如果j为0则第4行不输出)，用
空格隔开，行末无空格。

输入样例

10
1 2 3 4 5 6 7 8 9 10

输出样例

5
1 3 5 7 9
5
2 4 6 8 10

思路

带刀的水题，输入后判断奇偶后输出即可

tip

1.如薯条或鸡米花的数量为0，则只输出0，不能有多的换行！

比赛代码(AC)

#include<bits/stdc++.h>
using namespace std;
int n,x;
vector<int>v,v1;
int main(){freopen("kdj.in","r",stdin);freopen("kdj.out","w",stdout);cin>>n;for(int i=1;i<=n;i++){cin>>x;if(x%2==0){v.push_back(x);}else{v1.push_back(x);}}cout<<v1.size()<<endl;if(v1.size()!=0){for(int i=0;i<v1.size();i++){cout<<v1[i];if(i!=v1.size()-1){cout<<" ";}else{cout<<endl;} }}cout<<v.size()<<endl;if(v.size()!=0){for(int i=0;i<v.size();i++){cout<<v[i];if(i!=v.size()-1){cout<<" ";}}}fclose(stdin);fclose(stdout);return 0;
}

T3 星巴克(xbk.cpp)

题目描述

一天，星巴克里来了一个奇怪的客人，他要买 n * n 杯咖啡，并
且对每一杯的咖啡甜度都有严格的要求(星巴克里的咖啡甜度分为
0,1,2,…级(ps:也有负等级哦)),他只给藤藤三个数字n,m,k,要藤藤
算出每一杯咖啡的甜度并按照一定的规律将它们放到箱子里打包好。
藤藤将箱子用纸片隔成了n * n个格子之后，客人便说出了要求：
如果格子的位置是第一行第一列，则此位置上的咖啡甜度要等于
m；
如果格子的位置是行和列相同，则此位置的咖啡甜度等于上一个
行和列相同的格子里的咖啡甜度+k；
如果格子的位置是当前行数大于列数，则此位置上的咖啡甜度等
于同一列的前一行的咖啡甜度-1；
如果格子的位置是当前行数小于列数，则此位置上的咖啡甜度等
于同一行的前一列的咖啡甜度-1；
藤藤拍了拍脑袋，想不出来怎么排，只能请你来写个程序来帮他
排了。

输入文件

输入文件xbk.in包括 3 个整数 n,m,k（4<=n<=100,5<=m<=100,2<=k<=50）

输出文件

输出文件xbk.out按要求排列的矩阵，格式见样例。

输入样例

5 10 7

输出样例

10 9 8 7 6
9 17 16 15 14
8 16 24 23 22
7 15 23 31 30
6 14 22 30 38

思路

将a[1][1]初始化为m，随后根据题目要求递推，最后输出即可

比赛代码(AC)

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int a[210][210];
int main(){freopen("xbk.in","r",stdin);freopen("xbk.out","w",stdout);cin>>n>>m>>k;a[1][1]=m;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i==1&&j==1)continue;if(i==j){a[i][j]=a[i-1][j-1]+k;}else if(i>j){a[i][j]=a[i-1][j]-1;}else{a[i][j]=a[i][j-1]-1;}}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cout<<a[i][j]<<" ";}cout<<endl;}fclose(stdin);fclose(stdout);return 0;
}

T4 藤藤的序列(seq.cpp)

题目描述

给定一个长度为 N 的序列，每个位置上的数只可能是 1，2，3 中的
一种。
有 Q 次询问，每次给定两个数 a,b，请分别输出区间[a,b]里数字 1， 2，3 的个数。

输入文件

输入文件seq.in若干行，第一行两个整数 n 和 q，接下来 n 行表示 n 个数 字，且每个数字均为 1，2，3 中的一种，接下来 q 行，每行两个数字 a 和 b，表示询问区间[a,b]里数字 1，2，3 的个数。

输出文件

输出文件mdl.out对于每一次询问，每行输出三个用空格隔开的数字，分别表示区间
内 1，2，3 出现的个数

输入样例

6 3
2
1
1
3
2
1
1 6
3 3
2 4

输出样例

3 2 1
1 0 0
2 0 1

数据说明

12%的分数，n <= 10, q <= 10
另有12%的分数，n <= 1000, q <= 1000
100%的分数，n <= 100000, q <= 100000

思路

用二维数组sum[][]统计1、2、3出现的个数，在询问时计算前缀和差即可

tip

1.本题数据量微大，使用scanf更保险！
2.开二维数组时注意：把小状态放在行下标，这样C++编译器不会爆！

比赛代码(算AC，因为oj上判对+以后应注意cin和scanf的使用场合)

#include<bits/stdc++.h>
using namespace std;
int n,q,x,y;
int sum[10][100010];
/*
6 3 
2 
1 
1 
3 
2 
1 
1 6 
3 3 
2 4
*/
int main(){freopen("seq.in","r",stdin);freopen("seq.out","w",stdout);cin>>n>>q;//scanf("%d%d",&n,&q);for(int i=1;i<=n;i++){for(int j=1;j<=3;j++){sum[j][i]=sum[j][i-1];}cin>>x;//scanf("%d",&x);sum[x][i]++;}for(int i=1;i<=q;i++){cin>>x>>y;//scanf("%d%d",&x,&y);cout<<sum[1][y]-sum[1][x-1]<<" ";//printf("%d ",sum[1][y]-sum[1][x-1]);cout<<sum[2][y]-sum[2][x-1]<<" ";//printf("%d ",sum[2][y]-sum[1][x-1]);cout<<sum[3][y]-sum[3][x-1]<<endl;//printf("%d ",sum[3][y]-sum[1][x-1]);}fclose(stdin);fclose(stdout);return 0;
}

T5 藤藤的游戏(game.cpp)

题目描述

给定一个长度为 N 的序列，每个位置上的数只可能是 1，2，3 中的
一种。
有 Q 次询问，每次给定两个数 a,b，请分别输出区间[a,b]里数字 1， 2，3 的个数。

输入文件

输入文件seq.in若干行，第一行两个整数 n 和 q，接下来 n 行表示 n 个数 字，且每个数字均为 1，2，3 中的一种，接下来 q 行，每行两个数字 a 和 b，表示询问区间[a,b]里数字 1，2，3 的个数。

输出文件

输出文件mdl.out对于每一次询问，每行输出三个用空格隔开的数字，分别表示区间
内 1，2，3 出现的个数

输入样例

6 3
2
1
1
3
2
1
1 6
3 3
2 4

输出样例

3 2 1
1 0 0
2 0 1

数据说明

12%的分数，n <= 10, q <= 10
另有12%的分数，n <= 1000, q <= 1000
100%的分数，n <= 100000, q <= 100000

比赛思路

放弃思考，骗分40pts

比赛代码(40pts)

#include<bits/stdc++.h>
using namespace std;
char a[10][10],x;
int cnt;
int main(){freopen("game.in","r",stdin);freopen("game.out","w",stdout);for(int i=1;i<=4;i++){for(int j=1;j<=4;j++){cin>>a[i][j];}}for(int i=1;i<=4;i++){for(int j=1;j<=4;j++){cin>>x;if(a[i][j]!=x){cnt++;}}}cout<<cnt/2;fclose(stdin);fclose(stdout);return 0;
}

正确思路

使用字符串存储数组，随后使用map映射进行bfs，如下标符合要求则进行交换，具体要求参考下图

订正代码(AC)

#include<bits/stdc++.h>
using namespace std;
string s,e;
map<string,int>mp;
queue<string>q;
int main(){freopen("game.in","r",stdin);freopen("game.out","w",stdout);s="";for(int i=1;i<=4;i++){for(int j=1;j<=4;j++){char c;cin>>c;s+=c;}}e="";for(int i=1;i<=4;i++){for(int j=1;j<=4;j++){char c;cin>>c;e+=c;}}mp[s]=0;q.push(s);while(!q.empty()){string tmp=q.front();q.pop();if(tmp==e)break;for(int i=0;i<16;i++){if(i%4!=0&&tmp[i]!=tmp[i-1]){string ne=tmp;ne[i]=tmp[i-1];ne[i-1]=tmp[i];if(mp.find(ne)==mp.end()){q.push(ne);mp[ne]=mp[tmp]+1;}}if(i%4!=3&&tmp[i]!=tmp[i+1]){string ne=tmp;ne[i]=tmp[i+1];ne[i+1]=tmp[i];if(mp.find(ne)==mp.end()){q.push(ne);mp[ne]=mp[tmp]+1;}}if(i>=4&&tmp[i]!=tmp[i-4]){string ne=tmp;ne[i]=tmp[i-4];ne[i-4]=tmp[i];if(mp.find(ne)==mp.end()){q.push(ne);mp[ne]=mp[tmp]+1;}}if(i<=11&&tmp[i]!=tmp[i+4]){string ne=tmp;ne[i]=tmp[i+4];ne[i+4]=tmp[i];if(mp.find(ne)==mp.end()){q.push(ne);mp[ne]=mp[tmp]+1;}}}}cout<<mp[e];fclose(stdin);fclose(stdout);return 0;
}