2014 ACM/ICPC Asia Regional Beijing Online

Problem 1001. Always Cook Mushroom

Brief description:

给定一个 [1, 1000] x [1, 1000] 的点阵,每个点阵中的点有一个权值。
n 组询问,每次询问一个由 (0,0)、(x,0) 点一以及从原点出发的方向向量 (a,b) 构成的直角三角形包围的点的权值和。

Analysis:

离线,极角排序,树状数组。
http://vjudge.net/vjudge/problem/viewSource.action?id=2788351

Problem 1002. Building

Brief description:

x-轴上分布着 n 个位置为 xi,高度为 hi 的建筑物,问位置在 qi 的某个人,左右的视角有多少。人的高度为 0,并且不与建筑物重叠。

Analysis:

栈维护下凸壳。

http://vjudge.net/vjudge/problem/viewSource.action?id=2773898

(参见… SPOJ 13031. Vision Field/a>
Tsinsen A1377. 楼房重建

Problem 1005. Explosion

Brief description:

给定一个有向图,每个结点打开后,可以自动打开它的传递闭包。
问期望要暴力打开多少结点,可以打开所有结点。

Analysis:

http://codeforces.ru/problemset/problem/280/C
做法同这个题。根据期望的线性性,统计每个结点对期望的贡献为 1 的概率即可。
强连通缩点,后转换成 DAG,那么每个结点要么自己打开要么被一个能够到达它的结点打开。

http://vjudge.net/vjudge/problem/viewSource.action?id=2773890

Problem 1006. Frog

Brief description:

青蛙踩石子过河,河宽 [0, m],有 n 个石子坐标已知。青蛙每次最多跳 L,初始在 0。
现在可以在河中再放一些石子,要求在保证青蛙可以跳到 m 的情况下,使得青蛙在跳的步数最少的情况下次数最多。

Analysis:

好题!
。。。对已经存在的石子排序。从前往后一次处理。。。如果这一步可以一步跳过去,要讨论是否青蛙上一步就已经可以跳过去了。(相当于双方在博弈,到这里主要是知道需要保存上一步跳的距离 ll)。。如果一步跳不过去,那么可以知道每 (l+1) 长度至多需要跳两步。设这两步分别是aa,bb:

ll + aa = l+1
aa + bb = l+1

可知不会影响 ll,那么对直接用距离对 (l+1) 取模,可以规约到前面的情况。

//}/* .................................................................................................................................. */

const int N = int(1e5) + 9;
int n;

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    Rush{
        int n, m, l; RD(n, m, l); int x = 0, ll = l, c = 0;
        VI I; REP(i, n) I.PB(RD()); I.PB(m); UNQ(I); ECH(i, I){

            int d = *i - x; x = *i; if (d >= (l+1)){
                c += d / (l+1) * 2;
                d %= (l+1);
            }

            if (d + ll <= l){
                ll += d;
            }
            else{
                ll = d;
                ++c;
            }
        }
        OT(c);
    }
}

http://vjudge.net/vjudge/problem/viewSource.action?id=2788406

Problem 1008. Hilarity

Brief description:

给定一棵边权为 0/1 的树,要求支持两类操作:
1. 询问有多少条路径 xor 和为 1。
2. 修改一条边的权值。

Analysis:

。。(u, v) 路径的 xor 和。。。等价于 (1, u) xor (1, v)。。
。。于是用线段树维护所以从 (1, x) 的路径就可以了。。
。。修改操作等价于区间取反。

http://vjudge.net/vjudge/problem/viewSource.action?id=2773880

Problem 1009. Instrusive

Brief description:

给定一个 N*N 的格子,从 MT ,有些格子中有初始状态指向东西南北的摄像头,每 1s 顺时针转动 90 度,监控范围为摄像头所在的格子和它指向的一个格子。如果当前格子和下一个格子出发时刻都没被监,则移动的代价是 1s,否则移动需要 3s。可以等待不动,无论当前时刻是否被监控,等待的代价都是 1s。求最少的时间。

Analysis:

Dijkstra,题意不是很清楚,几乎无法一遍 AC。。。

题意
但从A格子走到B格子,其实时刻Ax,到达B的时刻Ax+1,如果在Ax时刻AB格子均不被照且AB格子均不是照相机,但是Ax+1时刻B被照,那么这个代价是1还是3?
team0227 北京航空航天大学 at 2014-09-21 16:25:40

RE:题意
1
admin at 2014-09-21 16:27:16                 

http://vjudge.net/vjudge/problem/viewSource.action?id=2784472