Contest - 2014 SWJTU ACM 手速測試賽（2014.10.31）

題目列表：

2146 Problem A	【手速】闊綽的Dim
2147 Problem B	【手速】頹廢的Dim
2148 Problem C	【手速】我的滑板鞋
2149 Problem D	【手速】潦倒的Dim
2150 Problem E	【手速】被NTR的Dim

?

---

?2146 Problem A：

簡單的最長回文串統計算法，這里沒有過高要求，n^2算法可以AC。其中包括dp動規以及中心法（以上兩種都是O(n^2)算法，可以參考白書）。推廣，可以嘗試擴展KMP(O(nlogn))或者Manacher算法（O(n)）。可以查閱相關資料自行選擇學習。這里給出中心法。

?

/****************************************/
/*****            Desgard_Duan        *****/
/****************************************/
//#pragma comment(linker, "/STACK:102400000,102400000")
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <stack>
#include <map>
#include <queue>
#include <vector>
#include <set>
#include <functional>
#include <cmath>
#include <numeric>

using namespace std;

char s[500]; int len;

inline void get_val(int &a) {
    int value = 0, s = 1;
    char c;
    while ((c = getchar()) == ' ' || c == '\n');
    if (c == '-') s = -s; else value = c - 48;
    while ((c = getchar()) >= '0' && c <= '9')
        value = value * 10 + c - 48;
    a = s * value;
}

int tofind(int h, int t) {
    int re = t - h + 1;
    while (h < t) {
        if (s[h++] != s[t--]) return 0;
    }
    return re;
}

int main() {
    //freopen("huiwen.in", "r", stdin);
    //freopen("huiwen.out","w",stdout);
    int T;
    cin >> T;
    while (T--) {
        scanf("%s", s);
        len = strlen(s);
        int ans = 1;
        for (int i = 0; i < len - 1; i++)
            for (int j = i + 1; j < len; j++) {
                ans = max(ans, tofind(i, j));
            }
        cout << ans << endl;
    }
    return 0;
}

?

?

2147 Problem B:

一道字符串水題，只要按位置遍歷一遍即可。C語言基礎題。

/****************************************/
/*****            Desgard_Duan        *****/
/****************************************/
//#pragma comment(linker, "/STACK:102400000,102400000")
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <stack>
#include <map>
#include <queue>
#include <vector>
#include <set>
#include <functional>
#include <cmath>
#include <numeric>

using namespace std;

inline void get_val(int &a) {
    int value = 0, s = 1;
    char c;
    while ((c = getchar()) == ' ' || c == '\n');
    if (c == '-') s = -s;
    else value = c - 48;
    while ((c = getchar()) >= '0' && c <= '9')
        value = value * 10 + c - 48;
    a = s * value;
}

string str1, str2;
int main () {
    int T;
    //cin >> T;
    while (cin >> str1 >> str2) {

        int ans = 0;
        for (int i = 0 ; i < str1.size(); ++ i) {
            if (str1[i] == str2[i]) {
                ans ++;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

?

2148 Problem C:

一道貪心的白書例題，類型歸類為查找不相交區間的最大個數。具體思路：對于相交的任意兩個區間分為兩種情況（圖A、圖B）。若出現情況A，直接將大區間刪除即可。若出現情況B，我們先將集合按照x進行升序排列，然后優先選取x最小的情況B中的區間，這樣可以得到最佳的方案。

/****************************************/
/*****            Desgard_Duan        *****/
/****************************************/
//#pragma comment(linker, "/STACK:102400000,102400000")
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <stack>
#include <map>
#include <queue>
#include <vector>
#include <set>
#include <functional>
#include <cmath>
#include <numeric>

using namespace std;

inline void get_val(int &a) {
    int value = 0, s = 1;
    char c;
    while ((c = getchar()) == ' ' || c == '\n');
    if (c == '-') s = -s;
    else value = c - 48;
    while ((c = getchar()) >= '0' && c <= '9')
        value = value * 10 + c - 48;
    a = s * value;
}

vector<pair<int, int> > shoes;
bool flag[1005];

int main () {
    int n, x, y;
    //freopen("out.txt", "w", stdout);
    while (~scanf ("%d", &n)) {
        shoes.clear();
        for (int i = 0; i < n; ++ i) {
            cin >> x >> y;
            shoes.push_back (make_pair(x, y));
        }
        sort (shoes.begin(), shoes.end());

        memset (flag, 0, sizeof (flag));
        for (int i = 0; i < n; ++ i) {
            if (flag[i]) {
                continue;
            }
            for (int j = 0; j < n; ++ j) {
                if (i == j) continue;
                else {
                    if (shoes[i].first <= shoes[j].first && shoes[i].second >= shoes[j].second) {
                        flag[i] = 1;
                    }
                }
            }
        }
        int cur = 0, ans = 1;
        for (; cur < shoes.size() && flag[cur]; cur ++);
        int last_end = shoes[cur].second, this_begin;
        for (int i = cur + 1; i < shoes.size(); ++ i) {
            if (flag[i]) continue;
            this_begin = shoes[i].first;
            if (last_end <= this_begin) {
                ans ++;
                last_end = shoes[i].second;
            }
        }
        cout << ans << endl;

    }
    return 0;
}

?

2149 Problem D:

一道大數題目。在n個大數中尋找最小的數。大數推薦使用Java大數類，相對來說代碼比較清晰。也可以直接開一個數組進行模擬。

?

import java.math.*;
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            BigInteger ans = BigInteger.ZERO;
            for (int i = 0; i < n; ++i) {
                BigInteger a = in.nextBigInteger();
                if (i == 0) {
                    ans = a;
                } else {
                    ans = ans.min(a);
                }
            }
            System.out.println (ans);
        }
    }
}

?

?

2150 Problem E:

一道簡單的數學題目。稍微推導一下就會發現這個函數最多只有六項。分別是a, b, b - a, -a, -b, a - b六個數，只要我們去一下重復的數即可。去重方法可以用一個字符串數組來做，這里用了set容器的性質進行了去重操作。

/****************************************/
/*****            Desgard_Duan        *****/
/****************************************/
//#pragma comment(linker, "/STACK:102400000,102400000")
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <stack>
#include <map>
#include <queue>
#include <vector>
#include <set>
#include <functional>
#include <cmath>
#include <numeric>

using namespace std;

inline void get_val(int &a) {
    int value = 0, s = 1;
    char c;
    while ((c = getchar()) == ' ' || c == '\n');
    if (c == '-') s = -s;
    else value = c - 48;
    while ((c = getchar()) >= '0' && c <= '9')
        value = value * 10 + c - 48;
    a = s * value;
}


int a, b, n;
set<int> S;
int main () {
    while (cin >> a >> b >> n) {
        S.clear();
        if (n >= 6) {
            S.insert (a);
            S.insert (b);
            S.insert (b - a);
            S.insert (-a);
            S.insert (-b);
            S.insert (a - b);
            cout << S.size() << endl;
            continue;
        } else {
            int last = a, now = b, t;
            S.insert (a);
            S.insert (b);
            for (int i = 3; i <= n; ++ i) {
                S.insert (now - last);
                t = now;
                now = now - last;
                last = t;
            }
            cout << S.size() << endl;
        }
    }
    return 0;
}

?

?

---

最后，感謝這次的命題者：王浩宇（stdiohero），葉鵬(yeahpeng)，王馳（wid），謝文亮（Dim），朱吳帥（JM）同學為我們出的這套熱身題目。祝大家在參賽后有所提高。謝謝大家。

——Desgard_Duan

2014.10.31