今天的题目主要涉及到的字符串的综合运用，以及双链表的用法，这里简单回顾一下
双链表：{
概念： 可以兼顾前后的链表
//双链表的初始化
head = 0,tail=N-1;//头尾节点
r[head] = tail;//后一个的下标,俗称后继
l[tail] = head;//前一个的下标，俗称前继
idx = 1;
//添加
e[idx]=x;//存入当前节点的值
r[idx]=r[k];//将当前节点的后继指向K的后继
l[idx]=k;//将当前节点的前继指向k
l[r[k]]=idx;//将k的后继的前继指向当前节点
r[k]=idx;//将k的新后继指向当前节点
idx++;//继续更新新的节点
//删除
r[l[k]]=r[k];//删除时，将k的后继的前继指向k的前继
l[r[k]]=l[k];//将k的前继的后继指向k的后继
}
今日例题：
1 Asya and Kittens{
-
题意：有一个数组，其中的元素可以两两互相合并，现在给出一组两两相邻的元素，求一个原始数组
-
思路：我们可以将两两互相合并的过程看作合并至同一个连通块中，连通块的父节点就是当前区间的左端点。合并时，将新添加进来的元素放在区间的最右端是最稳妥的办法
-
算法：并查集
}
for(int i=1;i<t;i++){
int l,r;
cin >> l >> r;
int rl=find(l),rr=find(r);
nxt[ri[rl]]=rr;
ri[rl]=ri[rr];
fa[rr]=rl;
}
2 String transformation 1{
- 题意：有一组数据，每次会给你两个字符串，你可以对第一个字符串进行若干次操作，每次操作分为两步：
1 选择一个子序列，使得序列中的字母都相同
2 将序列中的所有字母都替换为一个字典序大于原字母的子母
求最终字符串是否能变成字符串b,如果能，输出最小操作次数，不能输出-1
- 思路：如果我们将字母之间的相等看作是在两个字母之间建边，那么原本的判断两个字符串是否相等的问题就转化成了两个字符串中的字母是否能够建成一张连通图的问题。
而判断无解的情况也很简单，因为我们修改字母只能从小到大修改，所以一旦a中出现了比b更大的字母，那么直接输出-1
- 算法：并查集
}
核心代码：
for(int i=0;i<n;i++){
int x=a[i]-'a';
int y=b[i]-'a';
if(x>y){
ok=false;
break;
}
if(x==y) continue;
if(uni(x,y)) cnt++;//如果不在同一连通块内，那么操作次数+1
}
if(!ok){
cout<<-1<<endl;
continue;
}
3 Phase shift(这题只有J组23题难度我是没法接受){
-
题意：给定一组字符串，为了对原字符串进行加密，现要找出一个顺序使得原字符串中的字母经过顺时针旋转后得到的字符串的字典序最小
-
思路：这题其实顺不顺时针的没有什么太大关系，我们只要保证原字符串尽量按照abcd，也就是所谓的字母表顺序来就行。而这题要考虑的东西较多，我认为应该不止1400分吧。
首先我们要处理的事情就是将原字符串中的字母给映射到另一个字典序尽可能小的字符串当中去，mp[a[i]]=t[i]。于是我们可以从小到大遍历26个字母，只要出现没有出现过的且没有重复选择的直接选上。
但如果没有没出现过的怎么办？那么我们就要重新在初始字符串中选择还未出现的字母，最后用两个标记数组进行标记，一个标记原数组中已出现的字母，一个标记使用过进行覆盖的字母（思维难度不大，考虑的东西多，调了蛮久）
- 算法：并查集
}
核心代码：
for(int i=0;i<n;i++){
int go=a[i]-'a';
int chose=-1;
if(vis2[go]){
ans.push_back(char('a'+mp[go]));
continue;
}
for(int j=0;j<26;j++){
if(vis1[j]) continue;//字母被选
if(j==go) continue;//重复选择
if(cnt!=25&&find(j)!=find(go)){//如果没有形成环
chose=j;
break;
}
}
if(chose==-1){//没找到
for(int c=0;c<26;c++){
if(!vis1[c]&&c!=go){//选择还未选的
chose=c;
break;
}
}
}
mp[go]=chose;
ans.push_back(char(chose+'a'));
vis1[chose]=true;
vis2[go]=true;
fa[chose]=go;//指向当前的字符
cnt++;
}
4 Perfect security{
-
题意：两个数组，你可以任意替换第二个数组中的元素顺序，使得第一个数组中的元素按位异或第二个数组中的对应元素后产生的新数组的字典序最小
-
思路：这题的数据一度达到int类型的极限，数组也可开到1e6,这么大的数据显然不能一个个枚举最小值。而我们知道，一个数虽然大，但在二进制下的位数很小，最多只能到30位。因此问题就从枚举数变成了枚举位数。所以我们用trie树来维护第二个数组中的每个元素的二进制位数，定义节点
son[N*30][2]:第一维指数的个数的位数，第二维指0和1两种状态。每次到达一个新的节点时son[p][u]=idx++,且此时的cnt[p]++,因为每到达一个新节点都需要记录。计算答案时，只要还有下一个节点那么继续走下去，不行则合并此时的状态，换着继续走
3.算法：trie树
}
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+10;
int son[N*30][2],cnt[30*N];
int idx=0;//一定要定义全局变量，保证能一直指向数组末尾
void insert(int x){
int p=0;
for (int i=30;i>=0;i--){
int u=x>>i&1;
if (!son[p][u]) son[p][u]=++idx;
p=son[p][u];
cnt[p]++;//每经过一次都要加1
}
}
int query(int x){
int p=0,res=0;
for (int i=30;i>=0;i--){
int u=x>>i&1;
int s=son[p][u];
if (s&&cnt[s]>0){//当前还有路可走
p=s;//指向可走的路
}
else{
p=son[p][u^1];//换路走
res|=(1<<i);
}
cnt[p]--;
}
return res;
}
int main(){
int t;
cin >> t;
vector<ll> a(t),b(t);
for(int i=0;i<t;i++){
cin >> a[i];
}
for(int i=0;i<t;i++){
cin >> b[i];
insert(b[i]);
}
for(int i=0;i<t;i++) cout<<query(a[i])<<" ";
}
5 Correct longest Sequence Editor{
- 题意：有一个括号序列和一个光标，现有三种不同类型的操作：
1 将光标向左移
2 将光标向右移
3 删除当前光标所处的可匹配的括号序列，如果右边还有括号就停留在右边的括号上，否则停留在左边的括号上
输出经过若干次操作后的括号序列
- 思路：这题能够直接想到的就是用栈来维护每个可匹配的括号区间，标记当前括号序列是第几个。但我们怎么去实现删除的操作呢？
首先我们不可能去真的一个一个踢出其中的括号，那样的话就会超时。因此要想实现O(1)级别的删除，就要依靠链表
用什么链表？单链还是双链？
答案是双链。为什么单链不行？因为单链表只看它后面的一个元素是什么，不管前面是什么样子，就跟线性DP一样，而这题很明显要让我们兼顾前后，而双链表则成了不二之选
所以我们只要构建出一个双链表来模拟删除的过程就行
3.算法：双链表
}
代码：
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int pre[N],nxt[N],can[N];
int main(){
int n,m,p;
cin >> n >> m >> p;
string s,h;
cin >> s >> h;
s=" "+s;
h=" "+h;
stack<int> st;
for(int i=1;i<=n;i++){
if(s[i]=='('){
st.push(i);
}
else{
int macth=st.top(); st.pop();
can[i]=macth;//可以匹配的下标
can[macth]=i;
}
}
for(int i=1;i<=n;i++){
pre[i]=i-1;//前继
nxt[i]=i+1;//后继
} nxt[0]=1;
pre[n+1]=n;
for(int i=1;i<=m;i++){
if(h[i]=='R') p=nxt[p];
else if(h[i]=='L') p=pre[p];
else{
int l=min(p,can[p]);//找到最近的前继
int r=max(p,can[p]);//最远的后继
int prel=pre[l];
int nxtr=nxt[r];
nxt[prel]=nxtr;//删除区间内的字符
pre[nxtr]=prel;
if(nxtr!=n+1){//没到头
p=nxtr;
}
else p=prel;
}
}
for(int i=nxt[0];i!=n+1;i=nxt[i]) cout<<s[i];
}
6 Prefix--suffix Palindrome{
1.题意：给你一个字符串，要求你找出其中的某一个字符串，我们规定你找出的最长字符串必须满足一下三个定义：
1 长度必须不能超过原串。
2 必须是回文串
3 是由原串中的前缀和后缀拼接而来
输出这个字符串
- 思路：这题首先要能够找到最长的由前缀和后缀拼接而来的字符串，就要先找到最长的回文前缀和后缀。这里我选择用next数组来求最长回文前后缀，除中间不能匹配的以外，其余的在加上最长回文前缀和最长公共后缀之间取到最大长度。因为有了next数组，所以查询最长回文前后缀的时间复杂度接近O(1)
}
核心代码：
首先是这题next 数组的计算：
vector<int> pf(string s){
int n=s.size();
vector<int> p(n,0);//next数组
for(int i=1;i<n;i++){
int j=p[i-1];
while(j>0&&s[j]!=s[i]) j=p[j-1];//这里如果匹配不了必须跳回来再找
if(s[i]==s[j]) j++;
p[i]=j;
}
return p;
}
再是合法字符串的计算：
string solve(string s){
int n=s.size();
int l=0,r=n-1;
while(l<r&&s[l]==s[r]){
l++; r--;
}
if(l>=r) return s;//全部匹配，直接返回原串
string mid=s.substr(l,r-l+1);
string res=mid;
reverse(res.begin(),res.end());
string t1=mid+res;
vector<int> p1=pf(t1);
int len1=p1.back();//最长回文前缀
string t2=res+mid;
vector<int> p2=pf(t2);
int len2=p2.back();//最长回文后缀
string p=s.substr(0,l);
string h=s.substr(r+1);
if(len1>=len2) return p+mid.substr(0,len1)+h;
else return p+mid.substr(mid.size()-len2)+h;
}
评论
0