第一题
Q:
小Q想要给他的朋友发送一个神秘字符串，但是他发现字符串的过于长了，于是小Q发明了一种压缩算法对字符串中重复的部分进行了压缩，对于字符串中连续的m个相同字符串S将会压缩为m|S，例如字符串ABCABCABC将会被压缩为[3|ABC]，现在小Q的同学收到了小Q发送过来的字符串，你能帮助他进行解压缩么？
输入描述:
输入第一行包含一个字符串s，代表压缩后的字符串。
S的长度<=1000;
S仅包含大写字母、[、]、|;
解压后的字符串长度不超过100000;
压缩递归层数不超过10层;
输出描述:
输出一个字符串，代表解压后的字符串。
输入例子1:
HG[3|B[2|CA]]F
输出例子1:
HGBCACABCACABCACAF
例子说明1:
HG[3|B[2|CA]]F−>HG[3|BCACA]F−>HGBCACABCACABCACAF
A：
用栈：
int main(){
string s;
cin>>s;
stack<char> sta;
int i=0;
while(i<s.size()){
if(s[i]!=']'){
sta.push(s[i++]);
}
else{//s[i]==']'
string tmp="";
while(sta.top()!='|'){
tmp+=sta.top();
sta.pop();
}
reverse(tmp.begin(),tmp.end());
sta.pop(); //pop掉'|'
string str=tmp;
tmp="";
while(sta.top()!='['){
tmp+=sta.top();
sta.pop();
}
reverse(tmp.begin(),tmp.end());
int num=stoi(tmp);
sta.pop(); //pop '['
tmp="";
while(num>0){
tmp+=str;
num--;
}
for(char& c:tmp){
sta.push(c);
}
++i;
}
}
string res="";
while(!sta.empty()){
res+=sta.top();
sta.pop();
}
reverse(res.begin(),res.end());
cout<<res<<endl;
return 0;
}
递归：
string func(const string& s,int& index){
string res="";
while(index<s.size() and s[index]!=']'){
if(s[index]<='Z' and s[index]>='A'){
res+=s[index++];
}
else{ //s[index]=='['
index++;//指向第一个数字
int tmp=s.find(index,'|');
int num=stoi(s.substr(index,tmp-index));
index++;//指向第一个字母
string str=func(s,index);
index++;
while(num>0){
res+=str;
num--;
}
}
}
return res;
}
int main(){
int i=0;
string s="";
cin>>s;
cout<<func(s,i)<<endl;
return 0;
}
第二题
Q：
小Q在周末的时候和他的小伙伴来到大城市逛街，一条步行街上有很多高楼，共有n座高楼排成一行。
小Q从第一栋一直走到了最后一栋，小Q从来都没有见到这么多的楼，所以他想知道他在每栋楼的位置处能看到多少栋楼呢？（当前面的楼的高度大于等于后面的楼时，后面的楼将被挡住）
输入描述:
输入第一行将包含一个数字n，代表楼的栋数，接下来的一行将包含n个数字wi(1<=i<=n)，代表每一栋楼的高度。
1<=n<=100000;
1<=wi<=100000;
输出描述:
输出一行，包含空格分割的n个数字vi，分别代表小Q在第i栋楼时能看到的楼的数量。
输入例子1:
6
5 3 8 3 2 5
输出例子1:
3 3 5 4 4 4
例子说明1:
当小Q处于位置3时，他可以向前看到位置2,1处的楼，向后看到位置4,6处的楼，加上第3栋楼，共可看到5栋楼。当小Q处于位置4时，他可以向前看到位置3处的楼，向后看到位置5,6处的楼，加上第4栋楼，共可看到4栋楼。
A：
#pragma warning(disable:4996)
#include <iostream>
#include<istream>
#include <string>
#include <cctype>
#include<vector>
#include<list>
#include<cstring>
#include<random>
#include<typeinfo>
#include<set>
#include<map>
#include<deque>
#include<regex>
#include<sstream>
#include<cstdlib>
#include<queue>
#include<stdlib.h>
#include<stdio.h>
#include<stack>
#include<algorithm>
#include<thread>
#include<mutex>
#include<assert.h>
#include<fstream>
#include<unordered_map>
#include<unordered_set>
using namespace std;
int main(){
int N;
cin>>N;
vector<int> vec(N);
int i=0;
while(i<N and cin>>vec[i++]){;}
stack<int> sta;
vector<int> look_left(N,0);
//向左看，不包括所在的楼
for(int i=1;i<N;++i){
if(sta.empty() or sta.top()>vec[i-1]){
sta.push(vec[i-1]);
}
else{
while(!sta.empty() and sta.top()<=vec[i-1]){
sta.pop();
}
sta.push(vec[i-1]);
}
look_left[i]=sta.size();
}
//向右看，不包括所在的楼
vector<int> look_right(N,0);
sta=stack<int>();
for(int i=N-2;i>=0;--i){
if(sta.empty() or sta.top()>vec[i+1]){
sta.push(vec[i+1]);
}
else{
while(!sta.empty() and sta.top()<=vec[i+1]){
sta.pop();
}
sta.push(vec[i+1]);
}
look_right[i]=sta.size();
}
for(int i=0;i<N;++i){
cout<<1+look_left[i]+look_right[i]<<" ";
}
cout<<endl;
}
4
#pragma warning(disable:4996)
#include <iostream>
#include<istream>
#include <string>
#include <cctype>
#include<vector>
#include<list>
#include<cstring>
#include<random>
#include<typeinfo>
#include<set>
#include<map>
#include<deque>
#include<regex>
#include<sstream>
#include<cstdlib>
#include<queue>
#include<stdlib.h>
#include<stdio.h>
#include<stack>
#include<algorithm>
#include<thread>
#include<mutex>
#include<assert.h>
#include<fstream>
#include<unordered_map>
#include<unordered_set>
#include<limits.h>
using namespace std;
int main(){
int n;
cin>>n;
vector<int> company(n),gym(n);
for(int i=0;i<n;++i){
cin>>company[i];
}
for(int i=0;i<n;++i){
cin>>gym[i];
}
vector<vector<int> >dp(n,vector<int>(3,INT_MAX));//dp[i][0]截止第i天，第i天去公司最少休息天数，dp[i][1]表示第i天去健身
//dp[i][2]是截止到第i天，第i天休息的最少休息天数
if(company[0]==1){
dp[0][0]=0;
}
if(gym[0]==1){
dp[0][1]=0;
}
dp[0][2]=1;
for(int i=1;i<n;++i){
if(company[i]){//上班
dp[i][0]=min(dp[i-1][2],dp[i-1][1]);
}
if(gym[i]){//锻炼
dp[i][1]=min(dp[i-1][0],dp[i-1][2]);
}
dp[i][2]=min(min(dp[i-1][2],dp[i-1][1]),dp[i-1][0])+1;
}
cout<<*min_element(dp[n-1].begin(),dp[n-1].end());
}
5
#pragma warning(disable:4996)
#include <iostream>
#include<istream>
#include <string>
#include <cctype>
#include<vector>
#include<list>
#include<cstring>
#include<random>
#include<typeinfo>
#include<set>
#include<map>
#include<deque>
#include<regex>
#include<sstream>
#include<cstdlib>
#include<queue>
#include<stdlib.h>
#include<stdio.h>
#include<stack>
#include<algorithm>
#include<thread>
#include<mutex>
#include<assert.h>
#include<fstream>
#include<unordered_map>
#include<unordered_set>
#include<limits.h>
using namespace std;
struct range{
int le;
int ri;
range():le(0),ri(0){}
// range(int a,int b):le(a),ri(b){}
bool operator<(const range& x){
return le<x.le or (le==x.le and ri<x.ri);
}
};
int main(){
int n,l;
cin>>n>>l;
if(n<=0){
cout<<-1;
return 0;
}
vector<range> data(n);
for(int i=0;i<n;++i){
cin>>data[i].le>>data[i].ri;
}
sort(data.begin(),data.end());
if(data[0].le!=0){
cout<<-1;
return 0;
}
int cur_reach=data[0].ri,cur_base=data[0].le;
int i=1,cnt=1;
while(data[i].le==0){
cur_reach=max(cur_reach,data[i++].ri);
}
while(i<n and cur_reach<l){
int farthest=0,base;
while(i<n and data[i].le<=cur_reach){
if(data[i].ri>farthest){
farthest=data[i].ri;
base=data[i].le;
}
++i;
}
if(farthest<cur_reach){
cout<<-1;
return 0;
}
cur_base=base;
cur_reach=farthest;
cnt++;
}
if(cur_reach>=l){
cout<<cnt;
}
else{
cout<<-1;
}
return 0;
}