A 花鳥風月
对于每个区间，若左边端点为 \(l\)，右边端点为 \(r\)，那这个地方能放下的线段数则为 \(\frac{r-l}{a+1}\)。
那么每进来一个坏点，只会影响它的前驱后继的区间。
那我们用 set 或者 map 维护一下前驱后继，每次加点去抵消它的区间的影响，再加回来就可以了。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a,m;
unordered_map<int,int>mp;
map<int,int>s;
signed main()
{
// freopen("in.in","r",stdin);
// freopen("ans.txt","w",stdout);
freopen("A.in","r",stdin);
freopen("A.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>a>>m;
int lstans=(n+1)/(a+1);
s[0]=1,s[n+1]++;
int cnt=0;
for(int i=1;i<=m;i++)
{
int now;cin>>now;
if(s[now])
{
cout<<lstans<<"\n";
continue;
}
int ans=lstans;
int l=(--s.lower_bound(now))->first,r=(s.upper_bound(now))->first;
ans-=(r-l)/(a+1);
ans+=(now-l)/(a+1);
ans+=(r-now)/(a+1);
s[now]=1;
cout<<ans<<"\n";
lstans=ans;
}
return 0;
}
B 九莲宝灯
非常好，我又成唐氏了。
考虑朴素式子：
\[\sum_{i\in A}\sum_{j\in B}\sum_{k\in C} \min_{t=1}^n(dis(i,t)+dis(j,t)+dis(k,t)) \]现在想一个问题，如果找一个点，到树上某三个点的距离和相等，那么这个距离一定等同于每两点距离之和除以二，即
\[\min_{t=1}^n(dis(i,t)+dis(j,t)+dis(k,t))=\frac 1 2 (dis(i,j)+dis(j,k)+dis(i,k)) \]这样就把 \(O(n^4\log n)\) 优化到 \(O(n^3\log n)\)。
然后，我们发现，在运算中，每一对数，假设为 \(a_i,b_j\) 都被加了 \(k\) 次。那就可以把每个数对进行分别的贡献计算。
\[k\times\sum_{i\in A}\sum_{j\in B}dis(i,j)+i\times \sum_{j\in B}\sum_{k\in C} dis(j,k)+j\times\sum_{i\in A}\sum_{k\in C}dis(i,k) \]这样就是 \(O(n^2\log n)\)。
然后考虑一条边的贡献，和之前一道题类似，等价于子树内的个数*字数外的个数，再乘以边权。
那直接一遍 dfs 就出来了。
要用 __int128 统计答案，然后顺便拿了最优解。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
using w=__int128;
int n;
const int N=2e5+5;
struct node{
int to,next,w;
}e[N<<1];
int head[N],cnt;
inline void add(int u,int v,int w)
{
e[++cnt].to=v,e[cnt].next=head[u],e[cnt].w=w;
head[u]=cnt;
}
bitset<N>a,b,c;
inline int read()
{
register int s=0;
register char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') s=(s<<1)+(s<<3)+(c^48),c=getchar();
return s;
}
w ansa,ansb,ansc;
int ca[N],cb[N],cc[N];
int ka,kb,kc;
void dfs(int u,int f)
{
if(a[u])ca[u]++;
if(b[u])cb[u]++;
if(c[u])cc[u]++;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(v==f) continue;
dfs(v,u);
ca[u]+=ca[v],cb[u]+=cb[v],cc[u]+=cc[v];
}
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(v==f) continue;
ansc+=(w)e[i].w*(ka-ca[v])*cb[v];
ansa+=(w)e[i].w*(kb-cb[v])*cc[v];
ansb+=(w)e[i].w*(kc-cc[v])*ca[v];
ansc+=(w)e[i].w*(kb-cb[v])*ca[v];
ansa+=(w)e[i].w*(kc-cc[v])*cb[v];
ansb+=(w)e[i].w*(ka-ca[v])*cc[v];
}
}
void write(w x)
{
if(x>9) write(x/10);
putchar(x%10+'0');
}
signed main()
{
freopen("B.in","r",stdin);
freopen("B.out","w",stdout);
n=read();
for(int i=1;i<n;i++)
{
int u=read(),v=read(),w=read();
add(u,v,w),add(v,u,w);
}
ka=read();
for(int i=1;i<=ka;i++) a[read()]=1;
kb=read();
for(int i=1;i<=kb;i++) b[read()]=1;
kc=read();
for(int i=1;i<=kc;i++) c[read()]=1;
dfs(1,0);
ansa*=(w)ka,ansb*=(w)kb,ansc*=(w)kc;
w ans=(w)ansa+ansb+ansc;
ans>>=1;
write(ans);
return 0;
}
C 石上三年
真是拿 solution 捏出来的题。。
因为他的 \(k\) 给的很小，所以解法一定和 \(k\) 有联系。
换句话说，部分分是依据 \(k\) 的递进给出的，那对正解一定又一定的提示性。
考虑一个很反常的结论：如果起点到终点的矩形中，存在不可走的点，那最短路径一定从某个不可走的点边上过去。
很显然的，如果最短路有多条，那最短路可以擦着不可走的点，也可以不走。那擦着走也就一定是最短路的一部分。
如果最短路只有一条，那一定是因为又障碍阻隔了，那贴着他走显然最优啊。
这样一来，就可以先预处理出每个障碍上下左右对于全局的最短路，然后每次询问枚举全部的障碍，把最短路分成两部分：起点到当前点+当前点到终点就好了。
预处理复杂度 \(O(4KNM)\)，询问是 \(O(QK)\)。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n,m,k,q;
const int N=2e5+5;
set<pair<int,int> >mp;
int stx,sty,edx,edy;
struct node{
int x,y,d,f;
inline bool operator<(const node &ll) const{
return ll.f<f;
}
};
map<pair<int,int>,bool>vis;
inline int man(int x,int y,int a,int b)
{
return abs(x-a)+abs(y-b);
}
const int dx[4]={0,0,1,-1};
const int dy[4]={1,-1,0,0};
namespace sub1{
void gowork()
{
while(q--)
{
cin>>stx>>sty>>edx>>edy;
cout<<man(stx,sty,edx,edy)<<"\n";
}
}
}
namespace sub2{
int x,y;
void gowork()
{
while(q--)
{
cin>>stx>>sty>>edx>>edy;
if(mp.count({stx,sty})||mp.count({edx,edy}))
{
cout<<"-1\n";continue;
}
int ans=man(stx,sty,edx,edy);
if(n==1)
{
if(stx==edx&&x==stx&&y>min(sty,edy)&&y<max(sty,edy))
cout<<"-1\n";
else cout<<ans<<"\n";
}
else if(m==1)
{
if(sty==edy&&y==sty&&x>min(stx,edx)&&x<max(stx,edx))
cout<<"-1\n";
else cout<<ans<<"\n";
}
else
{
if(stx==edx&&x==stx&&y>min(sty,edy)&&y<max(sty,edy))
ans+=2;
else if(sty==edy&&y==sty&&x>min(stx,edx)&&x<max(stx,edx))
ans+=2;
cout<<ans<<"\n";
}
}
}
}
vector<pair<int,int> >b;
int *dis[50][4][N];
void init()
{
for(int i=0;i<b.size();i++)
{
int x=b[i].first,y=b[i].second;
for(int j=0;j<4;j++)
{
int nxtx=x+dx[j],nxty=y+dy[j];
if(nxtx<1||nxty<1||nxtx>n||nxty>m) continue;
for(int k=1;k<=n;k++)
{
dis[i][j][k]=new int [m+4];
for(int o=1;o<=m;o++) dis[i][j][k][o]=1e9;
}
if(mp.count({nxtx,nxty})) continue;
queue<node>q{};
dis[i][j][nxtx][nxty]=0;
q.push({nxtx,nxty,0,0});
while(!q.empty())
{
node now=q.front();q.pop();
for(int k=0;k<4;k++)
{
node nt=now;
nt.x+=dx[k],nt.y+=dy[k];
if(nt.x<1||nt.y<1||nt.x>n||nt.y>m||mp.count({nt.x,nt.y})) continue;
if(dis[i][j][nt.x][nt.y]<1e9) continue;
dis[i][j][nt.x][nt.y]=now.d+1;
nt.d++;
q.push(nt);
}
}
}
}
}
inline bool ck(int a1,int b1,int a2,int b2)
{
if(a1>a2) swap(a1,a2);
if(b1>b2) swap(b1,b2);
for(int i=0;i<b.size();i++)
{
if(b[i].first>=a1&&b[i].first<=a2&&b[i].second>=b1&&b[i].second<=b2) return 1;
}
return 0;
}
inline int read()
{
register int s=0;
register char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') s=(s<<1)+(s<<3)+(c^48),c=getchar();
return s;
}
signed main()
{
freopen("C.in","r",stdin);
freopen("C.out","w",stdout);
n=read(),m=read(),k=read(),q=read();
for(int i=1;i<=k;i++)
{
int x=read(),y=read();
mp.insert({x,y});
sub2::x=x,sub2::y=y;
b.push_back({x,y});
}
if(k==0) return sub1::gowork(),0;
if(k==1) return sub2::gowork(),0;
if(q==1)
{
while(q--)
{
stx=read(),sty=read(),edx=read(),edy=read();
if(mp.count({stx,sty})||mp.count({edx,edy}))
{
printf("-1\n");continue;
}
vis.clear();
priority_queue<node>q{};
q.push({stx,sty,0,man(stx,sty,edx,edy)});
bool tag=0;
while(!q.empty())
{
node now=q.top();q.pop();
if(vis[{now.x,now.y}]) continue;
if(now.x==edx&&now.y==edy)
{
tag=1;
printf("%d\n",now.d);break;
}
vis[{now.x,now.y}]=1;
for(int i=0;i<4;i++)
{
node nxt=now;
nxt.x+=dx[i],nxt.y+=dy[i];
if(nxt.x<1||nxt.x>n||nxt.y<1||nxt.y>m||mp.count({nxt.x,nxt.y})) continue;
nxt.d++,nxt.f=nxt.d+man(nxt.x,nxt.y,edx,edy);
q.push(nxt);
}
}
if(!tag) printf("-1\n");
}
return 0;
}
init();
// return clock();
while(q--)
{
stx=read(),sty=read(),edx=read(),edy=read();
if(mp.count({stx,sty})||mp.count({edx,edy}))
{
printf("-1\n");continue;
}
if(!ck(stx,sty,edx,edy))
{
printf("%d\n",man(stx,sty,edx,edy));continue;
}
int ans=1e9;
for(int i=0;i<b.size();i++)
{
for(int j=0;j<4;j++)
{
int x=b[i].first+dx[j],y=b[i].second+dy[j];
if(x<1||y<1||x>n||y>m) continue;
ans=min(ans,dis[i][j][stx][sty]+dis[i][j][edx][edy]);
}
}
printf("%d\n",(ans==1e9?-1:ans));
}
return 0;
}