传送门

• https://atcoder.jp/contests/abc263

Problem E. Sugoroku 3

• 被遗忘的游戏史：“纸牌马里奥”和“桌上塞尔达”

题解：先写转移方程，发现自环的情况可以消掉，然后就很 straight forward。
（官方题解 居然没有看懂。。。）

#include <lastweapon/number>
#include <lastweapon/fenwicktree>
using namespace lastweapon;

const int N = int(2e5) + 9;
Int f[N]; int a[N];
int n;

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif

    RD(n); REP(i, n-1) RD(a[i]);
    fenwick_tree<Int> T(n);
    DWN(i, n-1, 0) f[i] = (T.sum(i+1, i+a[i]+1) + (a[i]+1)) / a[i];
    cout << f[0] << endl;
}

Problem F. Tournament

dp[u][i] 表示当前节点 u，获胜的玩家为 i 的最大得分。那么 i 当前轮次的连胜情况是可以通过 u 的高度推算出来的。
并且玩家 i 的得分和对手是无关的，因此 i 实际上是可以不记录在状态中的，复杂度 O(n2^n)。

实际在写的时候，在叶子处结算得分会更好写。
状态改成 dp[u][k] 表示当前节点为 u，且该节点的胜利者，未来向上还会连胜 k 场的最大得分。
（这个在状态中引入未来事件的方法很类似那个 SPOJ ZUMA）

#include <lastweapon/bitwise>
using namespace lastweapon;

const int N = int(16);
LL dp[1<<N][N+1]; int C[1<<N][N+1];
int n;

#define lx (x<<1)
#define rx (lx|1)
LL f(int x, int k) {
    if (x >= _1(n)) return C[x-_1(n)][k];
    LL &z = dp[x][k];
    if (!z) {
        ++k;
        z = max(f(lx,k)+f(rx,0),f(lx,0)+f(rx,k));
    }
    return z;
}

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif

    RD(n); REP(i, _1(n)) REP_1(j, n) RD(C[i][j]);
    cout << f(1, 0) << endl;
}

Problem G. Erasing Prime Pairs

带花树可以处理边权的情况么，我不太确定= =
那么首先不考虑 1 的情况，就是二分图匹配，于是我们可以枚举 1 之间的匹配重数，然后当成二分图匹配来做，这个函数显然是凸的，那么可以二分答案。
另一方面这个凸函数十分特殊，delta 是 {1,1,1,1,0,0,0,0,-1,-1,-1,-1} 这样的 pattern，可以直接计算两边的函数值，找到最优点。

Problem Ex. Intersection 2

给定 n 条直线，问所有的交点里，距离原点第 k 远的点的距离是多少。

我们要设法避免算出所有的交点。
考虑二分答案，那么子问题 f(x) 变成 n 条直线被半径为 x 的圆切割，然后这 n 条线段求交点总数，
因为所有交点都在圆周上，所以可以开个树状数组用辐角做扫描线，复杂度 O(nlogn)。

难点最后只有直线和圆求交点。。。（还好模板里有现成的。。相切的情况不用考虑，因为测度为 0。。
最后还需要用不等式估计一下二分的上界。。。

#include <lastweapon/geometry>
#include <lastweapon/fenwicktree>

using namespace lastweapon;
using namespace CG;

const int N = int(5e4) + 9;
DB d[N]; Line L[N];
int n, K;

int f(DB r) {
    Circle C(Po(0, 0), r); r *= r;
    vector<pair<double, int>> P; int m = 0;
    REP(i, n) if (d[i] < r){
        Po p0, p1; C.getIntersect(L[i], p0, p1);
        P.PB({p0.arg(), m}); P.PB({p1.arg(), m});
        ++m;
    }

    int z = 0; VI l(m, -1); fenwick_tree<int> T(m*2); SRT(P);
    REP(i, m*2) {
        int x = P[i].se;
        if (~l[x]) {
            T.add(l[x], -1);
            z += T.sum(l[x], i);
        } else {
            T.add(l[x] = i, 1);
        }
    }
    return z;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif

    RD(n, K); REP(i, n) {
        int A,B,C; RD(A,B,C);
        if (!A)
            L[i] = Line(Po(0, (DB)-C/B), Po(1, (DB)-C/B));
        else if (!B)
            L[i] = Line(Po((DB)-C/A, 0), Po((DB)-C/A, 1));
        else if (!C)
            L[i] = Line(Po(0, 0), Po(-B, A));
        else
            L[i] = Line(Po((DB)-C/A, 0), Po(0, (DB)-C/B));
        d[i] = dist2(L[i], Po(0, 0));
    }

    DB l = 0, r = 1e7;
    DO(233) {
        DB m = (l + r) / 2;
        if (f(m) < K) l = m;
        else r = m;
    }
    printf("%.9f\n", l);
}

Posted by xiaodao
Category: 日常