传送门
Table of Contents
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);
}
