知乎回答帖

目录

A. scx 的散文诗句

预估难度：*1200

贪心。很显然，最优的策略一定是尽可能让正数和正数分为一组，负数和负数分为一组。如果正数的数量和负数的数量均为奇数，需要最小化分组后剩下的正数和负数的绝对值。

一种想法是将正数和负数分别放进一个 vector 中并分别排序，然后分类讨论进行处理。也可以在 为奇数时往序列中加一个 （因为让最后剩下的一个数和 相乘与扔掉这个数是等价的），排序后每连续的两个数分组求和即可。

参考代码：

#include <bits/stdc++.h>

using i64 = long long;

void solve()
{
    int n;
    std::cin >> n;
    std::vector<i64> arr;
    for (int i = 1; i <= n; i++)
    {
        i64 x;
        std::cin >> x;
        arr.push_back(x);
    }
    if (n % 2)
        arr.push_back(0);
    std::sort(arr.begin(), arr.end());
    i64 ans = 0;
    for (int i = 0; i + 1 < arr.size(); i += 2)
        ans += arr[i] * arr[i + 1];
    std::cout << ans << '\n';
}

signed main()
{
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int _;
    std::cin >> _;
    while (_--)
        solve();
    return 0;
}

B. 喵喵喵

预估难度：*2000

莫比乌斯反演。记 出现的次数为 ，所求式即为 。

我们可以通过预处理前缀和快速计算

设 为数组 中最大的数，线性筛求出莫比乌斯函数时间复杂度为 ，预处理前缀和为 ，总体时间复杂度为 。

参考代码：

#include <bits/stdc++.h>

#define MAXN 100007
#define MAXM 5007
#define MOD 1000000007

typedef long long ll;

using namespace std;

ll X, Y, Z;
ll c[MAXN], a[MAXN], maxn;
ll mu[MAXN], sum_mu[MAXN], sum[MAXN];
bool isnp[MAXN];

vector<ll> prime;

void init_mu(ll limit)
{
    mu[1] = 1;
    for (ll i = 2; i <= limit; i++)
    {
        if (!isnp[i])
            prime.push_back(i), mu[i] = (-1LL + MOD) % MOD;
        for (ll p : prime)
        {
            if (p * i > limit)
                break;
            isnp[p * i] = 1;
            if (i % p == 0)
            {
                mu[i * p] = 0;
                break;
            }
            else
                mu[i * p] = (mu[i] * mu[p] % MOD + MOD) % MOD;
        }
    }
    for (ll p = 1; p <= limit; p++)
        for (ll T = p; T <= limit; T += p)
            sum_mu[T] = ((sum_mu[T] + mu[T / p] * (((X * p + Y) / Z) % MOD) % MOD) + MOD) % MOD;

    for (ll T = 1; T <= limit; T++)
        for (ll i = 1; i * T <= limit; i++)
            sum[T] = (sum[T] + i * c[T * i] % MOD + MOD) % MOD;
    for (ll i = 1; i <= limit; i++)
        sum[i] = (sum[i] * sum[i] % MOD + MOD) % MOD;
}

ll solve()
{
    ll ans = 0;
    for (ll i = 1; i <= maxn; i++)
        ans = (ans + i * i % MOD * sum[i] % MOD * sum_mu[i] % MOD + MOD) % MOD;
    return (ans % MOD + MOD) % MOD;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll n;
    cin >> n;
    cin >> X >> Y >> Z;
    for (ll i = 1; i <= n; i++)
    {
        cin >> a[i];
        c[a[i]]++;
        maxn = max(maxn, a[i]);
    }
    init_mu(maxn);
    cout << solve() << '\n';
    return 0;
}

C. 猫猫大队

预估难度：*800

签到题。按题意模拟即可。

参考代码：

#include <bits/stdc++.h>

void solve()
{
    int n;
    std::cin >> n;
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        int x;
        std::cin >> x;
        ans ^= x;
    }
    std::cout << (ans ? "miao" : "zzy") << '\n';
}

signed main()
{
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    solve();
    return 0;
}

D. 无限的韵律源点

预估难度：*1700

本题的重点在于 recent best部分，即指定下标和指定长度的区间 k 最大值，这实际上是区间 k 最值的***版。因此可以选择主席树，划分树等数据结构直接维护。由于本题固定长度的限制，实际上可以借助对顶堆，通过滑动窗口的思想直接维护。我们只需要维护两个堆，一个用来保存当前下标的 个最大值，另一个用来保存 到 大值即可。

也可以直接用set替代堆，实现两个部分的维护。

参考代码 ：

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1e6 + 10;

struct nodeA
{
    int val;
    int pos;
    nodeA(int x = 0, int y = 0) : val(x), pos(y){};
    bool operator<(const nodeA &x) const
    {
        return val > x.val;
    }
};
struct nodeB
{
    int val;
    int pos;
    nodeB(int x = 0, int y = 0) : val(x), pos(y){};
    bool operator<(const nodeB &x) const
    {
        return val < x.val;
    }
};

int a[N];

template <typename node>
struct rheap
{
    priority_queue<node> q;
    int sz;
    bool in[N];
    int sum;
    rheap()
    {
        memset(in, 0, sizeof in);
    }
    void push(int val, int pos)
    {
        if (!in[pos])
        {
            q.push(node(val, pos));
            in[pos] = 1;
            sz++;
            sum += val;
        }
    }
    node top()
    {
        node res;
        while (in[(res = q.top()).pos] == 0)
        {
            q.pop();
        }
        return res;
    }
    int get_sum()
    {
        return sum;
    }
    node pop()
    {
        node res;
        while (in[(res = q.top()).pos] == 0)
            q.pop();
        q.pop();
        sz--;
        in[res.pos] = 0;
        sum -= res.val;
        return res;
    }
    void del(int x)
    {
        if (in[x])
        {
            sz--, in[x] = 0;
            sum -= a[x];
        }
    }
    bool exist(int pos)
    {
        return in[pos];
    }
    bool empty()
    {
        return !sz;
    }
};

rheap<nodeA> Rah;
rheap<nodeB> Rbh;
rheap<nodeA> Bch;

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

    int n, b, ra, rb;
    cin >> n >> b >> ra >> rb;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }
    int ans = 0;

    for (int i = 1; i <= n; ++i)
    {
        Bch.push(a[i], i);
        if (Bch.sz > b)
        {
            Bch.pop();
        }
        if (i <= ra)
        {
            Rah.push(a[i], i);
            if (Rah.sz > rb)
            {
                nodeA tmp = Rah.pop();
                Rbh.push(tmp.val, tmp.pos);
            }
        }
        else
        {
            int del_pos = i - ra;
            if (Rah.exist(del_pos))
            {
                Rah.del(del_pos);
                if (Rbh.empty() || a[i] > Rbh.top().val)
                {
                    Rah.push(a[i], i);
                }
                else
                {
                    Rbh.push(a[i], i);
                    nodeB tmp = Rbh.pop();
                    Rah.push(tmp.val, tmp.pos);
                }
            }
            else
            {
                Rbh.del(del_pos);
                if (a[i] < Rah.top().val)
                {
                    Rbh.push(a[i], i);
                }
                else
                {
                    Rah.push(a[i], i);
                    nodeA tmp = Rah.pop();
                    Rbh.push(tmp.val, tmp.pos);
                }
            }
        }
        int res = Rah.sum + Bch.sum;
        ans = max(res, ans);
    }
    cout << ans << '\n';
    return 0;
}

参考代码 ：

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1e6 + 10;

int n, b, ra, rb;
int a[N];

signed main()
{
    cin >> n >> b >> ra >> rb;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }
    using PDI = pair<int, int>;
    multiset<PDI> sb, sra, srb;
    int ans = 0, suma = 0, sumb = 0;
    for (int i = 1; i <= n; ++i)
    {
        sb.insert({a[i], i});
        suma += a[i];
        if (sb.size() > b)
        {
            suma -= (*sb.begin()).first;
            sb.erase(sb.begin());
        }
        if (i > ra)
        {
            PDI del = {a[i - ra], i - ra};
            if (sra.count(del))
            {
                sumb -= a[i - ra];
                sra.erase(del);
                if (!srb.empty())
                {
                    PDI add = *srb.rbegin();
                    srb.erase(add);
                    sra.insert(add);
                    sumb += add.first;
                }
            }
            else if (srb.count(del))
            {
                srb.erase(del);
            }
        }
        PDI now = {a[i], i};
        sra.insert(now);
        sumb += a[i];
        if (sra.size() > rb)
        {
            PDI del = *sra.begin();
            sumb -= del.first;
            sra.erase(del);
            srb.insert(del);
        }
        ans = max(ans, suma + sumb);
    }
    cout << ans << '\n';
    return 0;
}

E. 樱花下落的速度

预估难度：*2000

一个小 trick 题。首先总结一个排列p对应的前缀 MEX 序列和后缀 MEX 的性质：前缀 MEX 序列 单调不减，且当且仅当遇到 时 ，后缀 MEX 序列单调不增，变化同理。因而我们可以通过前后缀 MEX 序列得到原排列部分固定位置的数。对于剩下不确定位置的数，它在原排列中的出现位置也是有限的：它必须出现在小于等于 的位置（ 前面），也必须出现在小于等于 的位置（ 后面），最终固定在一个区间内。可以发现，对于未知位置的数，越大的数对应的可放置区间越大。因而我们只需要从小到大放数字即可。公式为：

代表的是放置的第i个数的可放区间大小。接下来我们只需要求出每个未知位置数的 即可。可以直接在原顺序下查找每个未知位置的数右侧前缀 MEX 和左侧后缀 MEX（复杂度 ），也可以将所有原排列按照出现位置排序，根据区间的放缩得知每个数字的可放区间大小（复杂度 ）。

参考代码 ：

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1e6 + 10;
const int mod = 1e9 + 7;

void solve_n()
{
    int n;
    cin >> n;
    vector<int> o(n + 1, 0);
    for (int i = 1; i <= n; ++i)
    {
        int x;
        cin >> x;
        o[x + 1] = i;
    }
    int lef = n + 1, rig = 0;
    int result = 1;
    for (int i = 1; i <= n; ++i)
    {
        lef = min(lef, o[i]), rig = max(rig, o[i]);
        if (o[i] != lef && o[i] != rig)
        {
            (result *= (rig - lef + 1) - (i - 1)) %= mod;
        }
    }
    cout << result << '\n';
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve_n();
    return 0;
}

参考代码 ：

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1e6 + 10;
const int mod = 1e9 + 7;

void solve_nlogn()
{
    int n, cnt = 0, vis = 0;
    cin >> n;
    map<int, int> mp, lef, rig;
    set<int> cmp, need;
    vector<int> fa(n + 1, 0), fb(n + 1, 0), a(n + 1, 0);
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= n; ++i)
    {
        mp[a[i]] = 1;
        while (mp.count(cnt))
            ++cnt;
        fa[i] = cnt;
    }
    mp.clear(), cnt = 0;
    for (int i = n; i; --i)
    {
        mp[a[i]] = 1;
        while (mp.count(cnt))
            ++cnt;
        fb[i] = cnt;
    }
    a = vector<int>(n + 1, -1);
    fa.push_back(0);
    fb.push_back(0);
    mp.clear();
    for (int i = 1; i <= n; ++i)
    {
        need.insert(i - 1);
        if (fa[i] != fa[i - 1])
        {
            a[i] = fa[i - 1];
            ++vis;
            need.erase(a[i]);
        }
    }
    for (int i = n; i; --i)
    {
        if (fb[i] != fb[i + 1] && a[i] == -1)
        {
            a[i] = fb[i + 1];
            ++vis;
            need.erase(a[i]);
        }
    }
    cnt = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (a[i] == -1)
            cnt++;
        else
            mp[fa[i]] = cnt;
    }
    for (int i = n; i; --i)
    {
        cmp.insert(fa[i]);
    }
    for (auto v : need)
    {
        auto p = lower_bound(cmp.begin(), cmp.end(), v);
        rig[v] = mp[*p];
    }
    cnt = 0, mp.clear(), cmp.clear();
    for (int i = n; i; --i)
    {
        if (a[i] == -1)
        {
            cnt++;
        }
        else
            mp[fb[i]] = cnt;
    }
    for (int i = 1; i <= n; ++i)
    {
        cmp.insert(fb[i]);
    }
    for (auto v : need)
    {
        auto p = lower_bound(cmp.begin(), cmp.end(), v);
        lef[v] = mp[*p];
    }
    cnt = 0;
    int res = 1;
    for (auto v : need)
    {
        res *= (rig[v] + lef[v] + vis - n - (cnt++));
        res %= mod;
    }
    cout << res << '\n';
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve_nlogn();
    return 0;
}

F. 奕！悟！

预估难度：*2200

模拟题。

每次询问需要判断芙卡洛斯是否能在“黑——白——黑——白”的 步内判断芙卡洛斯是否能够取胜，而第 步为天理的落子阶段，对芙卡洛斯的获胜不产生影响。实际上我们只需要判断"黑——白——黑"的 步。为了叙述整洁，以下将上述 步分别称为第 步，第 步，第 步。

很显然暴力枚举每一步可能的位置会超时（因为棋盘上最多有 个落子的位置）。本题没有特意卡搜索剪枝的做法（因为验题的时候没人过这道题，导致没有搜索剪枝的样本），但是本题实际上可以在 的时间复杂度内通过（常数比较大）。

我们将连续的 个落子点，其中 个为黑子， 个没有任何棋子的情况称作黑子的即将获胜情况，这个没有任何棋子的落子点称为黑子的获胜点。类似地定义白子的即将获胜情况和白子的获胜点。

首先分析如果芙卡洛斯获胜，需要达成什么条件。最简单地，如果在第 步之前，当前局面已经存在获胜点，那么芙卡洛斯可以在第 步取胜。而如果不存在这样的局面，则需要考虑是否存在白子的获胜点，如果白子的获胜点的数量大于等于 ，芙卡洛斯就不可能获胜；如果白子的获胜点的数量等于 ，第 步落下的黑子必须落在白子的获胜点上；如果白子的获胜点的数量等于 ，第 步落下的黑子可以落在任何位置。在黑子落下第一步之后，考察当前局面上黑子的获胜点数量：如果黑子的获胜点的数量小于等于 ，那么芙卡洛斯无法获胜；否则芙卡洛斯可以获胜。

根据题意，首先需要判断当前局面天理是否已经达成获胜条件。如果没有，则继续判断芙卡洛斯是否已经达成获胜条件。如果没有，则计算黑子的获胜点：如果黑子的获胜点大于等于 ，那么芙卡洛斯可以获胜；否则判断白子的获胜点的数量，根据白子的获胜点的数量的不同分类讨论。

参考代码：

#include <bits/stdc++.h>

constexpr int N = 105 + 10;

int n, q;

char map[N][N];
int iskey[N][N]; // 黑棋可以获胜的点，下下去就五子连珠

struct opr
{
	int x, y;
	char ch, org;
};

inline bool validator(int x, int y)
{
	return 1 <= x && x <= n && 1 <= y && y <= n;
}

bool check_iskey(int x, int y, char target)
{
	if (map[x][y] == 'O')
		return 0;
	int cnt;
	cnt = 0;
	for (int d = -1; d >= -4; d--)
	{
		if (validator(x + d, y) == 0 || map[x + d][y] != target)
			break;
		cnt++;
	}
	for (int d = 1; d <= 4; d++)
	{
		if (validator(x + d, y) == 0 || map[x + d][y] != target)
			break;
		cnt++;
	}
	if (cnt >= 4)
	{
		return 1;
	}
	cnt = 0;
	for (int d = -1; d >= -4; d--)
	{
		if (validator(x, y + d) == 0 || map[x][y + d] != target)
			break;
		cnt++;
	}
	for (int d = 1; d <= 4; d++)
	{
		if (validator(x, y + d) == 0 || map[x][y + d] != target)
			break;
		cnt++;
	}
	if (cnt >= 4)
	{
		return 1;
	}
	cnt = 0;
	for (int d = -1; d >= -4; d--)
	{
		if (validator(x + d, y + d) == 0 || map[x + d][y + d] != target)
			break;
		cnt++;
	}
	for (int d = 1; d <= 4; d++)
	{
		if (validator(x + d, y + d) == 0 || map[x + d][y + d] != target)
			break;
		cnt++;
	}
	if (cnt >= 4)
	{
		return 1;
	}
	cnt = 0;
	for (int d = -1; d >= -4; d--)
	{
		if (validator(x - d, y + d) == 0 || map[x - d][y + d] != target)
			break;
		cnt++;
	}
	for (int d = 1; d <= 4; d++)
	{
		if (validator(x - d, y + d) == 0 || map[x - d][y + d] != target)
			break;
		cnt++;
	}
	if (cnt >= 4)
	{
		return 1;
	}
	return 0;
}

bool check(int len, char target)
{ // 检查是否存在连续的len个target
	for (int x = 1; x <= n; x++)
	{
		for (int y = 1; y <= n; y++)
		{
			bool isok = 1;
			for (int i = len - 1; i >= 0; i--)
			{
				if (validator(x + i, y + i) == 0)
				{
					isok = 0;
					break;
				}
				if (map[x + i][y + i] != target)
				{
					isok = 0;
					break;
				}
			}
			if (isok)
			{
				return 1;
			}
			isok = 1;
			for (int i = len - 1; i >= 0; i--)
			{
				if (validator(x + i, y - i) == 0)
				{
					isok = 0;
					break;
				}
				if (map[x + i][y - i] != target)
				{
					isok = 0;
					break;
				}
			}
			if (isok)
			{
				return 1;
			}
			isok = 1;
			for (int i = len - 1; i >= 0; i--)
			{
				if (validator(x + i, y) == 0)
				{
					isok = 0;
					break;
				}
				if (map[x + i][y] != target)
				{
					isok = 0;
					break;
				}
			}
			if (isok)
			{
				return 1;
			}
			isok = 1;
			for (int i = len - 1; i >= 0; i--)
			{
				if (validator(x, y + i) == 0)
				{
					isok = 0;
					break;
				}
				if (map[x][y + i] != target)
				{
					isok = 0;
					break;
				}
			}
			if (isok)
			{
				return 1;
			}
		}
	}
	return 0;
}

void query()
{
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			iskey[i][j] = 0;
		}
	}
	if (check(5, 'O'))
	{
		std::cout << "Pity" << '\n';
		return;
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (map[i][j] == 'X' && check_iskey(i, j, 'X'))
			{
				std::cout << "Focalors" << '\n';
				return;
			}
			if (map[i][j] == '*' && check_iskey(i, j, 'X'))
			{
				iskey[i][j] = 1;
				std::cout << "Focalors" << '\n';
				return;
			}
		}
	}
	int cnta = 0, cntb = 0;
	int keyx = 0, keyy = 0;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (map[i][j] == '*' && check_iskey(i, j, 'O'))
			{
				cnta++;
				keyx = i, keyy = j; // 必须堵白棋的点
			}
		}
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (map[i][j] == '*' && check_iskey(i, j, 'X'))
			{
				cntb++;
			}
		}
	}
	if (cnta >= 2)
	{
		std::cout << "Pity" << '\n';
		return;
	}
	if (cnta == 1)
	{
		map[keyx][keyy] = 'X';
		iskey[keyx][keyy] = 1;
		for (int i = keyx - 4; i <= keyx + 4; i++)
		{
			for (int j = keyy - 4; j <= keyy + 4; j++)
			{
				if (validator(i, j) && iskey[i][j] == 0 && check_iskey(i, j, 'X'))
					cntb++;
			}
		}
		map[keyx][keyy] = '*';
		iskey[keyx][keyy] = 0;
		if (cntb >= 2)
		{
			std::cout << "Focalors" << '\n';
			return;
		}
		std::cout << "Pity" << '\n';
		return;
	}
	else
	{
		for (int chx = 1; chx <= n; chx++)
		{
			for (int chy = 1; chy <= n; chy++)
			{
				if (map[chx][chy] != '*')
					continue;
				int add = 0;
				int keyx = chx, keyy = chy;
				map[keyx][keyy] = 'X';
				iskey[keyx][keyy] = 1;
				for (int i = keyx - 4; i <= keyx + 4; i++)
				{
					for (int j = keyy - 4; j <= keyy + 4; j++)
					{
						if (validator(i, j) && iskey[i][j] == 0 && check_iskey(i, j, 'X'))
						{
							add++;
						}
					}
				}
				map[keyx][keyy] = '*';
				iskey[keyx][keyy] = 0;
				if (cntb + add >= 2)
				{
					std::cout << "Focalors" << '\n';
					return;
				}
			}
		}
	}
	std::cout << "Pity" << '\n';
	return;
}

int opr_vec_x[5005], opr_vec_y[5005];
char opr_vec_ch[5005], opr_vec_org[5005];
int tot = 0;

void solve()
{
	std::cin >> n >> q;
	// n = 15;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			std::cin >> map[i][j];
		}
	}
	std::vector<opr> opr_vec;
	for (int i = 1; i <= q; i++)
	{
		int op;
		std::cin >> op;
		if (op == 1)
		{
			int x, y;
			char ch;
			std::cin >> x >> y >> ch;
			opr_vec.push_back({x, y, ch, map[x][y]});
			map[x][y] = ch;
		}
		else if (op == 2)
		{
			opr lstopr = opr_vec.back();
			opr_vec.pop_back();
			map[lstopr.x][lstopr.y] = lstopr.org;
		}
		else
		{
			query();
		}
	}
}

signed main()
{
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);
	solve();
	return 0;
}

G. 怯战蜥蜴

预估难度：*1200

二分+前缀和。实际上是对于每一次询问，需要给出最大的下标 ，使得 。比较自然地可以想到先用前缀和预处理，对于每一次询问二分查找合法答案即

参考代码：

#include <bits/stdc++.h>

constexpr int N = 2e5 + 10;

int a[N], pre[N];

void solve()
{
    int n, q;
    std::cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        std::cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
    }
    for (int i = 1; i <= q; i++)
    {
        int x;
        std::cin >> x;
        int l = 0, r = n, ans = 0;
        while (l <= r)
        {
            int mid = (l + r) / 2;
            if (pre[mid] > x)
                r = mid - 1;
            else
                l = mid + 1, ans = mid;
        }
        std::cout << ans << '\n';
    }
}

signed main()
{
    std::ios::sync_with_stdio(0), std::cin.tie(0);
    solve();
    return 0;
}

H. To the Moon, Finding Paradise

预估难度：*1600

题意：给你一个有向无环图，请你寻找出从起点 到终点 的一条路径，在保证路径上点权之和小于等于 的前提下，使得路径中最大的边权最小。

当看到最大边权最小这句话时，大概就知道：本题主要考察了二分。

一个显然的结论：当我们规定的路径中的最大边权越大，能够加入此路径的边就越多，能够经过的点就越多，就越有可能得到一个点权和更小的路径。由于题目保证了一定有解，因此当最大边权的上限足够大时，一定能够找到一个合法的路径。

由此可以得出该问题的单调性：最大边权的上限越大，路径的点权和越小，直到达到最小的点权和。

因此我们可以二分路径中最大边权的上限 ，然后以 为起点进行 ，遇到边权大于 的边直接忽略，最后判断一下 到 是否可达以及路径的最小点权和是否小于等于 即可。

正解的时间复杂度是 。由于校内 OJ 较为抽象的评测速度以及出题人不会如何在 DAG 上优雅地卡掉 SPFA ，本题的数据范围由 缩小至 ，放过了 Dijkstra​ 和 SPFA​ 做法。

参考代码：

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 2e5 + 10;

int n, m, cnt, s, t, c, ans;
int head[N], in[N], dis[N], a[N], tmp[N];

struct Edge
{
    int nxt, to, w;
} edge[N << 3];

void add(int from, int to, int w)
{
    edge[++cnt].nxt = head[from];
    edge[cnt].to = to;
    edge[cnt].w = w;
    head[from] = cnt;
}

bool check(int qwq)
{
    queue<int> q, q1;
    for (int i = 1; i <= n; ++i)
        in[i] = tmp[i];
    for (int i = 1; i <= n; ++i)
        dis[i] = 1e12;
    for (int i = 1; i <= n; ++i)
        if (!in[i] && i != s)
            q1.push(i);
    while (!q1.empty())
    {
        int cur = q1.front();
        q1.pop();
        for (int i = head[cur]; i; i = edge[i].nxt)
        {

            int nxt = edge[i].to;
            --in[nxt];
            if (!in[nxt])
                q1.push(nxt);
        }
    }
    dis[s] = 0;
    q.push(s);
    while (!q.empty())
    {
        int cur = q.front();
        q.pop();
        for (int i = head[cur]; i; i = edge[i].nxt)
        {
            int nxt = edge[i].to;
            --in[nxt];
            if (edge[i].w <= qwq)
                dis[nxt] = min(dis[nxt], dis[cur] + a[cur]);
            if (!in[nxt])
                q.push(nxt);
        }
    }
    return dis[t] + a[t] <= c;
}

void solve()
{
    cnt = 0;
    cin >> n >> m >> s >> t >> c;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i <= m; ++i)
    {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z);
        ++tmp[y];
    }
    ans = 1e9;
    int l = 0, r = 1e9;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (check(mid))
        {
            ans = mid;
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    cout << ans << '\n';
}

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

I. fumo星

预估难度：*1500

一个不像计算几何的计算几何。根据题意，有以下几种特殊情况：

1. 时答案为 。

2. 当存在两颗 fumo 星坐标相同时，答案为 inf（因为题目中要求经过序号不同的 fumo 星的直线数量）。

3. 当存在多点共线时需要去重（因为题目中要求不同的直线的数量）

因为数据范围比较大，以及题目中没有给出 ，所以在计算直线的时候不能直接使用点斜式，而是应该将直线化为一般式放入 set 进行比对。

参考代码：

#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 1e3 + 10;

i64 gcd(i64 a, i64 b)
{
	if (b == 0)
		return a;
	return gcd(b, a % b);
}

struct NODE
{
	i64 x, y;
} node[N];

struct LINE
{
	i64 A, B, C;
	bool operator<(LINE l) const { return A == l.A ? (B == l.B ? C < l.C : B < l.B) : A < l.A; }
};

void solve()
{
	int n;
	std::cin >> n;
	for (int i = 1; i <= n; i++)
	{
		std::cin >> node[i].x >> node[i].y;
	}
	if (n == 1)
	{
		std::cout << 0 << '\n';
		return;
	}
	std::set<LINE> s;
	for (int i = 1; i <= n; i++)
	{
		for (int j = i + 1; j <= n; j++)
		{
			if (node[i].x == node[j].x && node[i].y == node[j].y)
			{
				std::cout << "inf" << '\n';
				return;
			}
			i64 a = node[i].y - node[j].y;
			i64 b = node[j].x - node[i].x;
			i64 c = node[i].x * node[j].y - node[j].x * node[i].y;
			i64 g = gcd(gcd(a, b), c);
			a /= g, b /= g, c /= g;
			if (c < 0)
			{
				a = -a, b = -b, c = -c;
			}
			s.insert({a, b, c});
		}
	}
	std::cout << s.size() << '\n';
}

signed main()
{
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);
	solve();
	return 0;
}

J. 上春山

预估难度：*1400

题意：给你两个长度为 的序列 和 ，求：

由于每个位置对最终答案的贡献是相互独立的，因此 的相对位置是不重要的，所以可以将 由小到大排好序后再处理。

除此之外，一个很显然的贪心： 只有取得与某个 相差为 时，才有可能取得最优解。

这个贪心策略的证明如下：

假设当 时取得最优解 ，我们用 表示数组 中第一个大于 的位置。当我们继续增大 且保证 ，此时我们获得的价值 会增大，与假设不符。

由此，我们只需要按照 对每个春山进行排序，对 和 分别维护一个前缀和 与 ，接下来枚举 ，然后更新 即可。

参考代码：

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

const int N = 2e5 + 10;

int n;
i64 ans, preh[N], prea[N], h[N], a[N];

struct node
{
    i64 first, second;
    node(int x, int y)
    {
        first = x;
        second = y;
    }
    friend bool operator<(node x, node y) { return x.first < y.first; }
};

vector<node> p;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> h[i];
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        p.push_back(node(h[i], a[i]));
    }
    sort(p.begin(), p.end());
    for (int i = 1; i <= n; ++i)
    {
        preh[i] = preh[i - 1] + p[i - 1].first;
        prea[i] = prea[i - 1] + p[i - 1].second;
    }
    for (int i = 1; i <= n; ++i)
    {
        i64 cur = prea[n] - prea[i - 1] - (preh[n] - preh[i - 1] - (n - i + 1) * (p[i - 1].first - 1));
        ans = max(ans, cur);
    }
    cout << ans << '\n';
    return 0;
}

K. BiuBiuBiu

预估难度：*2400

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define MAXN 1000107
#define MAXM 400107
#define MOD 1000000007

const ll inf = 1e9;

pair<ll, ll> t1, t2, t;
ll n, m, x, y, p, q, base;

ll qpow(ll a, ll n, ll mod)
{
    ll ans = 1;
    a = a % mod;
    while (n)
    {
        if (n & 1)
            ans = (ans * a) % mod;
        n >>= 1;
        a = (a * a) % mod;
    }
    return ans;
}

ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if (!b)
    {
        x = 1;
        y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}

pair<ll, ll> sol(ll a, ll b, ll c)
{
    pair<ll, ll> ans;
    ll x, y;
    ll d = exgcd(a, b, x, y);
    if (c % d)
        ans.first = ans.second = -1;
    else
    {
        ll dx = b / d;
        x = x * (c / d);
        x = (x % dx + dx) % dx - dx;
        ans.first = dx;
        ans.second = x;
    }
    return ans;
}

pair<ll, ll> hb(pair<ll, ll> t1, pair<ll, ll> t2)
{
    pair<ll, ll> ans;
    if (t1.first == -1 || t2.first == -1)
        ans.first = ans.second = -1;
    else
    {
        if (t1.second > t2.second)
            swap(t1, t2);
        ans = sol(t1.first, t2.first, t2.second - t1.second);
        if (ans.first == -1 && ans.second == -1)
            ans.first = ans.second = -1;
        else
        {
            ans.first = ans.first * t1.first;
            ans.second = ans.second * t1.first + t1.second;
            ans.second = (ans.second % ans.first + ans.first) % ans.first - ans.first;
        }
    }
    return ans;
}

ll check_x(ll lenx)
{
    ll sum1 = (lenx + x) / n;
    ll sum2 = (lenx * q + y * p) / (m * p);
    ll time = lenx / p;
    ll add = (time - t.second) / t.first;
    return sum1 + sum2 - add;
}

ll check_y(ll leny)
{
    ll sum1 = (leny * p + x * q) / (n * q);
    ll sum2 = (leny + y) / m;
    ll time = leny / q;
    ll add = (time - t.second) / t.first;
    return sum1 + sum2 - add;
}

void solve()
{
    cin >> n >> m >> x >> y >> p >> q >> base;
    ll gcd_qp = gcd(p, q);
    p /= gcd_qp, q /= gcd_qp;
    t1 = sol(p, n, n - x);
    t2 = sol(q, m, m - y);
    t = hb(t1, t2);
    if (t.first == -1)
        t.second = 0, t.first = 9e18;
    ll ans1 = inf, ans2 = inf;
    ll l = 0, r = inf;
    while (l < r)
    {
        ll mid = (l + r) >> 1;
        if (check_x(mid * n - x) >= base + 1)
            r = mid;
        else
            l = mid + 1;
    }
    if (check_x(l * n - x) == base + 1)
        ans1 = l;

    l = 0, r = inf;
    while (l < r)
    {
        ll mid = (l + r) >> 1;
        if (check_y(mid * m - y) >= base + 1)
            r = mid;
        else
            l = mid + 1;
    }
    if (check_y(l * m - y) == base + 1)
        ans2 = l;

    if ((ans1 * n - x) * q <= (ans2 * m - y) * p)
        printf("%lld %lld\n", (ans1 * n - x) % MOD, (ans1 * n - x) % MOD * q % MOD * qpow(p, MOD - 2, MOD) % MOD);
    else
        printf("%lld %lld\n", (ans2 * m - y) % MOD * p % MOD * qpow(q, MOD - 2, MOD) % MOD, (ans2 * m - y) % MOD);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

L. 南湖少年团

预估难度：*800

签到题。按题意模拟即可。

参考代码：

#include <bits/stdc++.h>

char s1[105], s2[105];

void solve()
{
	int n, m;
	std::cin >> n >> m;
	std::cin >> s1 >> s2;
	int cnt = 0;
	for (int i = 0; i + n - 1 < m; i++)
	{
		bool isok = 1;
		for (int j = 0; j < n; j++)
		{
			if (s2[i + j] != s1[j])
			{
				isok = 0;
				break;
			}
		}
		cnt += isok;
	}
	std::cout << cnt << std::endl;
}

signed main()
{
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);
	solve();
}

M. 上帝造题的八分钟

预估难度：*1800

数位 dp。由于读入的数字超过了 long long 的范围，所以考虑使用字符串读入。dp[pos][last2][last1][c1][dx] 表示已经搜到了第 位(从高位到低位)， 位数字为 ， 位数字为 ， 表示之前的数字是否满足数位中有至少 个相邻的数字 的性质， 表示数字 的个数与数字 的差值。接下来注意转移细节即可。

参考代码：

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

#define MAX_LEN 100
#define MOD 1000000007

ll A[MAX_LEN + 2], dp[MAX_LEN + 2][11][11][2][((MAX_LEN + 2) << 1) + 2];
ll cnt, digit;
ll l, r;

ll dfs(ll pos, ll last, ll llast, bool c1, ll dx, bool limit, bool zero)
{
    if (!pos)
        return (c1 && (abs(dx - MAX_LEN - 2) >= 1));
    if (!limit && !zero && dp[pos][llast][last][c1][dx] != -1)
        return (dp[pos][llast][last][c1][dx] % MOD + MOD) % MOD;
    ll ans = 0;
    ll res = limit ? A[pos] : 9;
    for (ll i = 0; i <= res; i++)
    {
        if (zero && !i)
            ans = (ans + dfs(pos - 1, 10, 10, 0, dx, limit && (i == res), 1)) % MOD;
        else if (zero)
            ans = (ans + dfs(pos - 1, i, 10, c1, dx + (i == 0) - (i == 1), limit && (i == res), 0)) % MOD;
        else
            ans = (ans + dfs(pos - 1, i, last, c1 || (i == 3 && i == last && last == llast), dx + (i == 0) - (i == 1), limit && (i == res), 0)) % MOD;
    }
    ans = (ans % MOD + MOD) % MOD;
    if (!limit && !zero)
        dp[pos][llast][last][c1][dx] = ans;
    return ans;
}

ll f(string s)
{
    cnt = s.size();
    for (ll i = 1; i <= cnt; i++)
        A[i] = (s[cnt - i] - '0');
    return (dfs(cnt, 10, 10, 0, (MAX_LEN + 2), 1, 1) % MOD + MOD) % MOD;
}

ll check(string s)
{
    bool c1 = 0;
    for (ll i = 2; i < s.size(); i++)
        if (s[i] == '3' && s[i - 1] == '3' && s[i - 2] == '3')
            c1 = 1;
    if (!c1)
        return 0;
    ll cnt1 = 0, cnt2 = 0;
    for (ll i = 0; i < s.size(); i++)
        if (s[i] == '0')
            cnt1++;
        else if (s[i] == '1')
            cnt2++;
    if (cnt1 == cnt2)
        return 0;
    return 1;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    memset(dp, -1, sizeof(dp));
    string l, r;
    cin >> l >> r;
    printf("%lld ", ((f(r) - f(l) + check(l)) % MOD + MOD) % MOD);
}