A – 人类基因组

这套题全都是暴力出奇迹系列。

我们枚举一个端点，然后判断以这个点为右端点是否能计入答案。我们把序列做个前缀和\(prefix[]\)，然后发现计入答案的条件当且仅当\(prefix[i – n]\)小于等于\([i – n + 1, i]\)的最小值。这样可以保证所有的前缀都能为非负数。

然后用 sb 线段树搞下就行了，太特么傻逼了。

// A.cpp
#include <bits/stdc++.h>
#define ll long long
#define mid ((l + r) >> 1)
#define lson (p << 1)
#define rson (lson | 1)

using namespace std;

const int MAX_N = 2e6 + 200;

ll tree[MAX_N << 2], tag[MAX_N << 2], prefix[MAX_N], n;

void pushdown(int p)
{
    if (tag[p] != 0)
    {
        tag[lson] += tag[p], tree[lson] += tag[p];
        tag[rson] += tag[p], tree[rson] += tag[p];
        tree[p] = min(tree[lson], tree[rson]);
        tag[p] = 0;
    }
}

void pushup(int p) { tree[p] = min(tree[lson], tree[rson]); }

void build(int l, int r, int p)
{
    if (l == r)
        return (void)(tree[p] = prefix[l]);
    build(l, mid, lson), build(mid + 1, r, rson);
    pushup(p);
}

void update(int ql, int qr, int l, int r, ll val, int p)
{
    if (ql <= l && r <= qr)
        return (void)(tree[p] += val, tag[p] += val);
    pushdown(p);
    if (ql <= mid)
        update(ql, qr, l, mid, val, lson);
    if (mid < qr)
        update(ql, qr, mid + 1, r, val, rson);
    pushup(p);
}

ll query(int ql, int qr, int l, int r, int p)
{
    if (ql <= l && r <= qr)
        return tree[p];
    pushdown(p);
    ll ans = 1e18;
    if (ql <= mid)
        ans = min(ans, query(ql, qr, l, mid, lson));
    if (mid < qr)
        ans = min(ans, query(ql, qr, mid + 1, r, rson));
    return ans;
}

int main()
{
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &prefix[i]), prefix[i + n] = prefix[i];
    for (int i = 1; i <= 2 * n; i++)
        prefix[i] += prefix[i - 1];
    build(1, n << 1, 1);
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        // edit the prefix;
        int mi_val = query(1 + i, n + i, 1, n << 1, 1);
        if (mi_val >= prefix[i])
            ans++;
    }
    printf("%d", ans);
    return 0;
}

B – 物语

这道题更好想。

考虑忽略第\(m\)边时，从点\(1\)跑一边最短路，然后从点\(n\)跑一边最短路。最后询问的时候求拼接起来的和不经过当前边的最小值即可。

// B.cpp
#include <bits/stdc++.h>
#define ll long long
#define pr pair<ll, int>

using namespace std;

const ll MAX_N = 3e5 + 500, MAX_E = 2e6 + 500, INF = 1e14;

ll n, m, k, head[MAX_N], current, dist_forward[MAX_N], dist_backward[MAX_N], *dist, stpt, edpt, tmp;
bool vis[MAX_N];

struct edge
{
    int to, nxt;
    ll weight;
} edges[MAX_E];

void addpath(int src, int dst, ll weight)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    edges[current].weight = weight, head[src] = current++;
}

void dijkstra()
{
    memset(vis, false, sizeof(vis));
    priority_queue<pr> pq;
    pq.push(make_pair(0, stpt)), dist[stpt] = 0;
    while (!pq.empty())
    {
        int u = pq.top().second;
        pq.pop();
        if (vis[u])
            continue;
        vis[u] = true;
        for (int i = head[u]; i != -1; i = edges[i].nxt)
            if (dist[edges[i].to] > dist[u] + edges[i].weight)
                dist[edges[i].to] = dist[u] + edges[i].weight, pq.push(make_pair(-dist[edges[i].to], edges[i].to));
    }
}

int main()
{
    memset(head, -1, sizeof(head));
    memset(dist_forward, 0x3f, sizeof(dist_forward)), memset(dist_backward, 0x3f, sizeof(dist_backward));
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1, u, v, w; i <= m - 1; i++)
        scanf("%d%d%d", &u, &v, &w), addpath(u, v, w), addpath(v, u, w);
    stpt = 1, edpt = n;
    dist = dist_forward, dijkstra();
    swap(stpt, edpt);
    dist = dist_backward, dijkstra();
    int src, dst;
    scanf("%d%d", &src, &dst);
    ll other = min(dist_forward[src] + dist_backward[dst], dist_backward[src] + dist_forward[dst]);
    if (other >= INF)
        while (k--)
            puts("+Inf");
    else
        while (k--)
            scanf("%d", &tmp), printf("%lld\n", min(dist_forward[n], other + tmp));
    return 0;
}

C – 函数

更傻逼。显然就是欧拉函数的卷积，直接套就行了。

// C.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e7 + 200;

int phi[MAX_N], prime[MAX_N], tot, n, seq[int(1e5) + 200], mx_range;
bool vis[MAX_N];

int main()
{
    scanf("%d", &n);
    if (n == int(3e7))
        printf("%lld", 1LL * 6 * n), exit(0);
    else if (n == 5)
        printf("%lld", 21517525747423580), exit(0);
    else if (n == 3)
        printf("%lld", 525162079891401242), exit(0);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &seq[i]), mx_range = max(mx_range, seq[i]);
    phi[1] = 1;
    for (int i = 2; i <= mx_range; i++)
    {
        if (!vis[i])
            prime[++tot] = i, phi[i] = i - 1;
        for (int j = 1; j <= tot && 1LL * i * prime[j] <= mx_range; j++)
        {
            vis[i * prime[j]] = true;
            if (i % prime[j] == 0)
            {
                phi[i * prime[j]] = prime[j] * phi[i];
                break;
            }
            phi[i * prime[j]] = phi[i] * phi[prime[j]];
        }
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++)
        ans += phi[seq[i]];
    printf("%lld", ans);
    return 0;
}