UVa 12545 – Bits Equalizer

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=3990

這題因為可以任意調換位置，所以要盡可能減少掉換次數，可以採取Greedy策略。另外，因為不存在1轉換成0的操作，所以如果原字串0 + ?的個數小於目標字串0的個數，則無解。

UVa 11624 – Fire!

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=543&page=show_problem&problem=2671

題目大意：

給你一張迷宮圖，圖上有四種標記，分別代表人、火焰、牆壁、可以走的路，可能會有多個火焰，但人只有一個，火每單位時間會往上下左右擴展一步，人則可以選擇往四個方向走一步，但有火的地方不能走，問你人是否能安全逃出迷宮?如果可以還要輸出最短時間。

UVa 501 – Black Box

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=442

利用二分搜尋法尋找要插入Black Box的點，使Black Box非嚴格遞減排序。

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

int main()
{
	int dataset;
	int M, N;
	int A[30001];
	int U[30001];
	int Box[30001];
	int size, index;

	scanf("%d", &dataset);
	while(dataset --)
	{
		scanf("%d %d", &M, &N);
		for(int i = 1; i <= M; i ++)
			scanf("%d", &A[i]);
		for(int i = 1; i <= N; i ++)
			scanf("%d", &U[i]);

		size = 0, index = 0;
		for(int i = 1; i <= N; i ++)
		{
			while(size < U[i])
			{
				size ++;
				int key = A[size];

				int l = 1, r = size - 1, m;
				while(l <= r)
				{
					m = (l + r) / 2;
					if(Box[m] < key)
						l = m + 1;
					else
						r = m - 1;
				}

				for(int i = size - 1; i >= l; i --)
					Box[i + 1] = Box[i];
				Box[l] = key;

			}

			index ++;
			printf("%d\n", Box[index]);
		}

		if(dataset > 0) printf("\n");
	}

	return 0;
}

Codeforces 509 C. Sums of Digits

http://codeforces.com/contest/509/problem/C

前面爽爽過兩題後，我剩下的時間都栽在這題，最後我甚至還認為，我的Code有de不了的bug……後來比賽完參考別人的Code，我才恍然大悟，我覺得有時候要弄清楚問題的本質，不要一直ㄍㄧㄥ在你最原始的想法，換個方法事情說不定會變簡單!

這是我參考某大大的Code

http://codeforces.com/contest/509/submission/9663004

感覺超淺顯易懂的，所以我就模仿一下啦!至於原來的Code……就算了吧~~~

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

int digit[1000] = {};
int len = 0;

void nextInt(int d)
{
    int idx;
    for(idx = 1; d > 0; idx++)
    {
        while(d > 0 && digit[idx] < 9)
        {
            d--;
            digit[idx]++;
        }
        if(idx > len) len = idx;
    }
}

void printInt()
{
    int idx;
    for(idx = len; idx >= 1; idx--)
        cout << digit[idx];
    cout << endl;
}

void solve(int d)
{
    if(d > 0)
    {
        nextInt(d);
    }
    else
    {
        int idx;
        for(idx = 1; ; idx++)
        {
            if(idx > len) len = idx;
            
            if(d > 0 && digit[idx] < 9)
            {
                d--;
                digit[idx]++;
                nextInt(d);
                break;
            }
            
            d += digit[idx];
            digit[idx] = 0;
        }
    }
    
    printInt();
}

int main()
{
    int n;
    int sum[310];
    
    cin >> n;
    
    sum[0] = 0;
    for(int i = 1; i <= n; i++)
        cin >> sum[i];
        
    for(int i = 1; i <= n; i++)
        solve(sum[i] - sum[i - 1]); 
    
    
    return 0;
}