0%

学军网络赛A-D题解

学军网络赛A-D 题解

补题链接

注:左侧可以跳转

T1.核酸检测

题意概括:没啥好概括的

解:最小的花费是$n\times (n+1)-1$
考虑构造一种方案即可证明。
对于$n$为奇数的情况,可以这样构造:(从左下角开始)A2.jpg

方框内的两行为一组,自下而上摆即可。注意最上面一行特殊处理。

对于$n$为偶数的情况,可以旋转一下,也可以从左上角开始类似构造。时间复杂度$\mathcal O(n^2)$

代码,比较简单就不写注释了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

/**********/
int main()
{
ll n=read();
if(n==1){puts("0"),puts("1 1");return 0;}
printf("%lld\n",n*(n+1)-1);
if(n&1)
{
for(ll i=n;i>1;i-=2)
{
for(ll j=1;j<=n+1;++j)
if(j&1)printf("%lld %lld\n",i,j);
else printf("%lld %lld\n",i-1,j);
for(ll j=n+1;j;--j)
if(j&1)printf("%lld %lld\n",i-1,j);
else printf("%lld %lld\n",i,j);
}
for(ll j=1;j<=n+1;++j)printf("%lld %lld\n",1,j);
}
else
{
for(ll j=1;j<=n-1;j+=2)
{
for(ll i=1;i<=n;++i)
if(i&1)printf("%lld %lld\n",i,j);
else printf("%lld %lld\n",i,j+1);
for(ll i=n;i;--i)
if(i&1)printf("%lld %lld\n",i,j+1);
else printf("%lld %lld\n",i,j);
}
for(ll i=1;i<=n;++i)printf("%lld %lld\n",i,n+1);
}
return 0;
}

T2.齐心抗疫

题意:给一棵树,有点权。定义链$u->v(w(u)\le w(v))$的价值为 $dist(u,v)\times w(v)$ ($dist(u,v)$表示$(u,v)$的距离,即链长)

求最大价值。$n\le 5\times 10^4$

解:设点对$(u,v)满足$$w(u)\le w(v)$.考虑有

也就是忽略$w(u)\le w(v)$的限制,答案不变。

接下来就有各种做法:换根dp,点分,贪心+直径······

讲一下换根dp的做法。定义$f(u)$表示$u$能到达的最远距离(即$\max_v{dist(u,v)}$)。这是个经典问题,可以用换根dp在$\mathcal O(n)$时间内求解所有$f(u)$。

而答案$=\max_u{f(u)\times w(u)}$.时间复杂度$\mathcal O(n)$
代码,比较经典就不写注释了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/**********/
#define MAXN 200011
struct Edge
{
ll v,w,nxt;
}e[MAXN];
ll cnt=0,last[MAXN];
void adde(ll u,ll v,ll w)
{
++cnt;
e[cnt].v=v;e[cnt].w=w;
e[cnt].nxt=last[u],last[u]=cnt;
}

ll fa[MAXN],fw[MAXN],len[MAXN],l1[MAXN],l2[MAXN],ans[MAXN];
void dfs1(ll u)
{
len[u]=0;
for(ll i=last[u];i;i=e[i].nxt)
{
ll v=e[i].v;
if(v==fa[u])continue;
fa[v]=u;
dfs1(v);
if(len[v]+e[i].w>len[l1[u]]+fw[l1[u]])l2[u]=l1[u],l1[u]=v,len[u]=len[v]+e[i].w;
else if(len[v]+e[i].w>len[l2[u]]+fw[l2[u]])l2[u]=v;
}
}
void dfs2(ll u,ll fal=0)
{
ans[u]=max(fal,len[u]);
for(ll i=last[u];i;i=e[i].nxt)
{
ll v=e[i].v;
if(v==fa[u])continue;
if(l1[u]==v)
{
dfs2(v,max(fal+e[i].w,len[l2[u]]+fw[l2[u]]+e[i].w));
}
else dfs2(v,max(fal+e[i].w,len[l1[u]]+fw[l1[u]]+e[i].w));
}
}
ll a[MAXN];
int main()
{
ll n=read();
for(ll i=1;i<=n;++i)a[i]=read(),fw[i]=1;
for(ll i=1;i<n;++i)
{
ll u=read(),v=read();
adde(u,v,1),adde(v,u,1);
}
dfs1(1),dfs2(1);
ll res=-INF;
for(ll i=1;i<=n;++i)umax(res,a[i]*ans[i]);
printf("%lld",res);
return 0;
}

T3.病毒研究

题意:给一个序列$a_{1…n}(a_0=0)$.有一种病毒,活性为$[1,a_n]$中的随机整数。设病毒活性为$x$,若$i$满足$a_{i-1}<x\le a_i$,则可知病毒在状态$i$.(只能知道病毒的状态,不能知道具体活性,否则就是弱智题)

有$m$种操作$(v_i,w_i)$,可以花费$v_i$的代价将病毒活性减少$w_i$.当病毒活性$\le 0$时会死亡。 (每个操作可以使用任意次;每次操作之后都可以查询病毒的状态)

求让病毒处于状态1的最小期望代价乘$a_n$的值。如果不能保证病毒最后一定能处于状态1,则输出-1。

$m\le a_n\le 2000,a$严格递增.

这题太神,赛时WA到自闭

解:区间dp。令$dp(l,r)$表示病毒活性在区间$[l,r]$内的最小期望代价乘$r-l+1$的值.

  • 当$l,r$状态相同:

    • 若状态为1,$dp(l,r)=0$
    • 否则,枚举所有操作转移。注意只能考虑$w_i<l$的操作,避免病毒死亡。
  • 否则,必然由若干段状态相同的区间构成。求这些区间的和即可。

用记忆化搜索实现,$dp(1,a_n)$即为答案。为INF时答案即为-1。
时间复杂度显然$\mathcal O(a_n^2m)$,有62pts。

若区间$[l,r]$满足$l,r$状态不同,则称$[l,r]$为“有效区间”。
注意到当$l,r$状态相同且不为1时,可能要连续操作多次才能到达“有效区间”。于是可以先预处理一下完全背包,处理出$f(i)$表示将病毒活性减少$i$的最小代价。然后强制让其一步到达“有效区间”(或状态1)。
另外,求解“有效区间”时,只有边缘两段是“有效区间”,中间都不是。预处理出每一段的代价的前缀和即可$\mathcal O(1)$求出中间部分的代价之和。

看似只是常数上的优化,但由于求解有效区间时只递归求解边缘两段,所以需要枚举操作的区间皆形如$[x,a_i],[a_{i-1}+1,x]$($x$的状态是$i$),只有$2a_n$个,所以这样的时间复杂度是$\mathcal O(a_nm+a_n^2)$,可以通过。

代码,写了点注释。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**********/
#define MAXN 2011
ll dp[MAXN][MAXN],a[MAXN],status[MAXN],n,m;//status[x]表示x所处的状态
ll f[MAXN],sum[MAXN];
ll mdfs(ll l,ll r)
{
if(dp[l][r]<INF)return dp[l][r];//记忆化(初值为INF)
ll &cur=dp[l][r];
if(status[l]==status[r])//不是“有效区间”
{
if(status[l]==1)return cur=0;
for(ll i=1;i<l;++i)
if(f[i]<INF&&(status[r-i]==1||status[l-i]!=status[r-i]))umin(cur,mdfs(l-i,r-i)+f[i]*(r-l+1));//强行到达有效区间或状态1
return cur;
}
cur=mdfs(l,a[status[l]])+(sum[status[r]-1]-sum[status[l]])+mdfs(a[status[r]-1]+1,r);//只递归求解边缘两段,中间用前缀和优化
return cur;
}
int main()
{
ll t=read();
while(t--)
{
n=read(),m=read();
for(ll i=1;i<=n;++i)
{
a[i]=read();
for(ll j=a[i-1]+1;j<=a[i];++j)status[j]=i;
}
for(ll i=1;i<=a[n];++i)f[i]=INF;
f[0]=0;
for(ll i=1;i<=m;++i)//完全背包预处理
{
ll v=read(),w=read();
for(ll j=w;j<=a[n];++j)
umin(f[j],f[j-w]+v);
}
for(ll i=1;i<=a[n];++i)
for(ll j=i;j<=a[n];++j)dp[i][j]=INF;
for(ll i=1;i<=n;++i)//预处理前缀和
{
sum[i]=sum[i-1]+mdfs(a[i-1]+1,a[i]);
}
printf("%lld\n",mdfs(1,a[n])>=INF?-1ll:mdfs(1,a[n]));
}
return 0;
}

T4.抗疫斗争

题意:有一个博弈游戏:有$m$颗石子,A先手,B后手。每个人取的石子数量不能超过前者所取的数量。取走最后石子者胜。令$h(i)$表示A为了必胜,第一次至少取的石子数量。

令$f(i)=\sum_{m|i}h(m)$,求$\sum_{i=1}^nf(i)$ .

95%数据满足$n\le 5\times 10^{13}$;100%数据满足$1\le n\le 10^{15}$

解:首先要高效求解$h(x)$.注意到当$x$为奇数,$h(x)=1$.当$x$为偶数时,取奇数的一方必败(因为给对方剩下了奇数颗)。

也就是

这玩意,就是lowbit啊。

又因为

然后就能$\mathcal O(n)$做了。

进一步优化:

算法一:(我在比赛时的做法)

这个式子一看就很能整除分块。考虑计算$lowbit(i)$的区间和。显然$[1,i]$中偶数有$\lfloor\frac{i}{2}\rfloor$个,其中4的倍数又有$\lfloor\frac{i}{4}\rfloor$个······所以$S(i)=\sum_{j=1}^ilowbit(j)$可以这样在$\mathcal O(\log n)$时间内求解:

1
2
3
4
5
6
7
8
9
10
11
12
const ll mod=998244353;
ll calc(ll n)//计算S(n)
{
ll ans=0,cur=1;
while(n)
{
ans=(ans+(n-(n>>1))*cur)%mod;
n>>=1;
cur<<=1;
}
return ans%mod;
}

总时间复杂度是$\mathcal O(\sqrt n\times\log n)$然后就能95pts了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**********/
const ll mod=998244353;
ll calc(ll n)......
int main()
{
ll n=read(),ans=0,l,r;
for(l=1;l<=n;l=r+1)
{
r=n/(n/l);
//ans=(ans+(calc(r)-calc(l-1))*(n/l))%mod;
ans=(ans+calc(r)*(n/l-n/(r+1))%mod)%mod;
//这两种写法都正确,但显然后者常数约为前者的1/2
}
printf("%lld",ans);
return 0;
}

杨爷:卡卡常就能A了啊(我:????我能说我95pts都是卡过常的吗)

算法二:

枚举$lowbit(i)$的取值。记$g(n)=\sum_{i=1}^n \lfloor\frac{n}{i}\rfloor $(显然$g(n)$是可以$\mathcal O(\sqrt n)$求的)

另外,求$g(n)=\sum_{i=1}^n \lfloor\frac{n}{i}\rfloor $我一开始用整除分块被卡常了,有另外一个神仙科技可以求,见代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**********/
const ll mod=998244353;
ll upd(ll x)
{
return (x%mod+mod)%mod;
}
ll g(ll n)//O(sqrt n)求g(n)
{
ll t=sqrt(n),sum=0;
for(ll i=1;i<=t;++i)sum+=n/i;
return upd(2*sum-t*t);
}

int main()
{
ll n=read(),ans=g(n);
for(ll k=1;(1ll<<k)<=n;++k)
ans=(ans+(1ll<<(k-1))*g(n/(1ll<<k)))%mod;
printf("%lld",ans);
return 0;
}

为什么没有E?这。。官方题解说的动态半平面交和凸包二分我都不会啊

End.