今天是余俊言同学的生日，发 $10$ 道题目的题解祝他生日快乐。

⚠警告

这篇 blog 是用来祝余俊言同学生日快乐的。这 $10$ 道题解仅限余俊言同学参考使用。如果请不要复制到题目提交。（使用 bcoi/gfhd 网站的随机跳题 “ 手气不错 ”，只因外面的随机跳题 75% 都是不好的。实再太简单的题目就跳过了）

1. 危险的实验

这是一道贪心题。首先化学物质的位置肯定是不能改变的，要使化学物质不发生爆炸，一定要放到足够远的位置。因此，只需要遍历一遍数组，每次把距离更远的化学物质的距离直接加到 ans 里面就好了。代码：

#include <bits/stdc++.h>
using namespace std;
long long n,a[1000005],ans;
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i < n; i++)
		ans += max(a[i],a[i + 1]);
	cout << ans;
	return 0;
}

---

2. 素数问题

一想到这个我就生气。 这是很简单的递推（就是循环）题。只需要每次输入 n ，从 1 ~ n 找素数就好了。这是很简单的代码：

#include <iostream>
using namespace std;
int main()
{
    int n;
    while (1)
    {
        cin >> n;
        if (n == 0)break;
        int prt = 0;
        for (int i = 2; i < n; i++)
        {
            bool flag = 0;
            for (int j = 2; j * j <= i; j++)
            {
                if (i % j == 0)
                {
                    flag = 1;
                    break;
                }
            }
            if (!flag)prt++;
        }
        cout << prt << "\n";
    }
    return 0;
}

不过呢，这里只用一种素数筛算法（具体见素数筛）。虽然这道题目只有一个样例， $1<=n<=10000000$ 根本就体现不出来。先求出 $1到100000$ 的素数（其实还可以用前缀和优化），每次遍历就好了。代码2：

#include <iostream>
using namespace std;
bool isp[10000005];
void makep()
{
    isp[0] = isp[1] = 1;
    for (int i = 1; i <= 10000; i++)
    {
        if (!isp[i])
        {
            for (int j = i * i; j <= 100000; j += i)
            {
                isp[j] = 1;
            }
        }
    }
}
int main()
{
    makep();
    int n;
    while (1)
    {
        cin >> n;
        if (n == 0)break;
        int prt = 0;
        for (int i = 1; i <= n; i++)
        {
            if (!isp[i])prt++;
        }
        cout << prt << "\n";
    }
    return 0;
}

（后面的题目就不讲那么详细了）

---

3. GCD和LCM是好朋友(数据加强版)

暴力枚举，加上一点优化和利用数学思维。

#include <iostream>
#include <cmath>
#include <vector>
#define int long long

using namespace std;

int x, y;

int count_distinct_prime_factors(int n) {
    int cnt = 0;
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            ++cnt;
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) ++cnt;
    return cnt;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> x >> y;
    if (y % x != 0) {
        cout << 0 << '\n';
        return 0;
    }

    int k = y / x;
    int m = count_distinct_prime_factors(k);
    cout << (1LL << m) << '\n';

    return 0;
}

---

4. 孤独的鱼

桶排序。

#include <iostream>
using namespace std;
int n, a, c[10005], ans;
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a;
		c[a]++;
		if (c[a] > 1)
		{
			ans++;
			if (c[a] == 2)ans++;
		}
	}
	cout << (n - ans);
	return 0;
}

5. 阿尔法乘积

简单循环

#include <iostream>
using namespace std;

int main()
{
	int n,x,s = 1;
	cin >> n;
	while(n > 9)
	{
		x = n;s = 1;
		while(x != 0)
		{
			if((x % 10) != 0)
				s *= (x % 10);
			x /= 10;
		}
		n = s;
	}
	cout << n;
	return 0;
}

6. 高精度减法

高精度模板

#include <bits/stdc++.h>
using namespace std;
string sa,sb;

bool cmp(string sa,string sb)
{
    int alen = sa.size(),blen = sb.size();
    if (alen > blen)
        return 1;
    else if (blen > alen)
        return 0;
    return sa >= sb;
}

string myless(string sa,string sb)
{
    int a[205] = {},b[205] = {},c[205] = {};
    string sc = "";
    if (!cmp(sa,sb))
    {
        swap(sa,sb);
        sc += '-';
    }
    int alen = sa.size(),blen = sb.size(),clen = max(alen,blen);
    
    for (int i = 0; i < alen; i++)
        a[alen - 1 - i] = sa[i] - '0';
    for (int i = 0; i < blen; i++)
        b[blen - 1 - i] = sb[i] - '0';
    
    for (int i = 0; i < clen; i++)
    {
        c[i] = a[i] - b[i] + c[i];
        
        if (c[i] < 0)
        {
            c[i + 1] -= 1;
            c[i] += 10;
        }
        
    }
    bool flag = 0;
    for (int i = clen - 1; i >= 0; i--)
    {
        if (c[i] >= 1) flag = 1;
        if (flag)
            sc += to_string(c[i]);
    }
    if (sc == "") sc += '0';
    return sc;
}

int main()
{
    string sa,sb;
    cin >> sa >> sb;
    cout << myless(sa,sb);
    return 0;
}

7. 夏令营小旗手

数组问题

#include <iostream>
#include <climits>
using namespace std;
int n,x[1100],c[1100],minx = INT_MAX,maxx = INT_MIN;
int main()
{
	cin >> n >> x[1];
	c[ x[1] ]++;
	for (int i = 2; i <= n; i++)
	{
		x[i] = (x[i - 1] * 37 + 33031) % n + 1;
		c[ x[i] ]++;
		minx = min(minx,x[i]);
		maxx = max(maxx,x[i]);
	}
	int sa = 0,si = 0;
	for (int i = minx; i <= maxx; i++)
	{
		if (c[i] > sa)
		{
			sa = c[i];si = i;
		}
	}
	cout << si;
	return 0;
}

8. 方阵填数

模拟

#include <iostream>
using namespace std;
int n,a[250][250];
int main()
{
    cin >> n;
    int x = 1,y = n,k = 1;
    a[x][y] = 1;
    while (k < n * n)
    {
        while (x + 1 <= n && a[x + 1][y] == 0) a[++x][y] = ++k;
        while (y - 1 >= 1 && a[x][y - 1] == 0) a[x][--y] = ++k;
        while (x - 1 >= 1 && a[x - 1][y] == 0) a[--x][y] = ++k;
        while (y + 1 <= n && a[x][y + 1] == 0) a[x][++y] = ++k;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cout << a[i][j] << ' ';
        }
        cout << endl;
    }
}

9. 蜜蜂路线

递推

#include <bits/stdc++.h>
using namespace std;
long long m,n,f[105];
int main()
{
    cin >> m >> n;
    f[m] =  1;f[m + 1] = 1;
    for (int i = m + 2; i <= n; i++)
        f[i] = f[i - 1] + f[i - 2];
    cout << f[n];
    return 0;
}

10. 十六进制转二进制

进制转换。先转成十进制，再转成二进制。

#include <iostream>
using namespace std;
int num(char ch)
{
    if (ch >= '0' && ch <= '9')
        return ch - '0';
    else
        return (ch - 'A' + 10);
}
long long tod(int k, string n)
{
    long long w = 0,p = 1;
    for (int i = n.size() - 1; i >= 0; i--)
    {
        w += num(n[i]) * p;
        p *= k;
    }
    return w;
}
int a[10005],k = 0;
int main()
{
	string m;
    cin >> m;
    if (m == "0")
    {
        cout << 0;
        return 0;
    }
	long long n = tod(16,m);
    while (n)
    {
        a[++k] = n % 2;
        n /= 2;
    }
    for (int i = k; i >= 1; i--)
    {
        if (a[i] < 10)
            cout << a[i];
        else
            cout << char(a[i] - 10 + 'A');
    }
    return 0;
}

余俊言生日快乐