SDAU寒假训练三 题解（2019/1/16）

今天的比赛，怎么说呢，出了A E H三个，都是1A但是出的速度太慢了，第一题是区间DP的裸题，自己巴拉巴拉敲了一堆，结果不对，断点输出，变量监视全用上了，没毛病啊，结果发现最后输出结果那里忘了-1，emmm果然还是太笨了。E题题目读起来巨难理解，和旁边的郭大佬商量了老半天，想出了三个条件，凭着感觉暴力出来了（我还以为肯定不止三个条件呢，试试看就对了，到现在不知道自己思路是否正确，但是代码确实AC掉了）。H是树的直径啊，裸题。就那么弄上了，没啥技术含量。。。

【树状数组】Curious Robin Hood

Robin Hood likes to loot rich people since he helps the poor people with this money. Instead of keeping all the money together he does another trick. He keeps n sacks where he keeps this money. The sacks are numbered from 0 to n-1.

Now each time he can he can do one of the three tasks.

1)                  Give all the money of the ith sack to the poor, leaving the sack empty.

2)                  Add new amount (given in input) in the ith sack.

3)                  Find the total amount of money from ith sack to jth sack.

Since he is not a programmer, he seeks your help.

【最短路】Destroying Roads

In some country there are exactly n cities and m bidirectional roads connecting the cities. Cities are numbered with integers from 1 to n. If cities a and b are connected by a road, then in an hour you can go along this road either from city ato city b, or from city b to city a. The road network is such that from any city you can get to any other one by moving along the roads. 继续阅读【最短路】Destroying Roads

【思维+暴力】Block Towers

Students in a class are making towers of blocks. Each student makes a (non-zero) tower by stacking pieces lengthwise on top of each other. n of the students use pieces made of two blocks and m of the students use pieces made of three blocks.

The students don’t want to use too many blocks, but they also want to be unique, so no two students’ towers may contain the same number of blocks. Find the minimum height necessary for the tallest of the students’ towers. 继续阅读【思维+暴力】Block Towers