Level 1
Coin Flip: 签到
Delicious Dishes: 签到
Sridhar Likes Travelling：签到
Level 2
A Wonderful Chocolate：SCDP + 矩阵
Candy Collecting Game：DP Lucky Balance：组合
Jam Board：并查集 ( 注意卡 scanf()… 使用 getchar() .. .
Level 3
Arithmetic Progressions：链表优化暴力 ( 快速 FFT
Martial Arts：费用流 || KM ??
Many Left：卡时 + 启发式贪心
。。。考试周。。各种忙爆。。 himehime 做掉了 3 道签到题。。我做了中间 5 道题。。附加题中间交了 1 次。。。最后一天又改了改。。。。。。（。再次对 ACRush 深表敬佩。。真完美主义者！。跪烂！。
.. 本月最有价值的题是 Martial Arts
“给定一个 n 阶带权二分完全图。。求一个完备匹配。。使得该完备匹配去掉一组权值最大的边后。。权值最大。”。。。 ( n <= 100 .. )
。。（如果如果是求 n-1 条边的最优匹配的话可以直接费用流。。但是题目中问题的定义略有不同。。二分答案的话似乎这个题只是局部单调。。 已知最大权完备匹配（多解时取最大值最短的那组）。。减去权值最大的一条边是一个 “潜在解”。。（除此潜在解之外。。还有哪些是潜在解？。。如何通过增广转移过去？。。
————
。。。。也就是说我这个 SB 一开始就把题目抽象错了。。。实际上 tie-breaking 的情况是需要仔细处理的。（同样是因为 tie-breaking 的原因。。使得解只是局部单调。。无法直接二分答案。。）。我开始以为标程被 cha。。后来发现只是写解题报告的人也没有完全理解清楚。。评论的地方 anton_lunyov 给了极好的描述。。。总之直接看 Editorial 吧。。。
（也就是说可以理解成有两个玩家。。玩家 A（防御方）确定一个完备匹配。。之后玩家 B ( 进攻方）会干掉一个最优边。。注意这个和 k 部最优匹配之间的不同。这个问题要难很多。。）。。
。。唔。。。问题的关键是表述成 “a function of the weight of the highest weighted edge” 。。。之后拍 “Dynamic Assignment Problem” 。。( 只有单边修改操作。。)。。。一般情况下玩家 A 和玩家 B 朝相反方向决策。。而在 tie-breaking 的情况。。玩家 A 和 玩家 B 的目标又变得一致了。。这样直接向题解里开始说的 “To handle this we can consider each edge’s weight as pair (score difference, score to home team)” 是不行的。。我们需要这个结构设计两个比较函数。。
。。。基本融合了 标程 和 anton_lunyov 的写法。。（anton_lunyov 是排序后正向插入边表。。标程是逆序删除。 … (。这样可以得到一个 5s 左右的剪枝。。
struct rec{
LL x, y;
rec(LL _x = 0):x(_x),y(_x){}
rec(LL x, LL y):x(x),y(y){}
rec operator+ (const rec &rhs) const {return rec(x+rhs.x, y+rhs.y);}
void operator+=(const rec &rhs) {x+=rhs.x, y+=rhs.y;}
rec operator- (const rec &rhs) const {return rec(x-rhs.x, y-rhs.y);}
void operator-=(const rec &rhs) {x-=rhs.x, y-=rhs.y;}
rec operator-() const {return rec(-x, -y);}
bool operator==(const rec &rhs) const {return x==rhs.x && y==rhs.y;}
bool operator< (const rec &rhs) const {return x<rhs.x || x==rhs.x && y<rhs.y;}
bool operator<=(const rec &rhs) const {return x<rhs.x || x==rhs.x && y<=rhs.y;}
bool isZero() const {return (*this) == rec();}
bool operator!() const {return isZero();}
void output(){
printf("%lld %lld\n", y, y - x);
}
} W[N][N], lx[N], ly[N], slack[N];
inline bool comp(const rec &lhs, const rec &rhs){ //Player B perspective .. .
return lhs.x < rhs.x || lhs.x == rhs.x && lhs.y > rhs.y;
}
。。权值对象。。以 pair 的形式存储 G-S 和 G 。。（。。。支持两个比较函数。。默认的小于。。和在 tie-breaking 下。。玩家 B 为视角的小于。。
。之后紧接一个 动态匈牙利 算法的模板。。。
int px[N], py[N], pxx[N], ps[N], Q[N], op, cz;
bool vx[N], vy[N];
int n;
#define w(x, y) (lx[x] + ly[y] - W[x][y])
void add_to_tree(int x, int xx){
vx[Q[op++] = x] = true, pxx[x] = xx;
REP(y, n) if (w(x, y) < slack[y])
slack[y] = w(x, y), ps[y] = x;
}
void augment(int root){ // 1. Designate each exposed (unmatched) node in V as the root of a Hungarian tree.
int x, y; RST(vx, vy), op = cz = 0;
pxx[x = root] = -1, add_to_tree(x, -1);
REP_N(y, n) slack[y] = w(x, y), ps[y] = x;
while (true){
while (cz < op){ // 2. Grow the Hungarian trees rooted at the exposed nodes in the equality subgraph.
x = Q[cz++]; REP_N(y, n) if (w(x, y).isZero() && !vy[y]){
if (py[y] == -1) goto Augment;
vy[y] = true, add_to_tree(py[y], x);
}
}
rec delta = rec(INFF); // 3. Modify the dual variables lx and ly as follows to add new edges to the equality subgraph.
REP(i, n) if (!vy[i]) checkMin(delta, slack[i]);
REP(i, n){
if (vx[i]) lx[i] -= delta;
if (vy[i]) ly[i] += delta; else slack[i] -= delta;
}
REP_N(y, n) if (!vy[y] && slack[y].isZero()){ // 2.' Grow the Hungarian trees directely by the new edges in the equality subgraph.
if (py[y] == -1){
x = ps[y];
goto Augment;
}
else {
vy[y] = true; if (!vx[py[y]])
add_to_tree(py[y], ps[y]);
}
}
}
assert(0); // !! Impossible Position !!..
Augment: for (int t;x!=-1;x=pxx[x],y=t) // 4. Augment the current matching by flipping matched and unmatched edges along the selected augmenting path.
t = px[x], py[y] = x, px[x] = y;
}
void KM(){
static bool first_time = true;
if (first_time){
first_time = false;
FLC(px, py, -1), RST(lx, ly);
REP_2(i, j, n, n) checkMax(lx[i], W[i][j]);
REP(root, n) augment(root);
}
else {
// .. .
}
}
#define y px[x]
rec maximum_match(){
rec res = rec(); REP(x, n) res += W[x][y];
return res;
}
rec secondary_match(){
rec del = rec(0); REP(x, n) checkMax(del, W[x][y], comp);
return maximum_match() - del;
}
#undef y
。。。此处的两个小函数。。分别是返回完备匹配。。和被删除一条边后的完备匹配。（下称亏格为 1 的匹配。。。。
vector<pair<PLL,PLL> > E;
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
RD(n); REP_2(i, j, n, n){
LL p1, p2; RD(p1, p2);
W[i][j] = rec(p1-p2, p1);
E.PB(MP(MP(W[i][j].x, -W[i][j].y), MP(i,j)));
}
KM(), SRT(E);
rec res = rec(-N*V);
DWN(i, SZ(E), 0){
int x = E[i].se.fi, y = E[i].se.se;
int yy = px[x]; if (yy != y){
W[x][y] = rec(V), px[x] = py[yy] = -1;
checkMax(lx[x], W[x][y] - ly[y]);
augment(x);
}
checkMax(res, secondary_match());
W[x][y] = rec(-N*V);
if (px[x]==y) {
px[x] = py[y]=-1;
augment(x);
}
if (maximum_match() <= res) break; // Cut .. .
}
res.output();
}
。。主函数。。（主要是排序边表。。以及逆序挨个删边。。。。
枚举每条边。。将该边的权值设置成最大（保证其一定被选中。增广一次后取解。。（此时求出的解此边的函数。。
。。。之后在设置成负无穷大。（。。表示删边。。删边不会导致可行顶标的修改。。但是也要增广一次。。
其次是 Arithmetic Progressions 。。
“给定一个长度为 n 数列 {an}，求所有满足 i < j < k，且 a[j] – a[i] = a[k] – a[j] 的三元组数。。”
( n <= 1e6, 1 <= ai <= 3e4 .. . )
。。开始的想法是链表优化的暴力算法。。。。然后是觉得正解应该是分块后使用 FFT。但是一交 TLE 。（当时猜测是常数写渣了。。后来发现确实是这样 T T。。。
。。。后来这个题就被搁置了。。直到期中考试前夕在评论区里看到姿势帝 anton_lunyov 说他姿势过了这题。。（。无限仰慕。。。。
“@kunalgaurav18 Because of the condition i < j < k. Well, for me this condition ruins very beautiful solution. Currently to handle this condition I have very bad solution that pass the TL which were very surprisingly for me.”
。。。然后我揣测了一下他这个思路。。回来写了一发居然过了。。 。。（。。大概是把分成前面一半和后面一半。。注意处理左边一半时要先插入进去然后逆序 Resume。。。（类似对 Dance Link 的处理。。
（最有仰慕一下 Rank I 的 CPU 并行的神犇。。标程已被撸爆！。）
————– PS :
… 给 SB Codechef 的 UI 跪了啊。。。每次进去要载入一个 Facebook 按钮。。然后呵呵呵你懂的。结果页面右边出来一大片白。。把各种按钮什么的全遮住了。。
。。。。每次都要用 审查元素 Kill 掉。。。。）
