Contents

## Cute Numbers

For you, numbers have personalities. The number 4 is elegant, 18 is strong and 42 is enigmatic. And, of course, any number ending in 0 is cute.

The more zeroes at the end of a number, the cuter that number is. Therefore 70, 36640 and 1800090 are only a little bit cute (ending in just one zero), whereas 400 and 99200 are very cute (ending in two zeroes) and 30000 is really really cute (ending in four zeroes).

Your task is to read in a number *N* and determine how many zeroes are at the end of that number, so you can tell just how cute the number is.

### Solution

思博题，代码都不想贴

## Curry

You are at a very fancy dinner party with some very good friends, trying to eat a very hot curry. On your plate is a pile of curry, rice and vegetables. You are finding it quite difficult to eat, since the curry is too hot, the rice is too sticky and you don't like vegetables.

To work around this problem, you eat in such a way that each mouthful includes a scoop of two different items. For example, the first mouthful might include a scoop of curry with a scoop of rice. The next mouthful might include a scoop of rice with a scoop of vegetables. You cannot eat three scoops all at once, since your spoon is too small.

The danger with your plan is that you might not be able to finish your meal. At last week's dinner party you started off by eating all your curry and rice, which meant that you could not finish your vegetables since there was nothing left to eat them with. It was most embarrassing. Determined not to be humiliated again, you pull your laptop out of your bag and tap away secretly beneath the table, hoping to solve your eating problems for once and for all.

Your task is to work out how to eat your meal so that you eat as much total food as possible.

### Solution

每次取最大的两个减下就好了，懒得写if于是干脆用了优先队列

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include <bits/stdc++.h> using namespace std; struct node { int id, val; node(){} node(int _, int __){id = _; val = __;} friend bool operator< (node a, node b) { return a.val < b.val; } }; priority_queue<node> q; int c,r,v,ans[4]; node x,y; int main() { freopen("curryin.txt","r",stdin); freopen("curryout.txt","w",stdout); cin >> c >> r >> v; q.push(node(1,c)); q.push(node(2,r)); q.push(node(3,v)); while(1) { x = q.top(); q.pop(); y = q.top(); q.pop(); if(!y.val) break; x.val --; y.val --; q.push(x); q.push(y); if((x.id == 2 && y.id == 3)||(x.id == 3 && y.id == 2)) ++ ans[1]; else if((x.id == 2 && y.id == 1)||(x.id == 1 && y.id == 2)) ++ ans[3]; else ++ ans[2]; } cout << ans[1] << ' ' << ans[2] << ' ' << ans[3]; return 0; } |

## Landmark

You are mayor of the city, and it's almost election time. It is clear to you that the only way to get re-elected is to construct a huge landmark in the centre of the city. Perhaps a bird park, since the polls show that most people associate colourful birds with happiness.

Trouble is, the city is already full of buildings and there is no free space. To build your bird park, you will need to knock some buildings down.

The city is divided into square blocks. Each block is either commercial or residential. You cannot knock down any commercial buildings, since the businesses will get angry and stop donating to your campaign fund. You therefore need to find a suitable residential area that can be knocked down so that you can build your new bird park and make your citizens happier people.

The bird park will be rectangular in shape. Due to building regulations it may only be one block wide, though it can be as long as you like. The bird park may be placed either horizontally or vertically in the city.

Two city maps of 5 x 6 blocks are illustrated below. In each map the commercial blocks are coloured black, and the blocks used to create the largest possible bird park are marked with the letter `B`. In the first map, the largest possible bird park is horizontal and four blocks in length, whereas in the second map it is vertical and three blocks in length.

### Solution

一开始以为是最大全0子矩阵于是乎写了一发悬线法。。扫了一眼题意发现这玩意宽度为

然后暴力搞搞就好了

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include <bits/stdc++.h> using namespace std; #define rep1(i,t) for(int i = 1; i <= t; ++ i) const int N = 1005; int n, m, ax, ay, bx, by, ans, cur; char g[N][N]; int main() { freopen("landin.txt","r",stdin); freopen("landout.txt","w",stdout); scanf("%d%d",&n,&m); ++ m; rep1(i,n) {scanf("%s",g[i]+1); g[i][m] = '#';} rep1(i,n) { cur = 0; rep1(j,m) { if(g[i][j] == '.') ++ cur; else { if(cur > ans){ax = i; ay = j-cur; bx = i; by = j-1; ans = cur;} cur = 0; } } } rep1(i,m-1) { cur = 0; rep1(j,n) { if(g[j][i] == '.') ++ cur; else { if(cur > ans){ax = j-cur; ay = i; bx = j-1; by = i; ans = cur;} cur = 0; } } if(cur > ans){ax = n-cur+1; ay = i; bx = n; by = i; ans = cur;} } printf("%d %d %d %d",ax,ay,bx,by); return 0; } |

## Sculpture

As a highly acclaimed sculpture artist, you have been commissioned to make an abstract 3-dimensional artwork to commemorate the Melbourne International Fruit Festival.

You have decided to construct an elaborate tree by joining apples together with sticks of wood. The artwork will have a single apple at its base, with two wooden sticks rising up to meet new apples. Each of these apples has two more wooden sticks rising up to meet two new apples, and so on. An example of such a tree is illustrated below, where the apples are numbered from 1 to 9 and the lengths of the sticks are shown.

Consider the apples with no new sticks rising up — call these the *top apples*. In the example above, the top apples are numbers 4, 5, 7, 8 and 9. By examining the stick lengths, we can measure the distance from each top apple to the base of the tree. These distances are as follows.

Unfortunately you are running short of wood, and so you would like to add the smallest total length possible. For the example above, you could change the stick lengths as follows (changed lengths are indicated with arrows).

You must write a program that reads in a tree of apples and sticks, and then determines the smallest total increase in stick lengths that is needed to bring all top apples to the same distance from the base.

### Solution

考虑贪心，显然尽可能往离根近的边加值最优，但是加值要考虑到不能溢出上限

那么问题来了，上限怎么确定呢？（上限即调整后最终根到叶子节点的距离）

结论是，一开始根到叶子节点的距离的最大值即为上限，大概yy下就能发现是正确的

于是大概做法是：

先跑一次树DP，记录以为根的最远节点到整棵树的根的距离的最大值

那么我们的上限就是

再进行一次分治即可，时间复杂度

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include <bits/stdc++.h> using namespace std; #define rep(i,s,t) for(int i = s; i <= t; ++ i) const int N = 50005; int n, son[N][2], path[N][2], dis[N], ans, f; int heavs[N]; bool isleaf(int x){return son[x][0] == 0;} void dfs(int x) { if(isleaf(x)) {heavs[x] = dis[x]; return;} rep(i,0,1) { dis[son[x][i]] = dis[x] + path[x][i]; dfs(son[x][i]); heavs[x] = max(heavs[x], heavs[son[x][i]]); } } void work(int x,int g) { if(isleaf(x)) return; ans += f-(heavs[son[x][0]]+g); work(son[x][0],f-heavs[son[x][0]]); ans += f-(heavs[son[x][1]]+g); work(son[x][1],f-heavs[son[x][1]]); } int main() { freopen("sculpin.txt","r",stdin); freopen("sculpout.txt","w",stdout); scanf("%d",&n); rep(i,1,n) scanf("%d%d%d%d",&son[i][0],&path[i][0],&son[i][1],&path[i][1]); dfs(1); rep(i,1,n) if(!son[i][0] && !son[i][1]) f = max(f,dis[i]); work(1,0); printf("%d",ans); return 0; } |

## Chimpanzee

It has been a long hard day trekking through the jungle, and it is almost dark. Exhausted, you sit down to rest and pull a book from your backpack for some light reading. Suddenly, with an excited cry, a chimpanzee leaps from a nearby tree and snatches the book from your hands.

In horror you watch as the chimpanzee runs through the jungle in a spiral pattern, ripping pages from your book as it goes. Soon your horror gives way to curiosity as you contemplate the very precise spiral pattern that the chimpanzee is following.

Consider the jungle to be a grid of squares in a coordinate system, where you are sitting at square (0,0). The chimpanzee follows a tight spiral out from (0,0) as illustrated below.

Fortunately you have also brought your laptop on your jungle trek. Pulling it from your bag and plugging it into a nearby power point, you sit down to write a program that will help you put the pages together in the correct order.

Your specific task is to write a program that reads in a pair of (*x*,*y*) coordinates and outputs which page the chimpanzee has left in that square.

### Soluion

大概就是分象限，举例子，然后手推推，~~然后assert崩出数据判断哪里错了~~

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include <bits/stdc++.h> using namespace std; #define rep(i,s,t) for(int i = s; i <= t; ++ i) int n, x, y, ans; int main() { freopen("chimpin.txt","r",stdin); freopen("chimpout.txt","w",stdout); cin >> x >> y; n = max(abs(x),abs(y)); rep(i,1,n-1) ans += 4*(2*i+1)-4; if(x > 0 && y < 0 && x == -y) {cout << ans + 4*(2*n+1)-4; return 0;} if(x == 0) { if(y>0) ans += 3*n; else if(y<0) ans += 7*n; } if(y == 0) { if(x>0) ans += n; else if(x<0) ans += 5*n; } if(x>0 && y>0) { if(x < n) ans += 3*n-x; else ans += n + y; } if(x>0 && y<0) { if(x < n) {ans += 4*(2*n+1)-4; ans -= n-x;} else ans += n-abs(y); } if(x<0 && y>0) { if(x > -n) ans = ans + 3*n - x; else ans = ans + 5*n - y; } if(x<0 && y<0) { if(x > -n) ans = ans + 7*n + x; else ans = ans + 5*n - y; } printf("%d",ans); return 0; } |