总结
仍然是三题打暴力，和前面的人分差巨大
最近有一段时间没有 \(A\) 题了
A. 灯
分析
首先把相同的颜色缩成一段，要求的就是总的加入的点的个数-相邻的不同颜色的点被点亮的个数
前面的部分比较好处理，直接记录一下每一种颜色有多少个点就行了
对于后面的部分，分情况考虑
当某种颜色出现的次数大于 \(\sqrt{n}\) 时
我们记录两个数组分别代表出现次数小于 \(\sqrt{n}\) 的颜色对它的贡献和出现次数大于 \(\sqrt{n}\) 的颜色对它的贡献
前面的那一部分我们可以在更新小块信息的时候顺便维护一下
后面的那一部分我们可以用一个二维数组预处理一下
当某种颜色出现的次数小于 \(\sqrt{n}\) 时
我们直接扫一遍它的 \(vector\) ，判断一下左右两边的元素能否作出贡献就行了
复杂度为 \(n\sqrt{n}\)
代码
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=1e5+5,maxm=355;
int n,m,q,a[maxn],nn,blo,jud[maxn],cnt[maxn],lk[maxm][maxm],sta[maxn],tp,ans,rk[maxn],ed[maxn];
std::vector<int> g[maxn];
int main(){
n=read(),m=read(),q=read();
for(rg int i=1;i<=n;i++) a[i]=read();
rg int lst=-1,ans=0;
for(rg int i=1;i<=n;i++){
if(a[i]==lst) continue;
else {
a[++nn]=a[i];
lst=a[i];
}
}
n=nn;
a[n+1]=0;
blo=sqrt(n);
for(rg int i=1;i<=n;i++) g[a[i]].push_back(i);
for(rg int i=1;i<=m;i++) cnt[i]=g[i].size();
for(rg int i=1;i<=m;i++) if(cnt[i]>=blo) sta[++tp]=i,rk[i]=tp;
for(rg int i=2;i<=n;i++) lk[rk[a[i]]][rk[a[i-1]]]++,lk[rk[a[i-1]]][rk[a[i]]]++;
rg int aa,bb;
for(rg int i=1;i<=q;i++){
aa=read();
if(jud[aa]){
ans-=cnt[aa];
if(rk[aa]){
ans+=ed[rk[aa]];
for(rg int i=1;i<=tp;i++){
if(jud[sta[i]]) ans+=lk[rk[aa]][i];
}
} else {
for(rg int i=0;i<g[aa].size();i++){
bb=g[aa][i];
if(jud[a[bb-1]]) ans++;
if(jud[a[bb+1]]) ans++;
ed[rk[a[bb-1]]]--;
ed[rk[a[bb+1]]]--;
}
}
jud[aa]=0;
} else {
ans+=cnt[aa];
if(rk[aa]){
ans-=ed[rk[aa]];
for(rg int i=1;i<=tp;i++){
if(jud[sta[i]]) ans-=lk[rk[aa]][i];
}
} else {
for(rg int i=0;i<g[aa].size();i++){
bb=g[aa][i];
if(jud[a[bb-1]]) ans--;
if(jud[a[bb+1]]) ans--;
ed[rk[a[bb-1]]]++;
ed[rk[a[bb+1]]]++;
}
}
jud[aa]=1;
}
printf("%d\n",ans);
}
return 0;
}
B. 十字路口
分析
设周期为 \(T\)
对于 \(m<n\) 的数据
我们把每一次的观察看作点，以同一盏红绿灯作为关系连边
设该灯在第 \(i\) 次观察时还有 \(x_i\) 秒变为绿灯，第 \(i\) 次观察的时间为 \(t_i\)
在第 \(j\) 次观察时还有 \(y_i\) 秒 变为绿灯，第 \(j\) 次观察的时间为 \(t_j\)
因为该灯变为绿灯的时刻肯定是相隔若干个周期的，所以 \(x_i+t_i \equiv x_j+t_j (mod\ T)\)
所以如果 \(x_i>x_j\)，我们由 \(i\) 向 \(j\) 建一条权值为 \(x_i-x_j\) 的边，强制规定一下边的方向
如果形成了环，那么肯定会有 \(x_1-x_2+x_2-x_3+..-x_1 \equiv 0(mod\ T)\)
所以形成的环的长度一定是 \(T\) 的倍数，我们在原图上求一个最小环就是答案了
对于 \(m \geq n\) 的数据
我们把每一盏灯看做点，以同一次观察作为关系连边
设两个红绿灯红灯变绿灯的时间分别为 \(t_i\) 和 \(t_j\)，一个距离这个时刻 \(x_i\) 秒，一个距离这个时刻 \(x_j\) 秒
则有 \(t_i-x_i \equiv t_j-x_j (mod\ T)\)
本质上还是与上面那个式子是一样的
这样我们就可以根据 \(m\) 和 \(n\) 的关系判断选择使用哪一种建边方式了
时间复杂度为 \(nm\sqrt{nm}\)
代码
#include<cstdio>
#include<algorithm>
#include<vector>
#include<iostream>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=1e5+5;
int n,m,ans=0x3f3f3f3f;
std::vector<int> g[maxn],f[maxn];
int main(){
n=read(),m=read();
rg int aa;
for(rg int i=1;i<=m;i++){
g[i].push_back(0);
for(rg int j=1;j<=n;j++){
aa=read(),g[i].push_back(aa);
}
}
if(m<=n){
for(rg int i=1;i<=m;i++){
for(rg int j=0;j<=m;j++){
f[i].push_back(0x3f3f3f3f);
}
}
for(rg int k=1;k<=n;k++){
for(rg int i=1;i<=m;i++){
for(rg int j=1;j<=m;j++){
if(g[i][k] && g[j][k] && g[i][k]>g[j][k]){
f[i][j]=g[i][k]-g[j][k];
}
}
}
}
for(rg int k=1;k<=m;k++){
for(rg int i=1;i<=m;i++){
for(rg int j=1;j<=m;j++){
f[i][j]=std::min(f[i][j],f[i][k]+f[k][j]);
}
}
}
for(rg int i=1;i<=m;i++) ans=std::min(ans,f[i][i]);
} else {
for(rg int i=1;i<=n;i++){
for(rg int j=0;j<=n;j++){
f[i].push_back(0x3f3f3f3f);
}
}
for(rg int k=1;k<=m;k++){
for(rg int i=1;i<=n;i++){
for(rg int j=1;j<=n;j++){
if(g[k][i] && g[k][j] && g[k][i]>g[k][j]){
f[i][j]=g[k][i]-g[k][j];
}
}
}
}
for(rg int k=1;k<=n;k++){
for(rg int i=1;i<=n;i++){
for(rg int j=1;j<=n;j++){
f[i][j]=std::min(f[i][j],f[i][k]+f[k][j]);
}
}
}
for(rg int i=1;i<=n;i++) ans=std::min(ans,f[i][i]);
}
if(ans==0x3f3f3f3f) ans=-1;
printf("%d\n",ans);
return 0;
}
C. 密室逃脱
分析
\(dp\) 的定义还是很巧妙的
对于一个区间 \([i,j]\) 来说，如果这个区间里的人达到了一定的数量，那么这一群人一定想去区间里的那个地方就去哪一个地方
我们定义这样的区间为一个段
设 \(f[i][j]\) 为 \(i\) 当前所在的段内有 \(j\) 个人，可以放的最多人数
当 \(j<a[i]\) 时，\(i\) 处的人无法打开门，如果在 \(i+1\) 处新加的人小于 \(b[i]\) 那就只能新开一个段了
\(f[i+1][0\sim b[i]-1]=\max(f[i+1][0\sim b[i]-1],f[i][j]+0\sim b[i]-1) j\in[0,a[i]-1]\)
如果新加的人恰好等于 \(b[i]\)，那么 \(i+1\) 处的人就可以打开门
\(f[i+1][j+b[i]]=\max(f[i+1][j+b[i]],f[i][j]+b[i]) j\in[0,a[i]-1]\)
\(如果 i+1\) 处新加的人大于 \(b[i]\) 时，我们完全可以看作 \(b[i]\) 个人开着门，剩下的人都去了 \(i\)
这种转移在上面已经体现了，没有必要再更新一次
当 \(a[i] \leq j < a[i]+b[i]\) 时，
第 \(i\) 个房间的人可以自己打开通道，但是为了保证第 \(i\) 个房间只能恰好 \(j\) 个人到达
所以第 \(i+1\) 个房间一个人不能放，没有贡献，而且必须舍弃 \(a[i]\) 个人去开门
\(f[i+1][j−a[i]]=\max(f[i+1][j-a[i]],f[i][j])\)
当 \(j \geq a[i]+b[i]\) 时，
和上面一样，但是不用留人去守门了
\(f[i+1][j]=\max(f[i+1][j],f[i][j])\)
代码
#include<cstdio>
#include<algorithm>
#include<vector>
#include<iostream>
#include<cstring>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=1e3+5,maxm=2e4+10;
int n,m,a[maxn],b[maxn],mmax,f[2][maxm];
int main(){
memset(f,~0x3f,sizeof(f));
n=read(),m=read();
for(rg int i=1;i<n;i++) a[i]=read(),b[i]=read(),mmax=std::max(mmax,std::max(a[i],b[i]));
mmax=std::max(mmax,m)*2+1;
rg int now=1;
for(rg int i=0;i<m;i++) f[1][i]=i;
for(rg int i=1;i<n;i++){
now^=1;
for(rg int j=0;j<=mmax;j++) f[now][j]=-0x3f3f3f3f;
rg int haha=-0x3f3f3f3f;
for(rg int j=0;j<a[i];j++) f[now][j+b[i]]=std::max(f[now][j+b[i]],f[now^1][j]+b[i]),haha=std::max(haha,f[now^1][j]);
for(rg int j=0;j<b[i];j++) f[now][j]=std::max(f[now^1][j],haha+j);
for(rg int j=a[i];j<a[i]+b[i];j++) f[now][j-a[i]]=std::max(f[now][j-a[i]],f[now^1][j]);
for(rg int j=a[i]+b[i];j<=mmax;j++) f[now][j]=std::max(f[now][j],f[now^1][j]);
}
rg int ans=-0x3f3f3f3f;
for(rg int i=0;i<=mmax;i++) ans=std::max(ans,f[now][i]);
printf("%d\n",ans);
return 0;
}