PAT甲级题解1061-1090
1061
样例
输入:
3485djDkxh4hhGE
2984akDfkkkkggEdsb
s&hgsfdk
d&Hyscvnm输出:
THU 14:04思路和坑点
字符串处理，遍历一遍就行了。注意星期几的字母要求是大写的A-G，小时的字符是星期几之后遇到的共有的0~9，A-N（大写）范围的字符，分钟只要求相同字符的下标。
可以使用isdigit();isupper()
AC代码
#include<bits/stdc++.h>
using namespace std;
int main(void){
string a,b,c,d;
string day[7]={"MON","TUE","WED","THU","FRI","SAT","SUN"};
cin>>a>>b>>c>>d;
int i,t,h,m;
for(i=0;i<a.size()&&i<b.size();i++){ //计算第几天
if(a[i]==b[i]&&a[i]>='A'&&a[i]<='G'){
t=a[i]-'A'; break;
}
}
for(i++;i<a.size()&&i<b.size();i++){ //计算第几小时
if(a[i]==b[i]){
if(isdigit(a[i])){ //如果是数字
h=a[i]-'0'; break;
}
else if(isupper(a[i])&&a[i]>='A'&&a[i]<='N'){ //如果是A-N的字母
h=a[i]-'A'+10; break;
}
}
}
for(i=0;i<c.size()&&i<d.size();i++){ //计算分钟
if(c[i]==d[i]&&isalpha(c[i])){
m=i; break;
}
}
printf("%s %02d:%02d",day[t].c_str(),h,m); //按照格式输出
return 0;
} 1062
样例
输入:
14 60 80
10000001 64 90
10000002 90 60
10000011 85 80
10000003 85 80
10000004 80 85
10000005 82 77
10000006 83 76
10000007 90 78
10000008 75 79
10000009 59 90
10000010 88 45
10000012 80 100
10000013 90 99
10000014 66 60输出:
12
10000013 90 99
10000012 80 100
10000003 85 80
10000011 85 80
10000004 80 85
10000007 90 78
10000006 83 76
10000005 82 77
10000002 90 60
10000014 66 60
10000008 75 79
10000001 64 90思路和坑点
德才论，主要是在于理解划分不同等级的规则和排序规则的书写。这里为了减少时间开销，使用下标排序的方法。
坑点:
不满足最低要求的不能参与排序。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef struct node{
int id,t,v,rank,score;
}Node;
vector<Node> v; //存放数据
vector<int> idsort; //下标排序的数组
bool cmp(int i,int j){ //排序方法
if(v[i].rank!=v[j].rank) return v[i].rank<v[j].rank;
else if(v[i].score!=v[j].score) return v[i].score>v[j].score;
else if(v[i].v!=v[j].v) return v[i].v>v[j].v;
else return v[i].id<v[j].id;
}
int main(void){
int n,l,h;
scanf("%d%d%d",&n,&l,&h);
for(int i=0;i<n;i++){
Node temp;
scanf("%d%d%d",&temp.id,&temp.v,&temp.t);
if(temp.v<l||temp.t<l) //低于标准的不参与排序
continue;
temp.score=temp.v+temp.t;
if(temp.v>=h&&temp.t>=h) temp.rank=1; //根据分数确定不同的等级
else if(temp.v>=h) temp.rank=2;
else if(temp.v<h&&temp.t<h&&temp.t<=temp.v) temp.rank=3;
else temp.rank=4;
idsort.push_back(v.size());
v.push_back(temp);
}
sort(idsort.begin(),idsort.end(),cmp); //下标排序
n=idsort.size(); //输出结果
printf("%d\n",n);
for(int i=0;i<n;i++){
int k=idsort[i];
printf("%08d %d %d\n",v[k].id,v[k].v,v[k].t);
}
return 0;
} 1063
样例
输入:
3
3 99 87 101
4 87 101 5 87
7 99 101 18 5 135 18 99
2
1 2
1 3输出:
50.0%
33.3%思路和坑点
使用map容器筛选掉重复的数据，并且使用map映射标记，记录每一个数的归属，属于第一组数据，还是第二组数据，还是共有的。
{{< alert warning >}}
第一种解法，最后一个擦边过的时间，可能会超时。参见第二种AC代码
{{< /alert >}}
AC代码
#include<bits/stdc++.h>
using namespace std;
void check(vector<int> &a,vector<int> &b){ //求解一组数据
unordered_map<int,int> mp; //mp容器记录所有出现过的数字
int cnt=0; //cnt为共有数字的个数
for(int i=0;i<a.size();i++) // 如果该数为第一组所有则标记为1
mp[a[i]]=1;
for(int i=0;i<b.size();i++){
switch(mp[b[i]]){
case 0: mp[b[i]]=2;break; //如果第一组数中没出现过，说明为第二组数所有，标记为2
case 1: mp[b[i]]=3;cnt++;break; //如果第一组也有，第二组也有，共有标记为3，并计数
case 2:
case 3: continue;break; //如果已经标记为特有或者共有，则跳过
}
}
printf("%.1f%%\n",cnt*100.0/mp.size()); //计算结果
}
int main(void){
int n,k;
scanf("%d",&n);
vector<int> v[n+1];
for(int i=1;i<=n;i++){
int m;
scanf("%d",&m);
v[i].resize(m);
for(int j=0;j<m;j++){
scanf("%d",&v[i][j]);
}
}
scanf("%d",&k);
for(int i=0;i<k;i++){
int a,b;
scanf("%d%d",&a,&b);
check(v[a],v[b]);
}
return 0;
} AC代码（更优）
感谢**张勇**同学提供的更优方法
#include<bits/stdc++.h>
using namespace std;
#define MAXN 51 //最多有MAXN组
unordered_map<int,int>G[MAXN]; //创建一个map容器的数组
int main(void){
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++){ //读入n组数据，记录在map中
int m;
scanf("%d", &m);
for (int j = 0; j < m; j++){
int num;
scanf("%d", &num);
G[i][num] = 1;
}
}
int k;
scanf("%d", &k);
for (int i = 0; i < k; i++){ //k组查询
int a, b; //查询的组号
int nc = 0,nt = 0; //nc为共同数字个数，nt为不同数字个数
scanf("%d%d", &a, &b);
nt = G[b].size(); //nt初始化为其中一个序列包含的数字个数，然后遍历第二个序列，继续统计
for (auto it = G[a].begin(); it != G[a].end(); it++){
if (G[b].find(it->first) != G[b].end())
nc++; //如果是共有的，nc加一
else
nt++; //如果不是共有的，nt加一
}
float ans = (1.0 * nc) / (1.0 * nt) * 100;
printf("%.1f", ans); puts("%");
}
return 0;
}1064
样例
输入:
10
1 2 3 4 5 6 7 8 9 0输出:
6 3 8 1 5 7 9 0 2 4思路和坑点
二叉搜索树的中序遍历是有序的，因此排序后，根据次该性质进行计算。完全二叉树的结构可以通过结点数来确定，可以计算出左右子树的结点个数，从而确定树的根结点在中序中的位置，然后递归解决左子树和右子树的根，由于层次序列的整体顺序为root,2*root+1（左子树的根）,2*root+2（右子树的根）
AC代码
#include<bits/stdc++.h>
using namespace std;
vector<int> L,v; //用于存放数据，L为最终的层次输出序列，v为输入序列
int getroot(int l,int r){ //计算输入序列中下标l~r中字数的根，并返回其下标
int num=r+1-l,layer=0; //num为l~n中的元素个数，layer为该区间元素构成完全二叉树的层数
while((int)pow(1.0*2,layer)-1<=num) //计算layer表示为最大整层数+1
layer++;
layer--; //循环结束，把layer取到最大整层数
int flnum=num-((int)pow(1.0*2,layer)-1); //flnum为最后一层的结点个数
int tag=pow(1.0*2,layer-1),leftnum; //tag为满二叉时，最后一层结点数的一半，leftnum为l~n区间构成的树的左子树元素个数
if(flnum<=tag) leftnum=tag-1+flnum; //如果最后一层不满一半，计算左子树元素个数
else leftnum=2*tag-1; //如果满一半，计算左子树个数
return leftnum+l; //返回根结点所在的下标
}
void solve(int l,int r,int root){ //将l~n区间中的根结点放置在层次序列的对应位置上
if(l>r) return; //如果该区间没有元素，直接返回
int index=getroot(l,r); //计算根在输入序列中的位置
L[root]=v[index]; //将根放在层次序列的位置上
solve(l,index-1,2*root+1); //递归求解右子树的根
solve(index+1,r,2*root+2); //递归求解右子树的根
}
int main(void){
int n;
scanf("%d",&n);
v.resize(n); L.resize(n);
for(int i=0;i<n;i++)
scanf("%d",&v[i]);
sort(v.begin(),v.end()); //排序，搜索树的中序序列是有序的
solve(0,n-1,0); //递归的起始参数
for(int i=0;i<n;i++){ //输出结果
if(i) putchar(' ');
printf("%d",L[i]);
}
return 0;
} 1065
样例
输入:
3
1 2 3
2 3 4
9223372036854775807 -9223372036854775808 0输出:
Case #1: false
Case #2: true
Case #3: false思路和坑点
直接使用long double类型直接过。
AC代码
#include<bits/stdc++.h>
using namespace std;
int main(void){
long double a,b,c;
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a>>b>>c;
cout<<"Case #"<<i<<": ";
if(a+b>c) puts("true");
else puts("false");
}
return 0;
} 1066
样例
样例1
输入:
5
88 70 61 96 120输出:
70样例2
输入:
7
88 70 61 96 120 90 65输出:
88思路和坑点
AVL树的建树，直接使用AVL树的模板即可，一定要会写AVL树的调整函数。
AVL树的总结可以参考之前的文章树和二叉树中关于AVL树部分的总结。
注意：根据题目要求调整插入的方法。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef struct node{ //结点的定义和初始化
int data;
int high=1; //高度初始化
struct node *left=NULL,*right=NULL; //左右孩子初始化为空
}Node;
int gethigh(Node *root){ //获取树的高度
if(root==NULL) return 0;
else return root->high;
}
int getbf(Node *root){ //获取结点的平衡因子
return gethigh(root->left)-gethigh(root->right);
}
void updatahigh(Node *root){ //更新结点的平衡因子
root->high=max(gethigh(root->left),gethigh(root->right))+1;
}
void L(Node *&root){ //左旋
Node *temp=root->right;
root->right=temp->left;
temp->left=root;
updatahigh(root);
updatahigh(temp);
root=temp;
}
void R(Node *&root){ //右旋
Node *temp=root->left;
root->left=temp->right;
temp->right=root;
updatahigh(root);
updatahigh(temp);
root=temp;
}
void Insert(Node *&root,int x){ //插入
if(root==NULL){
root=new Node;
root->data=x;
return;
}
if(x<root->data){
Insert(root->left,x);
updatahigh(root);
if(getbf(root)==2){
if(getbf(root->left)==1)
R(root);
else if(getbf(root->left)==-1){
L(root->left);
R(root);
}
}
}
else{
Insert(root->right,x);
updatahigh(root);
if(getbf(root)==-2){
if(getbf(root->right)==-1)
L(root);
else if(getbf(root->right)==1){
R(root->right);
L(root);
}
}
}
}
int main(void){
Node *root=NULL;
int n;
cin>>n;
for(int i=0;i<n;i++){
int temp;
cin>>temp;
Insert(root,temp);
}
cout<<root->data;
return 0;
} 1067
样例
输入:
10
3 5 7 2 6 4 9 0 8 1输出:
9思路和坑点
表排序。给出的序列，由若干个环组成。由于和0交换，因此根据环的特征分三类：
- 单独一个元素构成一个环，即自己在自己的位置上，不需要交换，交换次数为0
- 包含0的环，这样的环只和0交换，假设环中有n个元素，则需要交换n-1次
- 不包含0的换，由于只能和0交换，因此将任意一个环中的元素和0交换，将其纳入环中再进行交换，假设环中有n个元素，则需要n+1次交换
具体的解释参见代码注释或者参考MOOC陈越姥姥的讲解swap(0,*)
AC代码
#include<bits/stdc++.h>
using namespace std;
int main(void){
int n,ans=0;
cin>>n;
vector<int> v(n); //存储数据
vector<bool> vis(n,false); //访问标记
for(int i=0;i<n;i++){ //读取输入
cin>>v[i];
}
for(int i=0;i<n;i++){ //遍历数组，统计环，并计算
if(vis[i]==false){
int flag=0,cnt=0,k=i; //flag表示有没有0，如果是0表示没有，否则表示有，cnt统计环中元素个数
while(vis[k]==false){ //使用k做指针，遍历环并标记环上的元素为已访问
if(v[k]==0) flag=1;
vis[k]=true; cnt++; //统计环上元素个数
k=v[k];
}
if(cnt>1){ //如果环中的个数超过1
if(flag) ans+=cnt-1; //如果有0，则需要和0交换cnt-1 次
else ans+=cnt+1; //如果没有0，需要先把0任意交换进环中，然后此时共cnt+1个数，需要交换cnt+1-1=cnt次
//加上交换进去0的一次共cnt+1次
}
}
}
cout<<ans;
return 0;
} 1068
样例
样例1
输入:
8 9
5 9 8 7 2 3 4 1输出:
1 3 5样例2
输入:
4 8
7 2 4 3输出:
No Solution思路和坑点
0-1背包问题，这里仅给出参考代码，倒是可以理解，可是我真的自己写不出来啊，考完试再认真研究吧。
这里给一个链接帮助理解背包问题的动态规划的原理，这样讲0-1背包太生动了
AC代码
#include<bits/stdc++.h>
using namespace std;
//0-1背包问题
int w[10004],dp[103]={0};
bool flag[10004]={false};
bool choice[10004][103]={false};
bool cmp(int a,int b){
return a>b;
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&w[i]);
}
sort(w+1,w+n+1,cmp);
for(int i=1;i<=n;i++){
for(int v=m;v>=w[i];v--){
if(dp[v]<=dp[v-w[i]]+w[i]){ //如果放入i
dp[v]=dp[v-w[i]]+w[i];
choice[i][v]=true;
}
}
}
if(dp[m]!=m)
puts("No Solution");
else{
int k=n,num=0,v=m;
while(k>0){
if(choice[k][v]==true){
flag[k]=true;
v-=w[k];
num++;
}
k--;
}
for(int i=n;i>=1;i--){
if(flag[i]){
printf("%d",w[i]);
num--;
if(num>0) putchar(' ');
}
}
}
return 0;
}1069
样例
样例1
输入:
6767输出:
7766 - 6677 = 1089
9810 - 0189 = 9621
9621 - 1269 = 8352
8532 - 2358 = 6174样例2
输入:
2222输出:
2222 - 2222 = 0000思路和坑点
对字符串进行升序和降序排列，然后用其相应的数值进行计算，然后按照格式输出结果，直到出现6174.
坑点:
输出的数字不一定是刚好4位的，所以需要先按照数字读入，然后补充成4位的字符串；注意输出格式中的空格个数。
AC代码
#include<bits/stdc++.h>
using namespace std;
int main(void){
char ch[5];
int n;
scanf("%d",&n); //对于不足四位的整数，要补0
sprintf(ch,"%04d",n);
if(ch[0]==ch[1]&&ch[1]==ch[2]&&ch[2]==ch[3]){ //如果全等，直接输出
printf("%s - %s = 0000",ch,ch);
}
else{
while(1){ //循环处理
int a,b,c; //被减数，减数，差
sort(ch,ch+4); //给字符排序
sscanf(ch,"%d",&b); //读取降序排列的数
reverse(ch,ch+4); //降序逆置后变为升序
sscanf(ch,"%d",&a); //读取升序排列的数
c=a-b; //计算并输出
printf("%04d - %04d = %04d\n",a,b,c);
if(c==6174) break; //如果达到要求，结束循环，否则将字符串置为差继续循环
else sprintf(ch,"%04d",c); //必须保证4位的格式，不够的补0
}
}
return 0;
} 1070
样例
输入:
3 200
180 150 100
7.5 7.2 4.5输出:
9.45思路和坑点
将月饼按照单价从高往低排序，然后遍历对每种月饼进行出售，直到需求的量被满足，或者所有的月饼都卖完。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef struct node{ //月饼结构体
double num,total,price; //总数，总价，单价
}MC;
bool cmp(MC a,MC b){
return a.price>b.price; //按照单价从高到低排序
}
int main(void){
int n;
double d;
scanf("%d%lf",&n,&d); //读入数据
vector<MC> v(n);
for(int i=0;i<n;i++){
scanf("%lf",&v[i].num);
}
for(int i=0;i<n;i++){
scanf("%lf",&v[i].total);
v[i].price=v[i].total/v[i].num;
}
sort(v.begin(),v.end(),cmp); //排序
double sum=0;
for(int i=0;i<n;i++){ //遍历月饼数组
if(v[i].num>d){ //如果需求小于库存，出售需求量即可
sum+=v[i].price*d; //并将需求置0
d=0;
}
else{ //如果，库存小于需求，则全部出售该种月饼
sum+=v[i].total;
d-=v[i].num; //需求减小
}
if(d==0) break; //如果循环未结束之前需求被满足，则退出循环
}
printf("%.2f",sum); //输出结果
return 0;
} 1071
样例
输入:
Can1: "Can a can can a can? It can!"输出:
can 5思路和坑点
思路一：从序列中读取一个符合单词定义的字符串，使用map容器统计每一个单词的出现次数，然后取其出现次数最大者。
思路二：将整个字符串一次性读入，然后做预处理，将所有不构成单词的字符替换为空格，然后把数组和字母全改为小写。之后，分每个单词的读出并统计
坑点:
单词的定义：连续出现的只有字母或者数字构成的混合串。这些单词是被其他字符（非组成单词的字符，或者行末和行开头）分隔开的。比如can**me或者peng3-p2ang等这种情况算所两个单词，因为其中有两个连续的混合串。
AC代码（思路一）
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
getline(cin,s); //使用s记录整个字符串
string word,ans; //word记录每一个单词
unordered_map<string,int> mp; //映射每一个单词的个数
int maxcnt=0;
for(int i=0;i<s.size();){
word.clear(); //每次记录新单词前，清空word
if(isalpha(s[i])||isdigit(s[i])){ //如果遇到一个单词的开头
int j=i; //往后遍历，查看当前单词的长度
int cnt=0;
while(isalpha(s[j])||isdigit(s[j])&&j<s.size()){
cnt++; //统计单词长度
j++;
}
word=s.substr(i,cnt); //截取单词
for(int k=0;k<word.size();k++){ //转化成小写
word[k]=tolower(word[k]);
}
mp[word]++; //出现次数加一
if(mp[word]>maxcnt){ //筛选最大次数的词语
maxcnt=mp[word];
ans=word;
}
i=j; //i指向该单词在串中的下一个位置
}
else
i++; //如果不是单词的开始，跳过到下一个字符
}
cout<<ans<<' '<<mp[ans]; //输出结果
return 0;
}
AC代码（思路二）
#include<bits/stdc++.h>
using namespace std;
int main(void){
string s;
string temp;
unordered_map<string, int>mp;
getline(cin, s);
for (int i = 0; i < s.size(); i++){
if (!isalpha(s[i]) && !isdigit(s[i]))
s[i] = ' ';
else
s[i] = tolower(s[i]);
}
for (int i = 0; i < s.size(); i++){
if (s[i] == ' ' || i == s.size() - 1){
if (i == s.size() - 1 && s[i] != ' '){
temp += s[i];
}
if (temp.size()>0){
mp[temp]++;
}
temp.clear();
}
else
temp += s[i];
}
string ans;
int cnt = 0;
for (auto it = mp.begin(); it != mp.end(); it++){
if (it->second > cnt){
ans = it->first;
cnt = it->second;
}
else if (it->second == cnt && it->first < ans){
ans = it->first;
}
}
cout << ans << " " << cnt;
return 0;
}1072
样例
样例1
输入:
4 3 11 5
1 2 2
1 4 2
1 G1 4
1 G2 3
2 3 2
2 G2 1
3 4 2
3 G3 2
4 G1 3
G2 G1 1
G3 G2 2输出:
G1
2.0 3.3样例2
输入:
2 1 2 10
1 G1 9
2 G1 20输出:
No Solution思路和坑点
对每一个加油站，使用dijkstra算法求解单源最短距离，然后计算每一个加油站的各项要求指标，将符合的备选方案存放在数组中，按照要求排序输出符合最终结果的一个。
坑点:
读入数据的时候要区分居民点和加油站，需要把加油站映射成为图中的顶点。
AC代码
#include<bits/stdc++.h>
using namespace std;
#define MAXV 1015
#define INF 0x3fffffff
typedef struct gas{ //加油站结构体
string id; //id
int mindis; //到城市的最短距离
double ad; //到城市的平均距离
}Gas;
typedef struct node{ //邻接表储存图
int v,w;
node(int _v,int _w):v(_v),w(_w){}
}Node;
vector<Node> G[MAXV];
vector<Gas> gasout; //保存符合条件的加油站
bool vis[MAXV]; //访问标记数组
int n,m,k,d;
void D(int s); //Dijkstra求单源最短路径
void getdis(int &a,int &b,int &c); //读取一条边的信息
bool cmp(Gas a,Gas b){ //对答案进行排序
if(a.mindis!=b.mindis) return a.mindis>b.mindis; //按照最小距离尽可能远
else if(a.ad!=b.ad) return a.ad<b.ad; //按照平均距离尽可能小
else return a.id<b.id; //按照编号尽可能小
}
int main(){
scanf("%d%d%d%d",&n,&m,&k,&d);
for(int i=0;i<k;i++){
int a,b,c;
getdis(a,b,c); //读入一条边信息
G[a].push_back(node(b,c)); //构建图
G[b].push_back(node(a,c));
}
for(int i=1;i<=m;i++){ //对每一个加油站求解单源最短路径
D(n+i);
}
if(gasout.size()==0) puts("No Solution"); //如果没有答案
else{
sort(gasout.begin(),gasout.end(),cmp); //排序后输出第一个
cout<<gasout[0].id;
printf("\n%.1f %.1f",gasout[0].mindis*1.0,gasout[0].ad);
}
return 0;
}
void D(int s)
{
int dis[MAXV];
fill(dis,dis+MAXV,INF);
fill(vis,vis+MAXV,false);
dis[s]=0;
for(int i=1;i<=n+m;i++){
int u=-1,MIN=INF;
for(int j=1;j<=n+m;j++){
if(vis[j]==false&&dis[j]<MIN){
u=j;
MIN=dis[j];
}
}
if(u==-1) return;
vis[u]=true;
for(int j=0;j<G[u].size();j++){
int v=G[u][j].v;
if(vis[v]==false&&dis[u]+G[u][j].w<dis[v]){
dis[v]=dis[u]+G[u][j].w;
}
}
}
double sum=0;
int min=INF;
for(int i=1;i<=n;i++){ //统计加油站和居民住房的关系值
if(dis[i]>d) //如果到居民距离超过服务距离，不能入选
return;
sum+=dis[i];
min=dis[i]<min?dis[i]:min;
}
int index=s-n; //如果满足选择要求，加入最后的答案数组中
string id="G";
if(index==10) id="G10"; //G10比较特殊，单独处理
else id.push_back('0'+index);
Gas isok;
isok.id=id;
isok.ad=sum/n;
isok.mindis=min;
gasout.push_back(isok);
}
void getdis(int &a,int &b,int &c)
{
string st1,st2,st3;
cin>>st1>>st2>>st3; //按照字符串读入
if(st1[0]=='G'){ //如果是加油站，映射成结点n+i
string temp=st1.substr(1,st1.size()-1);
sscanf(temp.c_str(),"%d",&a);
a+=n;
}
else
sscanf(st1.c_str(),"%d",&a); //如果是居民楼，直接映射成结点
if(st2[0]=='G'){
string temp=st2.substr(1,st2.size()-1);
sscanf(temp.c_str(),"%d",&b);
b+=n;
}
else
sscanf(st2.c_str(),"%d",&b);
sscanf(st3.c_str(),"%d",&c);
}1073
样例
样例1
输入:
+1.23400E-03输出:
0.00123400样例2
输入:
-1.2E+10输出:
-12000000000补充样例1
输入:
-1.23456789E+003输出:
-1234.56789补充样例2
输入:
-1.23456789E-000输出:
-1.23456789思路和坑点
对数值部分和指数部分各自分别处理，然后确定最终输出的位数和小数点的位置即可，注意是否需要补0，以及补0的个数。
其中，如果指数为负数，需要前面补0；如果指数为整数，可能需要补0，如样例2，有可能不需要补0，如补充样例。
AC代码
#include<bits/stdc++.h>
using namespace std;
int main(void){
string str;
getline(cin,str);
int tag=0,etag=0,e=0,pose; //tag记录正负，etag记录指数的正负，e为指数，pose表示E在字符中的位置
swap(str[1],str[2]); //将小数点和第一位数字交换，使得数字字符串连续
if(str[0]=='-') tag=1; //如果是负数
pose=str.find('E'); //找到E的位置
if(str[pose+1]=='-') etag=1; //判断e的正负
for(int i=pose+2;i<str.size();i++){ //E之后从非零位置开始是指数
if(str[i]!='0'){
sscanf(str.substr(i,str.size()-i).c_str(),"%d",&e);
break;
}
}
str=str.substr(2,pose-2); //截取E之前的连续不包含点的字符串
if(tag==1) putchar('-'); //如果是负数，输出符号
if(e==0){ //如果指数为0，原样输出数字部分的字符串（加上小数点）
for(int i=0;i<str.size();i++){
if(i==1) putchar('.');
putchar(str[i]);
}
}
else{ //如果指数不为0
if(etag==1){ //如果指数为负数，0.后边补上|e|-1个0
cout<<"0.";
for(int i=0;i<e-1;i++)
putchar('0');
cout<<str;
}
else{ //如果指数为正
for(int i=0;i<str.size()||i<e+1;i++){
if(i>=str.size()) putchar('0'); //如果需要补零
else putchar(str[i]);
if(e<str.size()-1&&i==e) putchar('.'); //如果不需要补零，要在正确的位置上加上小数点
}
}
}
return 0;
} 1074
样例
输入:
00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218输出:
00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1思路和坑点
有两种思路。
第一种：将链表存放在数组中，然后每K个逆置，结尾不足k个不逆置。
第二种：没k个进行一组链表的头插，实现逆置。
坑点:
如果使用数组的方法，需要过滤掉不属于链表中的多余结点。
AC代码（数组实现）
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
typedef struct node{ //结点结构体
int id,data,next;
}Node;
vector<Node> all(MAXN); //存放所有输入结点
int main(void){
int head,n,k;
scanf("%d%d%d",&head,&n,&k);
for(int i=0;i<n;i++){ //读取输入
int id;
scanf("%d",&id);
all[id].id=id;
scanf("%d%d",&all[id].data,&all[id].next);
}
vector<Node> List; //用数组存放有效结点
for(int i=head;i!=-1;i=all[i].next)
List.push_back(all[i]); //有效结点存入数组
for(int i=0;i<List.size()/k;i++)//每K个逆序
reverse(List.begin()+i*k,List.begin()+(i+1)*k);
int i;
for(i=0;i<List.size()-1;i++) //输出 ，每一个的next是下一个的id，最后一个特殊处理
printf("%05d %d %05d\n",List[i].id,List[i].data,List[i+1].id);
printf("%05d %d -1",List[i].id,List[i].data);
return 0;
} AC代码（链表实现）
#include<bits/stdc++.h>
using namespace std;
typedef struct{
int id,data,next;
}Node;
Node List[100005];
int main(){
int n,k; //n为所谓的节点数量 ，k为逆转数
int cnt=0; //用于记录已经处理的节点数量
int L=100001; //链表表头的空结点
int head,temp,r,rear; //head为链表第一个结点 ，temp为保证链表不掉链，r用于最后的遍历输出，rear用于记录每次链表的尾巴，每k次需要从尾巴处头插
cin>>head>>n>>k;
for(int i=0;i<n;i++){ //读入数据
int index;
scanf("%d",&index);
scanf("%d%d",&List[index].data,&List[index].next);
}
n=0; //统计排除多余结点
for(int i=head;i!=-1;i=List[i].next){
n++;
}
List[L].next=-1; //摘下空的头结点，开始头插
rear=head; //每次第一个头插的结点会成为链表的尾巴
while(cnt!=n-n%k){ //如果不是k的整数倍个结点只需要处理前n-n%k个结点
temp=List[head].next;
List[head].next=List[L].next;
List[L].next=head;;
cnt++;
if(cnt%k==0){ //每当头插k个实现了逆序后，要更新到当前链表的尾巴处继续新一轮的头插
L=rear;
rear=temp;
}
head=temp;
}
if(cnt!=n){ //如果有尾巴，处理尾巴
List[L].next=head;
}
//输出
for(r=List[100001].next;List[r].next!=-1;r=List[r].next){
printf("%05d %d %05d\n",r,List[r].data,List[r].next);
}
printf("%05d %d -1",r,List[r].data);
return 0;
}1075
样例
输入:
7 4 20
20 25 25 30
00002 2 12
00007 4 17
00005 1 19
00007 2 25
00005 1 20
00002 2 2
00005 1 15
00001 1 18
00004 3 25
00002 2 25
00005 3 22
00006 4 -1
00001 2 18
00002 1 20
00004 1 15
00002 4 18
00001 3 4
00001 4 2
00005 2 -1
00004 2 0输出:
1 00002 63 20 25 - 18
2 00005 42 20 0 22 -
2 00007 42 - 25 - 17
2 00001 42 18 18 4 2
5 00004 40 15 0 25 -思路和坑点
对于每一个学生使用结构体存储，对于其成绩，使用数组表示并初始化为-2，表示未提交过，-1表示未通过编译。依次读取成绩的提交记录，每次如果有更高的成绩，则更新成绩。然后遍历并统计计算学生的各项参数，最后排序并输出。
主要的难点在于数据的处理：成绩的更新，统计和输出、不需要输出的删选、排序规则。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef struct node{
int id,total=0,tag=0,cnt=0; //id，total总分，tag为是否输出的标记，1表示需要输出，cnt为完美解题计数
int score[6]; //成绩记录数组，初始化为-2，表示未提交过
node(){
for(int i=1;i<=5;i++)
score[i]=-2;
}
}Node;
vector<Node> v; //存放数据
vector<int> sid; //用于下标排序
bool cmp(int i,int j){ //排序函数
if(v[i].tag!=v[j].tag) return v[i].tag>v[j].tag; //需要输出的在前
else if(v[i].total!=v[j].total) return v[i].total>v[j].total; //总成绩从高到底
else if(v[i].cnt!=v[j].cnt) return v[i].cnt>v[j].cnt; //cnt从高到底
else return v[i].id<v[j].id; //id从低到高
}
int main(void){
int n,m,k;
scanf("%d%d%d",&n,&k,&m); //读入数据，并初始化每一个容器的大小
vector<int> p(k+1); //记录每题的分值
v.resize(n+1); sid.resize(n+1);
for(int i=1;i<=k;i++) //读入各题分值
scanf("%d",&p[i]);
for(int i=0;i<m;i++){ //读入每次提交
int id,index,s;
scanf("%d%d%d",&id,&index,&s);
if(s>v[id].score[index]) //如果成绩更高则更新
v[id].score[index]=s;
}
for(int i=1;i<=n;i++){ //处理并统计每位学生的成绩信息
sid[i]=i; //初始化下标排序数组
v[i].id=i; //初始化每一个学生的id
for(int j=1;j<=k;j++){
if(v[i].score[j]>=0){ //如果有提交过则tag标记为1
v[i].tag=1;
v[i].total+=v[i].score[j]; //成绩总分累加
if(v[i].score[j]==p[j]) //如果完美解题，cnt计数加一
v[i].cnt++;
}
}
}
sort(sid.begin()+1,sid.end(),cmp); //排序
int rank,pre; //rank为排名 ，pre用于记录前一个记录的下标
for(int i=1;i<=n;i++){
int l=sid[i]; //读取当前的学生下标
if(v[l].tag==0) break; //如果不需要输出，则返回（因为排完序之后，不需要输出的都在后边）
if(i==1) rank=1; //第一个rank为1
else if(v[l].total!=v[pre].total) rank=i; //如果总成绩和前一个人不同，rank=i，否则和前一个人同排名
printf("%d %05d %d",rank,v[l].id,v[l].total); //输出结果
for(int j=1;j<=k;j++){ //输入每一题的成绩
switch(v[l].score[j]){
case -2: printf(" -");break; //未提交为 -
case -1: printf(" 0");break; //未通过编译为0
default: printf(" %d",v[l].score[j]);break;
}
}
putchar('\n');
pre=l; //更新pre
}
return 0;
} 1076
样例
输入:
7 3
3 2 3 4
0
2 5 6
2 3 1
2 3 4
1 4
1 5
2 2 6输出:
4
5思路和坑点
对查询的结点使用bfs方法，查询层数在规定的L以内的个数，即为所需要的统计结果，当遍历的层数达到要求时要提前终止循环。
AC代码
#include<bits/stdc++.h>
using namespace std;
#define MAXN 1002
vector<int> v[MAXN];
vector<bool> vis(MAXN);
int n,l;
int findans(int s){ //bfs函数
fill(vis.begin(),vis.end(),false); //访问标记初始化
int layer=1,last=s,tail; //层数，last为当前层的最后一个，tail用于更新last
int cnt=0; //cnt为计数
queue<int> q;
q.push(s);
vis[s]=true;
while(!q.empty()){ //使用队列进行层序遍历
int now=q.front();
q.pop();
for(int i=0;i<v[now].size();i++){
int k=v[now][i];
if(vis[k]==false){
q.push(k);
vis[k]=true;
cnt++;
tail=k;
}
}
if(now==last){ //如果当前层结束，layer++，如果层数超过规定的l则退出循环
layer++;
if(layer>l) break;
last=tail;
}
}
return cnt;
}
int main(void){
scanf("%d%d",&n,&l);
for(int i=1;i<=n;i++){ //读入数据
int num; scanf("%d",&num);
for(int j=0;j<num;j++){
int temp; scanf("%d",&temp);
v[temp].push_back(i);
}
}
int k;
scanf("%d",&k); //读入查询，并打印结果
for(int i=0;i<k;i++){
int id; scanf("%d",&id);
printf("%d\n",findans(id));
}
return 0;
} 1077
样例
样例1
输入:
3
Itai nyan~
Ninjin wa iyadanyan~
uhhh nyan~输出:
nyan~样例2
输入:
3
Itai!
Ninjinnwaiyada T_T
T_T输出:
nai思路和坑点
将所有的字符串逆置，然后比对公共头部即可。首先把第一个字符串作为比较基准，然后每次读取一个字符串，将基准和当前字符串的头部进行比对（对比结果要么公共字符串长度不变，要么缩短），提取公共的头部；依次比对完所有的字符串。最后再逆置输出，如果得到的是空字符串，说明没有答案，按照要求输出”nai“。
AC代码
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
getchar(); //吸收第一行的回车字符
string ans;
for(int i=0;i<n;i++){
string s;
getline(cin,s); //每次读一行
int lens=s.length();
reverse(s.begin(),s.end()); //字符串逆置
if(i==0){ //把第一个字符串作为对比标准 ，从第二个开始比较依次缩短至得到答案
ans=s;
continue;
}else{
int lenans=ans.length();
int minlen=min(lens,lenans); //最小长度为当前字符的长度和答案长度，两者取最小值
for(int j=0;j<minlen;j++){
if(s[j]!=ans[j]){ //直到比相同的位置停止对比
ans=ans.substr(0,j); //将答案缩短到长度为j的字符串 ，并推出比对循环
break;
}
}
}
}
reverse(ans.begin(),ans.end()); //答案要逆置输出
if(ans.length()==0) ans="nai"; //如果答案为空，则输出为nai
cout<<ans;
return 0;
}1078
样例
输入:
4 4
10 6 4 15输出:
0 1 4 -思路和坑点
使用hash函数直接进行hash运算，如果不成功则进行正的二次探测。
AC代码
#include<bits/stdc++.h>
using namespace std;
bool isprimer(int x){ //素数判别函数
if(x<=1) return false;
for(int i=2;i<=(int)sqrt(x*1.0);i++){
if(x%i==0)
return false;
}
return true;
}
int main(void){
int size,n;
scanf("%d%d",&size,&n);
while(!isprimer(size)) //找到一个符合条件的素数作为hash表的大小
size++;
vector<bool> Table(size,false); //hash表的标记，当前下标位置是否已被分配，初始化为false
for(int i=0;i<n;i++){
if(i) putchar(' '); //出了第一个不输出空格以外，之后的都输出空格
int num;
scanf("%d",&num); //读入一个数字
int pos=num%size;
if(Table[pos]==false){ //如果hash表中直接可分配位置，则分配，并修改标记
printf("%d",pos);
Table[pos]=true;
}
else { //否则，使用二次探测法
int step; //探测步长
for(step=1;step<size;step++){ //探测步长最大为hash表长
pos=(num+step*step)%size; //计算探测位置
if(Table[pos]==false){ //如果可以分配则分配，并修改标记
printf("%d",pos);
Table[pos]=true;
break;
}
}
if(step>=size) putchar('-'); //如果二次探测失败，则输出-
}
}
return 0;
} 1079
样例
输入:
10 1.80 1.00
3 2 3 5
1 9
1 4
1 7
0 7
2 6 1
1 8
0 9
0 4
0 3输出:
42.4思路和坑点
本题考查多叉树的层序遍历，对给出的结果建树。然后层序遍历，并记录层数，对于零售商来说，其销售额销售额=p*（1+r%）^layer
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef struct node{ //多叉树结点结构体
int tag; //-1表示不是零售商，不是-1则表示零售商货物储量
vector<int> child; //孩子数组
}Node;
int main(void){
int n;
double p,r;
scanf("%d%lf%lf",&n,&p,&r); //读入参数
r=1+r/100; //直接将r换算成价格p的倍数
vector<Node> v(n);
for(int i=0;i<n;i++){
int num;
scanf("%d",&num);
if(num==0) scanf("%d",&v[i].tag); //如果是零售商读入货物储量
else{
v[i].tag=-1; //如果不是零售商，标记为-1
for(int j=0;j<num;j++){ //读入其孩子序号
int temp; scanf("%d",&temp);
v[i].child.push_back(temp);
}
}
}
queue<int> q; //使用队列进行层次遍历
int layer=0,last=0,tail=0; //layer记录层数，last记录当前层的最后一个，tail用于在当前层结束后更新last
double sum=0; //统计总销售额
q.push(0);
while(!q.empty()){
int now=q.front(); //从队列中读出一个元素
q.pop();
int size=v[now].child.size();
for(int i=0;i<size;i++){ //将孩子依次入队
q.push(v[now].child[i]);
tail=v[now].child[i];
}
if(v[now].tag!=-1) //如果当前节点是零售商，累加销售额
sum+=v[now].tag*p*pow(r,layer);
if(now==last){ //当前层结束后，层数增加，更新last
layer++;
last=tail;
}
}
printf("%.1f",sum); //输出结果
return 0;
} 1080
样例
输入:
11 6 3
2 1 2 2 2 3
100 100 0 1 2
60 60 2 3 5
100 90 0 3 4
90 100 1 2 0
90 90 5 1 3
80 90 1 0 2
80 80 0 1 2
80 80 0 1 2
80 70 1 3 2
70 80 1 2 3
100 100 0 2 4输出:
0 10
3
5 6 7
2 8
1 4思路和坑点
录取规则：
- 按照总成绩排序，如果总成绩相同，按照ge成绩排序，如果两项都相同，则排名相同。
- 所有申请按照排名依次进行录取。
- 对于每一个申请来说，对于其申请的学校，按照申请的志愿顺序进行录取。如果志愿学校没有录取满，则录取；如果申请的学校录取满，但是该学生和此学校上一个录取的学生同排名，则超额录取；否则，按顺序考虑下一个志愿。如果所有志愿都未能被录取，则该申请无法被录取。
对学生按照要求进行排序，然后遍历计算排名。之后按照录取要求，一个一个的录取，直到最后，并输出结果。
AC代码
#include<bits/stdc++.h>
using namespace std;
#define MAXA 40009
#define MAXS 105
typedef struct school{ //学校结构体
int num; //招收人数
vector<int> get; //录取结果数组
}SC;
typedef struct app{ //学生申请的结构体
int rank; //排名
int ge,gi; //成绩
int final; //总成绩
vector<int> choice; //申请的学校数组
}AP;
SC sch[MAXS]; //学校数组
AP apps[MAXA]; //学生数组 ，由于使用下标排序，因此定义成全局变量
vector<int> sindex; //用于学生的下标排序
int n,m,k;
bool cmp(int a,int b){ //排序规则，先按总成绩从高到低排序，在按照ge成绩从高往低排序
if(apps[a].final!=apps[b].final) return apps[a].final>apps[b].final;
else return apps[a].ge>apps[b].ge;
}
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<m;i++){ //读入学校信息
scanf("%d",&sch[i].num);
}
for(int i=0;i<n;i++){ //读入申请信息
sindex.push_back(i);
scanf("%d%d",&apps[i].ge,&apps[i].gi);
apps[i].final=apps[i].ge+apps[i].gi; //计算总成绩
for(int j=0;j<k;j++){ //读入想要申请的学校
int num;
scanf("%d",&num);
apps[i].choice.push_back(num);
}
}
sort(sindex.begin(),sindex.end(),cmp); //学生申请排序
apps[sindex[0]].rank=0; //构建排名，这里从0开始，同排名模式0，1，1，2，2，3，4 类似的方式
for(int i=1;i<sindex.size();i++){
int v=sindex[i]; //当前学生申请的序号
int pre=sindex[i-1]; //前一个学生的序号
if(apps[v].final==apps[pre].final&&apps[v].ge==apps[pre].ge)
apps[v].rank=apps[pre].rank; //如果和前一个学生并列，则排名相同
else
apps[v].rank=apps[pre].rank+1; //否则在前一个排名的基础上+1
}
for(int i=0;i<sindex.size();i++){ //遍历所有的申请，开始录取环节
int v=sindex[i];
for(int j=0;j<k;j++){ //遍历申请的每一个选择
int ch=apps[v].choice[j]; //获取申请学校的编号
if(sch[ch].get.size()<sch[ch].num){ //如果申请的学校没有招满，则收入
sch[ch].get.push_back(v);
break;
}
else{ //如果已经招满，但该学生和此学校最后收入的学生同排名，则超额录取
int tail=sch[ch].get.back();
if(apps[v].rank==apps[tail].rank){
sch[ch].get.push_back(v);
break;
}
}
}
}
for(int i=0;i<m;i++){ //输出结果
if(sch[i].get.size()!=0){
sort(sch[i].get.begin(),sch[i].get.end());
for(int j=0;j<sch[i].get.size();j++){
if(j) putchar(' ');
printf("%d",sch[i].get[j]);
}
}
putchar('\n');
}
return 0;
}1081
样例
样例1
输入:
5
2/5 4/15 1/30 -2/60 8/3输出:
3 1/3样例2
输入:
2
4/3 2/3输出:
2样例3
输入:
3
1/3 -1/6 1/8输出:
7/24思路和坑点
定义分数的结构体，然后按照分数加法的运算方法进行运算。输出时注意真分数和假分数的区分，以及整数的输出格式。
坑点:
注意运算过程重要随时对分数进行通分化简。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef struct node{ //分数结构体
int up=0,down=1;
}Node;
int gcd(int a,int b){ //求最小公约数
return !b?a:gcd(b,a%b);
}
void simp(Node &a){ //分子分母化简
int g=gcd(a.up,a.down);
a.up/=g; a.down/=g;
}
void add(Node &a,Node &b){ //相加函数
simp(a); simp(b);
int up,down,g;
down=a.down*b.down;
up=a.up*b.down+b.up*a.down;
g=gcd(up,down); //相加之前和相加后都要化简
a.up=up/g; a.down=down/g;
}
int main(void){
Node sum;
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
Node temp;
scanf("%d/%d",&temp.up,&temp.down);
add(sum,temp);
}
if(sum.up==0) putchar('0'); //如果是0直接输出
else if(abs(sum.up)>=sum.down){ //如果是假分数，输出整数部分
printf("%d",sum.up/sum.down);
if(sum.up%sum.down!=0) //如果还有分数部分，则输出
printf(" %d/%d",sum.up%sum.down,sum.down);
}
else //真分数直接输出
printf("%d/%d",sum.up,sum.down);
return 0;
} 1082
样例
样例1
输入:
-123456789输出:
Fu yi Yi er Qian san Bai si Shi wu Wan liu Qian qi Bai ba Shi jiu样例2
输入:
100800输出:
yi Shi Wan ling ba Bai思路和坑点
依次对每一位进行处理，将数字和单位分开考虑，其中“万”一定会被读到，其他的单位需要考虑0的读法，由于0的读法和前一位有关，如果前一位不是0，并且不是“个位、万位、亿位“则需要读零。正负最后考虑，由于从低位到高位读，所以最终的输出序列中先读入单位，再读入数字，最后倒序输出。
AC代码
#include<bits/stdc++.h>
using namespace std;
int main(){
//数字位读法
string shu[10]={"ling","yi","er","san","si","wu","liu","qi","ba","jiu"};
//位数的读法
string wei[10]={"0","0","Shi","Bai","Qian","Wan","Shi","Bai","Qian","Yi"};
int n; //读入要处理的数
int tag=0; //正负数标记，1表示负数，0表示正数
cin>>n;
vector<string> v; //用于存放最终结果，最后倒序输出
int now,numcnt=0,pre; //now记录当前位的数字，pre记录前一位的数字，numcnt记录当前数字的位数
if(n==0) { //特判0
puts("ling"); return 0;
}
if(n<0){
tag=1;n=-n; //修改正负号标记，改为正数统一处理
}
while(n){
now=n%10;
n/=10;
numcnt++;
if(now){ //如果当前为不是0
if(numcnt>1) //如果当前为不是个位，则需要单位
v.push_back(wei[numcnt]); //如果需要单位，放入对应的单位
v.push_back(shu[now]); //存入数字的读法
}
else{ //如果是0，考虑读不读0
if(numcnt==5) //如果是万位，则加入万的单位
v.push_back(wei[numcnt]);
else if(pre&&numcnt!=9&&numcnt!=1) //如果前一位不是0，且不是亿位，万位和个位的时候读0
v.push_back(shu[now]);
}
pre=now; //更新pre
}
if(tag==1) v.push_back("Fu");
for(int i=v.size()-1;i>=0;i--){
if(i!=v.size()-1) putchar(' ');
cout<<v[i];
}
return 0;
}1083
样例
样例1
输入:
4
Tom CS000001 59
Joe Math990112 89
Mike CS991301 100
Mary EE990830 95
60 100输出:
Mike CS991301
Mary EE990830
Joe Math990112样例2
输入:
2
Jean AA980920 60
Ann CS01 80
90 95输出:
NONE思路和坑点
对学生按照成绩从高到低排序，然后遍历查询输出符合条件的学生，为了优化排序的时间，使用下标排序的方法。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef struct node{ //学生结构体
string name,id;
int score;
}Node;
vector<Node> v;
vector<int> sid; //排序用的下标数组
bool cmp(int a,int b){ //排序函数
return v[a].score>v[b].score;
}
int main(void){
int n; scanf("%d",&n);
v.resize(n); sid.resize(n); //初始化结构体数组大小和下标数组大小
for(int i=0;i<n;i++){
sid[i]=i; //初始化下标数组
cin>>v[i].name>>v[i].id; //读入学生数据
scanf("%d",&v[i].score);
}
sort(sid.begin(),sid.end(),cmp); //排序
int a,b,cnt=0;
scanf("%d%d",&a,&b); //读取上下限，cnt用于计数
for(int i=0;i<n;i++){
int k=sid[i];
if(v[k].score>=a&&v[k].score<=b){ //如果满足要求，输出并计数
printf("%s %s\n",v[k].name.c_str(),v[k].id.c_str());
cnt++;
}
else if(v[k].score<a) break; //由于分数从高到低排序，所以一旦分数低于下届，结束循环
}
if(cnt==0) puts("NONE"); //如果不存在给定范围内的学生，输出NONE
return 0;
} 1084
样例
输入:
7_This_is_a_test
_hs_s_a_es输出:
7TI思路和坑点
遍历一遍输出的结果，使用map容器做标记。然后遍历一遍完整的字符串，如果没有对应的映射值，则输出，并添加map的映射标记，表示已经输出过了。
坑点:
由于需要输出大写，而且大小写都对应同一个键位，所以统一转化为大写进行判定和操作。
AC代码
#include<bits/stdc++.h>
using namespace std;
int main(void){
string in,broken;
unordered_map<char,int> mp; //用于统计是否损坏
getline(cin,in); //输入序列
getline(cin,broken); //坏掉的序列
for(int i=0;i<broken.size();i++){
broken[i]=toupper(broken[i]); //统一转化为大写
mp[broken[i]]=1; //做标记
}
for(int i=0;i<in.size();i++){
in[i]=toupper(in[i]);
if(mp[in[i]]==0){ //如果不存在代表损坏
mp[in[i]]=1; //修改标记，表示已经输出过，下次不再输出
cout<<in[i];
}
}
return 0;
} 1085
样例
输入:
10 8
2 3 20 4 5 1 6 7 8 9输出:
8思路和坑点
先使用快速排序从小到大排序，然后遍历一边数组，对于每一个数字，寻找符合条件的最大值的后一个位置的下标（使用二分法，或者直接调用函数），获得当前的符合要求的序列长度，然后取最大值。
要点:
对于优化判定边界，由于当i的位置找到一个i-j的序列满足要求，且是目前以获得的最长序列ans，则n-ans之后的序列中能找到的最长序列完美序列一定不超过ans，因此可以作为结束循环的判定条件。
AC代码
#include<bits/stdc++.h>
using namespace std;
int main(void){
int n,p;
scanf("%d%d",&n,&p); //读取n和p
vector<long long> v(n); //使用long long存放数据
for(int i=0;i<n;i++)
scanf("%lld",&v[i]); //读入数据
sort(v.begin(),v.end()); //快速排序
int ans=1; //长度至少为1
for(int i=0;i<n-ans;i++){ //判断结束条件是i<n-ans ，因为当i=n-ans的时候，后半段得到的结果不会比ans更大，所以结束循环
//找到第一个大于当前数*p的数字的下标
int j=upper_bound(v.begin()+i,v.end(),v[i]*p)-v.begin();
if(j-i>ans) //如果这样的序列比ans更长 更新ans
ans=j-i;
}
cout<<ans;
return 0;
} 1086
样例
输入:
6
Push 1
Push 2
Push 3
Pop
Pop
Push 4
Pop
Pop
Push 5
Push 6
Pop
Pop输出:
3 4 2 6 5 1思路和坑点
通树的先序和中序的非递归算法可以直到，栈的push序列是其先序序列，pop序列是其中序序列。因此通过栈的模拟分别获得先序和中序序列，然后由此建树，可以直接在递归函数中加一个后序的下标位置作为参数，直接获得后序遍历的结果。
AC代码
#include<bits/stdc++.h>
using namespace std;
vector<int> pre,in,post; //用于存放先序、中序、后序的序列
//树的后序序列创建函数
//pl，pr，il，ir，pos分别表示当前的先序序列的左右端下标，中序序列的左右下标，以及在后序中根的位置
void creat(int pl,int pr,int il,int ir,int pos){
if(pl>pr) return; //如果当前递归的子树中没有结点，直接返回
post[pos]=pre[pl]; //先序的第一个便是根，放在后序序列的相应位置上
int k,leftnum,rightnum; //k表示根在中序中的位置下标，leftnum和rightnum分别表示左右子树元素个数
for(k=il;k<=ir;k++){ //确定k
if(in[k]==pre[pl])
break;
}
leftnum=k-il; rightnum=ir-k; //确定左右子树的元素个数
creat(pl+1,pl+leftnum,il,k-1,pos-rightnum-1); //递归左子树
creat(pl+leftnum+1,pr,k+1,ir,pos-1); //递归右子树
}
int main(void){
int n;
scanf("%d",&n);
post.resize(n);
stack<int> s;
for(int i=0;i<n*2;i++){ //有n*2此操作
string tag;
cin>>tag; //操作的类型
if(tag=="Push"){
int num; scanf("%d",&num); //如果是push，读入相应的数字分别压入栈和前序序列中
pre.push_back(num);
s.push(num);
}
else{
in.push_back(s.top()); //如果是pop，出栈顺序为中序序列，并从栈中出栈
s.pop();
}
}
creat(0,n-1,0,n-1,n-1); //建树并输出
for(int i=0;i<n;i++){
if(i) putchar(' ');
printf("%d",post[i]);
}
return 0;
} 1087
样例
输入:
6 7 HZH
ROM 100
PKN 40
GDN 55
PRS 95
BLN 80
ROM GDN 1
BLN ROM 1
HZH PKN 1
PRS ROM 2
BLN HZH 2
PKN GDN 1
HZH PRS 1输出:
3 3 195 97
HZH->PRS->ROM思路和坑点
由于，对于最短路径的优化条件比较复杂，还需要统计最短路径条数，因此，使用Dijksatra+dfs的方法得到所求的最短路径，其中Dijkstra算法用于获得多条备选路径，dfs对每一条路径进行遍历，然后根据优化尺度比较最终保留符合条件的路径，并输出。
要点:
其中，需要吧所有的城市结点映射成为0~n-1，其中由于起点城市没有happy值，所以不妨直接令起点映射为0，并且happy值为0，方便之后的统计计算。
AC代码
#include<bits/stdc++.h>
using namespace std;
#define MAXV 205
#define INF 0x3fffffff
int n,k; //图的顶点个数，图的边个数
int cnt=0; //记录路径条数
int totalh=-1; //第二优化尺度（总的happy值）
int happy[MAXV]; //happy映射
int G[MAXV][MAXV]; //图
int dis[MAXV]; //最短距离数组
bool vis[MAXV]={false}; //访问标记
string st,ed="ROM"; //起始和结束
vector<int> path[MAXV]; //多路径记录
vector<int> pathout,temppath; //输出路径和临时路径存放
unordered_map<string,int> mp; //城市的下标映射
unordered_map<int,string> mpi;
void D(); //Dijkstra算法
void DFS(int v);
int main(){
fill(G[0],G[0]+MAXV*MAXV,INF);
scanf("%d%d",&n,&k);
cin>>st;
mp[st]=0; //起始点映射为0
mpi[0]=st;
happy[0]=0; //起始点的happy为0
for(int i=1;i<n;i++){ //读入happy并完成坐标映射
string temp;
cin>>temp>>happy[i];
mp[temp]=i;mpi[i]=temp;
}
for(int i=0;i<k;i++){ //读入边
string c1,c2;
int ct1,ct2,c;
cin>>c1>>c2>>c;
ct1=mp[c1];ct2=mp[c2];
G[ct1][ct2]=G[ct2][ct1]=c;
}
int edn=mp[ed]; //终点下标
D();
DFS(edn);
int avh=totalh/(pathout.size()-1);
cout<<cnt<<' '<<dis[edn]<<' '<<totalh<<' '<<avh<<'\n';
for(int i=pathout.size()-1;i>=0;i--){
int k=pathout[i];
if(i!=pathout.size()-1) printf("->");
cout<<mpi[k];
}
return 0;
}
void D(){
fill(dis,dis+MAXV,INF);
dis[0]=0;
for(int i=0;i<n;i++){
int u=-1,MIN=INF;
for(int j=0;j<n;j++){
if(vis[j]==false&&dis[j]<MIN){
u=j;
MIN=dis[j];
}
}
if(u==-1) return;
vis[u]=true;
for(int v=0;v<n;v++){
if(vis[v]==false&&G[u][v]!=INF){
if(dis[u]+G[u][v]<dis[v]){
dis[v]=dis[u]+G[u][v];
path[v].clear();
path[v].push_back(u);
}
else if(dis[u]+G[u][v]==dis[v]){
path[v].push_back(u);
}
}
}
}
}
void DFS(int v){
if(v==0){ //当获得一条路径时
cnt++; //路径计数器加一
temppath.push_back(0);
int value=0; //计算当前获得路径的happy值
for(int i=0;i<temppath.size();i++){
int k=temppath[i];
value+=happy[k];
}
if(value>totalh){ //如果happy更多，则更新
totalh=value;
pathout=temppath;
}
else if(value==totalh&&temppath.size()<pathout.size()){ //如果happy相同，城市个数少的平均happy更高，则更新
pathout=temppath;
}
temppath.pop_back();
return;
}
temppath.push_back(v);
for(int i=0;i<path[v].size();i++){
DFS(path[v][i]);
}
temppath.pop_back();
}1088
样例
样例1
输入:
2/3 -4/2输出:
2/3 + (-2) = (-1 1/3)
2/3 - (-2) = 2 2/3
2/3 * (-2) = (-1 1/3)
2/3 / (-2) = (-1/3)样例2
输入:
5/3 0/6输出:
1 2/3 + 0 = 1 2/3
1 2/3 - 0 = 1 2/3
1 2/3 * 0 = 0
1 2/3 / 0 = Inf思路和坑点
分数的运算。使用结构体表示一个分数。按照分数的计算方法进行计算。
坑点:
一、分数的表示，即分数的打印，需要考虑真分数，假分数，还有整数已经正负号问题。
二、分数的运算中，需要时时刻刻注意化简分子和分母，另外求解分子和分母的公约数的时候要分别加上绝对值只有再求。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef struct{ //分数结构体
long long up;
long long down;
}FEN;
long long gcd(long long a,long long b){//求最小公约数
return !b?a:gcd(b,a%b);
}
void yuefen(FEN *py){ //约分成最简形式
long long y;
if(py->up==0) //如果分子是0，令分母为1
py->down=1;
else{
y=gcd(abs(py->up),abs(py->down)); //求分子分母绝对值的最大公约数，一定要绝对值之后求公约数
py->up/=y; py->down/=y; //约分
}
}
void print_fen(FEN *pf){ //分数的打印
long long up=pf->up,down=pf->down;
if(up==0){ //如果是0，直接打0
putchar('0'); return;
}
if(up<0) putchar('('); //如果是负数，打印括号
if(abs(up)>=down){ //假分数
printf("%d",up/down); //先打印整数部分
if(up%down) //如果不是整数，打印分数部分，一定要分子求绝对值
printf(" %d/%d",abs(up)%down,down);
}
else
printf("%d/%d",up%down,down); //真分数直接打印
if(up<0) putchar(')'); //负数括号配对
}
int main(void)
{
FEN a,b,temp;
scanf("%lld/%lld %lld/%lld",&a.up,&a.down,&b.up,&b.down);
yuefen(&a); yuefen(&b);
temp.down=a.down*b.down; //加法
temp.up=a.up*b.down+a.down*b.up;
yuefen(&temp); //算完后要化简
print_fen(&a);printf(" + ");print_fen(&b);printf(" = ");print_fen(&temp);putchar('\n');
temp.up=a.up*b.down-a.down*b.up; //减法，只是分子需要重新计算
yuefen(&temp);
print_fen(&a);printf(" - ");print_fen(&b);printf(" = ");print_fen(&temp);putchar('\n');
temp.up=a.up*b.up; //乘法，只是分子需要重新计算
yuefen(&temp);
print_fen(&a);printf(" * ");print_fen(&b);printf(" = ");print_fen(&temp);putchar('\n');
if(b.up==0){ //如果除0，特殊判定
print_fen(&a);printf(" / ");putchar('0');printf(" = ");printf("Inf");putchar('\n');
}
else{
temp.down=a.down*b.up; //除法运算
temp.up=a.up*b.down;
if(temp.down<0){ //保证分子带正负号，分母总为正数
temp.down=-temp.down;
temp.up=-temp.up;
}
yuefen(&temp); //约分并打印结果
print_fen(&a);printf(" / ");print_fen(&b);printf(" = ");print_fen(&temp);putchar('\n');
}
return 0;
}1089
样例
样例1
输入:
10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0输出:
Insertion Sort
1 2 3 5 7 8 9 4 6 0样例2
输入:
10
3 1 2 8 7 5 9 4 0 6
1 3 2 8 5 7 4 9 0 6输出:
Merge Sort
1 2 3 8 4 5 7 9 0 6思路和坑点
根据插入排序和归并排序的特点，插入排序前一部分有序，后一部分和原序列相同。一旦排除插入排序，则是归并排序，对原始序列模拟归并排序，当和中间序列相同时再进行一次归并几位所求结果。
AC代码
#include<bits/stdc++.h>
using namespace std;
int main(void){
int n,i,j;
cin>>n;
vector<int> v(n),vs(n); //两个序列，v为原始序列，vs为中间序列
for(i=0;i<n;i++) cin>>v[i];
for(i=0;i<n;i++) cin>>vs[i];
for(i=0;i<n-1;i++){ //找vs中前边不是有序的位置
if(vs[i]>vs[i+1]){
j=i+1; break;
}
}
for(j;j<n;j++){ //后半部分如果还和原始序列相同，则是插入 ，否则是归并
if(v[j]!=vs[j]) break;
}
if(j==n){ //如果后半部分和原始序列相同，j会走到n
puts("Insertion Sort");
sort(v.begin(),v.begin()+i+2); //将前半部分排序，统一都在v上操作，这样最后序列输出可以统一
}
else{
puts("Merge Sort");
int step=2,flag=1; //step表示归并段的长度，初始化为2，flag表示是否到达中间序列
while(flag){
if(v==vs) flag=0; //如果归并到给定的中间结果，修改flag=0，然后再归并一次之后结束循环
for(i=0;i<n/step;i++) //整齐部分的归并段排序，每个段内使用快排
sort(v.begin()+i*step,v.begin()+(i+1)*step);
sort(v.begin()+i*step,v.end()); //结尾部分不够整个step的单独处理
step*=2; //归并步长加倍
}
}
for(int i=0;i<n;i++){ //输出结果
if(i) putchar(' ');
printf("%d",v[i]);
}
return 0;
} 1090
样例
输入:
9 1.80 1.00
1 5 4 4 -1 4 5 3 6输出:
1.85 2思路和坑点
多叉树的层序遍历，找到最大成熟，并统计最大层数的叶子节点个数，使用结构体数组的形式表示多叉树。使用队列进行层序遍历。
AC代码
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
typedef struct node{ //多叉树结点
int layer; //结点层数
bool tag; //零售商标记 ，默认都是零售商 ,如果有孩子则修改为false
vector<int> child;
node(){
tag=true;
}
}Node;
Node T[MAXN];
int n;
double p,r;
int main(){
scanf("%d%lf%lf",&n,&p,&r);
if(n==1){ //特判
printf("%.2f 1",p);
return 0;
}
int root;
for(int i=0;i<n;i++){
int num;
scanf("%d",&num);
if(num==-1) root=i; //记录根
else{ //读入孩子
T[num].child.push_back(i); //如果有孩子说明不是零售商，修改标记为false
T[num].tag=false;
}
}
int maxlayer=0; //记录最大层数
int cnt=1;
queue<int> q; //层序遍历
q.push(root);
T[root].layer=0;
while(!q.empty()){
int now=q.front();
q.pop(); //当前结点的孩子入队，并且更新其层数
for(int i=0;i<T[now].child.size();i++){
int k=T[now].child[i];
T[k].layer=T[now].layer+1;
q.push(k);
}
if(T[now].tag==true){
if(T[now].layer>maxlayer){ //如果有更大层数，则更新maxlayer，并把cnt重置为1
maxlayer=T[now].layer;
cnt=1;
}
else if(T[now].layer==maxlayer) //如果和最大的层数相同，cnt加一
cnt++;
}
}
printf("%.2f %d",p*pow(1.0+r/100,maxlayer),cnt);
return 0;
}
Comments | NOTHING