[递推式求解、多指针、前缀和]XATU第七届算法大赛

赛后感想

总结来看的感觉只有一个吧，就是痛心于我校的算法教学、竞赛水平的滞后。题目不难，压轴题更是我签完到之后直接A掉了，并不是我有多强，而是我校同仁总体水平确实有差距——这种差距不在于和985、211相比，而是和一些本地的、同类院校相比，差距也不可谓不大。不过幸而今年有小川、一鸣等同学的热心，希望XATU-PST能够越办越好吧。

以下过于简单的题目略过。

1、2题略

3 乐华水上梦幻乐园之拖鞋失踪案[概率论、递推式求解]

题意

有$n$个人依次找拖鞋，第$1$位会随机挑选一位幸运观众，此后每一位将：

• 拿走自己的拖鞋，若自己的拖鞋还在
• 随机挑选一位幸运观众，若自己的拖鞋不在了

问第$n$位幸运儿拿到自己拖鞋的概率是？

分析

乍一看像是错位排列，但其实关系不大。本场比赛离AK就差这一道题。赛后看题解…好像确实不难。不过这里要提一句，网上的题解全都犯了一个不影响结论的错误，以下按照正确的讲。

设$f(n)$代表第1个人坐在座位$C(1)$后第$n$个人坐到自己座位的概率，显然有以下公式：
$$f(n)=\{\begin{array}{llc}1,& \text{if C(1)=1}& \\ 0,& \text{if C(1)=n}& \\ g(C(1)),& \text{else}& \end{array}$$
含义为：若1号坐到自己的位置，那么之后的人（包括$n$）一定能坐到自己的位置；若坐到位置$n$，则$n$号一定坐不到自己的位置，否则问题转化为被1号玩家抢占位置的$C(1)$号玩家找位置。网上的所有题解这里写的都是
$$g(C(1)),\text{else}$$
但实际上除了第一位玩家，其他人只要需要开始找座位，就不存在找到自己座位的可能性，因此有：
$$g(x)=\{\begin{array}{llc}0,& \text{if C(x)=n}& \\ g(C(x)),& \text{else}& \end{array}$$
但是由于对递推式求解时这一项1能够消掉，所以这个错误并不影响答案的正确性。

由等概率原理，我们能写出$f(x)$和$g(x)$的显式公式：
$$f(n)=\frac{1+{\sum }_{i=2}^{n-1}g(i)+0}{n}$$
$$g(x)=\frac{{\sum }_{i=2}^{x-1}g(i)}{x}$$
于是有
$$g(n)=\frac{{\sum }_{i=2}^{n-1}g(i)}{n}$$
$$g(n-1)=\frac{{\sum }_{i=2}^{n-2}g(i)}{n-1}$$
两式做差得到
$$ng(n)-(n-1)g(n)=g(n-1)$$
从而
$$g(n)=g(n-1)$$
得到了这样一个意想不到的结果。
容易知道$g(2)=0.5$并且有特例$g(1)=1$，从而有答案
$$g(x)=\{\begin{array}{llc}1,& \text{if x=1}& \\ 0.5,& \text{if x>1}& \end{array}$$

代码

略。

4、5、6、7、8题略

9 Ugly Number[多指针]

题意

质因数只包含2、3、5的正整数称之为Ugly Number，求第$N$个ugly number。

做法1[BFS with heap]

先交了一发暴力，果断TLE了。那么很快想到写BFS with heap，每次从堆里取出最小的数字为第++$i$个ugly number，然后放入$i\ast 2$、$i\ast 3$、$i\ast 5$。由于每次放入和取出heap的元素量同阶，因此复杂度是$O(NlogN)$。

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<cstring>
#include<queue>
#include<set>
using namespace std;
typedef long long ll;
vector<ll> list;
set<ll> vis;
void gen(int cnt)
{
	priority_queue<ll, vector<ll>, greater<ll> > heap;
	heap.push(1);
	while (list.size() < cnt)
	{
		ll now = heap.top();
		heap.pop();
		if (vis.find(now) != vis.end())
			continue;
		vis.insert(now);
		list.push_back(now);
		heap.push(now*2);
		heap.push(now*3);
		heap.push(now*5);
	}
}
int n;
vector<ll> ask;
int maxx = 0;
int main()
{
	cin>>n;
	for (int i = 1; i <= n; i++)
	{
		ll x;
		cin>>x;
		ask.push_back(x);
		if (x>maxx)
			maxx = x;
	}
	gen(2000);
	for (auto v : ask)
		if (!v)
		cout<<0<<' ';
		else
		cout<<list[v-1]<<' ';
	return 0;
}

做法2[多指针]

赛后看到题解，了解到是来自力扣的一道原题，标准做法是多指针，时间复杂度$O(N)$，看完代码表示确实学到了。

刚听到可以用三指针的时候没太明白怎么保证每时刻找到最小值的时候还能跑遍各自乘法群的，但仔细看一下代码就明白了，以下是代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    auto m = *max_element(a.begin(), a.end());
    vector<int> dp(m + 1);
    dp[1] = 1;
    int p2 = 1, p3 = 1, p5 = 1;
    for (int i = 2; i <= m; i++)
    {
        int num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5;
        dp[i] = min(min(num2, num3), num5);
        if (dp[i] == num2)
            p2++;
        if (dp[i] == num3)
            p3++;
        if (dp[i] == num5)
            p5++;
    }

    for (int i : a)
        cout << dp[i] << ' ';
    return 0;
}

与我的第一感不同，$p_2$、$p_3$、$p_5$指向的是要被乘以2、3、5的原数字，而每次$p_2$、$p_3$、$p_5$都只+1而非跳到新的数字上，所以跑遍正整数，从而$p_2\ast 2$、$p_3\ast 3$、$p_5\ast 5$跑遍丑数群。然后每时刻找到这三个产生数字中最小的即可。

这样看来，这种多指针问题适用于解决各种迭代产生某个群的问题，只要理解指针指原数字而非产生的数字，每次指针步进而非跳到新产生的数字即可。

10 怪兽大学

题意

给定一组数 A = { a 1 , a 2 , . . . , a n } A=\{a_1,a_2,...,a_n\} A={a1​,a2​,...,an​}，求$$\sum _i\sum _{j}floor(\frac{a_i}{a_j})$$

分析

据说又是力扣搬来的（都怪我不做力扣

做完带歪榜的不是签到题的签到题之后直接把这个所谓的压轴题A了。很裸的前缀和，有人说思路不好想，其实大概是这样：

所以其实感觉还是很好想的，这个力扣困难题不要说放到ICPC了，NOIP普及组可能都是d1t1够不上的水准。代码就非常简单了：

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<cstring>
#include<set>
using namespace std;
int n;
vector<int> arr;
#define N 200005
int pre[N];
#define M 1000000007
int ans;
int range(int x, int y)
{
	return pre[y] - pre[x-1];
}
int main()
{
	cin>>n;
	for (int i  = 1; i <= n ;i++)
	{
		int tmp;
		cin>>tmp;
		arr.push_back(tmp);
	}
	for (auto v : arr)
		pre[v]++;
	for (int i = 1; i <= 200000; i++)
		pre[i] += pre[i-1];
	for (auto v : arr)
		for (int i = 1; i*v <= 100000; i++)
		{
			ans += i*range(i*v, (i+1)*v-1);
			ans %= M;
		}
	cout<<ans;
	return 0;
}

总结

一直以出题人的身份参与学校各项比赛，好久没有真正参赛了。一方面因为懒得出题，另一方面因为奖品比较好？（可惜被某人抢走了，啧），赛前还是很期待的。

不过要实话实说，赛中体验还是非常不好，因为遇到了非常多的题意不清、数据规模没给、测试数据与题给范围不符，甚至还有赛后才被我找出来的数据错误。挺拉跨的。

如果没有被错误的数据浪费的1个小时的话，唯一一道没有A掉的“阴间题”拖鞋失踪案应该有机会打表找到这个呆逼规律的。但总归还是自己太菜了，不会推公式，这一块还需要加强。

不过这道题还是非常不错的，总归是这次比赛里最像正经题目的了——虽然还是力扣扒的（你们怎么这么爱扒力扣啊喂！

跟红细胞一起进步了这么久，希望没有我在的日子里学弟们还能继续发扬光大吧。