新生赛赛后总结

赛后总结"/>

新生赛赛后总结

1. 蒲煜凡的约会

题目描述
蒲煜凡学长跟学妹出来约会了！蒲煜凡学长作为一名标准直男，想要给学妹买一杯奶茶，便问学妹喜欢喝什么样的奶茶，学妹回了两个字
随便!
蒲煜凡学长傻眼了，但作为一名优秀的ACMer，他是不会坐以待毙的，他早早便将学妹喜欢喝的奶茶价格和奶茶店的价格表弄到了手!现在你要根据奶茶价格，判断学妹到底喜欢喝哪一种奶茶，如果有多种奶茶价格都符合要求，输入种类靠前的一种
输入描述:
第一行包含一个整数n，表示有n种奶茶
第二行有n个数字a[i]，a[i]表示第i种奶茶价格
第三行包含一个整数Q，表示Q次询问
第四行包含Q个整数x[i]，表示学妹喜欢喝的第i杯奶茶的价格,如果没有找到,则输出-1
输出描述:
输出Q行，每行一个整数表示答案

示例1
输入
6
1 2 10 5 3 2
1
3
输出
5
示例2
输入
5
3 1 7 5 8
2
6
7
输出
-1
3

备注:
1 \leq≤ Q \leq≤ 1e5, 1 \leq≤ n \leq≤ 1e6
奶茶价格都在int范围内～

过程：
说实话刚开始我真的以为这题是暴力查，即使一直被提示超时也完全没有想到用二分或者map。
xc学长讲解完后思路就很清晰啦，先用map M以对应价格为下标而存下输入的顺序，然后直接输入要找的价格下标就可以啦！
话不多说直接上代码：

#include<iostream>
#include<cmath>
#include<map>
const long N=1e6;
int a[N];
using namespace std;
map<long,int> M;
int main(){long n,minn=N;cin>>n;for(int i=0;i<n;i++){cin>>a[i];if(M[a[i]]==0) M[a[i]]=i+1;}long t;cin>>t;while(t--){int x;cin>>x;if(M[x]==0) cout<<"-1"<<endl;else cout<<M[x]<<endl;}return 0;
}

2 - 蒲煜凡送花

题目描述
蒲煜凡学长最近迷上了一个漂亮的小学妹,他想送一朵特别的花给这个小学妹。
他现在有一把N朵漂亮的花,每多花都有a[i]个花瓣,如果有1朵花的花瓣数与其他任意一朵花的花瓣数之差等于2,那么他可以选择把这朵花扔掉,也可以选择丢弃。
请问经过若干次操作之后蒲煜凡学学长能找到唯一的一支特别的花送给小学妹吗？

输入描述: 第一行一个整数t(1<=t<=500)表示测试样例数
每个测试样例第一行一个整数n(1<=n<=1e4)表示花的数量,第二行n个整数ai表示花瓣数。

输出描述:
输出t行"YES"or"NO"

示例1
输入
1
4
2 4 6 8
输出
YES
示例2
输入
1
5
9 3 5 6 7
输出
NO

过程：做题还是太少了，看到这些有情景的题目思绪就会开始混乱，不知道题目想要表达什么意思，加上在别的题上消耗了太多的时间，也没有怎么仔细看过这道题，感谢zzx大佬以及xc学长的思路。
这题可以用map，先将M数组初始化为0，输入花瓣数，如9 3 5 6 7，可以依次令M[9-2],M[9+2],M[3-2],M[3+2],M[5-2],M[5+2],M[6-2],M[6+2],M[7-2],M[7+2]赋值为1，最后再从花瓣数组中，以花瓣数为下标，在M数组中找出唯一的0，如M[9]=1,M[3]=1,M[5]=1,M[6]=0,M[7]=0,此时为0并不唯一，因此输出’NO’。
刚开始自己写的时候没有考虑到两边，只从当前位往前-2，应该同时考虑到往后+2，下面上代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
map<int,int> M;
int a[100010],n,t;
int main(){cin>>t;while(t--){cin>>n;M.clear();for(int i=0;i<n;i++){scanf("%d",a+i);M[a[i]+2]=1;M[a[i]-2]=1;}int flag=0;for(int i=1;i<n;i++)if(M[a[i]]==0){flag=1;break;}if(flag==0) puts("YES");else puts("NO");}return 0;
}

3 - 甘靖的普通话

题目描述
大多数情况下甘靖学长说普通话时都很标准，但有时却令人抓狂，这件事困扰他很久了，突然有一天，他想通过读数字来纠正他的发音，
但是他不想按正常的顺序读数字，于是他按照某种规律写了一些数字在黑板上，比如如果他想数到9，那么他会把数字写成如下格式：

1 2 6 7
3 5 8
4 9

如果他想数到15，那么他会把数字写成如下格式:

1 2 6 7 15
3 5 8 14
4 9 13
10 12
11

他突然发现他写数字的规律是个蛇形，具体描述是这样的:
对于每一条左下-右上的斜线，从左上到右下依次编号1,2,…,2n-1；按编号从小到大的顺序，将数字从小到大填入各条斜线，其中编号为奇数的从左下向右上填写，编号为偶数的从右上到左下填写
输入描述:
输入一个不大于10000的正整数n，表示要填充到的数字的大小
输出描述:
按规律输出这些数字，相邻两个元素之间用单个空格间隔
示例1
输入

50

输出

1 2 6 7 15 16 28 29 45 46
3 5 8 14 17 27 30 44 47
4 9 13 18 26 31 43 48
10 12 19 25 32 42 49
11 20 24 33 41 50
21 23 34 40
22 35 39
36 38
37

过程：同样是感谢zzx大佬的思路，zzxyyds！！！太强辽！！！
我们可以将其看成斜着的行。
由于注释都放在代码里了所以直接上代码（不得不说这个方法真的很妙）：

#include<iostream>
#include<iostream>
#include<cstdio>
using namespace std;
int a[215][215],n,cnt;
int main(){cin>>n;int p=0,q=0;for(int i=1;p<n;i++){p+=i;  //每行的个数都比前一个多一个cnt++;  //计算斜着的行数 }for(int i=1;i<=cnt;i++)  //通过判断这一行是奇数行还是偶数行来决定是从上向下读数还是从下向上读数 for(int j=1;j<=i;j++){  //每行横纵坐标相加都是本行数+1if(i%2==1) a[i+1-j][j]=++q;  //以坐标的方式读入数据 从下向上，纵坐标j总以1开始else a[j][i-j+1]=++q;  //从上向下，横坐标x总以1开始if(q==n) break;}for(int i=1;i<=cnt;i++){  //每一横行每一横行的输出数据if(i>1) cout<<endl;int k=1;while(a[i][k]) printf("%d ",a[i][k++]);}return 0;
}