2015年11月30日 星期一

[UVA] 402 - M*A*S*H

/* 題目: UVa 402 - M*A*S*H
 * Language: C++
 * Created on: 2015年12月1日
 *   Author: hanting
 */
#include <iostream>
#include <vector>
using namespace std;
void killSomeone(vector<int> &vec, int &n, int &num)
{
     int t = n - 1;
     while (vec.size() > num and t < vec.size())
     {
           vec.erase(vec.begin() + t);
           t += n - 1;
     }
}
int main()
{
     int N; // N people
     int testCase = 1;
     while (cin >> N)
     {
           int luckyMan = 0;
           cin >> luckyMan;
           vector<int> point(20);
           vector<int> man(N);
           for (int i = 0; i < N; i++)
                man[i] = i + 1;
           for (int i = 0; i < 20; i++)
           {
                cin >> point[i];
           }
           for (int i = 0; i < 20 and man.size() > luckyMan; i++)
           {
                killSomeone(man, point[i], luckyMan);
           }
           cout << "Selection #" << testCase++ << endl;
           for (int i = 0; i < man.size(); i++)
           {
                cout << man[i];
                if (i == man.size() - 1)
                     cout << endl;
                else
                     cout << " ";
           }
           cout << endl;
     }

     return 0;
}

[UVA] 305 - Joseph


題目連結

題意:


給你一個K,表示有K個好人和K個壞人,
好人排在壞人前面,
例如k=3,
排成=>好好好壞壞壞
現在有一數字n,表示從第一個開始數第n個要被殺掉,
殺完繼續數,超過第2*k個就再重頭開始數。
如果n=4,
好好好壞壞壞(第四個被殺掉)
好好好壞壞壞
....過程中殺到好人了
但如果n=5,
好好好壞壞壞
好好好壞壞壞
好好好壞壞壞
把壞人都殺光了而且都沒殺到好人!


今天要求n最小為多少,可以將壞人殺光而不殺到好人。

我的作法:


直接模擬,
但是要先將k=1~13的答案先存起來,不然會TLE

--------------------------------------------------

/* 題目: UVa 305 - Joseph
 * Language: C++
 * Created on: 2015年11月28日
 *   Author: hanting
 */
#include <iostream>
#include <vector>
using namespace std;
vector<bool> arr;
bool test(int &n, int &k)
{
     int cur = (n - 1) % (k * 2);
     while (arr.size() > k)
     {
           if (cur < k)
                return false;
           arr.erase(arr.begin() + cur);
           cur += n - 1;
           cur %= arr.size();
     }
     return true;
}
int main()
{
     int k;
     int ans[14] = { };
     for (k = 1; k < 14; k++)
     {
           int testk;
           for (testk = k;; testk++)
           {
                arr.assign(k * 2, 0);

                if (test(testk, k))
                     break;
           }
           ans[k] = testk;
     }
     while (cin >> k and k)
           cout << ans[k] << endl;
     return 0;
}


2015年11月28日 星期六

[UVA] 348 - Optimal Array Multiplication Sequence

題目鏈接

題意:

給你n個矩陣,求矩陣相乘的順序,
使得運算量最小。
矩陣A為a*b
矩陣B為b*c

矩陣相乘運算量為
a*b*c

我的作法:

dynamic programming
dp[ i ][ j ]為第 i 個矩陣到第 j 個矩陣的最小運算量
dp[ i ][ i ] = 0

其基本想法是這樣:
若有一 k 在 i 和 j 中間,
就可以將運算分成
第 i 個矩陣相乘到第 k 個矩陣,形成矩陣A,
再將矩陣A一路乘到矩陣 j ,
找到 k 可以使得 i 到 j 運算量最小 。

假設
第 i 個矩陣為a*b
第 k 個矩陣為c*d
第 j 個矩陣為e*f

dp[ i ][ j ] = dp[ i ][ k ] + dp[ k+1 ][ j ] + a*d*f ;
枚舉 k 從 i 到 j,找到最小值就是dp[ i ][ j ]值,
而形成最小值的 k 就是切割點,
cut[ i ][ j ] = k
就是表示第 i 個矩陣乘到第 j 個矩陣要先做 i 到 k 再做 k 到 j 的相乘。
最後輸出依據切割點遞迴輸出。

--------------------------------------------------

/* 20151128
 * hanting
 * UVa 348 - Optimal Array Multiplication Sequence
 * C++
 */
#include <iostream>
#include <cstring>
using namespace std;
pair<int, int> matrix[12];
int dp[12][12];
int cut[12][12];
int MCM(int i, int j)
{
    if(dp[i][j] != -1) return dp[i][j];
    if(i == j)
    {
        return dp[i][j] = 0;
    }
    else
    {
        int mini = 0x3fffffff;
        for(int k = i; k < j; k++)
        {
            int tmp = MCM(i, k) + MCM(k+1, j) + matrix[i].first * matrix[k].second * matrix[j].second;
            if(mini > tmp)
            {
                mini = tmp;
                cut[i][j] = k;
            }
        }
        return dp[i][j] = mini;
    }
}
int output(int i,int j)
{
    if(i == j)
    {
        cout << "A" << i+1;
    }
    else
    {
        cout << "(";
        output(i, cut[i][j]);
        cout << " x ";
        output(cut[i][j]+1, j);
        cout << ")";
    }
}
int main()
{
    int N;
    int testCase = 1;
    while(cin >> N and N)
    {
        for(int i = 0; i < N; i++)
        {
            cin >> matrix[i].first >> matrix[i].second;
        }
        memset(dp, -1, sizeof(dp));
        MCM(0, N-1);
        cout << "Case " << testCase++ << ": " ;
        output(0, N-1);
        cout << endl;
    }
    return 0;
}

[UVA] 108 - Maximum Sum

題目連結

題意:






給你n * m的二維陣列,
找到一個總和最大的矩形,
輸出其總和。


我的作法:

做二維之前,可以先了解一維的O(n)的作法!
如果已經會一維的了就可以開始做二維的啦

先做出另一個prefix的二維的table:
從第2列開始,將第 i 列的數字 += 第i-1列的數字
以範例測資為例,變成:
0 -2 -7 0
9 0 -13 2
5 1 -17 3
4 9 -17 1

如此一來!利用上面的prefix table的結果,
如果要求如下矩形的和就是= 9 - 0








如果要如下矩形的和就是= -17 - (7)







對於像這樣一豎的數列,你都可以在O(1)求出,
只要知道上界 a 和 下界 b,
就可以利用prefix的表 table[b] - table[a-1]求出該矩形的和,
如果上界是第二列,下界是第三列,
那麼你可以產生一個數列:
(5-0)  (1-(-2))  (-17-(-7))  (3-0)
=  5         3            -10           3
而此數列中的每個元素都是像剛剛那樣用table[3] - table[1]求出

發現了嗎弟弟!
這樣就是一個一維的數列了,
求出最大連續元素和=8,就是在第二列和第三列所組成的高度是2的矩形最大的總和,
也就是
  9  2  -6  2
-4   1  -4  1
這兩列可以組成的矩形中最大的和是8!

再舉一個例子,
上界是第一列,下界是第四列,
可以產生這個數列:
4 9 -17 1
這數列最大連續元素和為13
也就是說
 0 -2 -7  0
 9  2 -6  2
-4  1 -4  1
-1  8  0 -2
高度為4可以組成的矩形中最大的和是13!

所以只要列舉上界和下界就可以知道最大和的矩形了!

--------------------------------------------------

/* 20151102
 * hanting
 * UVa 108 - Maximum Sum
 * C++
 */
#include <iostream>
#include <vector>
using namespace std;
int MaxRectangleSum(vector<vector<int> > &table, int m, int n)
{
    for(int i = 1; i < m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            table[i][j] += table[i-1][j];
        }
    }
    int MaxSum = table[0][0];
    int arr[n];
    for(int low = 0; low < m; low++)
    {
        for(int up = low; up < m; up++)
        {
            if(low)
            {
                arr[0] = table[up][0] - table[low-1][0];
                for(int i = 1; i < n; i++)
                {
                    int tmp = table[up][i] - table[low-1][i];
                    arr[i] = max(arr[i-1]+tmp, tmp);
                    MaxSum = max(MaxSum, arr[i]);
                }
            }
            else
            {
                arr[0] = table[up][0];
                for(int i = 1; i < n; i++)
                {
                    int tmp = table[up][i];
                    arr[i] = max(arr[i-1]+tmp, tmp);
                    MaxSum = max(MaxSum, arr[i]);
                }
            }
        }
    }
    return MaxSum;
}
int main()
{
    int N;
    while(cin >> N)
    {
        vector<vector<int> > table(N,vector<int>(N));
        for(int i = 0; i < N; i++)
        {
            for(int j = 0; j < N; j++)
            {
                cin >> table[i][j];
            }
        }
        cout << MaxRectangleSum(table, N, N) << endl;;
    }

    return 0;
}

2015年11月2日 星期一

[UVA] 10020 - Minimal Coverage

題目鏈結

題意:

給一個數字m表示給你一個區間0到m
接著給你一堆線段,
輸入 0 0表示線段輸入結束,

1    (區間0到1)
-1 0 (線段1)
-5 -3 (線段2)
2 5 (線段3)
0 0 (線段輸入結束)

若給的線段不能覆蓋該區間則輸出0,
若可以覆蓋的話,輸出最少需要多少線段,以及需要用到那些線段。
測資間要有空行!最後一筆後面不用空行!

我的作法:

貪婪
先將所有線段依左端點 x 座標做排序,
start從0開始,
遍歷全部的 x < start 線段,找到一右端點 x 座標最大的線段,
接著更新start 為 其右端點,
直到覆蓋整個區間,
如果找不到x < start的線段,表示無法覆蓋,直接輸出0。

--------------------------------------------------
/* 20151102
 * hanting
 * UVa 10020 - Minimal Coverage
 * C++
 */
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Line
{
    int first, second;
    bool operator < (const Line &B)const
    {
        return second > B.second or (second == B.second and first < B.first);
    }
};
vector<Line> ans;
bool cover(vector<Line> &line, int M)
{
    sort(line.begin(), line.end());
    int Start = 0, End = M;
    while(Start < End)
    {
        for(int i = 0; i < line.size(); i++)
        {
            if(line[i].first <= Start and line[i].second >= Start)
            {
                ans.push_back(line[i]);
                Start = line[i].second;
                line.erase(line.begin()+i);
                break;
            }
            else if(i == line.size()-1) return false;
        }
    }
    return true;
}
int main()
{
    int testCase = 0;
    cin >> testCase;
    while(testCase--)
    {
        ans.clear();
        int M;
        cin >> M;
        int left, right;
        vector<Line> line;
        while(cin >> left >> right and left+right)
        {
            line.push_back(Line{left, right});
        }
        if(cover(line, M))
        {
            cout << ans.size() << endl;
            for(int i = 0; i < ans.size(); i++)
            {
                cout << ans[i].first << " " << ans[i].second << endl;
            }
        }
        else
        {
            cout << 0 << endl;
        }
        if(testCase) cout << endl;
    }
    return 0;
}