UCF Local Programming Contest 2012（Practice）

A. Wall Street Monopoly

思路：(cost = cost[i][j]+cost[j+1][j+i]+100*min(len[j][j],dep[j][j])*min(len[j+1][j+i],dep[j+1][j+i]))
AC代码

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string.h>
#include <string>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

ll mult_mod(ll x, ll y, ll mod){
    return (x * y - (ll)(x / (long double)mod * y + 1e-3) * mod + mod) % mod;
}

ll pow_mod(ll a, ll b, ll p){
    ll res = 1;
    while (b){
        if (b & 1)
            res = mult_mod(res, a, p);
        a = mult_mod(a, a, p);
        b >>= 1;
    }
    return res % p;
}

ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a;
}

const int N = 25;
const int times = 100;
const int INF = 0x3f3f3f3f;

struct Dim{
    int len, dep, cost;
    Dim(){ }
    Dim(int len_, int dep_, int cost_): len(len_), dep(dep_), cost(cost_){ }
};

int t, n, len, dep, cost;

int main(){
#ifndef ONLINE_JUDGE
    freopen("my_in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    for (int tot = 1; tot <= t; tot ++ ){
        cin >> n;
        Dim dim[N];
        for (int i = 0; i < n; i ++ ){
            cin >> dim[i].len >> dim[i].dep;
            dim[i].cost = 0;
        }
        Dim ans[N][N];
        for (int i = 0; i < n; i ++ )
            ans[i][i] = dim[i];
        for (int i = 1; i < n; i ++ ){
            for (int j = 0; j < n - i; j ++ ){
                len = ans[j][j].len + ans[j + 1][j + i].len;
                dep = max(ans[j][j].dep, ans[j + 1][j + i].dep);
                cost = ans[j][j].cost + ans[j + 1][j + i].cost + times * min(ans[j][j].len, ans[j][j].dep) * min(ans[j + 1][j + i].len, ans[j + 1][j + i].dep);
                // cout << len << " " << dep << " " << cost << "
";
                Dim min_(len, dep, cost);
                for (int k = j + 1; k < j + i; k ++ ){
                    len = ans[j][k].len + ans[k + 1][j + i].len;
                    dep = max(ans[j][k].dep, ans[k + 1][j + i].dep);
                    cost = ans[j][k].cost + ans[k + 1][j + i].cost + times * min(ans[j][k].len, ans[j][k].dep) * min(ans[k + 1][j + i].len, ans[k + 1][j + i].dep);
                    // cout << len << " " << dep << " " << cost << "
";
                    if (cost < min_.cost){
                        min_.len = len;
                        min_.dep = dep;
                        min_.cost = cost;
                    }
                }
                ans[j][j + i] = min_;
            }
        }
        // for (int i = 0; i < n; i ++ ){
        //     for (int j = 0; j < n; j ++ )
        //         cout << ans[i][j].cost << " ";
        //     cout << "
";
        // }
        cout << "The minimum cost for lot #" << tot << " is $" << ans[0][n - 1].cost << ".

";
    }
    return 0;
}

B. How Old Are You Mr.String?

思路：字符串处理水题
AC代码

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string.h>
#include <string>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

ll mult_mod(ll x, ll y, ll mod){
    return (x * y - (ll)(x / (long double)mod * y + 1e-3) * mod + mod) % mod;
}

ll pow_mod(ll a, ll b, ll p){
    ll res = 1;
    while (b){
        if (b & 1)
            res = mult_mod(res, a, p);
        a = mult_mod(a, a, p);
        b >>= 1;
    }
    return res % p;
}

ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a;
}

int t;
string a, b;

int main(){
#ifndef ONLINE_JUDGE
    freopen("my_in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    for (int i = 1; i <= t; i ++ ){
        int cnt1[26] = {0}, cnt2[26] = {0};
        cout << "Data set #" << i << ": ";
        cin >> a >> b;
        for (auto c: a)
            cnt1[c - 'a'] ++ ;
        for (auto c: b)
            cnt2[c - 'a'] ++ ;
        bool flag1 = false, flag2 = false;
        for (int j = 25; j >= 0; j -- ){
            if (cnt1[j] > cnt2[j]){
                flag1 = true;
                break;
            }
            else if (cnt1[j] < cnt2[j]){
                flag2 = true;
                break;
            }
            else
                continue;
        }
        if (flag1)
            cout << "First string is older

";
        else if (flag2)
            cout << "First string is younger

";
        else
            cout << "The two strings are the same age

";
    }
    return 0;
}

C. Clean Up the Powers that Be

思路：模拟题
AC代码

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string.h>
#include <string>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

ll mult_mod(ll x, ll y, ll mod){
    return (x * y - (ll)(x / (long double)mod * y + 1e-3) * mod + mod) % mod;
}

ll pow_mod(ll a, ll b, ll p){
    ll res = 1;
    while (b){
        if (b & 1)
            res = mult_mod(res, a, p);
        a = mult_mod(a, a, p);
        b >>= 1;
    }
    return res % p;
}

ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a;
}

const int N = 10010;

int t, n, base, exp_;
int prime[N];

int get_len(int x){
    int len = 0;
    while (x){
        x /= 10;
        len ++ ;
    }
    return len;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("my_in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    for (int tot = 1; tot <= t; tot ++ ){
        cin >> n;
        memset(prime, 0, sizeof(prime));
        for (int i = 1; i <= n; i ++ ){
            cin >> base >> exp_;
            prime[base] += exp_;
        }
        cout << "Prime Factorization #" << tot << ":
";
        for (int i = 2; i < N; i ++ ){
            if (!prime[i])
                continue;
            else{
                int len = get_len(i);
                for (int i = 1; i <= len; i ++ )
                    cout << " ";
                cout << prime[i];
            }
        }
        cout << "
";
        for (int i = 2; i < N; i ++ ){
            if (!prime[i])
                continue;
            else{
                cout << i;
                int len = get_len(prime[i]);
                for (int i = 1; i <= len; i ++ )
                    cout << " ";
            }
        }
        cout << "

";
    }
    return 0;
}

D. The Clock Algorithm

思路：阅读理解题同样的读完题模拟
AC代码

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string.h>
#include <string>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

ll mult_mod(ll x, ll y, ll mod){
    return (x * y - (ll)(x / (long double)mod * y + 1e-3) * mod + mod) % mod;
}

ll pow_mod(ll a, ll b, ll p){
    ll res = 1;
    while (b){
        if (b & 1)
            res = mult_mod(res, a, p);
        a = mult_mod(a, a, p);
        b >>= 1;
    }
    return res % p;
}

ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a;
}

const int N = 60;

int n, r, p, r_, k, now, c;
int v[N];
bool old[N];

int main(){
#ifndef ONLINE_JUDGE
    freopen("my_in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    while (cin >> n >> r && n){
        cout << "Program " << ++ p << "
";
        memset(v, -1, sizeof(v));
        memset(old, false, sizeof(old));
        now = 0, k = 0;
        while (r -- ){
            cin >> r_;
            c = -1;
            for (int i = 0; i < n; i ++ ){
                if (v[i] == r_){
                    c = i;
                    break;
                }
            }
            if (c >= 0){
                cout << "Access page " << r_ << " in cell " << c + 1 << ".
";
                old[c] = false;
                continue;
            }
            k ++ ;
            c = -1;
            for (int i = 0; i < n; i ++ ){
                if (v[i] < 0){
                    c = i;
                    break;
                }
            }
            if (c >= 0){
                cout << "Page " << r_ << " loaded into cell " << c + 1 << ".
";
                v[c] = r_;
                old[c] = false;
                continue;
            }
            while (true){
                if (old[now]){
                    cout << "Page " << r_ << " loaded into cell " << now + 1 << ".
";
                    v[now] = r_;
                    old[now] = false;
                    now = (now + 1) % n;
                    break;
                }
                else{
                    old[now] = true;
                    now = (now + 1) % n;
                }
            }
        }
        cout << "There are a total of " << k << " page faults.

";
    }
    return 0;
}

G. Lifeform Detector

思路：S后面可以跟空格每个a必须有b相对应 c既可以当S也可以当T
AC代码

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string.h>
#include <string>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

ll mult_mod(ll x, ll y, ll mod){
    return (x * y - (ll)(x / (long double)mod * y + 1e-3) * mod + mod) % mod;
}

ll pow_mod(ll a, ll b, ll p){
    ll res = 1;
    while (b){
        if (b & 1)
            res = mult_mod(res, a, p);
        a = mult_mod(a, a, p);
        b >>= 1;
    }
    return res % p;
}

ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a;
}

int t;
string s;

bool judge(string s){
    stack<char> st;
    for (auto a: s){
        if (a == 'a')
            st.push('a');
        else if (a == 'b'){
            if (!st.empty())
                st.pop();
            else
                return false;
        }
        else if (a != 'c')
            return false;
    }
    if (!st.empty())
        return false;
    else
        return true;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("my_in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    for (int tot = 1; tot <= t; tot ++ ){
        cin >> s;
        cout << "Pattern " << tot << ": ";
        if (judge(s))
            cout << "More aliens!

";
        else
            cout << "Still Looking.

";
    }
    return 0;
}

H. Ordered Numbers

思路：水题
AC代码

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string.h>
#include <string>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

ll mult_mod(ll x, ll y, ll mod){
    return (x * y - (ll)(x / (long double)mod * y + 1e-3) * mod + mod) % mod;
}

ll pow_mod(ll a, ll b, ll p){
    ll res = 1;
    while (b){
        if (b & 1)
            res = mult_mod(res, a, p);
        a = mult_mod(a, a, p);
        b >>= 1;
    }
    return res % p;
}

ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a;
}

int t;
int a[3];

int main(){
#ifndef ONLINE_JUDGE
    freopen("order.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    for (int i = 1; i <= t; i ++ ){
        cin >> a[0] >> a[1] >> a[2];
        cout << "Data set #" << i << ":
";
        cout << "   Original order: " << a[0] << " " << a[1] << " " << a[2] << "
";
        sort(a, a + 3);
        cout << "   Smallest to largest: " << a[0] << " " << a[1] << " " << a[2] << "

";
    }    
    return 0;
}