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;
}