Link with Bracket Sequence II(区间 DP)
Problem
有一个长度为\(n\)的括号序列，括号种类有\(m\)种，现在这个括号序列丢失了一些括号，问可能的合法括号序列个数
(和)可以匹配当且仅当它们的种类一样- \(A\)是合法的，\(x,y\)是某种括号，那么\(xAy\)是合法的当且仅当\(x,y\)匹配
- \(A、B\)是合法的，则\(AB、BA\)都是合法的
\(1\le n\le 500\)，\(1\le m\le 10^9\)
Solve
首先可以想到的是 DP，然后\(n\)只有\(500\)，所以可以考虑区间 DP。
\(f_{l,r}\)表示区间\([l,r]\)为合法括号序列
\(g_{l,r}\)表示区间\([l,r]\)为合法括号序列且\(a_l\)和\(a_r\)是匹配的一对括号的方案数
那么转移就是：
- 如果\(a_l=|a_r|\ne 0\)，那么\(f_{l,r}=g_{l,r}=f_{l+1,r-1}\)
- 如果\(a_l\gt 0,a_r=0\)或者\(a_l=0,a_r\lt 0\)，那么\(f_{l,r}=g_{l,r}=f_{l+1,r-1}\)
- 如果\(a_l=a_r=0\)，那么\(f_{l,r}=g_{l,r}=mf_{l+1,r-1}\)
然后再用区间里面的情况去更新\(f_{l,r}\)即可
Code
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=1e9+7;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin>>T;
while(T--){
int n,m;
cin>>n>>m;
vector<int>a(n+1);
for(int i=1;i<=n;i++) cin>>a[i];
vector<vector<ll>>g(n+1,vector<ll>(n+1,0)),f(n+1,vector<ll>(n+1,0));
for(int i=1;i<=n;i++) f[i][i-1]=g[i][i-1]=1;
for(int len=2;len<=n;len++){
for(int l=1;l<=n;l++){
int r=l+len-1;
if(r>n) break;
if(a[l]==0 && a[r]==0)
f[l][r]=g[l][r]=f[l+1][r-1]*m%mod;
else if((a[l]>0&&a[r]==0) || (a[l]==0&&a[r]<0) || (a[l]>0&&a[r]<0&&a[l]+a[r]==0))
f[l][r]=g[l][r]=f[l+1][r-1];
else
f[l][r]=g[l][r]=0;
for(int k=l+1;k<r;k++)
f[l][r]=(f[l][r]+f[l][k]*g[k+1][r]%mod)%mod;
}
}
cout<<f[1][n]<<'\n';
}
return 0;
}
Link with Running(tarjan 缩点、最短路、拓扑排序)
Problem
给定一个\(n\)个点\(m\)条边的有向图，每条边用\((u_i,v_i,e_i,p_i)\)表示从点\(u_i\)到\(v_i\)需要花费\(e_i\)元，并获得\(p_i\)点能量。问从\(1\)号点出发到\(n\)，在满足花费最小的前提下，可以得到的最大能量。输出最小花费和能量。
Solve
只考虑花费的话，跑个最短路即可。加入能量后，我们可以考虑先构建一个最短路图，即每个\(v\)可以转移过来的点一个是花费最小的。在这个图上\(dp\)求最大能量即可，但可能不是一个DAG，存在\(0\)环，所以缩点后在DAG上跑DP即可。
存在环的话一定是\(0\)环，因为如果\(x\rightarrow y\rightarrow z\rightarrow x\)，那么根据最短路图的性质，有\(d[y]=d[x]+w_1,d[z]=d[y]+w_2,d_[x]=d[y]+w_3\)，三个等式左右相加得到\(0=w_1+w_2+w_3\)，并且\(w_1,w_2,w_3\ge 0\)，故\(w_1=w_2=w_3=0\)
Code
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10,M=3e5+10;
const ll inf=1e18;
struct edges{
int v,nxt,e,p;
}E[M];
struct nedges{
int v,nxt,p;
}E_[M],nE[M];
int head[N],cnt,head_[N],cnt_,nhead[N],ncnt;
void add(int u,int v,int e,int p){
E[cnt]={v,head[u],e,p},head[u]=cnt++;
}
void add_(int u,int v,int p){
E_[cnt_]={v,head_[u],p},head_[u]=cnt_++;
}
void nadd(int u,int v,int p){
nE[ncnt]={v,nhead[u],p},nhead[u]=ncnt++;
}
int timing;
int dfn[N],low[N],st[N];
stack<int>s;
int tot;
int id[N];
void tarjan(int u){
dfn[u]=low[u]=++timing;
s.push(u),st[u]=1;
for(int i=head_[u];~i;i=E_[i].nxt){
int v=E_[i].v;
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}else if(st[v]) low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]){
tot++;
while(s.top()!=u){
id[s.top()]=tot;
st[s.top()]=0;
s.pop();
}
id[s.top()]=tot;
st[s.top()]=0;
s.pop();
}
}
ll dist[N],maxp[N];
int vis[N],deg[N];
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin>>T;
while(T--){
cnt=cnt_=ncnt=timing=tot=0;
memset(head,-1,sizeof head);
memset(head_,-1,sizeof head_);
memset(nhead,-1,sizeof nhead);
memset(E,0,sizeof E);
memset(E_,0,sizeof E_);
memset(nE,0,sizeof nE);
memset(dfn,0,sizeof dfn);
memset(low,0,sizeof low);
memset(st,0,sizeof st);
memset(vis,0,sizeof vis);
memset(id,0,sizeof id);
memset(deg,0,sizeof deg);
memset(maxp,0,sizeof maxp);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) dist[i]=inf;
for(int i=1;i<=m;i++){
int u,v,e,p;
cin>>u>>v>>e>>p;
add(u,v,e,p);
}
dist[1]=0;
priority_queue<pair<ll,int>>q;
q.push({0,1});
while(q.size()){
int u=q.top().second;
q.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=head[u];~i;i=E[i].nxt){
int v=E[i].v,e=E[i].e;
if(dist[v]>dist[u]+e){
dist[v]=dist[u]+e;
q.push({-dist[v],v});
}
}
}
cout<<dist[n]<<" ";
for(int u=1;u<=n;u++)
for(int i=head[u];~i;i=E[i].nxt){
int v=E[i].v,e=E[i].e,p=E[i].p;
if(dist[v]==dist[u]+e){
add_(u,v,p);
}
}
for(int i=1;i<=n;i++)
if(!dfn[i]) tarjan(i);
for(int u=1;u<=n;u++)
for(int i=head_[u];~i;i=E_[i].nxt){
int v=E_[i].v,p=E_[i].p;
if(id[u]!=id[v]){
nadd(id[u],id[v],p);
deg[id[v]]++;
}
}
queue<int>tq;
for(int i=1;i<=tot;i++)
if(deg[i]==0) tq.push(i);
while(tq.size()){
int u=tq.front();
tq.pop();
for(int i=nhead[u];~i;i=nE[i].nxt){
int v=nE[i].v,p=nE[i].p;
deg[v]--;
maxp[v]=max(maxp[v],maxp[u]+p);
if(!deg[v])tq.push(v);
}
}
cout<<maxp[id[n]]<<'\n';
}
}
Magic(差分约束、图论)
Problem
有\(n\)个城镇在一条直线上，从\(1\)到\(n\)标号。现在可以在某些城镇放置一个信号发送装置，假设放置这个城镇的位置为\(i\)，那么这个城镇可以向\([i-k+1,i+k-1]\)区间内的城镇发送信号。信号发送装置有信号强度，可以自定义，假设为\(power\)，那么它可以向范围内的城镇发送强度为\(power\)的信号，并且每个城镇的信号强度可以累加。现在每个城镇\(i\)要求它的信号强度不低于\(p_i\)，并且还有\(q\)个限制，每个限制给出一个\((L_i,R_i,B_i)\)，要求区间\([L_i,R_i]\)里面放置的信号发送装置的强度和不大于\(B_i\)。问是否可以在满足限制的条件下设置信号发送装置，如果可以，输出最小需要放置的装置的强度和，否则输出\(-1\)
\(1\le n\le 10000\)，\(1\le p_i\le 1000\)
Solve
记前\(i\)个城镇的放置信号发送装置的信号强度和为\(s[i]\)，那么约束条件可以表示为
- \(s_{\min(i+k-1,n)}-s_{\max(0,i-k)}\ge p_i\)，表示位置\(i\)可以被信号装置覆盖的位置的\(j\)的信号强度和要不小于\(p_i\)
- \(s_i-s_{i-1}\ge 0\)，放置的信号装置强度要大于等于\(0\)
- \(s_{R_i}-s_{L_i-1}\le B_i\)
这就是差分约束的形式，求最小等价于求最长路，判断无解等价于判断是否存在负环，转换一下等式形式后用SPFA即可
Code
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf=1e18;
const int N=1e5+10;
struct edges{
int v,nxt;
ll w;
}e[N*5];
int head[N],cnt;
void add(int u,int v,int w){
e[cnt]={v,head[u],w},head[u]=cnt++;
}
ll p[N],s[N];
ll dist[N];
bool vis[N];
int num[N];
int n;
bool spfa(int s){
for(int i=0;i<=n;i++) vis[i]=0,num[i]=0;
for(int i=0;i<=n;i++) dist[i]=-inf;
queue<int>q;
q.push(s);
dist[s]=0;
while(q.size()){
int u=q.front();
q.pop();
if(num[u]>=n) return false;
num[u]++;
vis[u]=0;
for(int i=head[u];~i;i=e[i].nxt){
int v=e[i].v;
ll w=e[i].w;
if(dist[v]<dist[u]+w){
dist[v]=dist[u]+w;
if(!vis[v]){
vis[v]=1;
q.push(v);
}
}
}
}
return true;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin>>T;
while(T--){
cnt=0;
memset(head,-1,sizeof head);
int k;
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>p[i],s[i]=s[i-1]+p[i];
for(int i=1;i<=n;i++){
add(i-1,i,0);
int l=max(1,i-k+1),r=min(n,i+k-1);
add(l-1,r,p[i]);
}
int q;
cin>>q;
while(q--){
int l,r;
ll b;
cin>>l>>r>>b;
add(r,l-1,-b);
}
if(!spfa(0))cout<<"-1\n";
else{
cout<<dist[n]<<'\n';
}
}
}
Climb Stairs(数据结构、模拟)
Problem
有\(n\)层楼，每层楼有一个怪物，血量为\(a_i\)，一开始你在第\(0\)层，并拥有\(base\)点攻击力。假设当前在第\(i\)层，每次你可以选择跳到\(i+1,i+2,\cdots,i+k\)中的某一层，即可以向上跳\(j\)层(\(1\le j\le k\))，或者向下跳一层到\(i-1\)层(\(i\ge 1\))。你可以到达一层当且仅当你的攻击力大于这一层怪物的血量，并且这一层没有访问过，每次你到达一层，你可以消灭怪物并将自己的攻击力叠加上怪物血量的数值\(a_i\)，问是否可以消灭完所有怪物。
\(1\le n,k\le 10^5\)，\(1\le a_i\le 10^9\)
Solve
跳跃方案一定是这种形式\((0,x_1,x_{1}-1,\cdots,1)\)，\((x_2,x_2-1,\cdots,x_1+1),\cdots\)，我们会从当前位置\(now\)跳到\(x\)后，继续往下跳到第一个之前跳过的地方
假设当前最高的跳过的地方是\(l\)，那么从当前位置\(now\)往上跳到一个地方\(x\)，这个\(x\)可以往下跳到\(l+1\)需要满足的条件是
\[base\ge a[x]\\ base+a[x]\ge a[x-1]\\ ...\\ base+a[x]+...+a[l+2]\ge a[l+1]\\ \]记前\(i\)层楼的怪物血量和为\(pre[i]\)，转换一下
\[base\ge a[x]=a[x]+pre[x]-pre[x]\\ base\ge a[x-1]-a[x] = a[x-1] - (pre[x] - pre[x-1])=a[x-1]+pre[x-1]-pre[x]\\ base\ge [x-2]-a[x-1]-a[x] =a[x-2] - (pre[x]-pre[x-2])=a[x-2]+pre[x-2]-pre[x]\\ ...\\ base\ge a[l+1]-a[l+2]-...-a[x] =a[l+1] - (pre[x] - pre[l+1])=a[l+1]+pre[l+1]-pre[x]\\ \]可以发现，对于区间\([l+1,x]\)里的每一项，\(a[i]+pre[i]\)是定值，而\(base\ge max(a[i]+pre[i]) -pre[x]\)，就是求一个区间最大值，用数据结构维护一下即可。每次知道这个\(x\)，就把区间里的血量累计当攻击力上即可。
Code
#include <bits/stdc++.h>
#define ll long long
#define ls rt<<1
#define rs rt<<1|1
using namespace std;
const int N=1e5+10;
ll tr[N*4],pre[N];
int a[N];
ll base;
int n,k;
void build(int rt,int l,int r){
if(l==r){
tr[rt]=pre[l]+a[l];
return;
}
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
tr[rt]=max(tr[ls],tr[rs]);
}
ll query(int rt,int L,int R,int l,int r){
if(l<=L&&R<=r){
return tr[rt];
}
ll res=0;
int mid=(L+R)>>1;
if(l<=mid) res=max(res,query(ls,L,mid,l,r));
if(r>mid) res=max(res,query(rs,mid+1,R,l,r));
return res;
}
bool check(int l,int r){
ll mx=query(1,1,n,l,r);
mx=max(0LL,mx-pre[r]);
return mx<=base;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin>>T;
while(T--){
cin>>n>>base>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
pre[i]=pre[i-1]+a[i];
}
build(1,1,n);
bool ok=true;
int l=1,r=min(k,n);
while(true){
int x=-1;
for(int i=l;i<=r;i++){
if(check(l,i)){
x=i;
break;
}
}
if(x==-1){
ok=false;
break;
}
base+=pre[x]-pre[l-1];
if(x==n) break;
r=min(n,l+k),l=x+1;
}
if(ok) cout<<"YES\n";
else cout<<"NO\n";
}
return 0;
}
Link is as bear(线性基)
Problem
给定一个长度为\(n\)的序列\(\left\{ a\right\}\)，你可以进行这样的操作若干次：选择一个区间\([l,r]\)，这个区间的数都变成\(\bigoplus_{i=l}^r a_i\)。问如果可以经过若干次操作使得所有数变成一样的，那么这个最终的数最大是多少。保证序列中至少存在一对数满足\(a_i=a_j\)
Solve
这个问题和找这个序列的最大异或子序列完全等价，线性基的板子题
证明：
首先最后相同的数，一定是原序列中若干数的异或和，其它数可以通过一系列操作变成\(0\)。现在记\(0\)表示最终这个数不贡献答案，\(1\)表示最终这个数贡献答案
- 若\(00\)，表示连续的两个数都不贡献在答案中，记是区间\([i,i+1]\)，那么对区间\([i,i+1]\)执行两次操作即可
- 若\(11\)，表示连续的两个数都贡献在答案中，记是区间\([i,i+1]\)，假设\(i+2\)个数不贡献在答案中，那么先对\([i,i+1]\)执行一次操作，在对\([i+1,i+2]\)执行两次操作。\(i-1\)不贡献在答案中同理
- 交错的情况，\(101010\)，由于题目保证了存在两个相同的数\(a_x=a_y\)
- 如果\(a_x\)和\(a_y\)均贡献或均不贡献，他们的贡献都是\(0\)，因为异或为\(0\)相当于不贡献。那么就可以根据他们旁边数的贡献性来调整自身的贡献性，就可以构造出\(00\)或\(11\)
- 如果\(a_x\)和\(a_y\)一个贡献一个不贡献，因为他们是相同的，所以也可以根据旁边的数来调整，只要保证\(a_x,a_y\)的贡献性不同即可，也可以调整出\(00\)或\(11\)
Code
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll p[100];
bool insert(ll x){
for(int i=60;i>=0;i--){
if(!(x>>i)) continue;
if(!p[i]){
p[i]=x;
return 1;
}else x^=p[i];
}
return 0;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin>>T;
while(T--){
memset(p,0,sizeof p);
int n;
cin>>n;
vector<ll>a(n+1);
for(int i=1;i<=n;i++) cin>>a[i],insert(a[i]);
ll ans=0;
for(int i=60;i>=0;i--)
if((ans^p[i])>ans) ans^=p[i];
cout<<ans<<'\n';
}
}