本地环境搭建网站,郑州优化公司有哪些,网页版微信和电脑版微信的区别,烟台网站制作这原题链接#xff1a;D-小苯的IDE括号问题#xff08;hard#xff09;
题目大意#xff1a;给定一个长度为n的字符串#xff0c;字符串由#xff08;#xff0c;#xff09;和I构成#xff0c;m组询问#xff0c;如果输入backspace#xff0c;如果I左右是#xff0…原题链接D-小苯的IDE括号问题hard
题目大意给定一个长度为n的字符串字符串由和I构成m组询问如果输入backspace如果I左右是和就一起删除如果是只有(就只删除左边。如果是delete就删除右边如果右边存在。如果输入-就把I向左移动如果是-就把I向右移动。
思路可以观察到每次操作都与I有关并且题目里面涉及大量的删改我的思路和题解不一样是用数组来记录字符然后用数组来模拟链表这样可以快速的删除I左右的元素和移动I。官方的思路是用栈来存在I左边和右边的字符串然后根据条件来操作为了方便输出栈可以用vector来模拟。
我的思路代码
#pragma GCC optimize(2)
#includebits/stdc.h
#define endl \n
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pairll,ll pii;
const int N1e610,mod10007;
char p[N];
ll l[N],r[N];
int main()
{ios::sync_with_stdio(NULL);cin.tie(0),cout.tie(0);ll n,m;cinnm;ll cnt0;for(int i1;in;i){cinp[i];l[i]i-1;r[i]i1;if(p[i]I)cnti;}r[0]1;l[n1]n;while(m--){if(r[0]n)break;string s;cins;if(sbackspace){ll al[cnt],bcnt,cr[cnt];if(a0)continue;else if(cn1){ll xl[a];r[x]b,l[b]x;}else{if(p[a](p[c])){ll xl[a],yr[c];r[x]b;l[b]x;r[b]y;l[y]b;}else{ll xl[a];r[x]b;l[b]x;}}}else if(sdelete){ll al[cnt],bcnt,cr[cnt];if(cn1)continue;else{ll xr[c];l[x]b;r[b]x;}}else if(s-){ll al[cnt],bcnt,cr[cnt];if(a0)continue;ll xl[a];l[c]a;r[a]c;l[b]x;r[b]a;r[x]b;l[a]b;}if(s-){ll al[cnt],bcnt,cr[cnt];if(cn1)continue;ll xr[c];r[a]c;l[c]a;l[b]c;r[b]x;r[c]b;l[x]b;}}for(int ir[0];in;ir[i]){coutp[i];}coutendl;return 0;
}
官方思路代码
#pragma GCC optimize(2)
#includebits/stdc.h
#define endl \n
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pairll,ll pii;
const int N1e610,mod10007;
char p[N];
int main()
{ios::sync_with_stdio(NULL);cin.tie(0),cout.tie(0);ll n,m;cinnm;ll cnt0;for(int i1;in;i){cinp[i];if(p[i]I)cnti;}vectorchar a,b;for(int i1;icnt;i)a.push_back(p[i]);//exit(0);for(int in;icnt;i--)b.push_back(p[i]);while(m--){string s;cins;if(sbackspace){if(a.size()){if(b.size()b[b.size()-1])a[a.size()-1](){b.pop_back();}a.pop_back();}}if(sdelete){if(b.size()){b.pop_back();}}if(s-){if(a.size()){b.push_back(a[a.size()-1]);a.pop_back();}}if(s-){if(b.size()){a.push_back(b[b.size()-1]);b.pop_back();}}}for(int i0;ia.size();i){couta[i];}coutI;for(int ib.size()-1;i0;i--){coutb[i];}return 0;
}
