PAT甲级题解1031-0160
1031
样例
输入:
helloworld!输出:
h !
e d
l l
lowor思路和坑点
按照要求算出需要打印的格式中，每一边的字母个数，然后按照要求打印即可。
AC代码
#include<bits/stdc++.h>
using namespace std;
int main(void){
int n1,n2,k,n;
string str;
cin>>str;
n=str.size(); //计算n1,n2,n3的数值
n1=(n+2)/3;
k=n-2*n1;
string temp;
for(int i=0;i<k;i++) //提前准备好空格字符串
temp.push_back(' ');
for(int i=0;i<n1-1;i++){ //按照要求打印
putchar(str[i]);
cout<<temp;
putchar(str[n-1-i]);
putchar('\n');
}
cout<<str.substr(n1-1,k+2); //最后一行直接取中间部分打印即可
return 0;
} 1032
样例
样例1
输入:
11111 22222 9
67890 i 00002
00010 a 12345
00003 g -1
12345 D 67890
00002 n 00003
22222 B 23456
11111 L 00001
23456 e 67890
00001 o 00010输出:
67890样例2
输入:
00001 00002 4
00001 a 10001
10001 s -1
00002 a 10002
10002 t -1输出:
-1思路和坑点
寻找两个链表的重合点。给节点多一个标记为，访问过标记为1，否则是0。第一个链表访问时候进行标记，第二个链表进行访问的时候如果遇到了已经访问过得，便是公共部分，或者没有公共结点，输出-1.
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef struct node{
char data;
int next,tag;
node(){
tag=0;
}
}Node;
Node a[100000];
int main(void){
int head1,head2,n;
scanf("%d %d %d",&head1,&head2,&n);
getchar(); //吸收换行符
for(int i=0;i<n;i++){
int id;
scanf("%d",&id);
scanf(" %c %d",&a[id].data,&a[id].next);
getchar(); //吸收换行符
}
for(int i=head1;i!=-1;i=a[i].next) //对第一个链表进行遍历，并作标记
a[i].tag=1;
int i;
for(i=head2;i!=-1;i=a[i].next){ //遍历第二个链表，如果到了已标记处，说明是重合部分，否则到最后的-1
if(a[i].tag==1)
break;
}
if(i==-1) printf("-1");
else printf("%05d",i);
return 0;
} 1033
样例
样例1
输入:
50 1300 12 8
6.00 1250
7.00 600
7.00 150
7.10 0
7.20 200
7.50 400
7.30 1000
6.85 300输出:
749.17样例2
输入:
50 1300 12 2
7.10 0
7.00 600输出:
The maximum travel distance = 1200.00思路和坑点
贪心算法，选择加油站的时候优先选择价格更低的。具体的选择规则参加代码部分的注释。
坑点
注意起始点没有加油站，汽车无法加油的特殊情况，对此进行特判。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef struct gas{ //汽油站结构体，距离和价格
double pric,dis;
}Gas;
bool cmp(Gas a,Gas b){ //按照距离排序
return a.dis<b.dis;
}
int main(void){
double c,ds,dv;
int n;
scanf("%lf%lf%lf%d",&c,&ds,&dv,&n);
vector<Gas> v(n+1);
for(int i=0;i<n;i++){
scanf("%lf %lf",&v[i].pric,&v[i].dis);
}
v[n].pric=0; v[n].dis=ds; //将目的地作为一个价格为0的加油站
sort(v.begin(),v.end(),cmp);
if(v[0].dis!=0){ //特判起点没有加油站
printf("The maximum travel distance = 0.00");
return 0;
}
double tank=0,maxd=c*dv,sum=0; //tank表示当前油箱储量，maxd表示满油箱时候的最大行程，sum表示价格总数
int now=0; //now表示现在的站点
while(1){
int next=-1; //next表示下一站
double min=0x3fffffff; //记录下一站的最低价格
for(int i=now+1;i<=n&&v[now].dis+maxd>=v[i].dis;i++){ //在满油箱能到达的范围内寻找价格最低的
if(v[i].pric<min){
min=v[i].pric;
next=i;
if(min<v[now].pric) //如果最低价格低于当前，则直接去这个，更便宜
break;
}
}
if(next==-1){ //如果下一站不可到达，终止并输出
printf("The maximum travel distance = %.2f",v[now].dis+maxd);
break;
}
double need=(v[next].dis-v[now].dis)/dv; //need表示当前站到下一站的距离所需要的油耗
if(min<v[now].pric){ //如果下一站的价格低于当前，则只要能到下一站即可
if(tank<need){ //如果需要加
sum+=(need-tank)*v[now].pric;
tank=0; //更新到下一站时候的剩余量
}
else tank-=need; //如果不需要加油，直接去
}
else{
sum+=(c-tank)*v[now].pric; //如果下一站比较贵，在这一站直接加满
tank=c-need;
}
now=next; //更新当前站
if(next==n){ //如果下一站就是终点，则输出结果，停止循环
printf("%.2f",sum); break;
}
}
return 0;
} 1034
样例
样例1
输入:
8 59
AAA BBB 10
BBB AAA 20
AAA CCC 40
DDD EEE 5
EEE DDD 70
FFF GGG 30
GGG HHH 20
HHH FFF 10输出:
2
AAA 3
GGG 3样例2
输入:
8 70
AAA BBB 10
BBB AAA 20
AAA CCC 40
DDD EEE 5
EEE DDD 70
FFF GGG 30
GGG HHH 20
HHH FFF 10输出:
0思路和坑点
此题有两种思路，一种是使用图的dfs算法进行处理，另一种是使用并查集的方法实现，这里对并查集实现的方法作详细的介绍，dfs算法仅给出AC代码。
把每一个人当作一个独立的个体，它既是一个并查集中的元素，也是一个犯罪团伙，用一个结构体记录作为个体以及作为一个团伙的相关信息，根据通话记录进行合并。
由于id都是字母，使用map映射分配结构体数组的下标，同时按照下标成对的存放通话记录，比如i和j通过话，这该记录为i*10000+j来保存（考虑到最多有2000人，因此使用10000来作为进率。这样的记录通过/和%
根据通话记录进行并查集的合并，并更新并查集中的信息，最后对每一个进行筛选，如果符合要求则输出。
AC代码 （并查集实现）
#include<bits/stdc++.h>
using namespace std;
map<string,int> mp; //id对应的下标映射
typedef struct node{ //每一个人对应的个人结构体，同时认为每个人是一个并查集，也是一个单独的团伙，
string id; //个人的id
int w,fa,maxi,total; //通话权重，并查集的father，该团伙中最大权重的id对应的下标（合并时用于更新团伙），团伙中的总权重（用于判定）
node(){ //初始化fa=-1表示该并查集只有一个人，总权重为0
fa=-1; w=total=0;
}
}Node;
Node v[2002]; //1000条信息，所以最多2000个人
int find_fa(int x){ //查找并查集的祖先
while(v[x].fa>=0){
x=v[x].fa;
}
return x;
}
void Union(int i,int j){ //并查集的合并
int fi=find_fa(i),fj=find_fa(j);
if(fi==fj) return; //如果两个人在同一个并查集中，不需要合并
if(v[fi].fa>v[fj].fa) //把小的合并到大的中，判断大小，为了代码统一，做适当的交换
swap(fi,fj); //并查集的根指向一个负数，数的绝对值代表并查集中元素个数
v[fi].fa+=v[fj].fa; //更新大小
v[fj].fa=fi; //合并
v[fi].total+=v[fj].total; //更新总权值
int p=v[fi].maxi,q=v[fj].maxi; //更新最大权值的id下标
v[fi].maxi=v[p].w>v[q].w?p:q;
}
int main(void){
int n,k,cnt=0;
scanf("%d%d",&n,&k);
k*=2; //合并更新总权值的时候计算会重复，所以筛选限度×2
vector<int> data(n);
for(int i=0;i<n;i++){
string a,b;
int c;
cin>>a>>b>>c;
if(mp.find(a)==mp.end()) mp[a]=cnt++; //分配下标
if(mp.find(b)==mp.end()) mp[b]=cnt++;
int ia=mp[a],ib=mp[b];
data[i]=ia*10000+ib; //将两个人的通话记录保存一下用于合并并查集
v[ia].w+=c; v[ia].id=a; v[ia].maxi=ia; v[ia].total+=c; //更新权重
v[ib].w+=c; v[ib].id=b; v[ib].maxi=ib; v[ib].total+=c;
}
for(int i=0;i<n;i++){
int a=data[i]/10000,b=data[i]%10000;
Union(a,b); //根据通话记录进行合并
}
map<string,int> out; //结果存放
for(int i=0;i<cnt;i++){ //按要求筛查
if(v[i].fa<-2&&v[i].total>k){ //如果团伙人数超过两人，并且超过限度
int k=v[i].maxi;
out[v[k].id]=-v[i].fa;
}
}
printf("%d\n",out.size()); //输出结果
for(auto it=out.begin();it!=out.end();it++){
cout<<it->first<<' '<<it->second<<'\n';
}
return 0;
} AC代码 （图的dfs算法实现）
#include<bits/stdc++.h>
using namespace std;
const int MAXV=2010;
const int INF=1000000000;
int G[MAXV][MAXV]={0},weight[MAXV]={0};
int n,k,numP=0;
bool vis[MAXV]={false};
map<int,string> int_str;
map<string,int> str_int;
map<string,int> gang;
void DFS(int u,int &head,int &numM,int &total);
void DFSTrave();
int change(string str);
int main(void)
{
int w;
string s1,s2;
cin>>n>>k;
for(int i=0;i<n;i++){
cin>>s1>>s2>>w;
int id1=change(s1);
int id2=change(s2);
weight[id1]+=w;
weight[id2]+=w;
G[id1][id2]+=w;
G[id2][id1]+=w;
}
DFSTrave();
cout<<gang.size()<<'\n';
for(auto it=gang.begin();it!=gang.end();it++){
cout<<it->first<<' '<<it->second<<'\n';
}
return 0;
}
int change(string str)
{
if(str_int.find(str)!=str_int.end()) return str_int[str];
else{
str_int[str]=numP;
int_str[numP]=str;
return numP++; //先return，在numP++，因为到括号程序才算结束
}
}
void DFS(int u,int &head,int &numM,int &total)
{
numM++; //该组成员人数加一
vis[u]=true;
if(weight[u]>weight[head]) head=u;
for(int i=0;i<numP;i++){
if(G[u][i]>0){
total+=G[u][i];
G[u][i]=G[i][u]=0;
if(vis[i]==false){
DFS(i,head,numM,total);
}
}
}
}
void DFSTrave()
{
for(int i=0;i<numP;i++){
if(vis[i]==false){
int head=i,numM=0,total=0;
DFS(i,head,numM,total);
if(numM>2&&total>k){
gang[int_str[head]]=numM;
}
}
}
}
1035
样例
样例1
输入:
3
Team000002 Rlsp0dfa
Team000003 perfectpwd
Team000001 R1spOdfa输出:
2
Team000002 RLsp%dfa
Team000001 R@spodfa样例2
输入:
1
team110 abcdefg332输出:
There is 1 account and no account is modified样例3
输入:
2
team110 abcdefg222
team220 abcdefg333输出:
There are 2 accounts and no account is modified思路和坑点
一边读入，一遍把需要修改的密码进行修改，并保存到最终的输出数组中即可，注意特殊情况的输出要求，单复数有别。
AC代码
#include<bits/stdc++.h>
using namespace std;
void check(string &str,int &flag){
for(int i=0;i<str.size();i++){
switch(str[i]){
case '1':str[i]='@';flag=1;break;
case '0':str[i]='%';flag=1;break;
case 'l':str[i]='L';flag=1;break;
case 'O':str[i]='o';flag=1;break;
}
}
}
int main(void){
int n,cnt=0;
vector<string> out;
scanf("%d",&n);
for(int i=0;i<n;i++){
string name,passw;
cin>>name>>passw;
int flag=0;
check(passw,flag);
if(flag==1){
cnt++;
out.push_back(name+' '+passw);
}
}
if(cnt==0){
if(n==1)
puts("There is 1 account and no account is modified");
else
printf("There are %d accounts and no account is modified",n);
}
else{
cout<<cnt<<'\n';
for(int i=0;i<cnt;i++){
cout<<out[i]<<'\n';
}
}
return 0;
} 1036
样例
样例1
输入:
3
Joe M Math990112 89
Mike M CS991301 100
Mary F EE990830 95输出:
Mary EE990830
Joe Math990112
6样例2
输入:
1
Jean M AA980920 60输出:
Absent
Jean AA980920
NA思路和坑点
使用两个结构体分别存储男生和女生要求的最低分和最高分个人信息，然后最后按照要求输出，初始化的时候把名字初始化为空字符，这样有利于最后判别是否有该类型的个体，并按照要求输出。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef struct node{
string name,id; //学生结构体
int score;
node(){
name=""; //姓名初始化为空字符，用于最后的判定
}
}Node;
int main(void){
Node m,w;
m.score=101;w.score=-1;
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
Node temp;
string tag;
cin>>temp.name>>tag>>temp.id>>temp.score; //读入并按照性别记录
if(tag=="F"){
if(temp.score>w.score)
w=temp;
}
else{
if(temp.score<m.score)
m=temp;
}
}
if(w.name=="") puts("Absent"); //判定输出
else cout<<w.name<<' '<<w.id<<'\n';
if(m.name=="") puts("Absent");
else cout<<m.name<<' '<<m.id<<'\n';
if(w.name==""||m.name=="") puts("NA");
else cout<<(w.score-m.score);
return 0;
} 1037
样例
输入:
4
1 2 4 -1
4
7 6 -2 -3输出:
43思路和坑点
正数和正数的最大值相乘，负数和负数的最小值相乘（负负得正，负数越小，绝对值越大）。然后，把每一种情况累计求和即可。
把每组的正数和负数分别存放，0忽略不计，因为0乘任何数都是0.注意两组的长度可能不同，所以注意数组不要越界。
AC代码
#include<bits/stdc++.h>
using namespace std;
bool cmp(int a,int b){
return a>b;
}
int main(void){
vector<int> az,af,bz,bf;
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){ //正数和负数分开存储
int temp;
scanf("%d",&temp);
if(temp<0)
af.push_back(temp);
else if(temp>0)
az.push_back(temp);
}
scanf("%d",&n);
for(int i=0;i<n;i++){
int temp;
scanf("%d",&temp);
if(temp<0)
bf.push_back(temp);
else if(temp>0)
bz.push_back(temp);
}
//正数从大到小排列，负数从小到大排列
sort(az.begin(),az.end(),cmp);sort(af.begin(),af.end());
sort(bz.begin(),bz.end(),cmp);sort(bf.begin(),bf.end());
int sum=0;
for(int i=0;i<az.size()&&i<bz.size();i++){ //累加求和
sum+=az[i]*bz[i];
}
for(int i=0;i<af.size()&&i<bf.size();i++){
sum+=af[i]*bf[i];
}
cout<<sum;
return 0;
} 1038
样例
样例1
输入:
5 32 321 3214 0229 87输出:
22932132143287补充样例1
输入:
7 32 321 3214 0229 87 00 000输出:
22932132143287补充样例2
输入:
2 00 000输出:
0思路和坑点
每一个数按照string类存储，然后按照string类a+b<b+a的原则进行排序，并最终输出。
简单证明：
对于两个字符串而言，如果组成最小数，则a+b<b+a的规则进行组和，组合成的数是最小的，如果将这个组和视为一个字符串和另外一个字符串仍然按照这种方式进行组和还会得到最小的。
坑点
首先是开头不能为0，不能只对第一个字符串进行判定，可能第一个串全是0.有以下两种方法可以解决：一、把所有的结果连成一个字符串进行判定输出。二、按照二维数组的方式进行单个字符的扫描，从遇到的第一个非0字符开始输出。
注意全是0的情况下，只需输出0。（见补充样例）
AC代码
#include<bits/stdc++.h>
using namespace std;
bool cmp(string a,string b){ //排序规则
return a+b<b+a;
}
int main(void){
int n;
scanf("%d",&n);
vector<string> v(n);
for(int i=0;i<n;i++)
cin>>v[i];
sort(v.begin(),v.end(),cmp);
int tag=0; //tag为遇到第一个非0的时候的标记，遇到了改为1
for(int i=0;i<n;i++){ //二维扫描输出
for(int j=0;j<v[i].size();j++){
if(tag==0&&v[i][j]=='0')
continue;
else
tag=1;
putchar(v[i][j]);
}
}
if(tag==0) cout<<0; //如果全是0，则输出0
return 0;
} 1039
样例
输入:
11 5
4 7
BOB5 DON2 FRA8 JAY9 KAT3 LOR6 ZOE1
1 4
ANN0 BOB5 JAY9 LOR6
2 7
ANN0 BOB5 FRA8 JAY9 JOE4 KAT3 LOR6
3 1
BOB5
5 9
AMY7 ANN0 BOB5 DON2 FRA8 JAY9 KAT3 LOR6 ZOE1
ZOE1 ANN0 BOB5 JOE4 JAY9 FRA8 DON2 AMY7 KAT3 LOR6 NON9输出:
ZOE1 2 4 5
ANN0 3 1 2 5
BOB5 5 1 2 3 4 5
JOE4 1 2
JAY9 4 1 2 4 5
FRA8 3 2 4 5
DON2 2 4 5
AMY7 1 5
KAT3 3 2 4 5
LOR6 4 1 2 4 5
NON9 0思路和坑点
使用map把每位学生的选课信息映射到一个数组中，然后要找要求查询并输出，使用unordered_map和printf标准输出防止最后一个点超时。
AC代码
#include<bits/stdc++.h>
using namespace std;
unordered_map<string,vector<int> > mp; //每个学生对应一个数组
void check(string str){ //查询函数
if(mp.find(str)==mp.end()) //如果没有记录则输出0
printf("%s 0",str.c_str());
else{
sort(mp[str].begin(),mp[str].end()); //如果有记录，先排序，再输出
printf("%s %d",str.c_str(),mp[str].size());
for(int i=0;i<mp[str].size();i++){
printf(" %d",mp[str][i]);
}
}
putchar('\n');
}
int main(void){
int n,k;
scanf("%d%d",&n,&k);
for(int i=0;i<k;i++){
int id,num;
scanf("%d%d",&id,&num);
for(int j=0;j<num;j++){
string name;
cin>>name;
mp[name].push_back(id);
}
}
for(int i=0;i<n;i++){
string temp;
cin>>temp;
check(temp);
}
return 0;
} 1040
样例
输入:
Is PAT&TAP symmetric?输出:
11思路和坑点
使用动态规划的思路解决这个问题，具体动态规划的算法思想参见博客动态规划中关于最长回文字串的算法和讲解。
AC代码
#include<bits/stdc++.h>
using namespace std;
int dp[1002][1002]={0}; //dp数组，dp[i][j]表示从下标i-j的串是不是回文串，是为1，否为0；
int main(void){
string s;
getline(cin,s);
int len=s.size(),ans=1;
for(int i=0;i<len;i++){ //初始化dp数组
dp[i][i]=1;
if(i<len-1){
if(s[i]==s[i+1]){
dp[i][i+1]=1;ans=2;
}
}
}
for(int L=3;L<=len;L++){ //每次取不同的长度，从0开始更新dp数组
for(int i=0;i+L-1<len;i++){
int j=i+L-1;
if(s[i]==s[j]&&dp[i+1][j-1]==1){
dp[i][j]=1;
ans=L;
}
}
}
cout<<ans;
return 0;
} 1041
样例
样例1
输入:
7 5 31 5 88 67 88 17输出:
31样例2
输入:
5 888 666 666 888 888输出:
None思路和坑点
使用两个映射记录数据，一个用于记录每个数字出现的个数，另一个用于记录备选答案以及其出现的次序，最后从备选答案中选出次序最小的也就是第一个出现的为最终答案。如果没有答案，则按照要求输出None
AC代码
#include<bits/stdc++.h>
using namespace std;
int main(){
#ifdef ONLINE_JUDGE
#else
freopen("1.txt", "r", stdin);
#endif
int n;
unordered_map<int,int> mp,mpout; //mp用于计数，mpout用于备选输出答案，记录出现的次序
scanf("%d",&n);
for(int i=0;i<n;i++){
int num;
scanf("%d",&num);
mp[num]++;
if(mp[num]==1) //如果只有一个则加入备选，，并记录次序
mpout[num]=i;
else
mpout.erase(num); //如果不只有一个，则从被选中删除
}
int win,min=n; //从备选的输出项中选出次序最小的，也就是第一次出现的答案
for(auto it=mpout.begin();it!=mpout.end();it++){
if(it->second<min){
win=it->first;
min=it->second;
}
}
if(mpout.size()==0) puts("None"); //如果最终没有答案，输出None
else cout<<win;
return 0;
}1042
样例
输入:
2
36 52 37 38 3 39 40 53 54 41 11 12 13 42 43 44 2 4 23 24 25 26 27 6 7 8 48 49 50 51 9 10 14 15 16 5 17 18 19 1 20 21 22 28 29 30 31 32 33 34 35 45 46 47输出:
S7 C11 C10 C12 S1 H7 H8 H9 D8 D9 S11 S12 S13 D10 D11 D12 S3 S4 S6 S10 H1 H2 C13 D2 D3 D4 H6 H3 D13 J1 J2 C1 C2 C3 C4 D1 S5 H5 H11 H12 C6 C7 C8 C9 S2 S8 S9 H10 D5 D6 D7 H4 H13 C5思路和坑点
洗牌的过程，给每张牌定义结构体，成员有排面和顺序，每次洗牌按照规定的顺序，遍历一遍数组，修改顺序。然后对结构体数组进行重排，便可以得到最终序列。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef struct node{ //牌的结构体
string id;
int order;
}Node;
bool cmp(Node a,Node b){ //排序函数
return a.order<b.order;
}
string cards[55]={"","S1","S2","S3","S4","S5","S6","S7","S8","S9","S10","S11","S12","S13",
"H1","H2","H3","H4","H5","H6","H7","H8","H9","H10","H11","H12","H13",
"C1","C2","C3","C4","C5","C6","C7","C8","C9","C10","C11","C12","C13",
"D1","D2","D3","D4","D5","D6","D7","D8","D9","D10","D11","D12","D13",
"J1","J2"};
int shuff[55]={0};
int main(void){
int k;
scanf("%d",&k);
vector<Node> v(55);
for(int i=1;i<=54;i++){ //一遍读入顺序，一遍初始化牌面
v[i].id=cards[i];
scanf("%d",&shuff[i]);
}
for(int i=0;i<k;i++){ //进行k次重新定数顺序并排序
for(int j=1;j<=54;j++){
v[j].order=shuff[j];
}
sort(v.begin()+1,v.end(),cmp);
}
for(int i=1;i<=54;i++){ //输出结果
if(i!=1) putchar(' ');
cout<<v[i].id;
}
return 0;
} 1043
样例
样例1
输入:
7
8 6 5 7 10 8 11输出:
YES
5 7 6 8 11 10 8样例2
输入:
7
8 10 11 8 6 7 5输出:
YES
11 8 10 7 5 6 8样例3
输入:
7
8 6 8 5 10 9 11输出:
NO思路和坑点
由于给的是前序序列，对于BST直接插入建树，同时建立对应的mirror树，然后保存两棵树其前序遍历的结果，如果和其中有一个与已给的序列相同，则认为YES，并后序输出对应的树，否则不是，输出NO。
使用全局变量tag控制插入的方式和遍历时候如何存放结果，tag=0，为一般树，tag=1为mirror树的操作。
AC代码
#include<bits/stdc++.h>
using namespace std;
int cnt=0; //后序输出时候空格控制的计数器
typedef struct node{
int data;
struct node *left,*right;
}Node;
vector<int> pre,mpre; //保存建立的一般树和镜像树的前序序列
int tag=0; //tag全局变量用于控制对一般树或者镜像树的操作，tag=0，对应一般树，tag=1对应镜像树
void preorder(Node *root){ //前序遍历
if(root==NULL) return;
if(tag==0)
pre.push_back(root->data);
else
mpre.push_back(root->data);
preorder(root->left);
preorder(root->right);
}
void postorder(Node *root){ //中序遍历
if(root==NULL) return;
postorder(root->left);
postorder(root->right);
if(cnt) putchar(' ');
printf("%d",root->data);
cnt++;
}
void Insert(Node *&root,int x){ //插入建树
if(root==NULL){
root=new Node;
root->data=x;
root->left=root->right=NULL;
return;
}
if(x<root->data){
if(tag==0) Insert(root->left,x);
else Insert(root->right,x);
}
else{
if(tag==0) Insert(root->right,x);
else Insert(root->left,x);
}
}
int main(void){
Node *root,*mroot;
root=mroot=NULL;
int n;
scanf("%d",&n);
vector<int> a(n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
tag=0;Insert(root,a[i]);
tag=1;Insert(mroot,a[i]);
}
tag=0;preorder(root); //获取一般树的前序序列
tag=1;preorder(mroot); //获取镜像树的前序序列
if(pre==a){ //若有其中一个符合则按照求输出对应的后序序列
puts("YES");
tag=0;
postorder(root);
}
else if(mpre==a){
puts("YES");
tag=1;
postorder(mroot);
}
else //如果都不是输出NO
puts("NO");
return 0;
} 1044
样例
样例1
输入:
16 15
3 2 1 5 4 6 8 7 16 10 15 11 9 12 14 13输出:
1-5
4-6
7-8
11-11样例2
输入:
5 13
2 4 5 7 9输出:
2-4
4-5思路和坑点
使用数组sum记录数据sum[0]初始化为0，sum[u]表示样例数据中从第1个到第u个的和，那么记需要支付的的数值为pay，使用两点法指针i和j，如果存在sum[i]-sum[j]==pay，则输出i+1~j；如果小于，则j++；如果大于，则i++，同时还要考虑如果都大于的情况需要，支付的时候使用大于pay但是最接近pay的支付数值来达到最小损失，因此每次记录，大于pay的所有备选值中的最小数，作为新的支付方案，如果有都大于pay（用cnt记录是否有刚好等于pay的记录），则对新的支付方案进行查询。
AC代码
#include<bits/stdc++.h>
using namespace std;
int n,pay,cnt=0; //pay为需要支付的数值，cnt用于等于pay的计数
vector<int> sum; //保存数据，sum[0]初始化为0
int find(int p){
int i=0,j=1,first=1000000000;
for(;i<=j&&j<sum.size();){ //两点法 i，j指针以前一后
int temp=sum[j]-sum[i]; //计算i-j区间内的数值
if(temp<p) //如果小于pay，j++
j++;
else if(temp==p){ //如果等于pay，输出并计数
printf("%d-%d\n",i+1,j);j++;cnt++;
}
else{ //如果大于pay，i++，同时记录可能的新方案
first=min(first,temp);
i++;
}
}
return first;
}
int main(void){
scanf("%d%d",&n,&pay);
sum.resize(n+1);sum[0]=0;
for(int i=1;i<=n;i++){ //直接读入并计算和记录sum
int temp;
scanf("%d",&temp);
sum[i]=sum[i-1]+temp;
}
int newpay=find(pay); //输出，并获得可能的新支付方案
if(cnt==0) //如果pay的支付不存在，按照新的支付方案进行查询，此处的左值newpay只是为了接应新方案的返回值
newpay=find(newpay);
return 0;
} 1045
样例
输入:
6
5 2 3 1 5 6
12 2 2 4 1 5 5 6 3 1 1 5 6输出:
7思路和坑点
将喜欢的序列映射成一个递增的序列，然后将给出的序列中使用动态规划的方式找到最长不下降子序列即可（动态规划的求解思路参见动态规划的总结）
AC代码
#include<bits/stdc++.h>
using namespace std;
int main(void){
int n;
scanf("%d",&n); //过滤第一个数字，其实第一个数字没有用处
scanf("%d",&n); //读入喜欢的序列
unordered_map<int,int> mp; //按照升序映射
for(int i=1;i<=n;i++){
int temp;
scanf("%d",&temp);
mp[temp]=i;
}
scanf("%d",&n); //读取提供的序列
vector<int> v;
for(int i=0;i<n;i++){ //如果没有喜欢的直接略过，不保存
int temp;
scanf("%d",&temp);
if(mp.find(temp)!=mp.end()) //按照映射的方式加入序列
v.push_back(mp[temp]);
}
if(v.size()==0){ //如果没有喜欢的颜色，特判输出0
cout<<0;
return 0;
}
int ans=1; //如果有喜欢的颜色，则至少为1
vector<int> dp(v.size(),1); //动态规划计算最长不下降子序列（可连续，也可以不连续）
for(int i=1;i<v.size();i++){
for(int j=0;j<i;j++){
if(v[j]<=v[i]&&dp[j]+1>dp[i]){
dp[i]=dp[j]+1;
}
}
ans=max(ans,dp[i]); //保存最长的序列
}
cout<<ans;
return 0;
} 1046
样例
输入:
5 1 2 4 14 9
3
1 3
2 5
4 1输出:
3
10
7思路和坑点
算出整个环路的路径长度，然后计算两个点i~j之间按照顺序的路径长度，然后总长度减去顺序的长度，便是另一半方向的长度，取其最小值。
坑点
顺序按照从小到大的结点顺序，如果输入时从大到小，交换一下即可。
AC代码
#include<bits/stdc++.h>
using namespace std;
int main(void){
int n;
scanf("%d",&n);
vector<int> v(n+1); v[0]=0; //v数组用于从放i~i+1的路径长度，其中v[0]用于存放总的路径长度
for(int i=1;i<=n;i++){
scanf("%d",&v[i]);
v[0]+=v[i];
}
scanf("%d",&n);
for(int i=0;i<n;i++){
int a,b,dis=0;
scanf("%d%d",&a,&b); //没队儿进行判定
if(a>b) swap(a,b); //从小到大的结点顺序
for(int j=a;j<b;j++){ //计算从小到大的路径长度
dis+=v[j];
}
printf("%d\n",min(dis,v[0]-dis)); //数组最小的值
}
return 0;
} 1047
样例
输入:
10 5
ZOE1 2 4 5
ANN0 3 5 2 1
BOB5 5 3 4 2 1 5
JOE4 1 2
JAY9 4 1 2 5 4
FRA8 3 4 2 5
DON2 2 4 5
AMY7 1 5
KAT3 3 5 4 2
LOR6 4 2 4 1 5输出:
1 4
ANN0
BOB5
JAY9
LOR6
2 7
ANN0
BOB5
FRA8
JAY9
JOE4
KAT3
LOR6
3 1
BOB5
4 7
BOB5
DON2
FRA8
JAY9
KAT3
LOR6
ZOE1
5 9
AMY7
ANN0
BOB5
DON2
FRA8
JAY9
KAT3
LOR6
ZOE1思路和坑点
对每个课程建立选课的学生表，然后排序输出即可。
AC代码
#include<bits/stdc++.h>
using namespace std;
int main(void){
int n,k;
scanf("%d%d",&n,&k);
vector<string> v[k+1];
for(int i=0;i<n;i++){
string name;
int m;
cin>>name; scanf("%d",&m); //读入数据
for(int j=0;j<m;j++){
int id;
scanf("%d",&id);
v[id].push_back(name); //插入到相应的课程名单中
}
}
for(int i=1;i<=k;i++){
int size=v[i].size();
printf("%d %d\n",i,size);
if(size) sort(v[i].begin(),v[i].end()); //如果不空排序输出
for(int j=0;j<size;j++){
printf("%s\n",v[i][j].c_str());
}
}
return 0;
} 1048
样例
样例1
输入:
8 15
1 2 8 7 2 4 11 15输出:
4 11样例2
输入:
7 14
1 8 7 2 4 11 15输出:
No Solution思路和坑点
使用两点法，把币值从小到大排序，然后头尾各一个指针向中间逼近，如果有答案则输出，否则按照要求输出无解。
AC代码
#include<bits/stdc++.h>
using namespace std;
int main(void){
int n,m;
scanf("%d%d",&n,&m);
vector<int> v(n);
for(int i=0;i<n;i++)
scanf("%d",&v[i]);
sort(v.begin(),v.end());
int i=0,j=n-1,flag=0; //两点法，i，j为两端的指针，flag为答案的标记
while(i<j){
int sum=v[i]+v[j];
if(sum<m) i++;
else if(sum==m){
printf("%d %d",v[i],v[j]);
flag=1; break;
}
else j--;
}
if(flag==0) puts("No Solution");
return 0;
} 1049
样例
输入:
12输出:
5思路和坑点
寻找数字的规律，统计从1-n的数字中所有1的个数，不妨这样思考：对于每一位而言，该位为1的数字有多少个，然后把每一位取到的个数相加，即最终的答案。
对于数的每一位而言：（以1014为例）
如果该位等于0（比如百位），则其左侧必有数字，记为left（1），说明该位可以取到1，比如0124，但其左侧的数字left只能取到[0，left-1]共left种情况，考虑其右侧的数字可以取遍[0，该位权值-1]。因此，该位取1的数字有left*该位权值个。
如果该位等于1(比如十位)，则其左边的数字记为left（10），右边数字记为right（4），左边数字可以先取[0，left-1]，类似于等于0时的情况，但是由于该位等于1，当左边数字取到left时，右侧的数字只能取[0，right]。因此，该位取1的数字有left*该位权值+right+1个。
如果该位大于1，当该位左侧数字可以取[0，left],同时右侧数字可以取[0，该位权值-1]。因此，该位取1的数字有（left+1）*该位的权值个。
补充
为了能清楚的理解该原理，可以按照从低到高依次竖排打印出每一位取1的数字情况以便参考。AC代码后面补充了打印1014的个位，十位，百位，千位取1时候的数字情况的测试代码，可以运行一下，以作观察和理解。
AC代码
#include<bits/stdc++.h>
using namespace std;
int main(){
#ifdef ONLINE_JUDGE
#else
freopen("1.txt", "r", stdin);
#endif
int n;
cin>>n;
int ans=0;
int a=1; //a表示当前位的权值，初始化为1
while(n/a){ //依次循环取每一位
int left=n/(a*10); //取左边的数字
int right=n%a; //取右边的数字
int now=n/a%10; //去当前位
if(now==0) //当前位等于0时
ans+=left*a;
else if(now==1) //当前位等于1时
ans+=left*a+right+1;
else //当前位大于1时
ans+=(left+1)*a;
a*=10; //权值扩大，为下一位判定做准备
}
cout<<ans;
return 0;
}用于理解的测试代码
#include<iostream>
#include<vector>
using namespace std;
int main(void){
int i=1;
vector<int> v1,v2,v3,v4;
for(int i=1;i<=1014;i++){
if(i%10==1) v1.push_back(i);
if(i/10%10==1) v2.push_back(i);
if(i/100%10==1) v3.push_back(i);
if(i/1000==1) v4.push_back(i);
}
int id1,id2,id3,id4;
id1=id2=id3=id4=0;
while(1){
if(id1<v1.size()) printf("%04d ",v1[id1++]);
else printf(" ");
if(id2<v2.size()) printf("%04d ",v2[id2++]);
else printf(" ");
if(id3<v3.size()) printf("%04d ",v3[id3++]);
else printf(" ");
if(id4<v4.size()) printf("%04d ",v4[id4++]);
else printf(" ");
putchar('\n');
if(id1==v1.size()&&id2==v2.size()&&id3==v3.size()&&id4==v4.size())
break;
}
}1050
样例
输入:
They are students.
aeiou输出:
Thy r stdnts.思路和坑点
将第二个字符串分成字符标记出来，然后遍历输出第一个字符串，只要遇到第二个字符串中的字母，不输出即可。
AC代码
#include<bits/stdc++.h>
using namespace std;
int main(void){
unordered_map<char,bool> mp;
string s;
getline(cin,s);
char ch;
while((ch=getchar())!='\n'){
mp[ch]=true;
}
for(int i=0;i<s.size();i++){
if(mp[s[i]])
continue;
putchar(s[i]);
}
return 0;
} 1051
样例
输入:
5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2输出:
YES
NO
NO
YES
NO思路和坑点
采用反向测试的方法，所给序列如果能通过入栈和出栈操作得到就可以以相同的方式逆向获得1-n的进栈序列。从序列的末尾逆序开始，如果栈空或者栈中的数小于序列中的数，就把序列中的数入栈，否则栈中出栈。由于是逆过程，所以读序列进行入栈相当于得到序列时的出栈操作，出栈相当于得到序列时的入栈操作。
接下来讨论何时为不能得到：
①如果中间过程中栈溢出（即满的时候还要进栈）
②如果出栈的序列不是从n-1的
AC代码
#include<bits/stdc++.h>
using namespace std;
int main(){
#ifdef ONLINE_JUDGE
#else
freopen("1.txt", "r", stdin);
#endif
int m,n,k,cnt=0;
cin>>m>>n>>k;
int a[n];
for(int i=0;i<k;i++){
stack<int> s;
cnt=0; //出栈得到1-n序列的逆序时候的计数器
int index=n-1; //序列判定的下标遍历指针
for(int j=0;j<n;j++){ //读入一组序列
scanf("%d",&a[j]);
}
while(index>=0){ //逆序遍历给定的序列
if(s.empty()||s.top()<a[index]){
if(s.size()==m) break; //栈溢出，不可得到
s.push(a[index]);
index--;
}
else{
if(s.top()!=n-cnt) break; //不是按照1-n的顺序入栈，不可得到
s.pop();
cnt++;
}
}
if(index<0) puts("YES"); //如果可以正常的反向进行进出栈模拟，认定可以
else puts("NO"); //如果中途判定不可逆，并且终止循环，认定不可得
}
return 0;
}1052
样例
输入:
5 00001
11111 100 -1
00001 0 22222
33333 100000 11111
12345 -1 33333
22222 1000 12345输出:
5 12345
12345 -1 00001
00001 0 11111
11111 100 22222
22222 1000 33333
33333 100000 -1思路和坑点
将整个链表单独拉出来，放在一个数组中，链表的结点结构体中要记录自己的id，便于最后输出。这里忽略对next指针的处理，因为对一个结点来说，下一个的id就是他的next，直接引用下一个结点的id就好了。
坑点
特判结点个数为0的情况，提前判定。
以上的next处理方法，最后尾指针需要单独处理。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef struct node{
int id,data,next;
}Node;
Node all[100005];
bool cmp(Node a,Node b){
return a.data<b.data;
}
int main(void){
int n,head;
scanf("%d%d",&n,&head);
vector<Node> v;
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);
}
for(int i=head;i!=-1;i=all[i].next) //将链表重新整合进一个数组中
v.push_back(all[i]);
sort(v.begin(),v.end(),cmp); //按要求排序
if(v.size()==0){ //特判如果0个有效结点
printf("0 -1");
return 0;
}
printf("%d %05d\n",v.size(),v[0].id); //输出结果
int i=0;
for(i=0;i<v.size()-1;i++){ //下一个next指针，即后边一个的id
printf("%05d %d %05d\n",v[i].id,v[i].data,v[i+1].id);
}
printf("%05d %d -1",v[i].id,v[i].data);
return 0;
} 1053
样例
输入:
20 9 24
10 2 4 3 5 10 2 18 9 7 2 2 1 3 12 1 8 6 2 2
00 4 01 02 03 04
02 1 05
04 2 06 07
03 3 11 12 13
06 1 09
07 2 08 10
16 1 15
13 3 14 16 17
17 2 18 19输出:
10 5 2 7
10 4 10
10 3 3 6 2
10 3 3 6 2思路和坑点
使用树的dfs和回说剪枝来实现统计要求的路径。其中为了输出路径时按照规则从大到小，对每个结点的孩子都按照权重从大到小排列。也可以把每个符合要求的路径保存，并按照要求排序，最后统一输出。
AC代码
#include<bits/stdc++.h>
using namespace std;
struct node{ //使用结构体存放结点
int weight; //权值
vector<int> child; //孩子结点使用数组表示
}Node[105]; //存放所有的结点，最多100个结点
int n,m,s;
vector<int> path; //存放路径
bool cmp(int a,int b){ //将孩子每一层按照权值从大到小排序，这样dfs的结果才能满足路径权值从大到小
return Node[a].weight>Node[b].weight;
} //（也可以将所有的路径保存后排序输出 ）
void DFS(int index,int sum);
int main(void)
{
scanf("%d%d%d",&n,&m,&s);
for(int i=0;i<n;i++)
scanf("%d",&Node[i].weight);
int id,k,child;
for(int i=0;i<m;i++){
scanf("%d%d",&id,&k);
for(int j=0;j<k;j++){
scanf("%d",&child);
Node[id].child.push_back(child);
}
sort(Node[id].child.begin(),Node[id].child.end(),cmp); //孩子读取完即排序
}
path.push_back(0);
DFS(0,Node[0].weight);
return 0;
}
void DFS(int index,int sum)
{
if(sum>s) return; //如果路径上的和大于s，不满足规则，返回
else if(sum==s){
if(Node[index].child.size()!=0) return; //说明该结点不是叶子结点，不满足题目要求，直接返回，否则输出路径
else{
for(int i=0;i<path.size();i++){
if(i) putchar(' ');
printf("%d",Node[path[i]].weight);
}
putchar('\n');
return;
}
}
else{ //否则对其所有孩子递归dfs
for(int i=0;i<Node[index].child.size();i++){
int child=Node[index].child[i];
path.push_back(child); //当前结点算入路径
DFS(child,sum+Node[child].weight); //当前孩子的递归dfs结束后，要从路径中删除，以继续进行下一个孩子的dfs
path.pop_back();
}
}
}1054
样例
输入:
5 3
0 0 255 16777215 24
24 24 0 0 24
24 0 24 24 24输出:
24思路和坑点
使用map记录每种颜色出现的次数，并记录出现次数最多的为主要颜色。
AC代码
#include<bits/stdc++.h>
using namespace std;
int main(void){
int m,n;
scanf("%d%d",&m,&n);
unordered_map<int,int> mp;
int max=-1,color;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
int temp;
scanf("%d",&temp);
mp[temp]++;
if(mp[temp]>max){
color=temp;
max=mp[temp];
}
}
}
cout<<color;
return 0;
} 1055
样例
输入:
12 4
Zoe_Bill 35 2333
Bob_Volk 24 5888
Anny_Cin 95 999999
Williams 30 -22
Cindy 76 76000
Alice 18 88888
Joe_Mike 32 3222
Michael 5 300000
Rosemary 40 5888
Dobby 24 5888
Billy 24 5888
Nobody 5 0
4 15 45
4 30 35
4 5 95
1 45 50输出:
Case #1:
Alice 18 88888
Billy 24 5888
Bob_Volk 24 5888
Dobby 24 5888
Case #2:
Joe_Mike 32 3222
Zoe_Bill 35 2333
Williams 30 -22
Case #3:
Anny_Cin 95 999999
Michael 5 300000
Alice 18 88888
Cindy 76 76000
Case #4:
None思路和坑点
排序，然后按照要求查找并输出，为了不超时，尽可能的少使用stl，并且快速排序使用排下标的方式实现。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef struct node{
string id;
int age,w;
}Node;
Node v[100005];
int sid[100005];
bool cmp(int i,int j){
if(v[i].w!=v[j].w) return v[i].w>v[j].w;
else if(v[i].age!=v[j].age) return v[i].age<v[j].age;
else return v[i].id<v[j].id;
}
int main(void){
int n,k;
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++){
sid[i]=i;
cin>>v[i].id;
scanf("%d%d",&v[i].age,&v[i].w);
}
sort(sid,sid+n,cmp);
for(int i=1;i<=k;i++){
printf("Case #%d:\n",i);
int num,st,ed,cnt=0;
scanf("%d%d%d",&num,&st,&ed);
for(int j=0;j<n;j++){
int index=sid[j];
if(v[index].age>=st&&v[index].age<=ed){
cnt++;
printf("%s %d %d\n",v[index].id.c_str(),v[index].age,v[index].w);
}
if(cnt==num) break;
}
if(cnt==0) puts("None");
}
return 0;
} 1056
样例
输入:
11 3
25 18 0 46 37 3 19 22 57 56 10
6 0 8 7 10 5 9 1 4 2 3输出:
5 5 5 2 5 5 5 3 1 3 5思路和坑点
首先要读懂选拔和排序规则，根据样例，每NG个分为一组，每组选出最重的晋级。剩下的排名相同。此处，加入本轮一共分成n组，则每组都会产生一名晋级的名额，那么剩下的全部排名为n+1。
对于每轮排名，使用队列进行。每次从队列中取出一组，最后一组可能不够NG个，这个时候需要用本轮参赛全部人数作为判定上界。每组的中选出晋级的编号，剩下的更新排名。直到产生冠军，即队列中只剩一个。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef struct node{
int w,rank;
}Node;
int main(void){
int n,m;
scanf("%d%d",&n,&m);
vector<Node> v(n);
queue<int> q;
for(int i=0;i<n;i++) //读取重量
scanf("%d",&v[i].w);
for(int i=0;i<n;i++){ //读入第一轮的序列，直接进队
int temp;
scanf("%d",&temp);
q.push(temp);
}
while(1){ //比赛进行
if(q.size()==1){ //直到产生冠军时停止，冠军排名为1
v[q.front()].rank=1; break;
}
int num=q.size(); //记录本轮参赛的选手个数
int rank=num%m?num/m+2:num/m+1; //计算本次一共有多少组，并未晋级选手的排名为rank
int cnt=0; //选手总数的计数器
for(int i=0;i<rank-1;i++){ //每次取出一组，共rank-1组
int maxid=q.front(); //maxid用于记录最重的编号
int maxw=v[maxid].w; //maxw记录最重的重量
for(int j=0;j<m&&cnt<num;j++){ //每次从中取出一组，共m个，最后一组由cnt计数器作为边界
int now=q.front(); //每次取出一个
cnt++; q.pop(); //计数并pop出队列
if(v[now].w>maxw){ //如果更大，则更新最大的记录
v[maxid].rank=rank; //将之前的记录淘汰，即确定排名
maxid=now;maxw=v[now].w;
}
else //否则直接淘汰，确定排名
v[now].rank=rank;
}
q.push(maxid); //将每组的获胜者进队，参与下一轮的比赛
}
}
for(int i=0;i<n;i++){ //输出结果
if(i) putchar(' ');
printf("%d",v[i].rank);
}
return 0;
} 1057
样例
输入:
17
Pop
PeekMedian
Push 3
PeekMedian
Push 2
PeekMedian
Push 1
PeekMedian
Pop
Pop
Push 5
Push 4
PeekMedian
Pop
Pop
Pop
Pop输出:
Invalid
Invalid
3
2
2
1
2
4
4
5
3
Invalid思路和坑点
分块思想（分桶法），太难了，实在是太难了，没时间具体写了，有空了再写！这里仅给出代码，注意分块的大小，不能太大，也不能太小。如果太小会有段错误，如果太大还会超时。需要详解的请参见《算法笔记》的讲解（书上有分桶法和树状数组法）
AC代码
#include<bits/stdc++.h>
using namespace std;
const int MAXS=100010;
const int sqrN=330;
stack<int> st;
int block[sqrN]={0};
unordered_map<int,int> mp;
void Pop();
void Push(int x);
void PeekMedian(int mid);
int main(void)
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
string str;
cin>>str;
if(str=="Pop"){
if(st.empty()==true)
puts("Invalid");
else
Pop();
}
else if(str=="Push"){
int num;
scanf("%d",&num);
Push(num);
}
else{
if(st.empty()==true)
puts("Invalid");
else{
int mid=st.size();
mid=(mid%2==0)?mid/2:(mid+1)/2;
PeekMedian(mid);
}
}
}
return 0;
}
void Pop()
{
int top=st.top();
st.pop();
block[top/sqrN]--;
mp[top]--;
printf("%d\n",top);
}
void Push(int x)
{
st.push(x);
block[x/sqrN]++;
mp[x]++;
}
void PeekMedian(int mid)
{
int sum=0,index=0;
while(sum+block[index]<mid)
sum+=block[index++];
int num=index*sqrN;
while(sum+mp[num]<mid)
sum+=mp[num++];
printf("%d\n",num);
}AC代码（对顶堆解法）
#include<bits/stdc++.h>
using namespace std;
int main(){
//使用对顶堆的思路，将数据一分为二,使用multiset来自动实现排序
//由于中间值是向下取整，所以前半部分要么和后半部分元素个数相同，要么前半部分比后半部分多一个元素
//只需要每次操作后维护好两部分的元素个数关系即可
multiset<int,less<int> > big; //小根堆，用于存放数值比较大的后半部分
multiset<int,greater<int> > small; //大根堆，用于存放数值比较小的前半部分，由于是大根堆的结构，所以堆顶便是中间值
stack<int> s; //用栈模拟操作
int n,x;
scanf("%d",&n); //读入数据
for(int i=0;i<n;i++){
char str[11]; scanf("%s",str); //读入请求的命令字符串
if(str[1]=='u'){ //如果是push，则在入栈
scanf("%d",&x);
s.push(x); //如果此时前半部分是空，或者x比中间值小则放在前半部分
(small.empty()||x<=*small.begin())? small.insert(x):big.insert(x);
} //由于中间值是向下取整，所以前半部分要么和后半部分元素个数相同，要么前半部分比后半部分多一个元素，故空时优先插入前半部分
else{
if(s.empty()){ //如果是栈空，则pop和查询中间值的操作都无效
puts("Invalid"); continue;
}
if(str[1]=='o'){ //pop操作有有效时出栈
x=s.top();s.pop(); //判断x在序列中的位置，然后从相应的堆中删除
(x<=*small.begin())?small.erase(small.find(x)):big.erase(big.find(x));
printf("%d\n",x);
}
else
printf("%d\n",*small.begin()); //输出中间值
}
while(small.size()<big.size()){ //调整两个堆的元素个数关系，若元素为偶数个调整到两部分相同
small.insert(*big.begin());big.erase(big.begin());
}
while(big.size()+1<small.size()){ //或者元素为奇数个，调整到前半部分的元素个数比后半部分多一
big.insert(*small.begin());small.erase(small.begin());
}
}
return 0;
}1058
样例
输入:
3.2.1 10.16.27输出:
14.1.28思路和坑点
直接使用类似于大数加法的计算方法，每一位按照该位的进制进行计算，然后计算进位给更高位计算作准备。
AC代码
#include<bits/stdc++.h>
using namespace std;
int main(void){
int a1,b1,c1,a2,b2,c2,tag=0; //tag为进位
scanf("%d.%d.%d %d.%d.%d",&a1,&b1,&c1,&a2,&b2,&c2);
c1=c1+c2+tag; tag=c1/29; c1%=29;
b1=b1+b2+tag; tag=b1/17; b1%=17;
a1=a1+a2+tag;
printf("%d.%d.%d",a1,b1,c1);
return 0;
} 1059
样例
输入:
97532468输出:
97532468=2^2*11*17*101*1291思路和坑点
首先需要获得素数表，使用筛选法获取素数表，考虑题目给的数值范围，素数表的大小10000即可。然后对每一个素数用除法进行因式分解，直到无法整除为止，由此获得因子的个数。每获得一个因子的信息，遍输出一次。为了控制号，使用标记进行控制，出了第一个不输出号以外，其他都需要输出。
坑点
要注意第三个测试点的特判 1=1
AC代码
#include<bits/stdc++.h>
using namespace std;
#define MAXN 10000
bool Prime[MAXN];
void getprime(){ // 筛选法获得素数表
fill(Prime,Prime+MAXN,true);
Prime[0]=Prime[1]=false;
for(int i=2;i<MAXN;i++){
if(Prime[i]){
for(int j=i+i;j<MAXN;j+=i)
Prime[j]=false;
}
}
}
int main(void){
getprime();
int n,tag=0; //tag为控制*号的标记
cin>>n;
if(n==1) {printf("1=1"); return 0;} //特判1的情况 （坑点所在，第三个测试点）
printf("%d=",n); //打印算式的头部
for(int i=2;;i++){ //因数从2开始
int cnt=0; //用于因数的计数
if(Prime[i]){ //如果该因数是素数
while(n%i==0){ //每次除以因数（直到不能整除），进行分解计数
n/=i; cnt++;
}
}
if(cnt){ //如果有因数
if(tag) putchar('*'); //如果是第一次打印，不需要*
tag=1; //修改标记
if(cnt==1) printf("%d",i); //如果因数个数为1，不打印个数
else printf("%d^%d",i,cnt);
}
if(n==1) break; //当n分解完成时结束循环
}
return 0;
} 1060
样例
样例1
输入:
3 12300 12358.9输出:
YES 0.123*10^5样例2
输入:
3 120 128输出:
NO 0.120*10^3 0.128*10^3补充样例1（关于0的情况）
输入:
3 0 0.000
输出:
YES 0.000*10^0补充样例2（小于1的小数，有前导0）
输入:
5 0.1 00.100输出:
YES 0.10000*10^0补充样例3（大于1的小数，有前导0）
输入:
3 010.25 0010.23输出:
YES 0.102*10^2补充样例4（小于1的小数，小数点之后有0）
输入:
4 0.0015 0.00150034 输出:
YES 0.1500*10^-2思路和坑点
对于科学计数法的求解，首先是解决0的问题，然后是有效位及其指数的确定，这里通过以下规则确定有效位，然后同时确定指数，最后比较并输出。
首先是要考虑数据过滤。包括特判0和前导0两个方面。
一、首先是特判0，凡是只有0或者.的都统一认为是0，如补充样例1所示。
二、如果不是0，则需要删除前导0，只留下有效位，此时分两种情况，一种是小于1的数000.0015和大于1的数12345.67，保留之后分别为.0015和12345.67
其次是要考虑指数的计算和有效位数补全的问题。
有效位数补全:对字符串的处理只留下第一个有效位之后的部分，然后如果少于有效位，补0。
指数的计算：有一下情况，正指数、如12345，指数为字符长度；12345.67指数为小数点‘.'在字符串中的下标。负指数、如0.001234，指数为小数点到有效位之间0的个数，比如.到1之间有两个零，指数为-2
AC代码
#include<bits/stdc++.h>
using namespace std;
int n;
string trans(string str,int &e){
string ret=""; //ret为返回值，表示有效字段，e表示指数
int tag=0; //是否为0的标记
for(int i=0;i<str.size();i++){ //判断是不是0（凡是没有非零数字的都是0，比如0 0.00）
if(str[i]!='0'&&str[i]!='.'){
tag=1;break; //如果不是0，修改标记tag为1
}
}
if(tag==0){ //如果是0，有效字段为n个0，并且指数为0
for(int i=0;i<n;i++)
ret+='0';
e=0;
}
else{
while(1){ //去除前导0
if(str[0]!='0')
break;
else str.erase(str.begin());
}
int pos=str.find('.'); //查找点的下标
if(pos==string::npos) //如果没有点 ，则是整数，e为字符串长度
e=str.size();
else if(pos==0){ //如果第一个是点，则这个数小于1，e<=0;
e=0; str.erase(str.begin());
while(str[0]=='0'){ //如果小数点和第一个非零数字之间还有0，则e--，并清除这些0
str.erase(str.begin());
e--;
}
}
else{
e=pos; //如果该数大于1，则指数等于点的下标 比如1234.56
str.erase(pos,1); //删除点
}
for(int i=0;i<n;i++){ //获取n位有效数字
if(i<str.size())
ret+=str[i];
else //如果字符串不够n位，补齐为0
ret+='0';
}
}
return ret;
}
int main(void){
string a,b;
int ea,eb;
ea=eb=0;
cin>>n>>a>>b;
a=trans(a,ea); b=trans(b,eb);
if(a==b)
printf("YES 0.%s*10^%d",a.c_str(),ea);
else
printf("NO 0.%s*10^%d 0.%s*10^%d",a.c_str(),ea,b.c_str(),eb);
return 0;
} 
Comments | NOTHING