P16055 [CSPro 31] 坐标变换（其二）题解

这篇题解主要针对不懂得矩阵乘法的人。主要思想：

视每次操作为：


newx = x * k1 - y * k2\\
newy = x * k2 + y * k1\\
x = newx, y = newy

其中：

操作为 1 时，$k1 = k, k2 = 0$。
操作为 2 时，$k1 = \cos(\theta), k2 = \sin(\theta)$。

80 pts 暴力

注意到 80% 的测试点满足 $n, m \le 1000$，此时最大执行次数为 $1000 \times 1000 = 10^6$，可以获得此部分分。

::::info[80 pts 代码]

#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<pair<int, double>> o;
double k1[100005], k2[100005];
int main() {
    scanf("%d%d", &n, &m);
    o.push_back({0, 0});
    for (int i = 1; i <= n; ++i) {
        int op;
        double k;
        scanf("%d%lf", &op, &k);
        o.push_back({op, k});
        if (op == 2) {
            k1[i] = cos(k);
            k2[i] = sin(k);
        } else {
            k1[i] = k;
            k2[i] = 0;
        }
    }
    for (int i = 1; i <= m; ++i) {
        int l, r, x, y;
        scanf("%d%d%d%d", &l, &r, &x, &y);
        double nx = x, ny = y;
        for (int j = l; j <= r; ++j) {
            if (o[j].first == 1)
                nx *= o[j].second, ny *= o[j].second;
            else {
                double tmpx = nx * k1[j] - ny * k2[j],
                       tmpy = nx * k2[j] + ny * k1[j];
                nx = tmpx, ny = tmpy;
            }
        }
        printf("%f %f\n", nx, ny);
    }
    return 0;
}

::::

100 pts st 表

注意到连续一段的操作可以由各部分操作叠加，可使用 st 表解决。

::::info[100pts 代码]

#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<pair<int, double>> o;
double st1[200005][21], st2[200005][21];
int main() {
    scanf("%d%d", &n, &m);
    o.push_back({0, 0});
    for (int i = 1; i <= n; ++i) {
        int op;
        double k;
        scanf("%d%lf", &op, &k);
        o.push_back({op, k});
        if (op == 1) {
            st1[i][0] = k;
            st2[i][0] = 0;

        } else {
            st1[i][0] = cos(k);
            st2[i][0] = sin(k);
        }
    }
    for (int i = 1; i <= 20; i++) {
        for (int j = 1; j + (1 << i) - 1 <= n; j++) {
            double tmp11 = st1[j][i - 1], tmp12 = st2[j][i - 1];
            double tmp21 = st1[j + (1 << (i - 1))][i - 1],
                tmp22 = st2[j + (1 << (i - 1))][i - 1];
            st1[j][i] = tmp11 * tmp21 - tmp12 * tmp22;
            st2[j][i] = tmp11 * tmp22 + tmp12 * tmp21;
        }
    }
    while (m--) {
        int l, r, x, y;
        scanf("%d%d%d%d", &l, &r, &x, &y);
        double nx = x, ny = y;
        r++;
        for (int i = 20; i >= 0; i--) {
            if (l + (1 << i) <= r) {
                double tmpx = st1[l][i] * nx - st2[l][i] * ny,
                       tmpy = st2[l][i] * nx + st1[l][i] * ny;
                nx = tmpx, ny = tmpy;
                l += 1 << i;
            }
        }
        printf("%f %f\n", nx, ny);
    }
    return 0;
}

::::

题解

🏠 返回仓库

P16055 [CSPro 31] 坐标变换（其二） 题解

80 pts 暴力

100 pts st 表

题解

根目录

P16055 [CSPro 31] 坐标变换（其二）题解