第31次CCF计算机软件能力认证
100+100+100+100+60=460
坐标变换 (其一)
题目大意
给定\(n\)个操作，每个操作将坐标 \((x,y)\)变为 \((x + dx, y + dy)\)。
给定 \(m\)个点，问这 \(m\)个点经过这 \(n\)次操作变换后的坐标。
解题思路
注意到操作是可合并的，因此可以先将这\(n\)个操作合并成一个操作，然后对每个点都经过这个操作变换即可，时间复杂度为 \(O(n + m)\)。
本题 \(n,m\)只有 \(100\)，也可以 \(O(nm)\)依次对每个点进行操作变换。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
int dx = 0, dy = 0;
for(int i = 0; i < n; ++ i){
int x, y;
cin >> x >> y;
dx += x;
dy += y;
}
for(int i = 0; i < m; ++ i){
int x, y;
cin >> x >> y;
cout << x + dx << ' ' << y + dy << '\n';
}
return 0;
}
坐标变换(其二)
题目大意
给定\(n\)个操作，操作分两类，一类将\((x, y)\)变为 \((kx, ky)\)，一类进行坐标旋转，并贴心地给出了旋转公式。
给定 \(m\)个点，问这 \(m\)个点经过第\(l\)次到第\(r\)次操作变换后的坐标。
解题思路
直接模拟的\(O(nm)\)可以拿 \(80\)分 。
考虑操作合并，因为在第二类操作里，两维会相互影响，不能像第一题单纯的合并，但由于是线形的，可以写成一个矩阵乘法的方式，因此可以写成矩阵乘法的形式，用线段树维护区间乘，当然也可以分块维护区间操作，但想到第二题应该不会有这么复杂的写法，于是赶紧冷静下来想想有什么其他的写法。
注意到一个操作是改变与原点的距离，一个操作是改变与\(x\)轴所夹成的角度，如果考虑坐标在极坐标系下的表示形式，会发现这两种操作只是分别对其中一维进行操作，且这些操作是可逆的，且不会相互影响。
因此我们就预处理出 \(op[i]\)表示操作 \(1..i\)对距离 \(r\)和角度 \(\theta\)的影响，这是一个前缀和数组。
然后对于一个点问经过操作 \(l..r\)的结果，先对它施加\(1..r\)操作的影响，再消除 \(1..l-1\)操作的影响，即可得到 \(l..r\)操作的结果。
施加影响，就是长度 \(\times k\)，角度 \(+ \theta\)，消除影响，就是长度 \(/ k\)，角度 \(- \theta\)。
最后根据\(r\)和 \(\theta\)还原出\(x = r\cos \theta, y = r\sin \theta\)。
时间复杂度为 \(O(n + m)\)。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1);
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
vector<array<double, 2>> op(n);
for(auto &i : op){
int opp;
double k;
cin >> opp >> k;
if (opp == 1)
i[0] = k;
else{
i[0] = 1;
i[1] = k;
}
}
for(int i = 1; i < n; ++ i){
op[i][0] *= op[i - 1][0];
op[i][1] += op[i - 1][1];
}
for(int i = 0; i < m; ++ i){
int l, r, x, y;
cin >> l >> r >> x >> y;
-- l, -- r;
double R = sqrt(1ll * x * x + 1ll * y * y), theta = 0;
if (x == 0){
if (y > 0)
theta = pi / 2;
else
theta = -pi / 2;
}else{
theta = atan2(y, x);
}
R *= op[r][0];
theta += op[r][1];
if (l){
R /= op[l - 1][0];
theta -= op[l - 1][1];
}
cout << fixed << setprecision(10) << R * cos(theta) << ' ' << R * sin(theta) << '\n';
}
return 0;
}
梯度求解
题目大意
给定一个仅包含\(+-*\)运算的多元函数，求关于 \(x_i\)在点 \((a_1,a_2,...)\)处的偏导值。
函数以逆波兰形式给出。
解题思路
感觉有意思的题，没接触过，琢磨了许久。
首先我们不能以人的方式考虑对\((x^3)^\prime = 3x^2\)这样的形式的求导，而是像例子给看成的\(x_1 \cdot x_1 \cdot x_1\)用乘法求导的式子计算。这样每个的原子项都是形如 \(x_i\)或者常数这样最简形式。虽然可能计算不如上述的简单，但毕竟是机器算，数据范围也比较小，就尽可能简单一点。
不合并同类项后，考虑对这个表达式的求导，我们尽可能要找一个可以递归的结构进行求导，这个结构其实跟表达式计算是一样的。
通过逆波兰表达式建立这个表达式树，如下图所示，题面也贴心地指出了逆波兰表达式就是这棵树的后序遍历。
树就是一棵有递归结构的表示形式，我们要求整棵树的偏导值，先看根节点的运算符，比如是乘号，由于\((uv)^\prime = u^\prime v + uv^\prime\)，那我们需要求左子树的函数值和偏导值，右子树的函数值和偏导值，然后根据上述求导的式子计算得到当前子树的函数值和偏导值。而求左右子树的函数值和偏导值实际上就是一个子问题，因此就可以递归下去了。如果是加法的话就是偏导值相加。
边界情况就是当前节点是常数或者变量时，根据求导式子可以直接得到函数值和偏导值。
其实最后发现和表达式计算没什么区别。时间复杂度为\(O(nm)\)。
注意减法不满足交换律，在建立表达式树时不要搞错运算符左右两个值的顺序。
考场上模数习惯性写成\(998244353\)找了好久的错误。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
const int mo = 1e9+7;
#define CONST -1
#define VAR -2
#define OP -3
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string s;
int n, m;
cin >> n >> m;
getline(cin, s); // '\n'
getline(cin, s);
istringstream qwq(s);
vector<int> l;
vector<int> r;
vector<int> info;
vector<int> kind;
stack<int> id;
int node_id = 0;
while(getline(qwq, s, ' ')){
if (s.size() == 1 && (s[0] == '+' || s[0] == '*' || s[0] == '-')){
int rson = id.top();
id.pop();
int lson = id.top();
id.pop();
l.push_back(lson);
r.push_back(rson);
info.push_back(s[0]);
kind.push_back(OP);
id.push(node_id);
++ node_id;
}else if (s[0] == 'x'){
int x = stoi(s.substr(1));
-- x;
l.push_back(-1);
r.push_back(-1);
info.push_back(x);
kind.push_back(VAR);
id.push(node_id);
++ node_id;
}else{
int x = stoi(s);
l.push_back(-1);
r.push_back(-1);
info.push_back(x);
kind.push_back(CONST);
id.push(node_id);
++ node_id;
}
}
int root = id.top();
vector<int> a(n);
function<array<int, 2>(int, int)> solve = [&](int u, int x){
if (kind[u] == VAR){
return array<int, 2>{a[info[u]], (info[u] == x)};
}else if (kind[u] == CONST){
return array<int, 2>{info[u], 0};
}else{
auto lans = solve(l[u], x), rans = solve(r[u], x);
int sum = 0, dsum = 0;
if (info[u] == '+'){
sum = lans[0] + rans[0];
dsum = lans[1] + rans[1];
if (sum >= mo) sum -= mo;
if (dsum >= mo) dsum -= mo;
}else if (info[u] == '-'){
sum = lans[0] - rans[0];
dsum = lans[1] - rans[1];
if (sum >= mo) sum -= mo;
if (dsum >= mo) dsum -= mo;
}else{
sum = 1ll * lans[0] * rans[0] % mo;
dsum = (1ll * lans[0] * rans[1] % mo + 1ll * lans[1] * rans[0] % mo);
if (dsum >= mo) dsum -= mo;
}
if (sum < 0)
sum += mo;
if (dsum < 0)
dsum += mo;
return array<int, 2>{sum, dsum};
}
};
for(int i = 0; i < m; ++ i){
int x;
cin >> x;
-- x;
for(auto &i : a)
cin >> i;
cout << solve(root, x)[1] << '\n';
}
return 0;
}
阴阳龙
题目大意
二维平面\(n \times m\)，有\(p\)个人，位于不同坐标。
有 \(q\)次事件\((x,y,t)\)发生， 每次事件，在\((x,y)\)上会有阴阳龙出现，从该位置的周围的8个方向中，找到切比雪夫距离最小的那些人，它们的位置将进行 \(t\)倍的 \(\frac{1}{8}\)圆的逆时针旋转。注意如果这个最小距离大于该位置\((x,y)\)到边界的切比雪夫距离，则无事发生（因为旋转的话可能会飞到区域外了）。没有人也无事发生。
问这 \(m\)次事件后，所有人的坐标。
解题思路
考虑暴力，对于某个事件，从\((x,y)\)依次往 \(8\)个方向递增，直到碰到人后，暴力旋转。时间复杂度为 \(O(max(n,m)q)\)。
注意到人的坐标互不相同，那么每个事件最多只会更改\(8\)个人的坐标，如果我们能快速找到这 \(8\)个人，复杂度就是 \(O(8q)\)。
考虑如何快速找到，对于同一行的人中，我们用set储存它们的列坐标，这样通过\(lower\_bound\)就可以在\(O(\log)\)的事件内找到 \((x,y)\) 最小的大于\(y\)和最大的小于 \(y\)的人，作为候选者。
同理对于同一列，同一对角线都这么找。同一行的人，它们的 \(x\)相同。同一列的人，它们的 \(y\)相同。同一对角线的人，它们的 \(x+y\)或 \(x-y\)是相同的。
因此就开\(row[x], col[y], ld[x + y], rd[x - y]\)表示第\(x\)行的所有人的 \(y\)集合，第 \(y\)列的所有人的 \(x\)集合，左上\(\to\)右下的对角线满足 \(x+y\)的所有人的\(y\)集合，以及左下\(\to\)右上的对角线满足 \(x-y\)的所有人的 \(y\)集合。
对于当前的阴阳龙位置 \((x,y)\)，分别花\(O(\log)\) 时间找到八个方向的最近 的候选人，然后根据距离排个序，得到最近的那些人，再进行题意所述的坐标变换即可。
时间复杂度是\(O(q\log p)\)
神奇的代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m, p, q;
cin >> n >> m >> p >> q;
vector<array<int, 2>> pos(p);
unordered_map<int, set<array<int, 2>>> row, col, ld, rd;
auto insert = [&](int id){
int x = pos[id][0], y = pos[id][1];
row[x].insert({y, id});
col[y].insert({x, id});
ld[x + y].insert({y, id});
rd[x - y].insert({y, id});
};
auto remove = [&](int id){
int x = pos[id][0], y = pos[id][1];
row[x].erase({y, id});
col[y].erase({x, id});
ld[x + y].erase({y, id});
rd[x - y].erase({y, id});
};
for(int i = 0; i < p; ++ i){
cin >> pos[i][0] >> pos[i][1];
insert(i);
}
for(int i = 0; i < q; ++ i){
int u, v, t;
cin >> u >> v >> t;
vector<array<int, 3>> candidate;
auto search = [&](const set<array<int, 2>>& people, int d, int dirr, int dirl){
auto pos = people.lower_bound(array<int, 2>{d, p});
if (pos != people.end()){
candidate.push_back({(*pos)[0] - d, (*pos)[1], dirr});
}
if (pos != people.begin()){
pos = prev(pos);
if ((*pos)[0] == d && pos != people.begin())
pos = prev(pos);
if ((*pos)[0] != d){
candidate.push_back({d - (*pos)[0], (*pos)[1], dirl});
}
}
};
search(row[u], v, 2, 6);
search(col[v], u, 0, 4);
search(ld[u + v], v, 3, 7);
search(rd[u - v], v, 1, 5);
if (candidate.empty())
continue;
sort(candidate.begin(), candidate.end(), [&](const array<int, 3>& a, const array<int, 3>& b){
return a[0] < b[0];
});
int mindis = min({u - 1, n - u, v - 1, m - v});
if (candidate[0][0] > mindis)
continue;
mindis = candidate[0][0];
for(int i = 0; i < candidate.size(); ++ i){
if (candidate[i][0] != mindis)
break;
int dis = candidate[i][0];
int id = candidate[i][1];
remove(id);
int dir = (candidate[i][2] + t) % 8;
pos[id][0] = u + dis * dx[dir];
pos[id][1] = v + dis * dy[dir];
insert(id);
}
}
LL ans = 0;
for(int i = 0; i < p; ++ i){
ans ^= (1ll * (i + 1) * pos[i][0] + pos[i][1]);
}
cout << ans << '\n';
return 0;
}
阻击
题目大意
给定一棵树，边有边权，\(m\)次修改，每次修改一个边权。
问每次修改后树的直径长度。
- 性质A，一个链。
- 性质B，边权非负。
- 性质C，任意两点的路径边数不超过\(100\)。
解题思路
树的直径经典求法就是\(O(n)\)的两次 \(BFS\)或\(DFS\)， 但有个前提是边权必须非负。而本题并不保证这一性质，只有数据里的性质B有这个特征。
尽管如此，注意到树的递归特性，直径要么在某个子树里，要么横跨了根节点，而后者是两条到根节点最长的路径拼接起来的。这非常类似分治的想法。
设\(maxd[u]\)表示在\(u\)的子树中到节点\(i\)的最长距离，在分治求解过程中，先求其儿子子树\(v\)的答案，然后求最大值\(max(maxd[u] + maxd[v] + d[u][v])\)，同时更新\(maxd[u]\)的值。
这样同样\(O(n)\)就可以得出直径长度。
时间复杂度是 \(O(nm)\)，有 \(48\)分。
考虑性质 \(A\)的链的做法，就是问一个区间的最大子区间和。这是一个经典问题，同样考虑分治，从中间切开后，答案要么在左右子区间里，要么横跨左右子区间，前者递归求解，后者则是从中间往左右延伸的最大和，这个 \(O(n)\)就能求解。
考虑实时维护信息，注意到这些信息是可合并的，也即一个大区间的答案可以由两个小区间的信息合并得到，因此我们用线段树维护这些区间，维护的信息包括：
- 区间答案
- 区间和
- 前缀最大值
- 后缀最大值
这样就可以得到大区间的这四个信息，就可以实时维护答案了。每次修改重新求答案的复杂度是 \(O(\log n)\)。总的时间复杂度是 \(O(m\log n)\)。这有\(12\)分。
到这里就\(60\)分了。
考虑性质 \(C\)，还是考虑上述树形态的做法，在边权修改时如何实时维护需要的信息。注意到合并答案时是根据子树的答案和子树的\(maxd\)进行的，我们需要实时维护这些值，当一条边权修改时，从这条边的点一路往父亲方向走的所有点的信息都会改变，由于性质\(C\)，这样的点最多 \(100\)个。因此每次修改重新求答案的时间复杂度是 \(O(100)\)，总的时间复杂度是 \(O(100m \log n)\)，这里的\(\log\)是要维护子树的 \(maxd\)的最大的两个值。时间上是能通过，但一直 \(WA\)，没找到原因，没拿到这\(12\)分。
至于性质 \(B\)， 没想到有什么用。
至于正解，不会，只会对着性质拿分了。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 8;
class segment{
#define lson root << 1
#define rson root << 1 | 1
LL ans[N << 2];
LL lsum[N << 2];
LL rsum[N << 2];
LL sum[N << 2];
public:
void popup(int root){
ans[root] = max({ans[lson], ans[rson], rsum[lson] + lsum[rson]});
lsum[root] = max(lsum[lson], sum[lson] + lsum[rson]);
rsum[root] = max(rsum[rson], sum[rson] + rsum[lson]);
sum[root] = sum[lson] + sum[rson];
}
void build(int root, int l, int r, vector<int>& a){
if (l == r){
ans[root] = (a[l] >= 0 ? a[l] : 0);
lsum[root] = (a[l] >= 0 ? a[l] : 0);
rsum[root] = (a[l] >= 0 ? a[l] : 0);
sum[root] = a[l];
return;
}
int mid = (l + r) >> 1;
build(lson, l, mid, a);
build(rson, mid + 1, r, a);
popup(root);
}
void update(int root, int l, int r, int pos, int val){
if (l == r){
ans[root] = (val >= 0 ? val : 0);
lsum[root] = (val >= 0 ? val : 0);
rsum[root] = (val >= 0 ? val : 0);
sum[root] = val;
return;
}
int mid = (l + r) >> 1;
if (pos <= mid)
update(lson, l, mid, pos, val);
else
update(rson, mid + 1, r, pos, val);
popup(root);
}
LL query(int root){
return ans[root];
}
}seg;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
vector<vector<int>> G(n);
vector<array<int, 4>> edge;
for(int i = 1; i < n; ++ i){
int u, v, w, b;
cin >> u >> v >> w >> b;
-- u, -- v;
G[u].push_back(edge.size());
G[v].push_back(edge.size());
edge.push_back({u, v, w, b});
}
vector<LL> maxd(n, 0);
LL ans = 0;
function<void(int, int)> dfs = [&](int u, int fa){
for(auto &i : G[u]){
int v = edge[i][0] ^ edge[i][1] ^ u;
if (v == fa)
continue;
int d = edge[i][3] - edge[i][2];
dfs(v, u);
ans = max(ans, maxd[u] + maxd[v] + d);
maxd[u] = max(maxd[u], maxd[v] + d);
}
};
dfs(1, 1);
cout << ans << '\n';
if (m < 100000){
for(int i = 1; i <= m; ++ i){
int x, y;
cin >> x >> y;
-- x;
edge[x][2] = y;
ans = 0;
fill(maxd.begin(), maxd.end(), 0);
dfs(1, 1);
cout << ans << '\n';
}
}else{
int ok1 = true;
for(int i = 0; i < n - 1; ++ i){
ok1 &= (edge[i][0] == i && edge[i][1] == i + 1);
}
if (ok1){
// A
vector<int> a(n);
for(int i = 1; i < n; ++ i){
a[i] = edge[i - 1][3] - edge[i - 1][2];
}
seg.build(1, 1, n - 1, a);
for(int i = 1; i <= m; ++ i){
int x, y;
cin >> x >> y;
-- x;
edge[x][2] = y;
seg.update(1, 1, n - 1, x + 1, edge[x][3] - edge[x][2]);
cout << seg.query(1) << '\n';
}
}else{
// C
vector<set<array<LL, 2>>> anss(n), maxs(n);
vector<unordered_map<int, LL>> anss_id(n), maxs_id(n);
vector<int> deep(n), f(n);
function<void(int, int)> dfs2 = [&](int u, int fa){
f[u] = fa;
int leave = true;
for(auto &i : G[u]){
int v = edge[i][0] ^ edge[i][1] ^ u;
if (v == fa)
continue;
leave = false;
deep[v] = deep[u] + 1;
dfs2(v, u);
int d = edge[i][3] - edge[i][2];
LL ans_val = (*anss[v].rbegin())[0];
anss[u].insert({ans_val, v});
anss_id[u][v] = ans_val;
LL maxs_val = (*maxs[v].rbegin())[0] + d;
maxs[u].insert({maxs_val, v});
maxs_id[u][v] = maxs_val;
}
anss[u].insert({0, -1});
maxs[u].insert({0, -1});
if (maxs[u].size() > 1){
auto c1 = maxs[u].rbegin();
auto c2 = next(c1);
anss[u].insert({(*c1)[0] + (*c2)[0], -2});
anss_id[u][-2] = (*c1)[0] + (*c2)[0];
}
};
dfs2(0, -1);
for(int i = 0; i < m; ++ i){
int x, y;
cin >> x >> y;
-- x;
edge[x][2] = y;
int d = edge[x][3] - edge[x][2];
ans = 0;
int cur = (deep[edge[x][0]] < deep[edge[x][1]] ? edge[x][0] : edge[x][1]);
int son = cur ^ edge[x][0] ^ edge[x][1];
while(cur != -1){
maxs[cur].erase({maxs_id[cur][son], son});
maxs_id[cur][son] = (*maxs[son].rbegin())[0] + d;
maxs[cur].insert({maxs_id[cur][son], son});
anss[cur].erase({anss_id[cur][son], son});
anss_id[cur][son] = (*anss[son].rbegin())[0];
anss[cur].insert({anss_id[cur][son], son});
anss[cur].erase({anss_id[cur][-2], -2});
if (maxs[cur].size() > 1){
auto c1 = maxs[cur].rbegin();
auto c2 = next(c1);
anss_id[cur][-2] = (*c1)[0] + (*c2)[0];
anss[cur].insert({anss_id[cur][-2], -2});
}
son = cur;
cur = f[cur];
}
ans = max(0ll, (*anss[0].rbegin())[0]);
cout << ans << '\n';
}
}
}
return 0;
}