本文主要是介绍编程之美2015资格赛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
A：处理下日期，容斥加减一下
B：DP，dp[l][r]表示区间回文子序列个数
C：模拟退火过了，然后还有个比较科学的方法，就是枚举B点，XY轴分开考虑，三分求解
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <string>
using namespace std;int t, year;char m1[2][15];
int m[2], d[2], y[2];char sb[13][15] = {"", "January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November" , "December"};
map<string, int> to;int main() {int cas = 0;for (int i = 1; i <= 12; i++)to[sb[i]] = i;scanf("%d", &t);while (t--) {scanf("%s%d,%d", m1[0], &d[0], &y[0]);scanf("%s%d,%d", m1[1], &d[1], &y[1]);m[0] = to[m1[0]]; m[1] = to[m1[1]];if (m[0] > 2 || (m[0] == 2 && d[0] > 29)) y[0]++;if (m[1] < 2 || (m[1] == 2 && d[1] < 29)) y[1]--;int ans = 0;ans += y[1] / 4 - (y[0] - 1) / 4;ans -= y[1] / 100 - (y[0] - 1) / 100;ans += y[1] / 400 - (y[0] - 1) / 400;printf("Case #%d: %d\n", ++cas, ans);}return 0;
}
#include <cstdio>
#include <cstring>const int MOD = 100007;
const int N = 1005;
char str[N];
int t, dp[N][N];int dfs(int l, int r) {if (dp[l][r] != -1) return dp[l][r];dp[l][r] = 0;if (l > r) return dp[l][r] = 0;if (l == r) return dp[l][r] = 1;if (str[l] == str[r]) dp[l][r] = (dp[l][r] + dfs(l + 1, r - 1) + 1) % MOD;dp[l][r] = ((dp[l][r] + dfs(l + 1, r) + dfs(l, r - 1) - dfs(l + 1, r - 1)) % MOD + MOD) % MOD;return dp[l][r];
}int main() {int cas = 0;scanf("%d", &t);while (t--) {int ans = 0;scanf("%s", str);int n = strlen(str);memset(dp, -1, sizeof(dp));printf("%d\n", dfs(0, n - 1));}return 0;
}
模拟退火
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;const int N = 105;int t, n, m;
int an, bn;struct Point {int x, y;Point() {}Point(int x, int y) {this->x = x;this->y = y;}void read() {scanf("%d%d", &x, &y);}
} a[N * 10], b[N];const int INF = 0x3f3f3f3f;
const int d[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
typedef long long ll;ll cal(int x, int y) {ll ans = 0;for (int i = 0; i < an; i++) {int dx = x - a[i].x;int dy = y - a[i].y;ans += (ll)dx * dx;ans += (ll)dy * dy;}int Min = INF;for (int i = 0; i < bn; i++) {int dx = b[i].x - x;if (dx < 0) dx = -dx;int dy = b[i].y - y;if (dy < 0) dy = -dy;Min = min(Min, dy + dx);}return ans + Min;
}int main() {int cas = 0;scanf("%d", &t);while (t--) {scanf("%d%d%d%d", &n, &m, &an, &bn);for (int i = 0; i < an; i++) a[i].read();for (int i = 0; i < bn; i++) b[i].read();int sx = 0, sy = 0;ll ans = (1LL<<63) - 1;int step = min(n, m);for (int ti = 0; ti < 1000; ti++) {for (int i = 0; i < 4; i++) {int x = sx + d[i][0] * step;int y = sy + d[i][1] * step;if (x < 0 || x > n || y < 0 || y > n) continue;ll tmp = cal(x, y);if (tmp < ans) {sx = x;sy = y;ans = tmp;}}step = (step * 0.83);if (step == 0) step = 1;}printf("Case #%d: %lld\n", ++cas, ans);}return 0;
}
科学
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;typedef long long ll;
const int N = 105;int ax[N * 10], ay[N * 10];int t, n, m, an, bn;int abss(int x) {if (x < 0) return -x;return x;
}ll cal2(int u, int v, int *x) {ll ans = 0;ans += abss(u - v);for (int i = 0; i < an; i++) {int dx = u - x[i];ans += (ll)dx * dx;}return ans;
}ll cal(int l, int r, int v, int *x) {while (r - l > 2) {int midl = (l * 2 + r) / 3;int midr = (l + 2 * r) / 3;if (cal2(midl, v, x) < cal2(midr, v, x)) r = midr;else l = midl;}ll ans = (1LL<<63) - 1;for (int i = l; i <= r; i++) ans = min(ans, cal2(i, v, x));return ans;
}ll gao(int x, int y) {ll ans = 0;ans += min(cal(1, x, x, ax), cal(x, n, x, ax));ans += min(cal(1, y, y, ay), cal(y, m, y, ay));return ans;
}int main() {int cas = 0;scanf("%d", &t);while (t--) {scanf("%d%d%d%d", &n, &m, &an, &bn);for (int i = 0; i < an; i++) scanf("%d%d", &ax[i], &ay[i]);ll ans = (1LL<<63) - 1;int x, y;for (int i = 0; i < bn; i++) {scanf("%d%d", &x, &y);ans = min(ans, gao(x, y));}printf("Case #%d: %lld\n", ++cas, ans);}return 0;
}
这篇关于编程之美2015资格赛的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
