AtCoder Beginner Contest 263
source link: https://www.shuizilong.com/house/archives/atcoder-beginner-contest-263/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
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_JUDGEfreopen("in.txt", "r", stdin);//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);#endifRD(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_JUDGEfreopen("in.txt", "r", stdin);//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);#endifRD(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_JUDGEfreopen("in.txt", "r", stdin);#endifRD(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));elseL[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: 日常
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK