编程之美2015资格赛解题报告-白红宇

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

阅读量：4554 次

发布时间：2019-06-08

本文共 4228 字，大约阅读时间需要 14 分钟。

题目链接：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）：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 using namespace std; 6  7 string month[] = {
    "January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November" , "December"}; 8 int T, n; 9 10 int get_month(string s) {11     return find(month, month + 12, s) - month + 1;12 }13 14 int calc(int y) {15     return y / 4 - y / 100 + y / 400;16 }17 18 char str[15];19 int yy, dd, mm;20 21 int main() {22     scanf("%d", &T);23     for(int t = 1; t <= T; ++t) {24         scanf("%s %d, %d", str, &dd, &yy);25         mm = get_month(str);26         int a = calc(yy + (mm > 2) - 1);27 28         scanf("%s %d, %d", str, &dd, &yy);29         mm = get_month(str);30         int b = calc(yy - (mm < 2 || (mm == 2 && dd < 29)));31         printf("Case #%d: %d\n", t, b - a);32     }33 }

View Code

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）：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 using namespace std; 6  7 const int MAXN = 1010; 8 const int MOD = 100007; 9 10 char s[MAXN];11 int dp[MAXN][MAXN];12 int T, n;13 14 int solve() {15     for(int i = 0; i < n; ++i) dp[i][i] = 1;16     for(int step = 1; step < n; ++step) {17         for(int l = 0; l + step < n; ++l) {18             int r = l + step;19             dp[l][r] = (dp[l + 1][r] + dp[l][r - 1] - dp[l + 1][r - 1] + MOD) % MOD;20             if(s[l] == s[r]) {21                 dp[l][r] = (dp[l][r] + dp[l + 1][r - 1] + 1) % MOD;22             }23         }24     }25     return dp[0][n - 1];26 }27 28 int main() {29     scanf("%d", &T);30     for(int t = 1; t <= T; ++t) {31         scanf("%s", s);32         n = strlen(s);33         printf("Case #%d: %d\n", t, solve());34     }35 }

View Code

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）：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 using namespace std; 8 typedef long long LL; 9 10 const int MAXN = 1010;11 12 int ax[MAXN], ay[MAXN], bx[MAXN], by[MAXN];13 int a, b, n, m, T;14 int now_x, now_y;15 16 LL sqr(int x, int y) {17 return LL(x) * x + LL(y) * y;18 }19 20 LL calc(int x, int y) {21 LL res = 0x3f3f3f3f;22 for(int i = 0; i < b; ++i)23 res = min(res, LL(abs(x - bx[i]) + abs(y - by[i])));24 for(int i = 0; i < a; ++i)25 res += sqr(x - ax[i], y - ay[i]);26 return res;27 }28 29 LL get_ans(int x, int y) {30 LL res = ~(1LL << 63);31 for(int i = -1; i <= 1; ++i)32 for(int j = -1; j <= 1; ++j) res = min(res, calc(x + i, y + j));33 return res;34 }35 36 LL solve() {37 static int fx[] = { 1, 0, -1, 0};38 static int fy[] = { 0, 1, 0, -1};39 40 int x = (n + 1) / 2, y = (n + 1) / 2;41 double step = max(n, m) / 2, v = 0.95;42 LL res = calc(x, y);43 44 while(step > 1e-4) {45 int p = int(ceil(step));46 for(int f = 0; f < 4; ++f) {47 int new_x = x + p * fx[f], new_y = y + p * fy[f];48 LL tmp = calc(new_x, new_y);49 if(tmp < res) {50 res = tmp;51 x = new_x, y = new_y;52 }53 }54 step *= v;55 }56 //cout<
            
             <<" # debug #"<
             
              << 63);62 for(int i = 1; i <= n; ++i)63 for(int j = 1; j <= m; ++j) res = min(res, calc(i, j));64 return res;65 }66 67 int main() {68 //freopen("input.txt", "r", stdin);69 scanf("%d", &T);70 for(int t = 1; t <= T; ++t) {71 scanf("%d%d%d%d", &n, &m, &a, &b);72 for(int i = 0; i < a; ++i) scanf("%d%d", &ax[i], &ay[i]);73 for(int i = 0; i < b; ++i) scanf("%d%d", &bx[i], &by[i]);74 //cout<