目录
1100 Mars Numbers （20 分）（字符串模拟）
1101 Quick Sort （25 分）（数组模拟+思维）
1102 Invert a Binary Tree （25 分）
1103 Integer Factorization （30 分）（dfs+剪枝）
1100 Mars Numbers （20 分）（字符串模拟）
【题意】即十进制与十三进制之间的转换；十三进制的定义：
- 0："tret"
- 1 ~ 12 ："jan, feb, mar, apr, may, jun, jly, aug, sep, oct, nov, dec"
- 高位： "tam, hel, maa, huh, tou, kes, hei, elo, syy, lok, mer, jou"
【分析】字符串模拟啦 做的时候还是做了特别久，果然模拟题做不出来的时候全部推翻重新来过没准就对了...
- 十进制转十三进制时，如果低位是tret不用输出
- 注意首尾的空格
- 其他好像就没啥要注意的了吧【还做了这么这么久................
【代码】
#include<bits/stdc++.h>
using namespace std;char s1[13][5]={"tret", "jan", "feb", "mar", "apr", "may", "jun", "jly", "aug", "sep", "oct", "nov", "dec"};
char s2[13][5]={"tret", "tam", "hel", "maa", "huh", "tou", "kes", "hei", "elo", "syy", "lok", "mer", "jou"};int main()
{int n;scanf("%d",&n);getchar();while(n--){string s;getline(cin,s);if(isdigit(s[0])){int x=stoi(s);if(x<=12)printf("%s\n",s1[x]);else{int t1=x/13,t2=x%13;if(t2==0)printf("%s\n",s2[t1]);else printf("%s %s\n",s2[t1],s1[t2]);}}else{int len=s.length();int cnt=0;string str1,str2;while(s[cnt]==' ')cnt++;while(s[cnt]!=' ' && cnt<len)str1+=s[cnt++];while(s[cnt]==' ')cnt++;while(s[cnt]!=' ' && cnt<len)str2+=s[cnt++];int x=-1,y=-1;if(str2==""){for(int i=0;i<13;++i)if(s1[i]==str1){x=i;printf("%d\n",x);break;}if(x==-1)for(int i=0;i<13;++i){if(s2[i]==str1){x=i;printf("%d\n",x*13);break;}}}else{for(int i=0;i<13;++i)if(s2[i]==str1){x=i;break;}for(int i=0;i<13;++i)if(s1[i]==str2){y=i;break;}printf("%d\n",x*13+y);}}}
}1101 Quick Sort （25 分）（数组模拟+思维）
【题意】给你一个序列，求满足一下条件的数的个数：
- 该数前面的数均比它小
- 该数后面的数均比它大
【分析】
- 建立两个数组，Min&&Max；一个从后往前扫，一个从前往后扫
- 如果相同的下标对应的Min和Max的值相等，则该下标对应的数是满足的
- 然后就是，，，，一个4分的测试点。。格式问题。如果没有数满足的话，要换行..........因为题目上有the first line....the next line 好坑啊。。。
【代码】
#include<bits/stdc++.h>
using namespace std;const int maxn=1e5+10;
int Min[maxn],Max[maxn];
int a[maxn];int main()
{int n;scanf("%d",&n);for(int i=0;i<n;++i)scanf("%d",&a[i]);Min[n-1]=a[n-1];for(int i=n-2;i>=0;--i){if(a[i]<Min[i+1])Min[i]=a[i];else Min[i]=Min[i+1];}Max[0]=a[0];for(int i=1;i<n;++i){//cout<<a[i]<<"---"<<Max[i-1]<<endl;if(a[i]>Max[i-1])Max[i]=a[i];else Max[i]=Max[i-1];}vector<int>v;for(int i=0;i<n;++i){// cout<<Min[i]<<","<<Max[i]<<endl;if(Min[i]==Max[i])v.push_back(a[i]);}int x=v.size();printf("%d\n",x);sort(v.begin(),v.end());for(int i=0;i<x;++i)(i==x-1)?printf("%d\n",v[i]):printf("%d ",v[i]);if(x==0)printf("\n");
}1102 Invert a Binary Tree （25 分）
【题意】给出0~N-1个结点的左右孩子，输出其invert后的层序遍历序列和中序遍历序列
【代码】
#include<bits/stdc++.h>
using namespace std;struct node{int lchild,rchild;int val;
}tree[20];
int pos[20];
int in[20],level[20];
int cnt1,cnt2;
int n;void build()
{for(int i=0;i<n;i++){tree[i].val=i;string s;getline(cin,s);if(s[0]=='-'&&s[2]=='-') tree[i].lchild=tree[i].rchild=-1;else if(s[0]=='-'){ tree[i].lchild=-1,tree[i].rchild=s[2]-'0';pos[tree[i].rchild]=1;}else if(s[2]=='-'){ tree[i].lchild=s[0]-'0',tree[i].rchild=-1;pos[tree[i].lchild]=1;}else tree[i].lchild=s[0]-'0',tree[i].rchild=s[2]-'0',pos[tree[i].lchild]=1,pos[tree[i].rchild]=1;}
}
void getIn(node &nd)
{ if(nd.rchild!=-1)getIn(tree[nd.rchild]);if(nd.val!=-1)in[cnt2++]=nd.val;if(nd.lchild!=-1)getIn(tree[nd.lchild]);
}
void getLevel(node &nd)
{queue<node>q;q.push(nd);while(!q.empty()){node n1=q.front();q.pop();level[cnt1++]=n1.val;if(n1.rchild!=-1)q.push(tree[n1.rchild]);if(n1.lchild!=-1)q.push(tree[n1.lchild]);}
}
int main()
{scanf("%d",&n);getchar();build();int index=0;cnt1=cnt2=0;for(int i=0;i<n;++i)if(pos[i]==0){ index=i;break;}getLevel(tree[index]);getIn(tree[index]);for(int i=0;i<n;++i)(i==n-1)?printf("%d\n",level[i]):printf("%d ",level[i]);for(int i=0;i<n;++i)(i==n-1)?printf("%d\n",in[i]):printf("%d ",in[i]);
}1103 Integer Factorization （30 分）（dfs+剪枝）
【题意】求出k个数的p次方和等于n的因子和最大的等式，不存在则输出impossible
【分析】因为n≤400，所以因子最大也就20；深搜+剪枝
- 如果因子数已经达到k但x!=0即和不为n，剪枝
- 如果因子数为达到k但x<0，剪枝
- 递归边界：x==0 && cnt==k，此时求出因子和并更新
- 求出递归起点和终点，注意起点只有在第一次才是从因子1开始，其他情况是从上一个因子开始；
【代码】
#include<bits/stdc++.h>
using namespace std;int n,k,p;
int cur_sum;//当前因子和
int max_sum;//最大因子和
vector<int>factor,result;//存储因子，最终答案
bool cmp(int x,int y){ return x>y; }
void dfs(int x,int cnt)
{if(x!=0 && cnt==k)return;if(x<0)return;if(x==0 && cnt==k){cur_sum=0;for(int i=0;i<k;++i)cur_sum+=factor[i];if(cur_sum>=max_sum)//更新最大和，相等也更新，这样才满足最大的因子序列{max_sum=cur_sum;result=factor;}return;}int start=(cnt>0)?factor[cnt-1]:1;int end=(int)sqrt(double(x));for(int i=start;i<=end;++i){
// cout<<cnt<<endl;factor[cnt]=i;//这里不可以直接push_back dfs(x-(int)pow(i,p),cnt+1);}return;
}
int main()
{max_sum=-1;cur_sum=0;scanf("%d%d%d",&n,&k,&p);factor.resize(k);//这里注意！！！ dfs(n,0);if(max_sum==-1)puts("Impossible");else{sort(result.begin(),result.end(),cmp);printf("%d = ",n);for(int i=0;i<result.size();++i){if(i==result.size()-1)printf("%d^%d\n",result[i],p);else printf("%d^%d + ",result[i],p);}}
}