编程之美2015资格赛 解题报告

题目链接：http://hihocoder.com/contest/msbop2015qual/problems

A. 2月29日

首先为了方便处理可以分类一下把问题转化成第a年到第b年的闰年数量。

然后如果要求fun(x)=1~x年中闰年的数量，容斥一下就是 (1~x中4的倍数) - (1~x中100的倍数) + (1~x中400的倍数)

答案为fun(b) - fun(a-1)。

代码（1ms）：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;

string month[] = {"January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November" , "December"};
int T, n;

int get_month(string s) {
    return find(month, month + 12, s) - month + 1;
}

int calc(int y) {
    return y / 4 - y / 100 + y / 400;
}

char str[15];
int yy, dd, mm;

int main() {
    scanf("%d", &T);
    for(int t = 1; t <= T; ++t) {
        scanf("%s %d, %d", str, &dd, &yy);
        mm = get_month(str);
        int a = calc(yy + (mm > 2) - 1);

        scanf("%s %d, %d", str, &dd, &yy);
        mm = get_month(str);
        int b = calc(yy - (mm < 2 || (mm == 2 && dd < 29)));
        printf("Case #%d: %d
", t, b - a);
    }
}

B. 回文字符序列

此题为DP，用dp[i][j]表示s[i..j]中的回文子序列数量。

那么，不考虑s[i] = s[j]的回文串，dp[i][j] = dp[i+1][j] + dp[i][j - 1] - dp[i+1][j-1]（容斥，怎么又是容斥……）

那么考虑包含s[i] = s[j]的回文串，dp[i][j] = dp[i + 1][j - 1] + 1（1表示回文串s[i]s[j]）

其中初始化为s[i][i] = 1。

记得取模。答案为dp[1][n]。

代码（126ms）：

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 1010;
const int MOD = 100007;

char s[MAXN];
int dp[MAXN][MAXN];
int T, n;

int solve() {
    for(int i = 0; i < n; ++i) dp[i][i] = 1;
    for(int step = 1; step < n; ++step) {
        for(int l = 0; l + step < n; ++l) {
            int r = l + step;
            dp[l][r] = (dp[l + 1][r] + dp[l][r - 1] - dp[l + 1][r - 1] + MOD) % MOD;
            if(s[l] == s[r]) {
                dp[l][r] = (dp[l][r] + dp[l + 1][r - 1] + 1) % MOD;
            }
        }
    }
    return dp[0][n - 1];
}

int main() {
    scanf("%d", &T);
    for(int t = 1; t <= T; ++t) {
        scanf("%s", s);
        n = strlen(s);
        printf("Case #%d: %d
", t, solve());
    }
}

C. 基站选址

这题我就随手写了个模拟退火……

其实这题的用户坐标的x、y是无关的，在不考虑基站的情况下，质心P（sum{x}/A, sum{y}/B）是最好的（求导可得）。

然而，P移动一个坐标，sum{(A-P)·(A-P)}的偏移≥1，而与基站的哈曼顿距离偏移≤1。

那么只要枚举P周围的9个点就行了，复杂度O(A+B)。不放心的可以枚举25个点。

代码（95ms）：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <cassert>
using namespace std;
typedef long long LL;

const int MAXN = 1010;

int ax[MAXN], ay[MAXN], bx[MAXN], by[MAXN];
int a, b, n, m, T;
int now_x, now_y;

LL sqr(int x, int y) {
    return LL(x) * x + LL(y) * y;
}

LL calc(int x, int y) {
    LL res = 0x3f3f3f3f;
    for(int i = 0; i < b; ++i)
        res = min(res, LL(abs(x - bx[i]) + abs(y - by[i])));
    for(int i = 0; i < a; ++i)
        res += sqr(x - ax[i], y - ay[i]);
    return res;
}

LL get_ans(int x, int y) {
    LL res = ~(1LL << 63);
    for(int i = -1; i <= 1; ++i)
        for(int j = -1; j <= 1; ++j) res = min(res, calc(x + i, y + j));
    return res;
}

LL solve() {
    static int fx[] = {1, 0, -1, 0};
    static int fy[] = {0, 1, 0, -1};

    int x = (n + 1) / 2, y = (n + 1) / 2;
    double step = max(n, m) / 2, v = 0.95;
    LL res = calc(x, y);

    while(step > 1e-4) {
        int p = int(ceil(step));
        for(int f = 0; f < 4; ++f) {
            int new_x = x + p * fx[f], new_y = y + p * fy[f];
            LL tmp = calc(new_x, new_y);
            if(tmp < res) {
                res = tmp;
                x = new_x, y = new_y;
            }
        }
        step *= v;
    }
    //cout<<res<<" # debug #"<<endl; assert(get_ans(x, y) == res);
    return get_ans(x, y);
}

LL test() {
    LL res = ~(1LL << 63);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j) res = min(res, calc(i, j));
    return res;
}

int main() {
    //freopen("input.txt", "r", stdin);
    scanf("%d", &T);
    for(int t = 1; t <= T; ++t) {
        scanf("%d%d%d%d", &n, &m, &a, &b);
        for(int i = 0; i < a; ++i) scanf("%d%d", &ax[i], &ay[i]);
        for(int i = 0; i < b; ++i) scanf("%d%d", &bx[i], &by[i]);
        //cout<<calc(2, 2)<<endl;
        cout<<"Case #"<<t<<": "<<solve()<<endl;
        //cout<<"#debug "<<test()<<endl;
    }
}