#135 测试点 7 的另类解法

前排提醒，也许这个做法已经火星了。（自我猜测）

几个月前，YuHaoXiang 拿着他刚写的 #135 可视化给全机房康了一遍十个测试点。不得不说，这个可视化写的很好（还可以手玩）。

当然七号测试点十分有趣，但是这种点不能跟着转以达到全避太可惜了。我在他写的可视化程序上面，我开了低速，绕着 $(200, 240)$ 转，发现理论上，避弹同时擦将近一半的弹是可行的。

于是我写了个爆搜，其优先选择离 $(200, 240)$ 近的点走。如果只是得出可行解，则不需要什么剪枝就能很快地跑出。

通过得出一个全避的可行解，我得到了比题解做法得分 10077858 稍微高一点点的 15726572 做法。

如果加上一些最优化，得分可能会更高？

至少目前的解已经具有了一点观赏性。

代码如下：

#include <bits/stdc++.h>

typedef long double db;
typedef db VT;
struct vec {
    VT x, y;
    vec() { x = y = 0; }
    vec(VT a, VT b) { x = a, y = b; }
    VT operator ^ (vec b) const { return x * b.y - y * b.x; }
    VT operator * (vec b) const { return x * b.x + y * b.y; }
    VT norm2() const { return x * x + y * y; }
    db norm() const { return sqrt(x * x + y * y); }
    vec operator - (vec b) const { return vec(x - b.x, y - b.y); }
    vec operator + (vec b) const { return vec(x + b.x, y + b.y); }
    vec operator * (db k) const { return vec(x * k, y * k); }
    bool operator < (const vec & b) const {
        return x == b.x ? y < b.y : x < b.x;
    }
    friend std::istream & operator >> (std::istream & in, vec & x) {
        in >> x.x >> x.y;
        return in;
    }
    friend std::ostream & operator << (std::ostream & out, vec x) {
        out << '(' << x.x << ',' << x.y << ')';
        return out;
    }
} ;
struct cir {
    vec o; int R;
} ;
std::vector<cir> hav[2641];
typedef std::vector<vec> VP;
vec ways[9];
const char tp[] = "WXADQZECS";
char opt[9999];
int TT;
typedef std::vector<cir> VI;
VI pool[9999];
auto cmp = [] (cir a, cir b) {
    static vec mid(200, 240);
    db da = (a.o - mid).norm2(), db = (b.o - mid).norm2();
    return da < db;
};
int W, H;
int steps = 0;
void dfs(int tn, vec cur) {
    ++steps;
    if (cur.x < 0 || cur.y < 0 || cur.x > W || cur.y > H) {
        return ;
    }
    for (auto t : hav[tn])
        if ((t.o - cur).norm2() <= t.R * t.R)
            return ;
    if (tn == TT) {
        std::cerr << cur << ' ' << steps << std::endl;
        opt[tn] = 0;
        std::cout << opt << '\n';
        exit(0);
    }
    VI & now = pool[tn];
    now.clear();
    for (int i = 0; i < 9; ++i)
        now.push_back((cir) {cur + ways[i], i});
    std::sort(now.begin(), now.end(), cmp);
    for (int i = 0; i < 9; ++i) {
        opt[tn] = tp[now[i].R];
        dfs(tn + 1, now[i].o);
    }
}
int main() {
    freopen("touhou7.in", "r", stdin);
    freopen("touhou7.out", "w", stdout);
    int r, R; vec O;
    int n, D;
    std::cin >> W >> H >> O >> D >> r >> R;
    std::cin >> n;
    for (int i = 1; i <= n; ++i) {
        int b, e;
        vec at, v; int rr, G;
        std::cin >> b >> e >> at >> v >> rr >> G;
        rr += r;
        for (int j = b; j <= e; ++j) {
            hav[j].push_back((cir) {at, rr});
            at = at + v;
        }
    }
    TT = 2640;
    for (int i = 0; i <= TT; ++i)
        std::sort(hav[i].begin(), hav[i].end(), cmp);
    ways[0] = vec(0, -D);
    ways[1] = vec(0, D);
    ways[2] = vec(-D, 0);
    ways[3] = vec(D, 0);
    const db Q = D / std::sqrt(2.);
    ways[4] = vec(-Q, -Q);
    ways[5] = vec(-Q, Q);
    ways[6] = vec(Q, -Q);
    ways[7] = vec(Q, Q);
    dfs(0, O);
    std::cerr << "NO SOL, TOTAL : " << steps << std::endl;
    return 0;
}

后附上决策文件，想看的可以去 #135 可视化

WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSQZQQWWASESESDECQDCDSCWCCXCSXEXXZCZADZZSZSACAASAQZSQQSQWASWSWSWEQSEDWSDWSDSDECSCECSCSCXEXXSXZCSZSZSZSZSAZQCAAQSQXQQWAWSWSWSWESEAESEDWDCQDDCEXDSCSCXEXXSXZCSZSZSZSZSAZQCAAQSQXQQWAWSWSWSWESEAESEDWDCQDDCEXDSCSCXEXXSXZCSZSZSZSZSAZQCAAQSQXQQWAWSWSWSWESEAESEDWDCQDDCEXDSCSCXEXXSXZCSZSZSZSZSAZQCAAQSQXQQWAWSWSWSWESEAESEDWDCQDDCEXDSCSCXEXXSXZCSZSZSZSZSAZQCAAQSQXQQWAWSWSWSWESEAESEDWDCQDDCEXDSCSCXEXXSXZCSZSZSZSZSAZQCAAQSQXQQWAWSWSWSWESEAESEDWDCQDDCEXDSCSCXEXXSXZCSZSZSZSZSAZQCAAQSQXQQWAWSWSWSWESEAESEDWDCQDDCEXDSCSCXEXXSXZCSZSZSZSZSAZQCAAQSQXQQWAWSWSWSWESEAESEDWDCQDDCEXDSCSCXEXXSXZCSZSZSZSZSAZQCAAQSQXQQWAWSWSWSWESEAESEDWDCQDDCEXDSCSCXEXXSXZCSZSZSZSZSAZQCAAQSQXQQWAWSWSWSWESEAESEDWDCQDDCEXDSCSCXEXXSXZCSZSZSZSZSAZQCAAQSQXQQWAWSWSWSWESEAESEDWDCQDDCEXDSCSCXEXXSXZCSZSZSZSZSAZQCAAQSQXQQWAWSWSWSWESEAESEDWDCQDDCEXDSCSCXEXXSXZCSZSZSZSZSAZQCAAQSQXQQWAWSWSWSWESEAESEDWDCQDDCEXDSCSCXEXXSXZCSZSZSZSZSAZQCAAQSQXQQWAWSWSWSWESEAESEDWDCQDDCEXDSCSCXEXXSXZCSZSZSZSZSAZQCAAQSQXQQWAWSWSWSWESEAESEDWDCQDDCEXDSCSCXEXXSXZCSZSZSZSZSAZQCAAQSQXQQWAWSWSWSWESEAESEDWDCQDDCEXDSCSCXEXXSXZCSZSZSZSZSAZQCAAQSQXQQWAWSWSWSWESEAESEDWDCQDDCEXDSCSCXEXXSXZCSZSZSZSZSAZQCAAQSQXQQWAWSWSWSWESEAESEDWDCQDDCEXDSCSCXEXXSXZCSZSZSZSZSAZQCAAQSQXQQWAWSWSWSWESEAESEDWDCQDDCEXDSCSCXEXXSXZCSZSZSZSZSAZQCAAQSQXQQWAWSWSWSWESEAESEDWDCQDDCEXDSCSCXEXXSXZCSZSZSZSZSAZQCAAQSQXQQWAWSWSWSWESEAESEDWDCQDDCEXDSCSCXEXXSXZCSZSZSZSZSAZQCAAQSQXQQWAWSWSWSWESEAESEDWDCQDDCEXDSCSCXEXXSXZCSZSZSZSZSAZQCAAQSQXQQWAWSWSWSWESEAESEDWDCQDDCEXDSCSCXEXXSXZCSZSZSZSZSAZQCAAQSQXQQWAWSWSWSWESEAESEDWDCQDDCEXDSCSCXEXXSXZCSZSZSZSZSAZQCAAQSQXQQWAWSWSWSWESEAESEDWDCQDDCEXDSCSCXEXXSXZCSZSZSZSZSAZQCAAQSQXQQWAWSWSWSWESEAESEDWDCQDDCEXDSCSCXEXXSXZCSZSZSZSZSAZQCAAQSQXQQWAWSWSWSWESEAESEDWDCQDDCEXDSCSCXEXXSXZCSZSZSZSZSAZQCAAQSQXQQWAWSWSWSWESEAESEDWDCQDDCEXDSCSCXEXXSXZCSZSZSZSZSAZQCAAQSQXQQWAWSWSWSWESEAESEDWDCQDDCEXDSCSCXEXXSXZCSZSZSZSZSAZQCAAQSQXQQWAWSWSWSWESEAESEDWDCQDDCEXDSCSCXEXXSXZCSZSZSZSZSAZQCAAQSQXQQWAWSWSWSWESEAESEDWDCQDDCEXDSCSCXEXXSXZCSZSZSZSZSAZQCAAQSQXQQWAWSWSWSWESEAESEDWDCQDDCEXDSCSCXEXXSXZCSZSZSZSZSAZQCAAQSQXQQWAWSWSWSWESEAESEDWDCQDDCEXDSCSCXEXXSXZCSZSZSZSZSAZQCAAQSQXQQWAWSWSWSWESEAESEDWDCQDDCEXDSCSCXEXXSXZCSZSZSZSZSAZQCAAQSQXQQWAWSWSWSWESEAESEDWDCQDDCEXDSCSCXEXXSXZCSZSZSZSZSAZQCAAQSQXQQWAWSWSWSWESEAESEDWDCQDDCEXDSCSCXEXXSXZCSZSZSZSZSAZQCAAQSQXQQWAWSWSWSWESEAESEDWDCQDDCEXDSCSCXEXXSXZCSZSZSZSZSAZQCAAQSQXQQWAWSWSWSWESEAESEDWDCQDDCEXDSCSCXEXXSXZCSZSZSZSZSAZQCAAQSQXQQWAWSWSWSWESESCCCCDSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS

daklqw的博客

博客

评论

发表评论