Source: JOI 2018 Final T2-T5
绝了会最后一题不会 T2，麻了。
美术展览
显然的事情：在规定 \(A\) 的值域 \([l,r]\) 之后，对于所有 \(A_i\in[l,r]\)，都选进来一定最优。
按 \(A_i\) 从小到大排序后，问题变成了选定一个区间 \([l,r]\)，其答案为 \(s_r-s_{l-1}-a_r+a_l\)，随便记个前缀 \(\max\) 就行了。
当然我场上脑抽抽了，写了棵线段树。
Code
const int N=5e5+5;
struct node {ll a,b;} t[N];
bool cmp(node x,node y) {return x.a<y.a;}
ll ma[N*4],add[N*4];
void pushadd(int p,ll v) {ma[p]+=v,add[p]+=v;}
void pushdown(int p) {if(add[p]) pushadd(p*2,add[p]),pushadd(p*2+1,add[p]),add[p]=0;}
void pushup(int p) {ma[p]=max(ma[p*2],ma[p*2+1]);}
void build(int p,int l,int r) {
if(l==r) return ma[p]=t[l].a,void();
int mid=(l+r)>>1;
build(p*2,l,mid),build(p*2+1,mid+1,r);
pushup(p);
}
void update(int p,int l,int r,int x,int y,ll v) {
if(x<=l&&r<=y) return pushadd(p,v);
int mid=(l+r)>>1;pushdown(p);
if(x<=mid) update(p*2,l,mid,x,y,v);
if(y>mid) update(p*2+1,mid+1,r,x,y,v);
pushup(p);
}
ll query(int p,int l,int r,int x,int y) {
if(x<=l&&r<=y) return ma[p];
int mid=(l+r)>>1;pushdown(p);
ll ret=0;
if(x<=mid) ret=max(ret,query(p*2,l,mid,x,y));
if(y>mid) ret=max(ret,query(p*2+1,mid+1,r,x,y));
return ret;
}
int main() {
int n=read();
FOR(i,1,n) t[i].a=read(),t[i].b=read();
sort(t+1,t+n+1,cmp);
build(1,1,n);
ll ans=0;
FOR(i,1,n) {
update(1,1,n,1,i,t[i].b);
ans=max(ans,query(1,1,n,1,i)-t[i].a);
}
printf("%lld\n",ans);
}
团子制作
我，挺脑瘫的。
注意到互斥的团子串的中间 G 对应的位置一定是对角线：
R
G
RGW
枚举每一条对角线，对对角线从上往下做 DP，具体地，设 \(f_{i,0/1/2}\) 表示第 \(i\) 行 不选/选横的/选竖的 的答案，注意这里的横竖以 G 为中心。
做到 \(O(nm)\)。
Code
const int N=3005;
char ch[N][N];
int f[N][3];
int main() {
int n=read(),m=read();
FOR(i,1,n) scanf("%s",ch[i]+1);
int ans=0;
FOR(s,2,n+m) {
memset(f,0,sizeof f);
int sum=0,i,j;
for(i=max(1,s-m),j=s-i;i<=n&&j;i++,j--) {
f[i][0]=max({f[i-1][0],f[i-1][1],f[i-1][2]});
if(ch[i][j]=='G') {
if(ch[i-1][j]=='R'&&ch[i+1][j]=='W') f[i][1]=max(f[i][1],max(f[i-1][0],f[i-1][1])+1);
if(ch[i][j-1]=='R'&&ch[i][j+1]=='W') f[i][2]=max(f[i][2],max(f[i-1][0],f[i-1][2])+1);
}
sum=max({sum,f[i][0],f[i][1],f[i][2]});
}
ans+=sum;
}
printf("%d\n",ans);
}
月票购买
求出 \(S\to T\) 的最短路 DAG，考虑 \(U,V\) 的最短路的变化：
- 不经过最短路 DAG，此时的答案可以直接预处理出来。
- 经过最短路 DAG，若最短路 DAG 上存在 \(S\to a\to b\to T\)，则有一种路径就是 \(U\to a\to b\to T\)，以及 \(T\to a\to b\to U\)，拓扑排序 DP 即可。
总时间复杂度 \(O(n\log n)\)。
Code
const int N=1e5+5;
vector<pii> G[N];
vi G2[N];
int n,u[2*N],v[2*N],w[2*N],deg[N];
ll dS[N],dT[N],dU[N],dV[N],f1[N],f2[N];
void dijskra(int s,ll *dis) {
FOR(i,1,n) dis[i]=1e18;
priority_queue<pair<ll,int> > pq;
pq.push({0,s}),dis[s]=0;
while(sz(pq)) {
int u=pq.top().se;
ll d=pq.top().fi;
pq.pop();
if(-d!=dis[u]) continue;
for(pii i:G[u]) {
int v=i.fi,d=i.se;
if(dis[u]+d<dis[v]) dis[v]=dis[u]+d,pq.push({-dis[v],v});
}
}
}
int main() {
n=read();int m=read(),S=read(),T=read(),U=read(),V=read();
FOR(i,1,m) {
u[i]=read(),v[i]=read(),w[i]=read();
G[u[i]].pb({v[i],w[i]}),G[v[i]].pb({u[i],w[i]});
}
dijskra(S,dS),dijskra(T,dT),dijskra(U,dU),dijskra(V,dV);
ll ans=dU[V];
FOR(i,1,m) {
if(dS[u[i]]+w[i]+dT[v[i]]==dS[T]) G2[u[i]].pb(v[i]),deg[v[i]]++;
if(dS[v[i]]+w[i]+dT[u[i]]==dS[T]) G2[v[i]].pb(u[i]),deg[u[i]]++;
}
queue<int> q;
q.push(S);
FOR(i,1,n) f1[i]=dU[i],f2[i]=dV[i];
while(sz(q)) {
int u=q.front();q.pop();
ans=min({ans,f1[u]+dV[u],f2[u]+dU[u]});
for(int v:G2[u]) {
f1[v]=min(f1[v],f1[u]),f2[v]=min(f2[v],f2[u]);
deg[v]--;
if(deg[v]==0) q.push(v);
}
}
printf("%lld\n",ans);
}
毒蛇越狱
听说过套路 trick 就薄纱了。
首先看到这个题，有三个暴力：
- 暴力枚举每个
?，然后累加贡献。 - 预处理 \(f_S=\sum_{S'\subseteq S}c_S\)，将每个
?看成1，然后对原本的1容斥成1或者0。 - 预处理 \(f_S=\sum_{S\subseteq S'}c_S\)，将每个
?看成0，然后对原本的0容斥成1或者0。
你发现三个暴力分别与 \(c_q,c_1,c_2\) 相关，所以取最小的一个即可做到 \(O(q2^{n/3})\)。
Code
const int MS=1<<21;
int L,Q,f[MS],g[MS];
char c[MS],q[22];
int ans=0;
void dfs1(int dep,int v) {
if(dep==L) return ans+=c[v]-'0',void();
if(q[dep]!='?') {
v|=((q[dep]-'0')<<dep);
return dfs1(dep+1,v);
}
dfs1(dep+1,v);
v|=(1<<dep);
dfs1(dep+1,v);
}
void dfs2(int dep,int v,int z) {
if(dep==L) return ans+=z*g[v],void();
if(q[dep]!='0') {
if(q[dep]=='1') v|=1<<dep;
return dfs2(dep+1,v,z);
}
dfs2(dep+1,v,z);
v|=1<<dep;
dfs2(dep+1,v,-z);
}
void dfs3(int dep,int v,int z) {
if(dep==L) return ans+=z*f[v],void();
if(q[dep]!='1') {
if(q[dep]=='?') v|=1<<dep;
return dfs3(dep+1,v,z);
}
dfs3(dep+1,v,-z);
v|=1<<dep;
dfs3(dep+1,v,z);
}
int main() {
scanf("%d %d",&L,&Q);
scanf("%s",c);
FOR(i,0,(1<<L)-1) f[i]=g[i]=c[i]-'0';
FOR(i,0,L-1) FOR(j,0,(1<<L)-1) if(!(j&(1<<i))) f[j|(1<<i)]+=f[j];
FOR(i,0,L-1) FOR(j,0,(1<<L)-1) if(j&(1<<i)) g[j^(1<<i)]+=g[j];
FOR(i,1,Q) {
int cq=0,c0=0,c1=0;
scanf("%s",q);
FOR(j,0,L-1) {
if(q[j]=='?') cq++;
if(q[j]=='0') c0++;
if(q[j]=='1') c1++;
}
reverse(q,q+L);
int mc=min(cq,min(c0,c1));
ans=0;
if(mc==cq) dfs1(0,0);
else if(mc==c0) dfs2(0,0,1);
else dfs3(0,0,1);
printf("%d\n",ans);
}
}