【UVa】Frogger

Problem here

Solution

自己的石子為點0，目標石子為1
生成MST直到點0點1連通

#include <iostream>
#include <vector>
#include <memory.h>
#include <utility>
#include <string>
#include <math.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
vector<pair<float, pair<int, int> > > edges;
string spp;
float cal(int x1, int x2, int y1, int y2){
    return (float)sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}

bool cmp(pair<float, pair<int, int> > a, pair<float, pair<int, int> > b){
    return a.first < b.first;
}

int pre[1000];

int find(int x){
    int r = x;
    while(pre[r] != r){
        r = pre[r];
    }
    int j = x, y;
    while(j != r){
        y = pre[j];
        pre[j] = r;
        j = y;
    }
    return r;
}

void join(int a, int b){
    int fa = find(a);
    int fb = find(b);
    if(fa != fb){
        pre[fa] = fb;
    }
}
int main(){
    int n;
    int count = 1;
    while(cin >> n){
        if(n==0)
            break;
        vector<pair<int , int > > point;
        for(int i = 0; i < n; i++){
            int x, y;
            cin >> x >> y;
            point.push_back(make_pair(x,y));
            for(int j = 0; j < i; j++){
                edges.push_back(make_pair(cal(point[i].first, point[j].first, point[i].second, point[j].second), make_pair(i, j)) );
            }
        }
        cout << "Scenario #" << count++ << endl;

        sort(edges.begin(), edges.end(), cmp);
        for(int i = 0; i < n; i++)
            pre[i] = i;
        for(int i = 0; i < edges.size(); i++){
            if(find(edges[i].second.first)==find(edges[i].second.second))
                continue;

            join(edges[i].second.first, edges[i].second.second);
            if(find(1) == find(0)){
                printf("Frog Distance = %.3lf\n", edges[i].first);
                break;
            }

        }

        edges.clear();
        cout << endl;
        getline(cin, spp);
    }
    return 0;
}

【Zerojudge】d908

Problem here

Solution

DFS

#include <iostream>
#include <memory.h>
using namespace std;
int rat[30][30];
bool visit[30];
int sum;
void solve(int here, int cost){
    sum = max(sum, cost);
    visit[here] = true;
    for(int i = 0; i < 26; i++){
        if(visit[i] == false && rat[here][i] != 0){
            solve(i, cost+rat[here][i]);
            visit[i] = false;
        }
    }
}

int main(){
    char start;
    while(cin >> start){
        int n;cin >> n;
        sum = 0;
        memset(rat, 0, sizeof(rat));
        memset(visit, false, sizeof(visit));
        while(n--){
            char a, b;int w;
            cin >> a >> b >> w;
            rat[a-'A'][b-'A'] = max(rat[a-'A'][b-'A'], w);
        }
        solve(start-'A', sum);
        cout << sum << endl;

    }

    return 0;
}

【UVa】12149 - Feynman

Problem here

Solution

N增加1, 總正方形數會增加N*N

1. #include <iostream>
2. #include <memory.h>
3. using namespace std;
4. int mark[101];
5. int main(){
6. int n;
7. memset(mark, 0, sizeof(mark));
8. while(cin >> n){
9. if(n == 0)
10. break;
12. for(int i = 1 ; i <= n; i++)
13. if(mark[i] == 0)
14. mark[i] = mark[i-1] + (i*i);
16. cout << mark[n] << endl;
18. }
19. return 0;
20. }

【SPOJ】AIBOHP - Aibohphobia

Problem here

Solution

答案＝原字串長度-原字串與其反轉後字串的lcm

一開始用top down寫，TLE orz…. 
之後改成 bottom up 才AC

#include <iostream>
#include <string>
using namespace std;
string input, res;
int lcs[6101][6101];

int main(){

    int kase;
    cin >> kase;
    while(kase--){
        cin >> input;
        res.resize(input.size());
        for(int i = 0; i < input.length(); i++)
            res[i] = input[input.length()-1-i];

        for(int m = 0; m <= input.length(); m++){
            for(int n = 0; n <= res.length(); n++){
                if(m == 0 || n == 0)
                    lcs[m][n] = 0;
                else if(input[m-1] == res[n-1])
                    lcs[m][n] = 1 + lcs[m-1][n-1];
                else
                    lcs[m][n] = max(lcs[m][n-1], lcs[m-1][n]);
            }
        }

        cout << input.length() - lcs[input.length()][res.length()] << endl;
    }

    return 0;
}

【POJ】Symmetric Order

Problem here

Solution

#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<string> strs;
int n, cnt = 0;

void solve(int a, int b){
    if(b == strs.size() || a == strs.size())
        return;

    cout << strs[a] << endl;
    solve(a+2, b+2);
    if(strs[b] != " ")
        cout << strs[b] << endl;
}

int main(){
    while(cin >> n){
        strs.clear();
        if(n == 0)
            break;
        for(int i = 0; i < n; i++){
            string input;
            cin >> input;
            strs.push_back(input);
        }
        cout << "SET " << ++cnt << endl;
        if(n%2!=0)
            strs.push_back(" ");
        solve(0,1);

    }

    return 0;
}

【USACO】Barn Repair

Problem here

Solution

dp~~~

/*
ID: LeongHouHeng
PROG: barn1
LANG: C++
 */

 #include <iostream>
 #include <memory.h>
 #include <string.h>
 #include <fstream>
 #include <algorithm>
 using namespace std;

 ifstream fin("barn1.in");
 ofstream fout("barn1.out");

 int cows[201];
 int dp[250][60];
 int MIN_NUM = 2e9;
 int main(){
     int M, S, C;
     fin >> M >> S >> C;

     for(int i = 0; i < C; i++){
         fin >> cows[i];
     }
     sort(cows, cows+C);
     memset(dp, 0x1f, sizeof(dp));
     dp[0][0] = 1;
     for(int i = 1; i < C; i++){
         for(int j = 0; j <= i && j < M; j++){
            dp[i][j] = dp[i-1][j] + (cows[i] - cows[i-1]);
            if(j > 0)
                dp[i][j] = min(dp[i][j], dp[i-1][j-1] + 1);
            if(C-1 == i)
                MIN_NUM = min(MIN_NUM, dp[i][j]);
         }
     }

     fout << MIN_NUM << endl;
 }

【UVa】11636 - Hello World!

Problem here

Solution

water water water water ~~~

#include <iostream>
using namespace std;

int main(){

    int n;
    int kase = 1;
    while(cin >> n){
        if(n < 0)
            break;

        int ans = 1;
        int cnt = 0;
        while(ans < n){
            ans = ans * 2;
            cnt++;
        }
        cout << "Case " << kase++ << ": " << cnt << endl;
    }
    return 0;
}