A – 小凯的疑惑

送命规律题。当然也可以考虑用 exgcd 的性质，以下是感性理解：

考虑设这个数为\(x \equiv ya {\pmod b}\)，展开就是：

\[ x = ya + kb, k \in [1, b – 1] \]

发现\(k \geq 0\)时都满足，那么反过来取\(-1\)就可以又满足最大又满足不满足条件。

// P3951.cpp
#include <iostream>
#include <cstring>

using namespace std;

int main()
{
    unsigned long long a, b, i;
    cin >> a >> b;
    cout << a * b - a - b;
    return 0;
}

B – 时间复杂度

刚开始我觉得这道题目非常的可怕，最后我还是自己写了出来（因为题目给的格式还是很好的，没有想象中的困难）。用计数器记录次数、是否零次循环即可。

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

using namespace std;

char content[1010], opt[20];
int T, L, complexity, vis[300];

struct instruction
{
    char typ, var_name[3];
    bool tag, tag2;
    int x, y;
    instruction()
    {
        typ = 0, memset(var_name, 0, sizeof(var_name));
        tag = tag2 = false;
        x = y = 0;
    }
};
stack<instruction> st;

int read()
{
    int pos = 1, ret = 0;
    while (opt[pos] != 0)
        ret = ret * 10 + opt[pos] - '0', pos++;
    return ret;
}

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        memset(vis, 0, sizeof(vis));
        // complexity reader;
        complexity = 0;
        memset(opt, 0, sizeof(opt));
        scanf("%d%s", &L, opt + 1);
        if (strlen(opt + 1) == 4)
            complexity = (opt[3] == '1') ? 0 : 1;
        else
            for (int i = 5, siz = strlen(opt + 1); i <= siz - 1; i++)
                complexity = complexity * 10 + (opt[i] - '0');
        // read the whole content;
        int mx_idx = 0;
        bool err_flag = false;
        while (!st.empty())
            st.pop();
        for (int i = 1, curt_complexity = 0, choke = 0; i <= L; i++)
        {
            instruction ist;
            ist.tag = false, ist.tag2 = false;
            scanf("%s", content + 1);
            ist.typ = content[1];
            if (ist.typ == 'F')
            {
                scanf("%s", ist.var_name + 1);
                // repeated name;
                err_flag |= (vis[ist.var_name[1]] > 0);
                vis[ist.var_name[1]]++;
                // read the condition;
                scanf("%s", opt + 1);
                if (opt[1] == 'n')
                    ist.x = -1;
                else
                    ist.x = read();

                scanf("%s", opt + 1);
                if (opt[1] == 'n')
                    ist.y = -1;
                else
                    ist.y = read();

                if (ist.x != -1 && ist.y == -1)
                {
                    // O(n);
                    if (choke == 0)
                        curt_complexity++, ist.tag2 = true;
                }
                else if (ist.x == -1 && ist.y != -1)
                    choke++, ist.tag = true;
                else if (ist.x != -1 && ist.y != -1 && ist.x > ist.y)
                    choke++, ist.tag = true;

                st.push(ist);
            }
            else if (ist.typ == 'E')
            {
                if (st.empty())
                    // nowhere to go;
                    err_flag = true;
                else
                {
                    instruction current_ist = st.top();
                    if (current_ist.tag)
                        choke--;
                    if (current_ist.tag2)
                        curt_complexity--;
                    vis[current_ist.var_name[1]]--;
                    st.pop();
                }
            }
            mx_idx = max(mx_idx, curt_complexity);
        }
        err_flag |= (!st.empty());
        if (err_flag)
        {
            puts("ERR");
            continue;
        }
        puts(mx_idx == complexity ? "Yes" : "No");
    }
    return 0;
}

C – 逛公园

策策主任逛机房。

这道题看上去超级难，但是最后用记忆化搜索的方式暴解起初让我意外，但是过了几秒之后真的觉得很妙。因为\(k < 50\)，显然可以直接记忆化搜索状态进行转移（管他妈的转移顺序）。

设置状态\(dp[u][addition]\)，其中\(addition\)代表的就是剩下的\(bonus\)成分，然后就可以开始暴力计数了。这个方法是真的好。

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

using namespace std;

const int MAX_N = 100100, MAX_E = 200010;

int head[MAX_N], n, m, k, p, current, T;
ll dist[MAX_N], dp[MAX_N][60];
bool vis[MAX_N], inst[MAX_N][60];

struct edge
{
	int to, nxt;
	ll weight;
	bool tag;
} edges[MAX_E << 1];

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

void shortest_path()
{
	memset(dist, 0x3f, sizeof(dist));
	memset(vis, false, sizeof(vis));
	priority_queue<pr> pq;
	pq.push(make_pair(0, n)), dist[n] = 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 (edges[i].tag == true && 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 dfs(int u, int addition)
{
	if (inst[u][addition])
		return -1;
	if (dp[u][addition])
		return dp[u][addition];
	inst[u][addition] = true;
	if (u == n)
		dp[u][addition] = 1;
	for (int i = head[u]; i != -1; i = edges[i].nxt)
		if (dist[edges[i].to] - dist[u] + edges[i].weight <= addition && edges[i].tag == true)
		{
			ll diff = dist[edges[i].to] - dist[u] + edges[i].weight;
			if (dfs(edges[i].to, addition - diff) == -1)
				return (dp[u][addition] = -1);
			dp[u][addition] = (1LL * dp[u][addition] + 1LL * dp[edges[i].to][addition - diff]) % p;
		}
	inst[u][addition] = false;
	return dp[u][addition];
}

int main()
{
	scanf("%d", &T);
	while (T--)
	{
		memset(head, -1, sizeof(head)), current = 0;
		memset(inst, 0, sizeof(inst)), memset(dp, 0, sizeof(dp));
		scanf("%d%d%d%d", &n, &m, &k, &p);
		for (int i = 1, u, v, w; i <= m; i++)
			scanf("%d%d%d", &u, &v, &w), addpath(u, v, w, false), addpath(v, u, w, true);
		shortest_path();
		for (int i = 0; i < current; i++)
			edges[i].tag ^= 1;
		printf("%d\n", dfs(1, k));
	}
	return 0;
}

D – 奶酪

sb 并查集搞定。

// P3958.cpp
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
#define ll long long

int n, h, r;

struct Point
{
    ll x, y, z;
    Point() {}
    Point(int x, int y, int z)
    {
        this->x = x;
        this->y = y;
        this->z = z;
    }
};

struct Sphere
{
    Point center;
    ll radius;
    bool upperColliding;
    bool lowerColliding;
    int index;

    Sphere() {}
    Sphere(Point c, int radius);
};

double getDist(Point a, Point b);
bool checkCollide(Sphere s1, Sphere s2);
bool checkLowerCollide(Sphere s);
bool checkUpperCollide(Sphere s);

Sphere::Sphere(Point c, int radius)
{
    center = c;
    this->radius = radius;
}

double getDist(Point a, Point b)
{
    return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2) + pow(a.z - b.z, 2));
}

bool checkUpperCollide(Sphere s)
{
    if (s.center.z + s.radius >= h)
        return true;
    return false;
}

bool checkLowerCollide(Sphere s)
{
    if (s.center.z - s.radius <= 0)
        return true;
    return false;
}

bool checkCollide(Sphere s1, Sphere s2)
{
    if (getDist(s1.center, s2.center) <= s1.radius + s2.radius)
        return true;
    return false;
}

struct Batch
{
    vector<Sphere> spheres;
    vector<Sphere> upper;
    vector<Sphere> lower;
    int mem[100100];

    void MakeHeap()
    {
        for (int i = 0; i < n + 2; i++)
            mem[i] = i;
    }

    void UnionElement(int p, int q)
    {
        int p_parent = FindElement(p);
        int q_element = FindElement(q);
        if (p_parent != q_element)
            mem[p_parent] = q_element;
    }

    int FindElement(int p)
    {
        if (mem[p] != p)
            mem[p] = FindElement(mem[p]);
        return mem[p];
    }

    bool allFlag = true;
    bool goFlag = false;

    void initialize()
    {
        cin >> n >> h >> r;
        for (int i = 0; i < n; i++)
        {
            ll x, y, z;
            cin >> x >> y >> z;
            Sphere sss = Sphere(Point(x, y, z), r);
            sss.index = i;
            sss.upperColliding = checkUpperCollide(sss);
            sss.lowerColliding = checkLowerCollide(sss);
            if (sss.upperColliding && sss.lowerColliding)
                goFlag = true;
            if (sss.upperColliding)
                allFlag = false, upper.push_back(sss);
            if (sss.lowerColliding)
                lower.push_back(sss);
            spheres.push_back(sss);
        }
        return;
    }

    void preprocess()
    {
        MakeHeap();
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
            {
                if (i == j)
                    continue;
                if (checkCollide(spheres[i], spheres[j]))
                    UnionElement(i, j);
            }
    }

    void Solve()
    {
        if (goFlag)
        {
            cout << "Yes" << endl;
            return;
        }
        if (allFlag)
        {
            cout << "No" << endl;
            return;
        }
        preprocess();
        for (int i = 0; i < upper.size(); i++)
            for (int j = 0; j < lower.size(); j++)
            {
                if (upper[i].index == lower[i].index)
                    continue;
                int resi = FindElement(upper[i].index), resj = FindElement(lower[j].index);
                if (resi != resj)
                    continue;
                cout << "Yes" << endl;
                return;
            }
        cout << "No" << endl;
    }
};

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        Batch b;
        b.initialize();
        b.Solve();
    }
    return 0;
}

E – 宝藏

想到了状态之后就算是 sb 题了。设置状态\(dp[stat][i]\)，stat 就是已有的点集，\(i\)是最大树高。知道这个之后枚举子集就可以搞定了（因为最大树高为最糟情况，且这个情况会由状态压缩自动处理掉，请自行思考）。

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

using namespace std;

const int MAX_N = 20, INF = 0x3f3f3f3f;

int dist[MAX_N][MAX_N], n, m, dp[1 << MAX_N][MAX_N], dist_mask[1 << MAX_N];

int main()
{
    memset(dist, 0x3f, sizeof(dist));
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v, w; i <= m; i++)
        scanf("%d%d%d", &u, &v, &w), u--, v--, dist[u][v] = dist[v][u] = min(dist[u][v], w);
    for (int i = 1; i < (1 << n); i++)
        for (int j = 0; j < n; j++)
            if (i & (1 << j))
            {
                dist[j][j] = 0;
                for (int k = 0; k < n; k++)
                    if (dist[j][k] != INF)
                        dist_mask[i] |= (1 << k);
            }
    memset(dp, 0x3f, sizeof(dp));
    for (int i = 0; i < n; i++)
        dp[1 << i][0] = 0;
    for (int stat = 2; stat < (1 << n); stat++)
        for (int subset = stat - 1; subset; subset = (subset - 1) & stat)
            if ((dist_mask[subset] | stat) == dist_mask[subset])
            {
                int sum = 0, from = subset ^ stat;
                for (int k = 0; k < n; k++)
                    if (from & (1 << k))
                    {
                        int tmp = INF;
                        for (int idx = 0; idx < n; idx++)
                            if (subset & (1 << idx))
                                tmp = min(tmp, dist[idx][k]);
                        sum += tmp;
                    }
                for (int i = 1; i < n; i++)
                    if (dp[subset][i - 1] != INF)
                        dp[stat][i] = min(dp[stat][i], sum * i + dp[subset][i - 1]);
            }
    int ans = INF;
    for (int i = 0; i < n; i++)
        ans = min(ans, dp[(1 << n) - 1][i]);
    printf("%d", ans);
    return 0;
}

F – 列队

50 分退役题。

首先有一个性质：每一次出队的时候，只会影响当前列和当前行和右下角的格子。所以，不难想到，维护一堆线段树来记录每一列某个位置前有多少个人，这样我们可以用权值线段树那一套，来二分出那个位置（每次多了一个点，加一之后就会自动偏移，非常巧妙）。超过范围的就用 vector 存就好。

当然，即使是这样，我还是不会。

// P3960.cpp
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int MAX_N = 3e5 + 200, SEG = 1e7 + 200;

ll siz[SEG], n, m, q, ptot, upper;
int lson[SEG], rson[SEG], roots[SEG];
vector<ll> vecs[MAX_N];

ll atRank(ll k, int l, int r, int p)
{
    if (l == r)
        return l;
    ll mid = (l + r) >> 1, lsiz = mid - l + 1 - siz[lson[p]];
    if (k <= lsiz)
        return atRank(k, l, mid, lson[p]);
    else
        return atRank(k - lsiz, mid + 1, r, rson[p]);
}

int update(int qx, int l, int r, int p)
{
    if (p == 0)
        p = ++ptot;
    ++siz[p];
    if (l == r)
        return p;
    int mid = (l + r) >> 1;
    if (qx <= mid)
        lson[p] = update(qx, l, mid, lson[p]);
    else
        rson[p] = update(qx, mid + 1, r, rson[p]);
    return p;
}

ll query_col(int x, int y)
{
    ll tmp = atRank(y, 1, upper, roots[x]);
    roots[x] = update(tmp, 1, upper, roots[x]);
    return tmp < m ? 1LL * (x - 1) * m + tmp : vecs[x][tmp - m];
}

ll query_row(int x)
{
    ll tmp = atRank(x, 1, upper, roots[n + 1]);
    roots[n + 1] = update(tmp, 1, upper, roots[n + 1]);
    return tmp <= n ? 1LL * tmp * m : vecs[n + 1][tmp - n - 1];
}

int main()
{
    scanf("%lld%lld%lld", &n, &m, &q);
    upper = max(n, m) + q;
    while (q--)
    {
        int x, y;
        ll tmp;
        scanf("%d%d", &x, &y);
        if (y == m)
            tmp = query_row(x), vecs[n + 1].push_back(tmp), printf("%lld\n", tmp);
        else
        {
            tmp = query_col(x, y), vecs[n + 1].push_back(tmp);
            printf("%lld\n", tmp);
            tmp = query_row(x), vecs[x].push_back(tmp);
        }
    }
    return 0;
}