测试专栏 & 2023 ICPC Asia Hangzhou Regional Contest 补题记录
minstdfx
·
·
算法·理论
前言
时隔几个月又一次开始加训，还是在联合省选结束以后，感觉很多认识的 oier 都退役了，有一种物是人非的感觉。
vp 的时候打的非常难受，这里错一点那里错一点，傻逼题都挂两发罚时，看来手感还是没了，需要加训。
总体上祝大家都有个好的去处吧，也希望自己这点半桶水的菜逼实力能混进那个缩招的校队，明年再接再厉！
赛时题解
M
结论：设 p 为最低点位置，[1,n]、[1,p+1]、[p-1,n] 中必有一个是答案。
证明：答案区间必然形如 [l,r] (l<p,r>p)。
令 s_{l,r}=\sum_{i-l}^r a_i，v_{l,r}=\dfrac {\sum_{i=l}^r a_i} {r-l+1}，
则
\begin{aligned}
f(i,r)&=v_{i,r}-v_{i-1,r}(i<p)\\
&=\dfrac {(r-i+2)s_{i,r}-(r-i+1)s_{i-1,r}} {(r-i+2)(r-i+1)}\\
&=\dfrac {s_{i,r}-(r-i+1)a_{i-1}} {(r-i+2)(r-i+1)}
\end{aligned}
令 g(i,r)=f(i,r) \times(r-i+2)(r-i+1)，
\begin{aligned}
g(i,r)-g(i-1,r)&=s_{i,r}-s_{i-1,r}-(r-i+1)a_{i-1}+(r-i+2)a_{i-2}\\
&=(r-i+2)(a_{i-2}-a_{i-1})>0
\end{aligned}
因此 r 确定，g(i,r) 单调递减，故 \operatorname{sgn} f(i,r) 单调递减，故右端点确定时，平均值随左端点右移先减后增。
同理左端点确定时平均值随右端点左移先减后增。
因此只要 check 三个区间即可。
void solve()
{
scanf("%d",&n); sum[0]=0;
for(int i=1;i<=n;++i)
{
scanf("%lld",a+i);
sum[i]=sum[i-1]+a[i];
}
int i=-1;
for(int j=2;j<n;++j)
{
if(a[j]<a[j+1] && a[j]<a[j-1])
{
i=j;
break;
}
}
double ans=-1e10;
ans=max(ans,sum[n]/double(n));
ans=max(ans,sum[i+1]/double(i+1));
ans=max(ans,(sum[n]-sum[i-2])/double(n-i+2));
printf("%.9f\n",ans);
return;
}
D
容易发现第二种状态的乘积不能太大，故考虑中间的 (a_{2k}+a_{2k+1}) 构造为和为 1 的 pair，因为不能有 0，考虑构造 a_{2k}=-1,a_{2k+1}=2,a_{1}=3,a_{2n}=1-2n 即可。
void solve()
{
scanf("%d",&n);
for(int i=2;i<=2*n-2;i+=2) a[i]=-1;
for(int i=3;i<2*n;i+=2) a[i]=2;
a[1]=3;
a[2*n]=-3-2*n+4;
for(int i=1;i<2*n;++i) printf("%lld ",a[i]);
printf("%lld\n",a[2*n]);
return;
}
J
考虑先找到一条边。由于菊花图的中心点一定连着所有点，所以把每个点都至少问一次（\lceil \frac n 2\rceil 次交互），如果都没有说明是链，否则我们至少获得了一条边，假设为 (u,v)。
现在只剩下三次询问了。考虑任取一个不是 u 或者 v 的点 w，分别询问 (u,w),(v,w) 是否存在。若都不存在，则不存在一个点连着所有点，故是链。否则，两条边至多存在一条，设它是 (u',w)。再找到最后一个不同于上述三个点的点 x，询问 (u',x)。如果存在这条边，则 \operatorname{u'}>2，说明是菊花图。否则，不存在一个点连着所有点，故是链。
void solve()
{
scanf("%d",&n);
mp.clear();
int uu=-1,vv=-1;
for(int i=2;i<=n;i+=2)
if(query(i-1,i)) uu=i-1,vv=i;
if(uu==-1)
{
if(query(1,n)) uu=1,vv=n;
}
if(uu==-1) {
answer(1);
return;
}
int w=-1;
for(int i=1;i<=n;++i)
if(i!=uu && i!=vv)
{
w=i;break;
}
int fl1=query(uu,w),fl2=query(vv,w);
if(fl1)
{
int kk=-1;
for(int i=1;i<=n;++i)
if(i!=uu && i!=vv && i!=w)
{
kk=i;break;
}
if(query(uu,kk)) answer(2);
else answer(1);
}
else if(fl2)
{
int kk=-1;
for(int i=1;i<=n;++i)
if(i!=uu && i!=vv && i!=w)
{
kk=i;break;
}
if(query(vv,kk)) answer(2);
else answer(1);
}
else answer(1);
}
G
容易发现（其实看了半小时才发现）无论如何每个单位时间内蛇尾巴缩一格。所以相当于蛇的倒数第 k 格身子有必须晚于 k 时刻访问的限制的 dijkstra 板子。
#include <bits/stdc++.h>
using namespace std;
constexpr int maxn=3009,maxk=1e5+9;
typedef long long ll;
typedef unsigned long long ull;
struct node
{
int x,y;
ull w;
node(int xx=0,int yy=0,ull ww=0):x(xx),y(yy),w(ww){}
bool operator < (const node &b) const
{
return w>b.w;
}
};
int n,m,k;
char ss[maxn][maxn];
bool check(int x,int y)
{
return x>=1 && x<=n && y>=1 && y<=m && ss[x][y]=='.';
}
const int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
ull dis[maxn][maxn],vis[maxn][maxn];
int bx[maxk][2],lim[maxn][maxn];
void dijkstra()
{
priority_queue<node> pq;
memset(dis,0x3f,sizeof(dis));
dis[bx[1][0]][bx[1][1]]=0;
pq.emplace(bx[1][0],bx[1][1],0);
while(!pq.empty())
{
node pp=pq.top();pq.pop();
if(vis[pp.x][pp.y]) continue;
vis[pp.x][pp.y]=1;
for(int ii=0;ii<4;++ii)
{
int x=pp.x+dx[ii],y=pp.y+dy[ii];
if(!check(x,y)) continue;
ull fuck=max(1ull*lim[x][y],pp.w+1);
if(dis[x][y]>fuck)
{
dis[x][y]=fuck;
pq.emplace(x,y,fuck);
}
}
}
}
int main()
{
scanf("%d %d %d",&n,&m,&k);
for(int i=1;i<=k;++i)
{
scanf("%d %d",&bx[i][0],&bx[i][1]);
lim[bx[i][0]][bx[i][1]]=k-i+1;
}
for(int i=1;i<=n;++i) scanf("%s",ss[i]+1);
dijkstra();
ull res=0;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
if(dis[i][j]<0x3f3f3f3f3f3f3f3full)
res+=dis[i][j]*dis[i][j];
printf("%llu\n",res);
return 0;
}
H
由于每个 a_i 最多被加一次，如果 a_i < a_{b_i}，则 a_i 必然被加。若 a_i \ge a_{b_i} + w_{b_i}，则a_i 必不动。
考虑 a_{b_i} \leq a_i <a_{b_i}+w_{b_i}。这种情况下，
将所有的 $i$ 到 $b_i$ 连边构成基环树（而**不是链**，因为连边条件为不大于而非小于），则假设某个可能（而非必然或者必然不发生）成功的“加糖判定” $i$ 在经过数个可能成功的判定到达了必然不动的事件，则它必然判定失效。否则，若到达了必然被加的祖先，则假设距离为 $L$，它前面的事件必须一个一个发生，由于顺序完全随机，所以被加的概率为 $\dfrac 1 {L!}$。
```cpp
#include <bits/stdc++.h>
using namespace std;
constexpr int maxn=5e5+9;
typedef long long ll;
constexpr int mod=1e9+7;
int qpow(int a,int b)
{
int res=1;
for(;b;b>>=1)
{
if(b&1) res=1ll*res*a%mod;
a=1ll*a*a%mod;
}
return res;
}
int n;
int indeg[maxn],tag[maxn],dis[maxn];
vector<int> e[maxn];
int a[maxn],b[maxn],w[maxn],ans[maxn];
int fac[maxn],facinv[maxn];
void solve()
{
scanf("%d",&n);
for(int i=1;i<=n;++i) tag[i]=0,dis[i]=0,indeg[i]=0,ans[i]=0;
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=1;i<=n;++i) scanf("%d",&b[i]);
for(int i=1;i<=n;++i) scanf("%d",&w[i]);
for(int i=1;i<=n;++i)
{
if(a[b[i]]>a[i]) ans[i]=(1ll*a[i]+w[i])%mod;
else if(1ll*a[b[i]]+w[b[i]]<=a[i]) ans[i]=a[i];
else tag[i]=1,e[b[i]].emplace_back(i),++indeg[i];
}
deque<int> q;
for(int i=1;i<=n;++i)
if(!indeg[i] && ans[i]!=a[i])
{
dis[i]=1;
q.push_back(i);
}
while(!q.empty())
{
int u=q.front();q.pop_front();
tag[u]=2;
for(int v:e[u])
{
dis[v]=dis[u]+1;
if(!--indeg[v]) q.push_back(v);
}
}
for(int i=1;i<=n;++i)
if(tag[i]==0) printf("%d ",ans[i]);
else if(tag[i]==1) printf("%d ",a[i]);
else printf("%d ",(a[i]+facinv[dis[i]]*1ll*w[i]%mod)%mod);
puts("");
for(int i=1;i<=n;++i) vector<int>().swap(e[i]);
}
int main()
{
fac[0]=facinv[0]=1;
for(int i=1;i<=5e5;++i) fac[i]=1ll*fac[i-1]*i%mod;
facinv[500000]=qpow(fac[500000],mod-2);
for(int i=499999;i>=0;--i)
facinv[i]=1ll*facinv[i+1]*(i+1)%mod;
int t;
scanf("%d",&t);
while(t--)solve();
return 0;
}
```
### F
key trick：带权树上查询距离给定点集中距离一个给定点最远的点只需要查询该点集的直径端点。
证明：若给定点在直径上，显然成立。否则设直径 $(u,v)$ 上离该点 $w$ 最近的点 $k$，不妨设 $\operatorname{dis}_{w,u}\ge \operatorname{dis}_{w,v}$。若点集中存在点 $u'$ 使得 $\operatorname{dis}_{w,u}=\operatorname{dis}_{w,k}+\operatorname{dis}_{k,u}<\operatorname{dis}_{w,u'}$，则 $\operatorname{dis}_{v,u'}>\operatorname{dis}_{w,u'}-\operatorname{dis}_{k,u}+\operatorname{dis}_{w,v}>\operatorname{dis}_{u,v}$。
设最小的没在点权中出现过的**自然数**为 $h$，则 $h$ 为答案下界。
由于点权两两不同，一个点权 $w_i$ 没有在点 $u$ 距离为 $k$ 的邻域出现过，当且仅当 $\operatorname{dis}_{i,u}>k$。
把所有点按照 $w_i$ 排序，对于每个询问，二分找到最小的$w$ 使得对于所有 $w_i<w$，所有的点 $i$ 均距离 $u$ 不超过 $k$。根据我们的 key-trick，只需要预处理直径即可。
注意判断没有 $0$ 的情况。另外 lca 需要 $O(1)$ 的快速写法。~~主播线性 lca 还写挂了，乐。~~
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int maxn=5e5+9;
int n,q,w[maxn];
bool cmp(int a,int b){
return w[a]<w[b];
}
vector<pair<int,ll>> e[maxn];
int nodes[maxn];
int dep[maxn];
ll dis[maxn];
int lg[maxn<<1],dfscnt=0,st[21][maxn<<1],stpos[maxn];
void dfs(int u,int f)
{
st[0][stpos[u]=++dfscnt]=u;
for(auto[v,w]:e[u])
{
if(v==f) continue;
dis[v]=dis[u]+w;
dep[v]=dep[u]+1;
dfs(v,u);
st[0][++dfscnt]=u;
}
return;
}
int posmin(int u,int v)
{
return dep[u]>dep[v]?v:u;
}
int lca(int u,int v)
{
u=stpos[u],v=stpos[v];
if(u>v) swap(u,v);
int lgg=lg[v-u+1],res=posmin(st[lgg][u],st[lgg][v-(1<<lgg)+1]);
// printf("lca %d %d = %d\n",u,v,res);
return res;
}
ll query_dis(int u,int v)
{
return dis[u]+dis[v]-2ll*dis[lca(u,v)];
}
int zj[maxn][2],len=-1;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>q;
for(int i=1;i<=n;++i) cin>>w[i],nodes[i]=i;
sort(nodes+1,nodes+n+1,cmp);
for(int i=1,u,v,w;i<n;++i)
{
cin>>u>>v>>w;
e[u].emplace_back(v,w);
e[v].emplace_back(u,w);
}
dep[1]=0;dis[1]=0;
dfs(1,0);
lg[1]=0;
for(int i=2;i<=dfscnt;++i)
{
lg[i]=lg[i>>1]+1;
}
for(int i=1;i<=20;++i)
for(int j=1;j<=dfscnt-(1<<i)+1;++j)
st[i][j]=posmin(st[i-1][j],st[i-1][j+(1<<(i-1))]);
for(int i=1;i<=n;++i)
if(w[nodes[i]]==i-1)
len=i-1;
else break;
zj[0][0]=zj[0][1]=nodes[1];
for(int u,i=1;i<=len;++i)
{
// xian kong zhe
u=nodes[i+1];
zj[i][0]=zj[i-1][0];
zj[i][1]=zj[i-1][1];
ll dis1=query_dis(zj[i][0],u),
dis2=query_dis(zj[i][1],u),
dis3=query_dis(zj[i][0],zj[i][1]);
if(dis1>=dis2 && dis1>dis3) zj[i][1]=u;
else if(dis1<=dis2 && dis3<dis2) zj[i][0]=u;
}
while(q--)
{
int u;
ll k;
cin>>u>>k;
if(len==-1 || query_dis(nodes[1],u)>k) // there's no zero
{
cout<<0<<"\n";
continue;
}
int l=0,r=len,res=len,mid;
while(l<=r)
{
mid=(l+r)>>1;
if(query_dis(zj[mid][0],u)<=k && query_dis(zj[mid][1],u)<=k)
res=mid,l=mid+1;
else r=mid-1;
}
cout<<res+1<<"\n";
}
}
```
## 赛后补题
### A
傻逼（字面意思）大模拟，花我一个上午+下午没调出来。
大致思路就是二分查找来处理三种情况（自己多 AC 了，别人挂分了，有爆零人过题了导致扩招了）。
太耻辱了，不放代码了。