2018年天梯赛全国总决赛

时间： 2023-12-16 admin IT培训

2018年天梯赛全国总决赛推荐度：
相关推荐

2018年天梯赛全国总决赛

前言
L1-1 天梯赛座位分配
L1-2 倒数第N个字符串
L1-3 打折
L1-4 2018我们要赢
L1-5 电子汪
L1-6 福到了
- 读取一行
L1-7 谁是赢家
L1-8 猜数字
L2-1 分而治之
- 首先就是一个STL写法，其实也是一种邻接表
- 并查集
L2-2 小字辈（25 分）
L2-3 名人堂与代金券
L2-4 秀恩爱分得快
- atoi()和stoi()的区别----数字字符串的处理
L3-1 代码排版
- string.find()
L3-2 至多删三个字符
L3-021 神坛
map排序
- map按key排序
- map按value值排序

前言

这个第一道题太复杂了，让我卡了半天，还是没太弄懂，然后后面的话倒也还好，就是感觉天梯赛呢，其实是很看中基础的，我觉得卡我的几个点都是在最基本的用法还有读入里面。也有可能是我太菜了。

L1-1 天梯赛座位分配

输入样例：

3
3 4 2

输出样例：

#1
1 4 7 10 13 16 19 22 25 28
31 34 37 40 43 46 49 52 55 58
61 63 65 67 69 71 73 75 77 79
#2
2 5 8 11 14 17 20 23 26 29
32 35 38 41 44 47 50 53 56 59
62 64 66 68 70 72 74 76 78 80
82 84 86 88 90 92 94 96 98 100
#3
3 6 9 12 15 18 21 24 27 30
33 36 39 42 45 48 51 54 57 60

#include <iostream>
#include <string>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<utility>
#include<map>
#include<set>using namespace std;const int N=110;
int num[N];
int idx[10010];
int main()
{int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&num[i]);}int cnt=n,pre=0,r=0;while(cnt){for(int i=1;i<=10;i++){for(int j=1;j<=n;j++){if(num[j]){if(pre==j&&cnt==1) r+=2;else r++;idx[r]=j;pre=j;}}}for(int i=1;i<=n;i++){if(num[i]){num[i]--;if(!num[i]) cnt--;}}}
for(int i=1;i<=n;i++){printf("#%d\n",i);cnt=0;for(int j=1;j<=r;j++){if(idx[j]==i){cnt++;if(cnt%10==0) printf("%d\n",j);else printf("%d ",j);}}}return 0;
}

最后两个测试点改了好久还是段错误，才发现是数据开小了，以后可要注意了！

L1-2 倒数第N个字符串

题目：
给定一个完全由小写英文字母组成的字符串等差递增序列，该序列中的每个字符串的长度固定为 L，从 L 个 a 开始，以 1 为步长递增。例如当 L 为 3 时，序列为 { aaa, aab, aac, …, aaz, aba, abb, …, abz, …, zzz }。这个序列的倒数第27个字符串就是 zyz。对于任意给定的 L，本题要求你给出对应序列倒数第 N 个字符串。
输入格式：
输入在一行中给出两个正整数 L（2 ≤ L ≤ 6）和 N（≤10^5）。

输出格式：
在一行中输出对应序列倒数第 N 个字符串。题目保证这个字符串是存在的。

输入样例：
3 7417

输出样例：
pat

感觉这题目可以转换为二进制来写，正着来写和倒着来写我觉得都是可以的。我这个是倒着来写的，因为他给的就是倒着的第几个数，我们在进行操作的时候要把它所给出的数先减1。

#include <iostream>
#include <sstream>
#include <string>
#include <iomanip>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;int l,n;
char a[10];
int main(){int L,N;cin>>L>>N;string a="";for(int i=1;i<=L;i++){a+='z';}int r=L-1,tmp;N--;while(N){tmp=N%26;a[r--]='z'-tmp;N/=26;}cout<<a<<endl;return 0;
}

L1-3 打折

#include <iostream>
#include <sstream>
#include <string>
#include <iomanip>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;int main()
{int a,b;cin>>a>>b;double ans=a*b/10.0;printf("%.2lf",ans);
}

L1-4 2018我们要赢

#include <iostream>
#include <sstream>
#include <string>
#include <iomanip>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;int main()
{cout<<"2018"<<endl<<"wo3 men2 yao4 ying2 !";
return 0;
}

L1-5 电子汪

#include <iostream>
#include <sstream>
#include <string>
#include <iomanip>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;int main()
{int a,b;cin>>a>>b;for(int i=0;i<a+b;i++)cout<<"Wang!";
return 0;
}

L1-6 福到了

输入1：

$ 9@  @@@@@
@@@  @@@ @   @ @ 
@@@  @@@ 
@@@ @@@@@
@@@ @ @ @
@@@ @@@@@@  @ @ @@  @@@@@

输出1：

$$$$$  $ 
$ $ $  $ 
$$$$$ $$$
$ $ $ $$$
$$$$$ $$$$$$  $$$$ $   $ $$$  $$$
$$$$$  $

输入2：

& 3
@@@@ 
@@@

输出2：

bu yong dao le
&&&& 
&&&

这一道题目卡了我好久，就是卡在了那个输入上面，读取一行，然后感觉像这类问题，不仅是天体赛会常考，这个也是蓝桥杯的重点哦！所以一定要掌握。

读取一行

C语言

char buf[80]={0};
　 gets(buf); //可以读取空格，回车结束输入

char buf[10] = {0};

scanf("%[^\n]",buf); //可以读取空格，回车结束输入

%[abc]表示字符组合包括a、b和c，如果遇到这三个字符之外的字符，则停止接收

%[^abc]代表字符组合为abc以外的所有字符

C++

char name[20];

cin.getline(name, 20);

string name;

getline(cin, name);

注：cin>> name遇到空格会被打断

#include <iostream>
#include <sstream>
#include <string>
#include <iomanip>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;const int N=110;
string a[N];int main()
{char k;int n;cin>>k>>n;getchar();for(int i=0; i<n; i++){getline(cin,a[i]);}bool f=true;for(int i=0; i<n; i++){for(int j=0; j<n; j++){if(a[i][j]!=a[n-1-i][n-1-j]) f=false;}}if(f) printf("bu yong dao le\n");for(int i=n-1; i>=0; i--){for(int j=n-1; j>=0; j--){if(a[i][j]!=' ') printf("%c",k);else printf(" ");}printf("\n");}return 0;
}

看到有人用vector来写，而且注释也很清楚，真的是很棒！

#include<bits/stdc++.h>
using namespace std;
int main(){vector<string> p;string c,a;int d,flag=1;//d即为题目中的N cin>>a>>d;getchar();//由于 getline函数以换行为结束，按照题目要求我们输入过d后，会用回车换行，此时的换行对//cin有效，也会对接下来的第一次for循环中的getline函数有效，使得第一次的字符串为空。//因为cin函数不会对缓冲区中的换行做处理 ，所以在进入循环之前，//使用getchar()可将换行从缓冲区“吃”掉，从而避免影响getline函数 for(int i=0;i<d;i++){getline(cin,c);//getline函数会自动处理本次结束时的换行，使之不影响下次的getline函数 p.push_back(c);//将得到的字符串c放入p数组中 c="";//将c变为空 }for(int i=0;i<d;i++){//判断倒放后是否与倒放前一致，来决定最后是否需要输出 "bu yong dao le"； for(int j=0;j<d;j++){if(p[i][j]!=p[d-1-i][d-1-j]){//d-1为p数组最后一个元素的下标 flag=0;break;}}}if(flag){//若flag为0，代表倒放前与倒放后不一致 cout<<"bu yong dao le"<<endl;}for(int i=d-1;i>=0;i--){//按照题目要求的格式输出倒放后的图案 for(int j=d-1;j>=0;j--){if(p[i][j]=='@'){cout<<a;}else{cout<<" ";}}cout<<endl;}return 0; 
}

L1-7 谁是赢家

某电视台的娱乐节目有个表演评审环节，每次安排两位艺人表演，他们的胜负由观众投票和 3 名评委投票两部分共同决定。规则为：如果一位艺人的观众票数高，且得到至少 1 名评委的认可，该艺人就胜出；或艺人的观众票数低，但得到全部评委的认可，也可以胜出。节目保证投票的观众人数为奇数，所以不存在平票的情况。本题就请你用程序判断谁是赢家。

输入格式：
输入第一行给出 2 个不超过 1000 的正整数 Pa 和 Pb，分别是艺人 a 和艺人 b 得到的观众票数。题目保证这两个数字不相等。随后第二行给出 3 名评委的投票结果。数字 0 代表投票给 a，数字 1 代表投票给 b，其间以一个空格分隔。

输出格式：
按以下格式输出赢家：

The winner is x: P1 + P2
其中 x 是代表赢家的字母，P1 是赢家得到的观众票数，P2 是赢家得到的评委票数。

输入样例：
327 129
1 0 1
输出样例：
The winner is a: 327 + 1

这是一道纯模拟题。

#include <iostream>
#include <sstream>
#include <string>
#include <iomanip>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;int main()
{int pa,pb;cin>>pa>>pb;int x1,x2,x3;cin>>x1>>x2>>x3;int a=0,b=0;if(x1==0)a++;else b++;if(x2==0)a++;else b++;if(x3==0)a++;else b++;if(pa==pb){if(a>b)printf("The winner is %c: %d + %d",'a',pa,a);else printf("The winner is %c: %d + %d",'b',pb,b);}else if(pa>pb){if(a>=1)printf("The winner is %c: %d + %d",'a',pa,a);else if(b==3)printf("The winner is %c: %d + %d",'b',pb,b);}else{if(b>=1)printf("The winner is %c: %d + %d",'b',pb,b);else if(a==3)printf("The winner is %c: %d + %d",'a',pa,a);}return 0;
}

L1-8 猜数字

一群人坐在一起，每人猜一个 100 以内的数，谁的数字最接近大家平均数的一半就赢。本题就要求你找出其中的赢家。

输入格式：
输入在第一行给出一个正整数N（≤10
4
）。随后 N 行，每行给出一个玩家的名字（由不超过8个英文字母组成的字符串）和其猜的正整数（≤ 100）。

输出格式：
在一行中顺序输出：大家平均数的一半（只输出整数部分）、赢家的名字，其间以空格分隔。题目保证赢家是唯一的。

输入样例：

7
Bob 35
Amy 28
James 98
Alice 11
Jack 45
Smith 33
Chris 62

输出样例：

22 Amy

猜数字这一道题让我觉得也是蛮有意思的一道题目哦！

#include <iostream>
#include <sstream>
#include <string>
#include <iomanip>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N=10010;
struct no{
char name[10];
int x;
}node[N];
bool cmp(no a,no b)
{return a.x < b.x;   //降序排列//return a > b;       升序排列
}
int main()
{int n;cin>>n;string l;int r;int  res=0;for(int i=0;i<n;i++){scanf("%s%d",node[i].name,&node[i].x);res+=node[i].x;}res/=n;res/=2;for(int i=0;i<n;i++){node[i].x=abs(node[i].x-res);}sort(node,node+n,cmp);printf("%d %s",res,node[0].name);return 0;
}

L2-1 分而治之

分而治之，各个击破是兵家常用的策略之一。在战争中，我们希望首先攻下敌方的部分城市，使其剩余的城市变成孤立无援，然后再分头各个击破。为此参谋部提供了若干打击方案。本题就请你编写程序，判断每个方案的可行性。

输入格式：
输入在第一行给出两个正整数 N 和 M（均不超过10 000），分别为敌方城市个数（于是默认城市从 1 到 N 编号）和连接两城市的通路条数。随后 M 行，每行给出一条通路所连接的两个城市的编号，其间以一个空格分隔。在城市信息之后给出参谋部的系列方案，即一个正整数 K （≤ 100）和随后的 K 行方案，每行按以下格式给出：

Np v[1] v[2] … v[Np]
其中 Np 是该方案中计划攻下的城市数量，后面的系列 v[i] 是计划攻下的城市编号。

输出格式：
对每一套方案，如果可行就输出YES，否则输出NO。

输入样例：

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

输出样例：

NO
YES
YES
NO
NO

这道题目没有写出来。
题意：给定n个城市和m条道路，然后提出k个进攻方案，然后你来判断是否可以通过攻击这些城市然后将把各个城市分隔开，然后一一攻破，如果可以，输出yes，不可以输出no。
这一题呢，我理解了好久，觉得还是蛮有意思的，然后终于弄懂了，也有好几个方法来写。

首先就是一个STL写法，其实也是一种邻接表

由于啊我对set等等STL的几个用法都是蛮生疏的，所以我看代码就看了很久。

#include <iostream>
#include <sstream>
#include <string>
#include <iomanip>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<utility>
#include<map>
#include<set>using namespace std;const int N=10010;
int mp[N][2];int main()
{int n,m;cin>>n>>m;for(int i=0;i<m;i++){cin>>mp[i][0]>>mp[i][1];}int k;cin>>k;while(k--){set<int>s;int n;int t;cin>>t;while(t--){int x;cin>>x;s.insert(x);}bool flag =true;for(int i=0;i<m;i++){if(s.find(mp[i][0])==s.end()&&s.find(mp[i][1])==s.end())//如果两个连同的城市都没有在所攻陷的城市里面，说明这个连同城市并没有被剪断{flag=false;break;}}if(flag)cout<<"YES"<<endl;else cout<<"NO"<<endl;}return 0;
}

反正这种方法看了很多都是来看是否一个没有攻陷，那么它的另一个所连接的城市也没有攻陷的时候就gg掉了！

并查集

那并查集嘛，不是很熟，所以对着敲一遍，希望自己能够多多看看他哈哈哈哈

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<cmath>
#include<cstring>
typedef long long ll;
using namespace std;
const int MAX = 2e5 + 6;
int f[MAX];
int n,m;
int u[MAX],v[MAX];
bool bk[MAX];
void init(int n) {for(int i = 1; i<=n; i++) f[i] = i;
}
int getf(int v) {return v == f[v] ? v : f[v] = getf(f[v]);
}
void merge(int u,int v) {int t1 = getf(u);int t2 = getf(v);f[t2] = t1;
}
bool ok() {for(int i = 1; i<=n; i++) {if(f[i] != i) return 0 ;}return 1;
}
int main() 
{cin>>n>>m;for(int i = 1; i<=m; i++) {scanf("%d%d",&u[i],&v[i]);}int k;cin>>k;for(int i = 1; i<=k; i++) {init(n);for(int i = 1; i<=n; i++) bk[i] = 0;int num;scanf("%d",&num);for(int tmp,j = 1; j<=num; j++) {scanf("%d",&tmp);bk[tmp]=1;}for(int j = 1; j<=m; j++) {if(bk[u[j]]|| bk[v[j]]) continue;merge(u[j],v[j]);}if(ok()) printf("YES\n");else printf("NO\n");}return 0 ;
}

这个fill()用法我是第一次见到，他是对数组进行填充，用第三个数字进行填充。这个仅仅是在看代码的时候看到的。

L2-2 小字辈（25 分）

本题给定一个庞大家族的家谱，要请你给出最小一辈的名单。

输入格式：
输入在第一行给出家族人口总数 N（不超过 100 000 的正整数） —— 简单起见，我们把家族成员从 1 到 N 编号。随后第二行给出 N 个编号，其中第 i 个编号对应第 i 位成员的父/母。家谱中辈分最高的老祖宗对应的父/母编号为 -1。一行中的数字间以空格分隔。

输出格式：
首先输出最小的辈分（老祖宗的辈分为 1，以下逐级递增）。然后在第二行按递增顺序输出辈分最小的成员的编号。编号间以一个空格分隔，行首尾不得有多余空格。

输入样例：

9
2 6 5 5 -1 5 6 4 7

输出样例：

4
1 9

#include <iostream>
#include <sstream>
#include <string>
#include <iomanip>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;const int N=1e5+10;
vector<int>v[N];
int k[N];
void dfs(int x,int d)
{k[x]=d;//这个点的深度是1for(int i=0;i<v[x].size();i++)dfs(v[x][i],d+1);
}int main()
{int n;cin>>n;int root=0;for(int i=1;i<=n;i++){int x;cin>>x;if(x==-1)root=i;else v[x].push_back(i);}dfs(root,1);//后面的表示深度int _max=-1;for(int i=1;i<=n;i++)_max=max(_max,k[i]);printf("%d\n",_max);bool f=false;for(int i=1;i<=n;i++)if(k[i]==_max)if(f)printf(" %d",i);else {printf("%d",i);f=true;}return 0;
}

L2-3 名人堂与代金券

对于在中国大学MOOC（/ ）学习“数据结构”课程的学生，想要获得一张合格证书，总评成绩必须达到 60 分及以上，并且有另加福利：总评分在 [G, 100] 区间内者，可以得到 50 元 PAT 代金券；在 [60, G) 区间内者，可以得到 20 元PAT代金券。全国考点通用，一年有效。同时任课老师还会把总评成绩前 K 名的学生列入课程“名人堂”。本题就请你编写程序，帮助老师列出名人堂的学生，并统计一共发出了面值多少元的 PAT 代金券。

输入格式：
输入在第一行给出 3 个整数，分别是 N（不超过 10 000 的正整数，为学生总数）、G（在 (60,100) 区间内的整数，为题面中描述的代金券等级分界线）、K（不超过 100 且不超过 N 的正整数，为进入名人堂的最低名次）。接下来 N 行，每行给出一位学生的账号（长度不超过15位、不带空格的字符串）和总评成绩（区间 [0, 100] 内的整数），其间以空格分隔。题目保证没有重复的账号。

输出格式：
首先在一行中输出发出的 PAT 代金券的总面值。然后按总评成绩非升序输出进入名人堂的学生的名次、账号和成绩，其间以 1 个空格分隔。需要注意的是：成绩相同的学生享有并列的排名，排名并列时，按账号的字母序升序输出。

输入样例：

10 80 5
cy@zju.edu 78
cy@pat-edu 87
1001@qq 65
uh-oh@163 96
test@126 39
anyone@qq 87
zoe@mit.edu 80
jack@ucla.edu 88
bob@cmu.edu 80
ken@163 70

输出样例：

360
1 uh-oh@163 96
2 jack@ucla.edu 88
3 anyone@qq 87
3 cy@pat-edu 87
5 bob@cmu.edu 80
5 zoe@mit.edu 80

#include <iostream>
#include <sstream>
#include <string>
#include <iomanip>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<utility>
#include<map>
using namespace std;const int N=1e4+10;
struct Node{char name[20];int s;bool operator < (const Node &t)const{if(s!=t.s) return s>t.s;if(strcmp(name,t.name)<0) return true;return false;}
}node[N];int main(){int n,g,k;cin>>n>>g>>k;for(int i=0;i<n;i++){scanf("%s%d",node[i].name,&node[i].s);}sort(node,node+n);int res=0;for(int i=0;i<n;i++){if(node[i].s>=g) res+=50;else if(node[i].s>=60) res+=20;}int r=1;cout<<res<<endl;for(int i=0;i<n;i++){if(i!=0&&node[i].s!=node[i-1].s) r=i+1;if(r>k) break;cout<<r<<" "<<node[i].name<<" "<<node[i].s<<endl;}return 0;
}

L2-4 秀恩爱分得快

古人云：秀恩爱，分得快。

互联网上每天都有大量人发布大量照片，我们通过分析这些照片，可以分析人与人之间的亲密度。如果一张照片上出现了 K 个人，这些人两两间的亲密度就被定义为 1/K。任意两个人如果同时出现在若干张照片里，他们之间的亲密度就是所有这些同框照片对应的亲密度之和。下面给定一批照片，请你分析一对给定的情侣，看看他们分别有没有亲密度更高的异性朋友？

输入格式：
输入在第一行给出 2 个正整数：N（不超过1000，为总人数——简单起见，我们把所有人从 0 到 N-1 编号。为了区分性别，我们用编号前的负号表示女性）和 M（不超过1000，为照片总数）。随后 M 行，每行给出一张照片的信息，格式如下：

K P[1] … P[K]
其中 K（≤ 500）是该照片中出现的人数，P[1] ~ P[K] 就是这些人的编号。最后一行给出一对异性情侣的编号 A 和 B。同行数字以空格分隔。题目保证每个人只有一个性别，并且不会在同一张照片里出现多次。

输出格式：
首先输出 A PA，其中 PA 是与 A 最亲密的异性。如果 PA 不唯一，则按他们编号的绝对值递增输出；然后类似地输出 B PB。但如果 A 和 B 正是彼此亲密度最高的一对，则只输出他们的编号，无论是否还有其他人并列。

输入样例 1：

10 4
4 -1 2 -3 4
4 2 -3 -5 -6
3 2 4 -5
3 -6 0 2
-3 2

输出样例 1：

-3 2
2 -5
2 -6

输入样例 2：

4 4
4 -1 2 -3 0
2 0 -3
2 2 -3
2 -1 2 
-3 2

输出样例 2：

-3 2

思路：用一个二维数组g来存储在同一张照片的不同人之间的亲密度，maxn来记录和A和异性的最大亲密度和B和异性的最大亲密度，因为题目要求按他们编号的绝对值递增输出，所以我们采用set分别存储男性和女性，最后遍历输出就行了

注：stoi是将string类型转换成int型

本题有很多坑，即使在过样例的时候，我用int来存数据也不能跑下来，我也很疑惑是为什么。感觉这些题目都在考察STL的使用。

坑一：序号0用可能为女，即-0，这时整形读取是没有区别的。

坑二：存储照片上的人要把男女分开，才可以满足时间要求，就只计算异性性间的亲密度。

坑三：在判断是否彼此为最亲近的人时，考虑两方最大亲密值相同，但不是对方的情况。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<set>
#include<vector>using namespace std;const int N=1010;double g[N][N],maxn[N];
vector<int>a,b;
set<int>A,B;
int n,m;int main()
{cin>>n>>m;while(m--){int k;a.clear();b.clear();cin>>k;for(int i=0;i<k;i++){string s;cin>>s;if(s[0]=='-')//女性{a.push_back(abs(stoi(s)));A.insert(abs(stoi(s)));}else//男性{b.push_back(stoi(s));B.insert(stoi(s));}}for(int i=0;i<a.size();i++){for(int j=0;j<b.size();j++){g[a[i]][b[j]]+=1.0/k;g[b[j]][a[i]]+=1.0/k;if(maxn[a[i]]<g[a[i]][b[j]]) maxn[a[i]]=g[a[i]][b[j]];if(maxn[b[j]]<g[b[j]][a[i]]) maxn[b[j]]=g[b[j]][a[i]];}}}string s1,s2;int aa,bb;cin>>s1>>s2;aa=abs(stoi(s1)),bb=abs(stoi(s2));if(maxn[aa]==g[aa][bb]&&maxn[bb]==g[bb][aa])//s1和s2正是彼此亲密度最高的{cout<<s1<<' '<<s2;return 0;}if(s1[0]=='-')//第一个人是女性{for(auto p:B)//遍历异性if(maxn[aa]==g[p][aa])cout<<s1<<' '<<p<<endl;}else{for(auto p:A)if(maxn[aa]==g[p][aa])cout<<s1<<' '<<'-'<<p<<endl;}if(s2[0]=='-'){for(auto p:B)if(maxn[bb]==g[bb][p])cout<<s2<<' '<<p<<endl;}else{for(auto p:A)if(maxn[bb]==g[bb][p])cout<<s2<<' '<<'-'<<p<<endl;}return 0;
}

atoi()和stoi()的区别----数字字符串的处理

相同点：
①都是C++的字符处理函数，把数字字符串转换成int输出
②头文件都是#include
不同点：
①atoi()的参数是 const char* ,因此对于一个字符串str我们必须调用 c_str()的方法把这个string转换成 const char类型的,而stoi()的参数是const string,不需要转化为 const char*；
②stoi()会做范围检查，默认范围是在int的范围内的，如果超出范围的话则会runtime error！
而atoi()不会做范围检查，如果超出范围的话，超出上界，则输出上界，超出下界，则输出下界；

L3-1 代码排版

这个大模拟我就不写了/尴尬

string.find()

string.find(s);//返回在string里面找到第一个出现s的下标
string.find(s,2);//返回从下标为2的string里面开始找第一次出现s的下标

L3-2 至多删三个字符

给定一个全部由小写英文字母组成的字符串，允许你至多删掉其中 3 个字符，结果可能有多少种不同的字符串？

输入格式：
输入在一行中给出全部由小写英文字母组成的、长度在区间 [4, 106] 内的字符串。

输出格式：
在一行中输出至多删掉其中 3 个字符后不同字符串的个数。

输入样例：

ababcc

输出样例：

提示：
删掉 0 个字符得到 “ababcc”。
删掉 1 个字符得到 “babcc”, “aabcc”, “abbcc”, “abacc” 和 “ababc”。
删掉 2 个字符得到 “abcc”, “bbcc”, “bacc”, “babc”, “aacc”, “aabc”, “abbc”, “abac” 和 “abab”。
删掉 3 个字符得到 “abc”, “bcc”, “acc”, “bbc”, “bac”, “bab”, “aac”, “aab”, “abb” 和 “aba”。

这是一道简单dp题目，我觉得很有意思。

#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<set>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
char s[maxn];
ll dp[maxn][4];int main(){scanf("%s",s+1);int len=strlen(s+1);dp[0][0]=1;  //讲真，这里赋值为1还是挺疑惑的for(int i=1;i<=len;i++){for(int j=0;j<=3;j++){if(i<j) break; //前i个都不够删肯定不行呀dp[i][j]=dp[i-1][j];  //第i位字符不删 if(j>=1) dp[i][j]+=dp[i-1][j-1];  //第i位字符删for(int k=i-1;k>=1&&i-k<=j;k--){if(s[k]==s[i]){dp[i][j]-=dp[k-1][j-(i-k)];break;}}}}ll res=0;for(int i=0;i<=3;i++){res+=dp[len][i];}printf("%lld\n",res);return 0;
}

L3-021 神坛

在古老的迈瑞城，巍然屹立着 n 块神石。长老们商议，选取 3 块神石围成一个神坛。因为神坛的能量强度与它的面积成反比，因此神坛的面积越小越好。特殊地，如果有两块神石坐标相同，或者三块神石共线，神坛的面积为 0.000。

长老们发现这个问题没有那么简单，于是委托你编程解决这个难题。

输入格式：
输入在第一行给出一个正整数 n（3 ≤ n ≤ 5000）。随后 n 行，每行有两个整数，分别表示神石的横坐标、纵坐标（−10
9
≤ 横坐标、纵坐标 <10
9
）。

输出格式：
在一行中输出神坛的最小面积，四舍五入保留 3 位小数。

输入样例：

输出样例：

0.500

①对于每个点，向其他所有点连一条向量，然后按照斜率从小到大（逆时针）排序
②对于点ABC构成的最小三角形，直线AB与AC肯定是相邻的边，扫一遍就好
③三角形的面积=abs(x1y2-y2x1)/2
④5*1e9的数据，记得开longlong+double

#include <iostream>
#include <sstream>
#include <string>
#include <iomanip>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<utility>
#include<map>
#include<set>using namespace std;typedef long long ll;
const int maxn=5e5+10;struct point{ll x,y;}pp[maxn],tmp[maxn];
bool cmp(point a,point b){return a.x*b.y>a.y*b.x;}int main()
{int n;cin>>n;for(int i=0;i<n;i++)cin>>pp[i].x>>pp[i].y;double ans=1e18;for(int i=0;i<n;i++){int cc=0;for(int j=0;j<n;j++){if(i==j)continue;tmp[cc].x=pp[j].x-pp[i].x;tmp[cc].y=pp[j].y-pp[i].y;//将任意两个点按照距离存起来cc++;}sort(tmp,tmp+cc,cmp);//按照我们所需要的面积公式进行排序for(int j=0;j<cc;j++)ans=min(ans,abs(0.5*(tmp[j].x*tmp[(j+1)%cc].y-tmp[(j+1)%cc].x*tmp[j].y)));}printf("%.3f\n",ans);return 0;
}

map排序

map按key排序

（1）map默认是按照key排序

 map<string,int> hash;等价于 map<string,int, less<string>> hash;

（2）map按照key从大到小排序

map<string,int, greater<string> > hash;

示范样例：

    map<string,int, greater<string>> m; // 默认 map<string,int, less<string>> m;m["you"] = 2;m["we"] = 3;m["they"] = 1;cout << "Map 按 key 从大到小排序" << endl;for (auto x : m) {cout << x.first << " " << x.second << endl;}

map按value值排序

按 value 值排序没有直接的方法，但我们可以把 map 存到 vector 中，再对 vector 进行自定义排序，因为 vector 是可以借助 cmp 随意排序的，所以这里以 value 值从小到大排序为例。

定义 vector 的 cmp 函数

bool cmp(pair<string,int> a, pair<string, int> b) {return a.second < b.second;
}

把 map 存到 vector 中进行排序

    map<string,int> m;m["you"] = 2;m["we"] = 3;m["they"] = 1;vector<pair<string,int> > vec(m.begin(),m.end());sort(vec.begin(),vec.end(),cmp);

2018年天梯赛全国总决赛