专栏文章

题解：P5016 [NOIP2018 普及组] 龙虎斗

LLan_yan
P5016题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqnj5na
此快照首次捕获于
2025/12/04 07:42
3 个月前
此快照最后确认于
2025/12/04 07:42
3 个月前
查看原文

思路

明显的小暴力做法。
可以两重循环来计算工兵在每个兵营里双方的气势。
时间复杂度简单 N2N^2，在 N≤105N \le 10^5 的情况下 TLE 是常有的事。
这时就要用到一个类似换根 DP 的思想。
注意到在工兵降临之前双方总气势不变，所以可以预处理双方各自的气势，这里同时将 s1s1 加入 pp 兵营方便计算。

代码

CPP
a[p]+=s1;
for(i=1;i<=n;i++)
	b[i]=abs(m-i)*a[i];
for(i=1;i<m;i++)
	tig+=b[i];
for(i=m+1;i<=n;i++)
	dra+=b[i];//计算双方总气势
然后就可以愉快统计 s1s1 名工兵在各个军营里导致的双方气势差了。

代码

CPP
for(i=1;i<m;i++)//比较工兵在龙方时的气势 
{
	if(wer>abs(tig+abs(m-i)*s2-dra))
	{
		ans=i;
		wer=abs(tig+abs(m-i)*s2-dra);
	}
}
for(i=m+1;i<=n;i++)//比较工兵在虎方时的气势 
{
	if(wer>abs(dra+abs(m-i)*s2-tig))
	{
		ans=i;
		wer=abs(dra+abs(m-i)*s2-tig);
	}
}

提示

在计算势力差时谨慎操作。
以及总势力在极端情况下会到 101410^{14}，注意安全。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...