[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;

}

[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;
}

[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;
}

[UVA] 10602 - Edit Nottobad

題目連結

題意:

以第一個輸入為例，
this
thin
thing
第一個輸入 this 這個字串，
可以刪除最後幾個字母後再加上幾個字母可以變成另一個字串，
像是刪除 s 後再加上 n 可以變成 thin，
然後不刪除直接加上 g 就可以變成 thing。

另一個例子，
popcorn
apple
apricote
plum
第一個輸入不能改，就是 popcorn 這個字串，
接著刪除掉 opcorn 再加上 lum 就可以變成 plum，
接著刪除 plum 再加上 apple 就可以變成 apple，
接著刪除 ple 再加上 ricote 就可以變成 apricote，

他要求的是你要加上的所有字串的總長度要最小，
最後再加上第一個輸入的字串的長度就是要輸出的數字。

例如以上兩個例子，
第一個例子 n + g 長度2
this + 2 = 6
第二個例子 lum + apple + ricote 長度14
popcorn + 14 = 21

接著要輸出每個字串的順序。

我的作法:

我是用suffix tree的方式，
將每個字串存在一棵多元樹裡面，

像這樣將每個字串存進去，
從根節點開始，
如果該節點的字元跟要存的字串的字元相同就繼續往下走，
如果不同就分支，
例如圖中的 n 就是一個分支，
'*' 表示依個字串結束，
存完後，就DFS就好囉~
輸出整個樹的全部節點的數量(不包括'*')，

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

/* 20151101
 * hanting
 * UVa 10602 - Edit Nottobad
 * C++
 * suffix tree
 */
#include <iostream>
#include <vector>
using namespace std;
struct Tree
{
    char ch;
    vector<Tree*> node;
};
vector<string> ans;
void BuildTree(Tree *root,string str);
int DFS(Tree *root,string str);
int main()
{
    int testCase;
    cin >> testCase;
    while(testCase--)
    {
        ans.clear();
        Tree *head = new Tree;
        int strN;
        cin >> strN;
        for(int i = 0; i < strN; i++)
        {
            string str;
            cin >> str;
            BuildTree(head, str);
        }
        cout << DFS(head, "")-1 << endl;
        for(int i = 0; i < ans.size(); i++)
        {
            cout << ans[i] << endl;
        }
    }
    return 0;
}
void BuildTree(Tree *root,string str)
{
    int i;
    bool New = true;
    for(i = 0; i < root->node.size(); i++)
    {
        if(root->node[i]->ch == str[0])
        {
            New = false;
            BuildTree(root->node[i], str.substr(1));
            break;
        }
    }
    if(New)//分支
    {
        Tree *NewRoot;
        root->node.push_back(NewRoot);
        root->node[root->node.size()-1] = new Tree;
        if(str.size())
        {
            root->node[root->node.size()-1]->ch = str[0];
            BuildTree(root->node[root->node.size()-1], str.substr(1));
        }
        else
        {
            root->node[root->node.size()-1]->ch = '*';
        }
    }
}
int DFS(Tree *root,string str)
{
    int cnt = 0;
    if(root->node.size())
    {
        cnt++;
        for(int i = 0; i < root->node.size(); i++)
        {
            cnt += DFS(root->node[i], str + root->node[i]->ch);
        }
    }
    else //一個字串結束
    {
        ans.push_back(str.substr(0,str.size()-1));
    }
    delete(root);
    return cnt;
}