这个周三呢，我们机房进行了一次膜你赛，本来以为自己能拿个比较不错的分数的，结果只得了 210 分，不是很理想，而且这次题也不算特别难，可以说是完全没考出自己应有的水平，所以觉得还是有必要对这次比赛进行一下总结

比赛经过

其实在周二的时候教练就已经跟我们说了要考一次试，普及组难度，再加上我觉得自己最近也学了不少新的算法和数据结构，所以就没怎么放在心上，该颓还是颓，也没有想到要去多做点题来巩固以前的知识什么的

周三下午，教练把我们带到隔壁机房开始考试，T1 本来乍一看觉得是道签到题，然后一看数据范围2632^{63}才知道不是那么简单，想了一小会后决定一边输入一边处理，然后稍微调试了一下，秒了。T2 就是道数学题，但数据范围又是2632^{63}，虽然开了 long long 还是有点不放心，但也没再多管它。T3 初看以为是区间操作，刚刚把 build 函数打完，仔细一想，不对啊，线段树做不了这道题啊，然后把前面全删了，想了一会，发现可以用队列来做这道题，于是先打了一发，后来发现有点小 bug，修了之后就去做 T4 了。T4 先是纠结了一会题目中说的“最短距离”是什么意思，跟旁边的人讨论了一下，决定先打一发最短路板子试试，然后一测大样例，本来以为输出的答案会比正确的要小的，结果居然是正确答案的三倍多，然后又是不停地调啊调，最后在有个判断那里加了一个条件，过了！于是又回去开始检查前三道题

然后，最骚的操作来了

我先是检查了 T3，仔细想了一下代码的思路，然后直接写了个数据把自己给 hack 了，又打了点补丁，把自己的数据测过了，就去检查 T2 了，然而过了一会我又想了一下，又写了组数据把自己 hack 了，然而当时只剩下不到两分钟了，再写貌似也来不及了，于是我放弃了 T3，又看了一次 T2，然后不假思索地把原来的 long long 改成了 unsigned long long，这倒是没什么问题，但我没有发现下面我在去重时为了排除第一个数字为00的情况，把要去重的两个数组的第00个下标都设成了−1-1，而且我在改时也没看一下，就直接把改过的交上去了，最终成绩100+60+0+50=210pts100+60+0+50=210\text{pts}，排名第六（老实说 T2 居然还能得6060分真的是我 rp 太好了）

题解

A. 灭火

题面

思路

签到题，根据下面非常良心的样例说明可以发现，这道题的答案就是把所有的燃烧值加起来再除以mm，如果有余数则再加一，但需要注意的是下面的毒瘤数据范围，263×202^{63}\times 20连 unsigned long long 都存不下，所以必须要在读入时进行累加并除以mm，代码和思路都很简单，没什么多说的

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
long long n,m,sum,ans;
int main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1; i<=n; i++)
	{
		long long t;
		scanf("%lld",&t);
		sum+=t%m;
		ans+=t/m+sum/m;
		sum%=m;
	}
	ans+=sum/m;
	if(sum%m)
		ans++;
	printf("%lld",ans);
	return 0;
}

B. 数学题

题面

思路

题如其名，真的就是一道数学题，首先把题面中给定的式子化简：

a−c=c−ba+b=2×ca-c=c-b\\ a+b=2\times c

由于cc的范围不受限制，所以这道题实质上就是求在给定的数中有多少个不同的组合加起来是一个偶数，我们在小学的时候学过，两个奇数加起来等于一个偶数，两个偶数加起来还是等于一个偶数，因此做法很明显，先分别统计一下这串数中有多少个不同的奇数和偶数，然后用排列组合算出答案即可，设有nn个不同的奇数，mm个不同的偶数，则答案为Cn2+Cm2C_n^2+C_m^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
#include<bits/stdc++.h>
using namespace std;
long long n,a,k1,k2,diff1,diff2,odd[100001],even[100001];
int main()
{
	scanf("%lld",&n);
	for(int i=1; i<=n; i++)
	{
		scanf("%lld",&a);
		if(a&1)
			odd[++k1]=a;
		else
			even[++k2]=a;
	}
	odd[0]=even[0]=-1;
	sort(odd+1,odd+1+k1);
	sort(even+1,even+1+k2);
	for(int i=1; i<=k1; i++)
		if(odd[i]!=odd[i-1])
			diff1++;
	for(int i=1; i<=k2; i++)
		if(even[i]!=even[i-1])
			diff2++;
	printf("%lld",diff1*(diff1-1)/2+diff2*(diff2-1)/2);
	return 0;
}

C. 吃蛋糕

题面

思路

关于这道题，其实我一开始想的是用线段树来做的，然后用一个 bitset 来储存树上的每个节点有哪些种类的蛋糕，最后用个 DFS 遍历一下整棵树，但是后来仔细一想发现这样完全是乱搞啊

其实这道题的正解是用队列，从开头开始遍历，每次先把下一个品种入队，再从队头不断弹出队列里已有的品种，直到队头的种类在队列里有且只有一种，在这个过程中用一个 num[] 记录队列里每个品种的个数，一个 sum 记录队列里有多少个不同的种类，一个 ans 记录最短的符合要求的区间，如果 sum 等于 m 了，就说明此时这个队列里所有的品种都有，就可以更新 ans 了

思路很简单，也不难想，但我在考场上只是想到要把队头的重复元素弹出，也就是不管队头元素有没有和队列内部元素重复，只管有没有和队头元素重复，这样很明显是不行的，比如这组数据：

1
2
7 5
2 1 3 4 1 2 5

如果按照我的那种方法来整的话，那么在第二个22入队的时候，由于队头是第一个22，所以会把它弹出去，但此时队列里已经有一个11了，队头的11已经不再需要，但由于我的思路只是比较队尾和队头以及队头和队头后面的元素，而此时队尾是22，队头的下一个元素是33，所以这个11并不会弹出去于是最后的答案就是66，但很明显只要不是瞎子就能看出正确答案应该是55

代码

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
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define min(a,b) a<b?a:b
using namespace std;
queue<int> q;
int n,m,a,ans=inf,sum,num[10001];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a);
		q.push(a);
		num[a]++;
		if(num[a]==1)
			sum++;
		while(num[q.front()]>1&&q.size())
		{
			num[q.front()]--;
			q.pop();
		}
		if(sum==m)
			ans=min(ans,q.size());
	}
	if(ans==inf)
		printf("no answer");
	else
		printf("%d",ans);
	return 0;
}

D. 导弹仓库

题面

思路

这道题其实就是一道最短路，建图后先跑一遍 Dijkstra，然后分几种情况进行判断即可，在点上很好判断，直接看这个点的 dis 值是否等于 l 就可以了，但在边上的情况却不是很好想，这里分三种情况来讨论（注：下文中“满足条件”指的是满足从首都到仓库的距离为 l 的条件）

情况一

（图画得丑点不要在意）

在这种情况下，Lu,c+Lv,c=Lu,vL_{u,c}+L_{v,c}=L_{u,v}，也就是说不论是经过uu点到cc还是经过vv点到cc，这个点cc都是唯一的，因此在这种情况下可以推出：

l−disu+l−disv=wu,vl-dis_u+l-dis_v=w_{u,v}

其中ll就是题面中给定的那个，wu,vw_{u,v}则是从uu到vv的边权

情况二

这种情况是指cc点不唯一，且cc只有通过uu到达才能满足条件，此时，设这条边上另一点满足条件的为c′c'，即c′c'只有通过vv点到达才能满足条件，此时，c′c'有两种情况，一种是在cc点左边，一种是在cc点右边，但由于cc点通过uu点到达已经是最短距离，如果c′c'还要在cc点的左边，那么c′c'的最短路径就不是通过vv到达，而是通过uu到达，而由于cc才是满足条件的那个点，所以c′c'就不满足条件。因此，c′c'应该在cc点的右边，此时可以得出式子：

l−disu+l−disv<wu,vl-dis_u+l-dis_v<w_{u,v}

情况三

这种情况其实与第二种类似，但cc点是通过vv到达才满足条件，相当于把上面那张图的uu和vv换了个位置，因此不再赘述，式子和上面那个是一样的，但需要注意的是，这种情况不能与第二种情况一起判断，即只要满足这个式子就直接把答案加22，因为有可能uu或vv正好就满足条件，此时虽然不是第一种情况，但这条边上还是只有一个点，而如果像上面那样的话，就会多算一个

另外还有一点，就是要判断这个点在不在这条边上，这个比较简单，首先看起点的距离是否小于 l，再看通过这条边到达终点的距离是否大于 l 就行了，式子是这样的：

disu<l,disu+wu,v>ldis_u<l,dis_u+w_{u,v}>l

把这一点理清楚后，代码其实就很简单了

对了，还有一点，由于数据范围比较大，所以普通的 Dijkstra 会 T，要加上堆优化才行

代码

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
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
#define pii pair<int,int>
#define mp(a,b) make_pair(a,b)
#define inf 0x3f3f3f3f
#define MAXN 100005
using namespace std;
struct Edge
{
	int next;
	int to;
	int w;
};
Edge edge[2*MAXN];
priority_queue< pii,vector<pii>,greater<pii> > q;
int n,m,s,l,ans,cnt,head[MAXN],dis[MAXN],b[MAXN],u[MAXN],v[MAXN],c[MAXN];
void add_edge(int u,int v,int c)
{
	cnt++;
	edge[cnt].next=head[u];
	edge[cnt].to=v;
	edge[cnt].w=c;
	head[u]=cnt;
}
int main()
{
	memset(dis,inf,sizeof(dis));
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1; i<=m; i++)
	{
		scanf("%d%d%d",&u[i],&v[i],&c[i]);
		add_edge(u[i],v[i],c[i]);
		add_edge(v[i],u[i],c[i]);
	}
	scanf("%d",&l);
	dis[s]=0;
	q.push(mp(0,s));
	while(q.size())
	{
		int u=q.top().second;
		q.pop();
		if(b[u])
			continue;
		b[u]=1;
		for(int i=head[u]; i; i=edge[i].next)
		{
			int v=edge[i].to,c=edge[i].w;
			if(dis[v]>dis[u]+c&&!b[v])
			{
				dis[v]=dis[u]+c;
				q.push(mp(dis[v],v));
			}
		}
	}
	for(int i=1; i<=n; i++)
		if(dis[i]==l)
			ans++;
	for(int i=1;i<=m;i++)
	{
		if(l-dis[u[i]]+l-dis[v[i]]==c[i]&&dis[u[i]]<l&&dis[v[i]]<l)
			ans++;
		if(l-dis[u[i]]+l-dis[v[i]]<c[i]&&l>dis[u[i]]&&l<dis[u[i]]+c[i])
			ans++;
		if(l-dis[u[i]]+l-dis[v[i]]<c[i]&&l>dis[v[i]]&&l<dis[v[i]]+c[i])
			ans++;
	}
	printf("%d",ans);
	return 0;
}

反思

这次比赛其实仔细想想，真的不算很难，即使是最后一道压轴题难度其实都不大，前面的题更是简单，连最讨厌的 dp 都没有，但我却还是考的不理想，我认为原因主要有几个：

  1. 比赛时间安排不合理，在 T1 和 T2 上花的时间过长，大约有 40-50 分钟，并不是说简单题就不该花时间，但很明显花这么多时间在前两道题上对于后两道题是很不利的，关键是这其中其实有些时间是拿去和旁边的人说话去了，这就很不好了
  2. 过于注重更高级的算法和数据结构，忽略了思维的训练，这次的题其实没有一道是真正用到了高级数据结构，几乎全都是思维题，但我还是没有拿到一个较高的分数，说明我在这方面的训练是有欠缺的
  3. 练题太少，有些一眼题没能马上看出其做法，积累的太少，必然会导致第二条的结果，如果只会做板子题，即使学再多的算法和数据结构也不可能有用的

这些是我这一段时间的 OI 学习上存在的问题，希望在最后一周里能有所改进