MoonChasing

传送门: 2018 牛客网暑期 ACM 多校训练营 (第五场) F.take

Problem

Description

Kanade has n boxes , the i-th box has p[i] probability to have an diamond of d[i] size.

At the beginning , Kanade has a diamond of 0 size. She will open the boxes from 1-st to n-th. When she open a box,if there is a diamond in it and it’s bigger than the diamond of her , she will replace it with her diamond.

Now you need to calculate the expect number of replacements.

You only need to output the answer module 998244353.

Accepts: 791 Submissions: 2435
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)

Problem

Description

度度熊专门研究过 “动态传递闭包问题”，他有一万种让大家爆蛋的方法；但此刻，他只想出一道简简单单的题 —— 至繁，归于至简。

度度熊有一张 n 个点 m 条边的无向图，第 $i$ 个点的点权为 $v_i$。

如果图上存在一条路径使得点 i 可以走到点 j，则称 i,j 是带劲的，记 $f (i,j)=1$；否则 $f (i,j)=0$。显然有 $f (i,j) = f (j,i)$。

度度熊想知道求出：$\sum ^{n-1}{i=1} \sum^{n}{j=i+1} f(i, j) \times \max(v_i, v_j) \times (v_i & v_j)$

我失去了一只臂膀， 就睁开了一只眼睛。
—— 顾城

Problem

Given an unsorted integer array, find the smallest missing positive integer.

传送门：Fire Game

人一我百！人十我万！永不放弃～～～怀着自信的心，去追逐梦想 ——kuangbin

Problem

Description

Fat brother and Maze are playing a kind of special (hentai) game on an N*M board (N rows, M columns). At the beginning, each grid of this board is consisting of grass or just empty and then they start to fire all the grass. Firstly they choose two grids which are consisting of grass and set fire. As we all know, the fire can spread among the grass. If the grid (x, y) is firing at time t, the grid which is adjacent to this grid will fire at time t+1 which refers to the grid (x+1, y), (x-1, y), (x, y+1), (x, y-1). This process ends when no new grid get fire. If then all the grid which are consisting of grass is get fired, Fat brother and Maze will stand in the middle of the grid and playing a MORE special (hentai) game. (Maybe it’s the OOXX game which decrypted in the last problem, who knows.)

传送门：Pots

人一我百！人十我万！永不放弃～～～怀着自信的心，去追逐梦想 ——kuangbin

Problem

Description

You are given two pots, having the volume of A and B liters respectively. The following operations can be performed:

1. FILL(i) fill the pot i (1 ≤ i ≤ 2) from the tap;
2. DROP(i) empty the pot i to the drain;
3. POUR(i,j) pour from pot i to pot j; after this operation either the pot j is full (and there may be some water left in the pot i), or the pot i is empty (and all its contents have been moved to the pot j).

Write a program to find the shortest possible sequence of these operations that will yield exactly C liters of water in one of the pots.

人一我百！人十我万！永不放弃～～～怀着自信的心，去追逐梦想 ——kuangbin

看了一眼，水题， 不想写了， 感觉提高不大。

传送门：Prime Path

人一我百！人十我万！永不放弃～～～怀着自信的心，去追逐梦想 ——kuangbin

Problem

Description

The ministers of the cabinet were quite upset by the message from the Chief of Security stating that they would all have to change the four-digit room numbers on their offices.

传送门：Find the Multiple

人一我百！人十我万！永不放弃～～～怀着自信的心，去追逐梦想 ——kuangbin

Problem

Description

Given a positive integer n, write a program to find out a nonzero multiple m of n whose decimal representation contains only the digits 0 and 1. You may assume that n is not greater than 200 and there is a corresponding m containing no more than 100 decimal digits.

传送门：Fliptile

人一我百！人十我万！永不放弃～～～怀着自信的心，去追逐梦想 ——kuangbin

Problem

Description

Farmer John knows that an intellectually satisfied cow is a happy cow who will give more milk. He has arranged a brainy activity for cows in which they manipulate an M × N grid (1 ≤ M ≤ 15; 1 ≤ N ≤ 15) of square tiles, each of which is colored black on one side and white on the other side.

人一我百！人十我万！永不放弃～～～怀着自信的心，去追逐梦想 ——kuangbin

传送门：POJ 3278 Catch That Cow

Problem

Description

Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.