目录
1084 Broken Keyboard （20 分）（字符串处理）
1085 Perfect Sequence （25 分）
1086 Tree Traversals Again （25 分）（二叉树中序+前序→后序）
1087 All Roads Lead to Rome （30 分）（dijkstra+dfs）
1084 Broken Keyboard （20 分）（字符串处理）
【题意】给两串字符串，输出缺失的字母或数字，如果是字母输出大写；每个缺失的字符只输出一次并且按串中的次序输出
【分析】字符串的处理模拟
【代码】
#include<bits/stdc++.h>
using namespace std;int book[300];//标记该字符是否已经被标记过 int main()
{string s1,s2;cin>>s1>>s2;int l1=s1.length();int l2=s2.length();int cnt=0;vector<char>v;memset(book,0,sizeof(book));for(int i=0;i<l1;++i){if(s1[i]!=s2[cnt] && !book[s1[i]]){if(isalpha(s1[i]))v.push_back(toupper(s1[i]));else v.push_back(s1[i]);book[s1[i]]=1; if(isalpha(s1[i]))book[tolower(s1[i])]=book[toupper(s1[i])]=1;} else if(s1[i]==s2[cnt])cnt++;} int l=v.size();for(int i=0;i<l;++i)printf("%c",v[i]);puts("");
}1085 Perfect Sequence （25 分）
【题意】求序列的最小值min与参数p的积大于等于最大值的序列的最大长度
【分析】序列先排序，然后最大长度由1开始递增；注意数据范围是可能会超int的，所以要用long long
【代码】
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
const int maxn=1e5+10;
int a[maxn];
ll n,p;int main()
{scanf("%lld%lld",&n,&p);for(int i=0;i<n;++i)scanf("%d",&a[i]);sort(a,a+n);int length=1; //最小长度是1 for(int i=0;i<n;++i)while(i+length<=n && a[i+length-1]<=p*a[i])length++;printf("%d\n",length-1);
}1086 Tree Traversals Again （25 分）（二叉树中序+前序→后序）
【题意】Push对应前序遍历，Pop对应中序遍历
【分析】做了两个多小时的题.... 然后，是因为，T=new node()写成了T=new node？？？？
- 不要直接用queue，queue只能弹出队列顶部元素，但是这里是先进先出型的。vector就好
- v.back() 取vector底部元素； v.pop_back() 弹出底部元素
- 然后就是已知中序+前序→后序了（ 模板记一记?
【代码】
#include<bits/stdc++.h>
using namespace std;typedef struct node{struct node *lchild;struct node *rchild;int val;
}node,*tree;const int maxn=50;
int pre[maxn],post[maxn],in[maxn];
int cnt1,cnt2,cnt,n;int findRoot(int x)
{for(int i=0;i<n;++i)if(in[i]==x)return i;return -1;
}
void build(tree &T,int left,int right)
{if(left>right || cnt>=n)return;//cout<<"cnt="<<cnt<<endl;int root=pre[cnt];cnt++;int index=findRoot(root);T=new node();T->val=root;if(right==left) T->lchild=T->rchild=NULL;else{build(T->lchild,left,index-1);build(T->rchild,index+1,right);}
}
void getPost(tree &T)
{if(T==NULL)return;getPost(T->lchild);getPost(T->rchild);post[cnt++]=T->val;
}
int main()
{scanf("%d",&n);vector<int>v;cnt1=cnt2=0;int num=0;string s;for(int i=0;i<n*2;++i){cin>>s;if(s=="Push"){int x;scanf("%d",&x);v.push_back(x);pre[cnt1++]=x; num=0;}else if(s=="Pop"){int x=v.back();in[cnt2++]=x;v.pop_back();}}
// for(int i=0;i<cnt1;++i)printf("%d ",pre[i]); puts("");
// for(int i=0;i<cnt2;++i)printf("%d ",in[i]); puts("");tree T;cnt=0; build(T,0,n-1);cnt=0; getPost(T);for(int i=0;i<n;++i)(i==n-1)?printf("%d\n",post[i]):printf("%d ",post[i]);
}
1087 All Roads Lead to Rome （30 分）（dijkstra+dfs）
【题意】给出每个城市的快乐值（除了起始城市）以及每两个城市之间的cost，求出最低花费下能获得的最大快乐值，并求出平均值
【分析】dijkstra+dfs
（代码参考）
【代码】
#include<bits/stdc++.h>
using namespace std;const int maxn=300;
const int inf=0x3f3f3f3f;
int hap[maxn];
int e[maxn][maxn];
int dis[maxn];
int book[maxn];
map<string,int>si;
map<int,string>is;
vector<int>path[maxn];int n,k;void Dijkstra(int x)
{memset(book,0,sizeof(book));memset(dis,inf,sizeof(dis));
// for(int i=0;i<n;i++) dis[i]=mp[v][i];dis[x]=0;for(int i=0;i<n;i++){int now=-1,minn=inf;for(int j=0;j<n;j++){if(!book[j] && minn>dis[j]){minn=dis[j];now=j;}}if(now==-1) return;book[now]=true;for(int j=0;j<n;j++){if(!book[j]){if(dis[j]>e[now][j]+dis[now]){dis[j]=e[now][j]+dis[now];path[j].clear();path[j].push_back(now);}else if(dis[j]==e[now][j]+dis[now])path[j].push_back(now);}}}
}
vector<int>t,tt;
int maxValue=0,sum=0;
void dfs(int x)
{if(x==0){sum++;t.push_back(x);int sumValue=0;for(int i=t.size()-1;i>=0;i--)sumValue+=hap[t[i]];if(maxValue<sumValue){maxValue=sumValue;tt=t;}else if(sumValue==maxValue){double a=1.0*sumValue/tt.size();double b=1.0*maxValue/t.size();if(a<b)tt=t;}t.pop_back();return;}t.push_back(x);for(int i=0;i<path[x].size();i++){dfs(path[x][i]);}t.pop_back();
}
int main()
{memset(e,inf,sizeof(e));memset(hap,0,sizeof(hap));scanf("%d%d",&n,&k);string s;cin>>s;si[s]=0;is[0]=s;for(int i=1;i<=n-1;i++){string s;cin>>s;scanf("%d",&hap[i]);si[s]=i;is[i]=s;}while(k--){string a,b;cin>>a>>b;int x;scanf("%d",&x);int a1=si[a];int b1=si[b];e[a1][b1]=e[b1][a1]=x;}Dijkstra(0);int ed=si["ROM"];dfs(ed);cout<<sum<<" "<<dis[ed]<<" "<<maxValue<<" "<<maxValue/(tt.size()-1)<<endl;reverse(tt.begin(),tt.end());for(int i=0;i<tt.size();i++){if(i) cout<<"->";cout<<is[tt[i]];}cout<<endl;return 0;
}