某岛

… : "…アッカリ~ン . .. . " .. .
April 8, 2020

Andrew Stankevich Contest 12

https://codeforces.com/gym/100215

Problem A. Brackets

从左到右扫,开个栈记录最优解。

Problem B. Dividing a Chocolate

斐波那契数列?

Problem C. Thermal Death of the Universe

线段树裸题,注意一下负数的 round 规则。

Problem D. Equations System

在多项式上跑扩展欧几里得。

Problem E. Fool’s Game

Wiki, Hall’s marriage theorem

Problem F. Lottery

直接组合 DP 就好。。。转移和 #27 的 G 几乎一样。

Problem G. Two Pipelines

简单计算几何,点到直线距离。贪心初始解调整一下即可。

Problem H. Manhattan Police

啊,曼哈顿。。。。

So now the wants to find out what minimal amount of money is needed to allow
people of Manhattan to get from any location to any other location turning only on crossings guarded by policemen.

这个题要把这个区域连通起来且代价最小,所以显然是求最小生成树,一共行+列个点,每个十字路口对应一条边。
bfs() 一次把所有边抠出来即可。

Problem I. Regular Words

三维版本的卡塔兰序列!数据范围很小,暴力组合 dp 即可。

Problem J. Greate Siberian Wall

最小外接三角形?这我哪会做啊。。

Problem K. Words Game

Dead-do