# LightOJ 1269.Consecutive Sum(01字典树)

传送门:LightOJ 1269..Consecutive Sum

## Problem

### Description

Little Jimmy is learning how to add integers. As in decimal the digits are 0 to 9, it makes a bit hard for him to understand the summation of all pair of digits. Since addition of numbers requires the knowledge of adding digits. So, his mother gave him a software that can convert a decimal integer to its binary and a binary to its corresponding decimal. So, Jimmy’s idea is to convert the numbers into binaries, and then he adds them and turns the result back to decimal using the software. It’s easy to add in binary, since you only need to know how to add (0, 0), (0, 1), (1, 0), (1, 1). Jimmy doesn’t have the idea of carry operation, so he thinks that

1 + 1 = 0

1 + 0 = 1

0 + 1 = 1

0 + 0 = 0

Using these operations, he adds the numbers in binary. So, according to his calculations,

3 (011) + 7 (111) = 4 (100)

Now you are given an array of **n** integers, indexed from **0** to **n-1**, you have to find two indices **i j** in the array **(0 ≤ i ≤ j < n)**, such that the summation (according to Jimmy) of all integers between indices **i** and **j** in the array, is maximum. And you also have to find two indices, **p q** in the array **(0 ≤ p ≤ q < n)**, such that the summation (according to Jimmy) of all integers between indices **p** and **q** in the array, is minimum. You only have to report the maximum and minimum integers.

### Input

Input starts with an integer **T (****≤ 10)**, denoting the number of test cases.

Each case starts with a line containing an integer **n (1 ≤ n ≤ 50000)**. The next line contains **n** space separated non-negative integers, denoting the integers of the given array. Each integer fits into a 32 bit signed integer.

### Output

For each case, print the case number, the maximum and minimum summation that can be made using Jimmy’s addition.

### Sample Input

2

5

6 8 2 4 2

5

3 8 2 6 5

### Sample Output

Case 1: 14 2

Case 2: 15 1

### Note

Dataset is huge, use faster I/O methods.

## Solution

# FZU 2150 Fire Game(BFS)

传送门：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.)

# 百度之星2018复赛 1003.带劲的and和

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)$

# 2018牛客网暑期ACM多校训练营(第五场) F.take (树状树组求期望)

传送门: 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.

# POJ 3414 Pots(BFS+记录路径)

传送门：Pots

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

## Problem

### Description

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

- FILL(i) fill the pot
**i**(1 ≤**i**≤ 2) from the tap; - DROP(i) empty the pot
**i**to the drain; - 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.

# POJ 3126 Prime Path(素数表+BFS)

传送门：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.

# POJ 1426 Find The Multiple(BFS)

人一我百！人十我万！永不放弃~~~ 怀着自信的心，去追逐梦想 ——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.

# POJ 3087 Shuffle'm Up(模拟)

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

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

# POJ 3279 Fliptile(爆搜+一点点状压的知识)

传送门：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.