本文主要是介绍135 - ZOJ Monthly, August 2014，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
135 - ZOJ Monthly, August 2014
A：构造问题，判断序列奇偶性，很容易发现最小值不是1就是0，最大值不是n就是n - 1，注意细节去构造即可
E：dp，dp[i][j]表示长度i，末尾状态为j的最大值，然后每个位置数字取与不取，不断状态转移即可
G：就一个模拟题没什么好说的
H：dfs，每次dfs下去，把子树宽度保存下来，然后找最大值，如果有多个，就是最大值+cnt宽度
I：构造，如果r * 2 > R，肯定无法构造，剩下的就二分底边，按等腰三角形去构造即可
代码：
A:
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;int n;void print(int n) {if (n == 3) {printf("3 1 2");return;}if (n % 2) {int len = (n - 3) / 2;printf("%d %d", n, n - len);for (int i = n - 1; i > n - len; i--)printf(" %d %d", i, i - len);printf(" 3 1 2");}else {int len = n / 2;printf("%d %d", n, n - len);for (int i = n - 1; i > n - len; i--)printf(" %d %d", i, i - len);}
}void print2(int n) {print(n - 2);printf(" %d %d", n - 1, n);
}void solve() {if (n == 1) {printf("1 1\n1\n1\n");return;}if (n == 2) {printf("1 1\n1 2\n2 1\n");return;}if (n == 3) {printf("0 2\n3 1 2\n1 2 3\n");return;}if (n % 2 == 0) {if (n / 2 % 2) {printf("1 %d\n", n - 1);print2(n); printf("\n");print2(n - 1);printf(" %d\n", n);}else {printf("0 %d\n", n);print(n); printf("\n");print(n - 1); printf(" %d\n", n);}}else {if ((n + 1) / 2 % 2) {printf("1 %d\n", n);print(n - 2); printf(" %d %d\n", n - 1, n);print(n - 1); printf(" %d\n", n);}else {printf("0 %d\n", n - 1);print(n); printf("\n");print2(n - 1); printf(" %d\n", n);}}
}int main() {while (~scanf("%d", &n)) {solve();}return 0;
}E:
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;const int INF = 0x3f3f3f3f;
int t, n;map<int, int> dp[2];
map<int, int>::iterator it;int lowbit(int x) {return (x&(-x));
}int solve() {dp[0].clear();int pre = 1, now = 0;int num;dp[0][0] = 0;for (int i = 0; i < n; i++) {scanf("%d", &num);num /= 2;swap(pre, now);dp[now].clear();for (it = dp[pre].begin(); it != dp[pre].end(); it++) {int s = it->first;if (dp[now].count(s) == 0) dp[now][s] = dp[pre][s];else dp[now][s] = max(dp[now][s], dp[pre][s]);int next;if (s % num) {next = num;if (dp[now].count(next) == 0) dp[now][next] = dp[pre][s] + num * 2;else dp[now][next] = max(dp[now][next], dp[pre][s] + num * 2);}else {next = s + num;int add = (s % lowbit(next) * 2 + num) * 2;if (dp[now].count(next) == 0) dp[now][next] = dp[pre][s] + add;else dp[now][next] = max(dp[now][next], dp[pre][s] + add);}}}int ans = 0;for (it = dp[now].begin(); it != dp[now].end(); it++)ans = max(ans, it->second);return ans;
}int main() {scanf("%d", &t);while (t--) {scanf("%d", &n);printf("%d\n", solve());}return 0;
}G:
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;const int N = 55;
const int d[8][2] = {{1, 0}, {1, 1}, {1, -1}, {0, 1}, {0, -1}, {-1, 0}, {-1, 1}, {-1, -1}};typedef pair<int, int> pii;int t;
int n, m, f, k;
int g[N][N];
int gg[N][N];
char str[55];
vector<pii> go[1005];void solve() {for (int ti = 1; ti <= f; ti++) {memset(gg, 0, sizeof(gg));for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (g[i][j] == 1) {for (int k = 0; k < 8; k++) {int xx = i + d[k][0];int yy = j + d[k][1];if (xx <= 0 || xx > n || yy <= 0 || yy > m) continue;gg[xx][yy]++;}}}}for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++) {if (g[i][j] == 2) continue;else if (g[i][j] == 0) {if (gg[i][j] == 3) g[i][j] = 1;}else {if (gg[i][j] < 2 || gg[i][j] > 3) g[i][j] = 0;}}for (int i = 0; i < go[ti].size(); i++) {g[go[ti][i].first][go[ti][i].second] = 2;}}for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (g[i][j] == 2) printf("X");else printf("%d", g[i][j]);}printf("\n");}
}int main() {scanf("%d", &t);while (t--) {scanf("%d%d%d%d", &n, &m, &f, &k);for (int i = 1; i <= f; i++)go[i].clear();for (int i = 1; i <= n; i++) {scanf("%s", str + 1);for (int j = 1; j <= m; j++) {g[i][j] = str[j] - '0';}}int ti, x, y;while (k--) {scanf("%d%d%d", &ti, &x, &y);go[ti].push_back(make_pair(x, y));}solve();}return 0;
}H:
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;const int N = 10005;int n;
vector<int> g[N];int dfs(int u) {int sz = g[u].size();vector<int> save;for (int i = 0; i < sz; i++)save.push_back(dfs(g[u][i]));sort(save.begin(), save.end());sz = save.size();int cnt = 0;int ans = 1;for (int i = sz - 1; i >= 0; i--) {if (i != sz - 1 && save[i] != save[i + 1]) break;ans = save[i] + cnt;cnt++;}return ans;
}int main() {while (~scanf("%d", &n)) {for (int i = 1; i <= n; i++)g[i].clear();int v;for (int i = 2; i <= n; i++) {scanf("%d", &v);g[v].push_back(i);}printf("%d\n", dfs(1));}return 0;
}I:
#include <cstdio>
#include <cstring>
#include <cmath>double r, R;double h, x;double cal(double a) {double d = a / 2;h = sqrt(R * R - d * d) + R;x = sqrt(h * h + d * d);return a * x * x / (2 * R * (a + x + x));
}void solve() {double lx = 0, rx = sqrt(3.0) * R;double mid;for (int i = 0; i < 1000; i++) {mid = (lx + rx) / 2;double tmp = cal(mid);if (tmp > r) rx = mid;else lx = mid;}cal((lx + rx) / 2);printf("%.10lf %.10lf %.10lf\n", mid, x, x);
}int main() {while (~scanf("%lf%lf", &r, &R)) {if (r * 2 > R) printf("NO Solution!\n");else solve();}return 0;
}这篇关于135 - ZOJ Monthly, August 2014的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
