The 2014 ACM-ICPC Asia Mudanjiang Regional Contest(2014牡丹江区域赛)
The 区域 2014 ACM Contest ICPC Asia
2023-09-11 14:14:43 时间
The 2014 ACM-ICPC Asia Mudanjiang Regional Contest
没去现场。做的网络同步赛。感觉还能够,搞了6题
A:这是签到题,对于A堆除掉。假设没剩余在减一。B堆直接除掉 + 1就能够了
B:二分贪心,二分长度。然后会发现本质上是在树上最长链上找两点,那么有二分出来的长度了,就从两端分别往里移动那么长,那两个位置就是放置位置。然后在推断一下就能够了
D:概率DP。首先知道放一个棋子。能够等价移动到右上角区域,那么就能够dp[x][y][k],表示已经完毕x行y列。已经放了k个棋子,那么棋盘被划分成4个区域。利用这个区域能够算概率,然后去转移就可以
H:字符串处理,先hash掉,记录每一个hash值相应的l,r区间。离线处理完每次询问输出就能够了,注意细节
I:签到题,注意0的时候是等于0就能够了
K:贪心,假设数字个数不够。在前面补是最优的。然后从左往右扫描一遍,每次遇到1个星号要扣掉两个数字,假设没有,这须要交换操作。交换肯定和最后面的数字交换是最优的,最后还要考虑一种特殊情况。就是没有交换,而且最后还有数字,这时候要加入一个星号
代码:
A:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 55; int t, n, m; int a, b, suma, sumb; int main() { scanf("%d", &t); while (t--) { scanf("%d%d", &n, &m); suma = sumb = 0; for (int i = 0; i < n - 1; i++) { scanf("%d", &a); suma += a; } for (int i = 0; i < m; i++) { scanf("%d", &b); sumb += b; } int l, r; l = suma / (n - 1) - (suma % (n - 1) == 0); r = sumb / m + 1; if (l > r) swap(l, r); printf("%d %d\n", l, r); } return 0; }
B:
#include <cstdio> #include <cstring> #include <queue> #include <algorithm> using namespace std; const int N = 200005; struct Edge { int u, v; Edge() {} Edge(int u, int v) { this->u = u; this->v = v; } } E[N * 2]; int first[N], next[N * 2], en; void add_Edge(int u, int v) { E[en] = Edge(u, v); next[en] = first[u]; first[u] = en++; } const int INF = 0x3f3f3f3f; int t, n, vis[N], f[N], u1, u2, Q[N * 2]; int bfs(int root) { int head = 0, rear = 0; vis[root] = 0; Q[rear++] = root; f[root] = 0; int u; while (head < rear) { u = Q[head++]; for (int i = first[u]; i + 1; i = next[i]) { Edge e = E[i]; int v = e.v; if (vis[v] > vis[u] + 1) { vis[v] = vis[u] + 1; f[v] = u; Q[rear++] = v; } } } return u; } bool judge(int len) { memset(vis, INF, sizeof(vis)); u1 = bfs(1); for (int i = 0; i < len; i++) { if (f[u1] == 0) { u2 = u1 % n + 1; return true; } u1 = f[u1]; } memset(vis, INF, sizeof(vis)); u2 = bfs(u1); for (int i = 0; i < len; i++) { if (f[u2] == 0) return true; u2 = f[u2]; } bfs(u2); for (int i = 1; i <= n; i++) if (vis[i] > len) return false; return true; } int main() { scanf("%d", &t); while (t--) { en = 0; memset(first, -1, sizeof(first)); scanf("%d", &n); int u, v; for (int i = 1; i < n; i++) { scanf("%d%d", &u, &v); add_Edge(u, v); add_Edge(v, u); } if (n == 2) { printf("0 1 2\n"); continue; } int l = 0, r = n; while (l < r) { int mid = (l + r) / 2; if (judge(mid)) r = mid; else l = mid + 1; } judge(l); if (u1 == u2) u2 = u2 % n + 1; printf("%d %d %d\n", l, u1, u2); } return 0; }
D:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 55; int t, n, m; double dp[N][N][N * N]; int main() { scanf("%d", &t); while (t--) { scanf("%d%d", &n, &m); memset(dp, 0, sizeof(dp)); dp[0][0][0] = 1; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { for (int k = max(i, j); k <= i * j; k++) { double p1 = (i * j - (k - 1)) * 1.0; double p2 = (n - i + 1) * j; double p3 = i * (m - j + 1); double p4 = (n - i + 1) * (m - j + 1); dp[i][j][k] = dp[i][j][k - 1] * p1 + dp[i - 1][j][k - 1] * p2 + dp[i][j - 1][k - 1] * p3 + dp[i - 1][j - 1][k - 1] * p4; dp[i][j][k] /= (n * m - (k - 1)); } } } double ans = 0; for (int i = max(n, m); i <= n * m; i++) ans += dp[n][m][i] * i - dp[n][m][i - 1] * i; printf("%.12lf\n", ans); } return 0; }
H:
#include <cstdio> #include <cstring> #include <map> using namespace std; #define MP(a,b) make_pair(a,b) typedef unsigned long long ull; const ull x = 123; const int N = 200005; typedef pair<int, int> pii; char str[N], q[N]; map<ull, pii> g; int t, u, k, lens; int build(ull st) { int flag = 1; while (u < lens) { if (str[u] == '{') { flag = 0; u++; } if (str[u] == '}') { u++; return u; } ull nt = st; while (str[u] != ':' && str[u] != ',' && str[u] != '}') nt = nt * x + str[u++]; if (str[u] == ':') { int l = ++u; int r = build(nt * x + '.'); g[nt] = MP(l, r); } if (str[u] == '}') { if (!flag) u++; return u; } if (str[u] == ',') { if (flag) return u; u++; } } } int main() { scanf("%d", &t); while (t--) { u = 0; g.clear(); scanf("%s", str); lens = strlen(str); build(0); scanf("%d", &k); while (k--) { scanf("%s", q); ull tmp = 0; int len = strlen(q); for (int i = 0; i < len; i++) tmp = tmp * x + q[i]; if (!g.count(tmp)) { printf("Error!\n"); continue; } int l = g[tmp].first, r = g[tmp].second; for (int i = l; i < r; i++) printf("%c", str[i]); printf("\n"); } } return 0; }
I:
#include <cstdio> #include <cstring> #include <cmath> int t, n; char str[10]; double solve(int x) { if (x == 0) return 0; double sb = x * 1.0 / 100; if (str[0] == 'b') return sb * log2(sb); if (str[0] == 'n') return sb * log(sb); if (str[0] == 'd') return sb * log10(sb); } int main() { scanf("%d", &t); while (t--) { scanf("%d%s", &n, str); double ans = 0; int x; for (int i = 0; i < n; i++) { scanf("%d", &x); ans += solve(x); } printf("%.12lf\n", -ans); } return 0; }
K:
#include <cstdio> #include <cstring> #include <map> using namespace std; #define MP(a,b) make_pair(a,b) typedef unsigned long long ull; const ull x = 123; const int N = 200005; typedef pair<int, int> pii; char str[N], q[N]; map<ull, pii> g; int t, u, k, lens; int build(ull st) { int flag = 1; while (u < lens) { if (str[u] == '{') { flag = 0; u++; } if (str[u] == '}') { u++; return u; } ull nt = st; while (str[u] != ':' && str[u] != ',' && str[u] != '}') nt = nt * x + str[u++]; if (str[u] == ':') { int l = ++u; int r = build(nt * x + '.'); g[nt] = MP(l, r); } if (str[u] == '}') { if (!flag) u++; return u; } if (str[u] == ',') { if (flag) return u; u++; } } } int main() { scanf("%d", &t); while (t--) { u = 0; g.clear(); scanf("%s", str); lens = strlen(str); build(0); scanf("%d", &k); while (k--) { scanf("%s", q); ull tmp = 0; int len = strlen(q); for (int i = 0; i < len; i++) tmp = tmp * x + q[i]; if (!g.count(tmp)) { printf("Error!\n"); continue; } int l = g[tmp].first, r = g[tmp].second; for (int i = l; i < r; i++) printf("%c", str[i]); printf("\n"); } } return 0; }
相关文章
- java 生成12位随机数,解决The literal 9999999999999 of type int is out of range 问题
- The three top-paying tech roles in 2022 and the skills you need to land them
- The need for legislative reform on secrecy orders
- What's the difference between the 'ref' and 'out' keywords?
- What are the differences between Flyweight and Object Pool patterns?
- 解决问题“The App ID ‘XXXXX‘ appears to be in use by the App Store, so it can not be removed at this ti”
- Hadoop- The Definitive Guide 笔记二
- 【转】eclipse运行 Ant报错Could not find the main class: org.eclipse.ant.internal.launching.remote.InternalAntRunner. Program
- The reference to entity "characterEncoding" must end with the ';' delimiter
- The development prospect of SAP consultants in China in the next decade
- The attribute required is undefined for the annotation type XmlElementRef
- Android can only be called from within the same library group prefix (referenced groupId=androidx
- The library 'xxx.jar' contains native libraries that will not run on the device. 解决方法(Eclipse)
- Unity 报错之 The same field name is serialized multiple times in the class or its parent class.
- 【RefactoringCode】The description of the refactoring book
- BEA-150021 - The admin server failed to authenticate the identity of the user username starting the managed server.
- You have an error in your SQL syntax; check the manual that corresponds to your MariaDB server
- POJ 2965--The Pilots Brothers' refrigerator
- The CompilerVersion constant identifies the internal version number of the Delphi compiler.