Vain

Vain
4个月前

## 思路

DP的推导过程和石子合并差不多，推导出动态方程即可，首先如果我么遇到匹配的，那么当前区间 $dp[i][j]=dp[i+1][j−1]+2$，然后枚举中间点，更新区间即可。

#include <cstdio>
#include <algorithm>
#include <vector>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
using namespace std;
typedef long long ll;
const int inf = 1 << 30;
const int maxn = 2e5 + 5;
const int N = 1e3 + 5;
const int base = 131;
string s1 = "xxxll", s2 = "xxlxll";
int n, t, m;
char s[maxn];
int a[N], sum[N];
int dp[N][N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> s + 1;
int n = strlen(s + 1);
for (int len = 2; len <= n; len++)
{
for (int i = 1; i + len - 1 <= n; i++)
{
int j = i + len - 1;
if ((s[i] == '(' && s[j] == ')') || (s[i] == '[' && s[j] == ']'))
dp[i][j] = dp[i + 1][j - 1] + 2;
for (int k = i; k < j; k++)
{
dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j]);
}
}
}
cout<<n-dp[1][n]<<endl;
}


Vain
6个月前

### 算法1

#### C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e2+5;
typedef unsigned long long ll;
const ll base=13331;
ll h[maxn],p[maxn];
char s[maxn];
ll get(ll l,ll r)
{
return h[r]-h[l-1]*p[r-l+1];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
while(cin>>s+1&&s[1]!='.')
{
p[0]=1;
ll len=strlen(s+1);
for(int i=1; i<=len; i++)
{
h[i]=h[i-1]*base+s[i]-'a';
p[i]=p[i-1]*base;
}
ll maxx=1;
int k=1;
while(1)
{
bool fla=true;
ll j,ans=1;
if(len%k==0)
{
j=len/k;
if(j==1)
break;
for(int i=1; i+2*k-1<=len; i+=k)
{
if(get(i,i+k-1)==get(i+k,i+2*k-1))
ans++;
else
{
fla=false;
break;
}
}
if(fla)
{
maxx=max(maxx,ans);
break;
}
}
k++;
}
cout<<maxx<<endl;
}
}



Vain
6个月前

### 线段树+树链剖分，处理好线段树合并的部分，注意在进行树链求和操作时，对于多部分链的端点需要进行合并判断，如果颜色相同,合并后的答案等于ans-1,反则等于ans

#### 代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1e5+5;
ll color[maxn],sizx[maxn],dfn[maxn],cnx,w[maxn];
struct node
{
ll to,nex;
} edge[maxn<<3];
{
edge[cnt].to=v;
}
void dfs1(ll u,ll fa)
{
pre[u]=fa;
deep[u]=deep[fa]+1;
ll maxson=-1;
sizx[u]=1;
{
ll v=edge[i].to;
if(v==fa)
continue;
dfs1(v,u);
sizx[u]+=sizx[v];
if(maxson<sizx[v])
{
maxson=sizx[v];
son[u]=v;
}
}
}
void dfs2(ll u,ll t)
{
top[u]=t;
dfn[u]=++cnx;
w[cnx]=color[u];
if(!son[u])
return ;
dfs2(son[u],t);
{
ll v=edge[i].to;
if(v==pre[u]||v==son[u])
{
continue;
}
dfs2(v,v);
}
}
struct vain
{
ll l,r;
ll sum,lazy,lc,rc;
} tr[maxn<<2];
void pushup(ll k)
{
ll sum=tr[k<<1].sum+tr[k<<1|1].sum;
if(tr[k<<1].rc==tr[k<<1|1].lc)
tr[k].sum=sum-1;
else
tr[k].sum=sum;
tr[k].lc=tr[k<<1].lc;
tr[k].rc=tr[k<<1|1].rc;
}
void pushdown(ll k)
{
if(tr[k].lazy)
{
tr[k<<1].lc=tr[k<<1].rc=tr[k].lazy;
tr[k<<1|1].lc=tr[k<<1|1].rc=tr[k].lazy;
tr[k<<1].lazy=tr[k<<1|1].lazy=tr[k].lazy;
tr[k<<1].sum=tr[k<<1|1].sum=1;
tr[k].lazy=0;
}
}
void build(ll k,ll l,ll r)
{
tr[k].l=l,tr[k].r=r;
if(l==r)
{
tr[k].lc=tr[k].rc=w[l];
tr[k].sum=1;
return ;
}
ll mid=l+r>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
pushup(k);
}
void modify(ll k,ll l,ll r,ll c)
{
if(tr[k].l>=l&&tr[k].r<=r)
{
tr[k].lazy=c;
tr[k].lc=tr[k].rc=c;
tr[k].sum=1;
return ;
}
pushdown(k);
ll mid=tr[k].l+tr[k].r>>1;
if(mid>=r)
modify(k<<1,l,r,c);
else if(mid<l)
modify(k<<1|1,l,r,c);
else
modify(k<<1,l,mid,c),modify(k<<1|1,mid+1,r,c);
pushup(k);
}
ll qid(ll k,ll x)
{
if(tr[k].l==tr[k].r)
return tr[k].lc;
pushdown(k);
ll mid=tr[k].l+tr[k].r>>1;
if(mid>=x)
return qid(k<<1,x);
else
return qid(k<<1|1,x);
pushup(k);
}
{
if(tr[k].l>=l&&tr[k].r<=r)
return tr[k].sum;
pushdown(k);
ll mid=tr[k].l+tr[k].r>>1;
if(mid>=r)
else if(mid<l)
else
}
void opt1(ll x,ll y,ll c)
{

while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]])
swap(x,y);
modify(1,dfn[top[x]],dfn[x],c);
x=pre[top[x]];
}
if(deep[x]>deep[y])
swap(x,y);
modify(1,dfn[x],dfn[y],c);
}
ll opt2(ll x,ll y)
{
ll res=0;
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]])
swap(x,y);
if(qid(1,dfn[top[x]])==qid(1,dfn[pre[top[x]]]))
res--;
x=pre[top[x]];
}
if(deep[x]>deep[y])
swap(x,y);
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
ll n,q;
cin>>n>>q;
for(ll i=1; i<=n; i++)
{
cin>>color[i];
}
ll u,v;
for(ll i=1; i<n; i++)
{
}
dfs1(1,0);
dfs2(1,1);
build(1,1,n);
while(q--)
{
char s;
ll x,y,z;
cin>>s;
if(s=='Q')
{
cin>>x>>y;
cout<<opt2(x,y)<<endl;
}
else
{
cin>>x>>y>>z;
opt1(x,y,z);
}
}
}