GDKOI 2024 Description & My Solution

发布时间 2024-01-11 22:20:52作者: 电乔

注:这里的 My Solution 仅提供我自己的赛时做法,可能非常乱搞。

Day 1

T1

Description

\(n\) 个怪物,\(m\) 点能量,每个怪血量为 \(a_{i}\),怪血量小于等于 \(0\) 就死亡。有三个技能:

  • 平 a:不花能量对指定怪造成 \(1\) 点伤害;
  • 战技:花 \(1\)点能量对指定怪造成 \(2\) 点伤害;
  • 大招:花 \(1\) 点能量对所有怪物造成 \(1\) 点伤害。

一开始自己先放技能,放完之后所有存活的怪对自己造成 \(1\) 点伤害。问最优策略打死所有怪最少会受到多少伤害。

My Solution

打了个 \(m=0\) 的部分分,即从小到大一个个平 a 刮。还写假了,爆零了(大悲)。

T2

Description

\(n\) 个怪血量为 \(a_{i}\)。有一个咒语,释放时需要指定初始威力 \(x\) 和初始目标 \(i\),然后对 \(i\) 号怪造成 \(x\) 点伤害,之后选定一个已打击的怪相邻的怪,对其造成 \(x-1\) 点伤害,再选定一个已打击的怪相邻的怪,对其造成 \(x-2\) 点伤害,以此类推,对每一个怪都进行打击。求一个可行的初始威力和操作序列,使得释放一次咒语即可打死所有怪。

My Solution

输出样例骗分。不出所料,爆零。

T3

Description

\(n\) 个怪血量为 \(a_{i}\),需要打死 \(m\) 个怪。但是有一个排列 \(p\),攻击 \(i\) 会使 \(p_{i}\) 受到一点伤害。排列 \(p\) 不知道,每次打完只能知道是否有怪死亡。求最差情况下最少需要多少次攻击打死 \(m\) 个怪。

My Solution

乱搞贪心。

先思考部分分。把 \(n=m\)\(m=1\),所有 \(a_{i}\) 相等的部分分都打出来了。

之后开始研究,发现两个样例对应做法:样例 #1 可以直接暴打,答案为前 \(m\) 大数和;样例 #2 可以把每个怪都打最小怪的血量下,这样肯定能打死最小的,然后再把剩下每个怪都打次小怪剩下的血量下,以此类推打死 \(m\) 个。根据贪心思想,发现如果像后者那样“每个怪都打最小怪的血量下”,那么需要最大的比最小怪的 \(n\) 倍大,否则明显前者更优。于是就能得出核心代码:

//a 数组排完序,这样方便些
if(a[n]<a[1]*n)
{
	ll as=0;//不开 long long 见祖宗
	for(int i=n;i>n-m;i--)
		as+=a[i];
}
else
{
	ll as=0;
	for(int i=1;i<=m;i++)
		as+=(a[i]-a[i-1])*(n-i+1);//剩下的血量*剩下的怪数
}

最后输出答案就好了。

但是最后被证实做法假了,正解是 dp。这个赛时以为是正解的乱搞代码挂了 \(20\) 分。

T4

Description

一个 \(n\) 个点 \(m\) 条边的无向连通图,有 \(k\) 次询问,每次询问删除 \(c_{i}\) 条给定编号的边后图是否还连通,一次询问的删边不会影响其他询问。

My Solution

一开始觉得能写并查集,但是发现打不出来。然后想着正常存图打个暴力,结果发现 vector 不好删边,前向星忘了咋写了。于是愤然不可以总司令,输出连通。

出来听人说 \(m=n-1\) 那里树删任意边都不连通,输出不连通还能骗到 \(10\) 分,然后我光荣爆零(

Day 2

T1

Description

俩人在一棵树上玩“捉迷藏”。给定一棵 \(n\) 个结点的树,俩人初始位置分别在 \(a,b\) 号结点,他们分别可以走 \([0,da],[0,db]\) 步,求最优策略下,谁在移动后可以最先和另一个人在同一结点。如果在 inf 回合后都没分出胜负,则算平局。

My Solution

猜结论,谁跑得快谁就能赢。要是先动的一步能抓到,那他也能赢。但是我没学过最短路,用 bfs 求的距离,好像写假了。

剩下咕咕咕。。。