首页 > 代码库 > ACdream原创群赛(18)のAK's dream
ACdream原创群赛(18)のAK's dream
ACdream原创群赛(18)のAK‘s dream
题目链接
A:水题,直接模拟题意去搞即可
D:贪心+组合数学,把剑和英雄都从小到大排序,每次计算该英雄能用前几把剑cnt,cnt减去之前有多少人就是该英雄能选的,种数乘上cnt - 之前有多少人
F:DP,dp[i][j][2]表示第i天,用了j次修改,当前状态是A还是B,然后去转移即可
G:水题,直接用字符串处理即可,把数字都加上前导零方便判断
H:几何,利用正弦定理,余弦定理乱搞就可以了
I:水题,直接每个位置推出来输出,化简利用gcd即可
J:并查集,把询问逆向处理,每次多一块,就和左边和右边合并,这样对应的块数跟着变化,最后再反过来输出即可
代码:
A:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int n, cur, d; int main() { int cas = 0; while (~scanf("%d%d%d", &n, &cur, &d)) { printf("Case #%d: ", ++cas); int l = max(1, cur - d); if (cur == 1) printf("[<<]"); else printf("(<<)"); if (l != 1) printf("[...]"); for (int i = l; i < cur; i++) printf("(%d)", i); printf("[%d]", cur); int r = min(n, cur + d); for (int i = cur + 1; i <= r; i++) printf("(%d)", i); if (r != n) printf("[...]"); if (cur == n) printf("[>>]"); else printf("(>>)"); printf("\n"); } return 0; }
D:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 100005; const int MOD = 1000000007; typedef long long ll; int t, n, a[N], b[N]; int main() { int cas = 0; scanf("%d", &t); while (t--) { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); for (int i = 0; i < n; i++) scanf("%d", &b[i]); sort(a, a + n); sort(b, b + n); int ans = 1; int l = 0; for (int i = 0; i < n; i++) { while (l < n && b[i] >= a[l]) l++; ans = (ll)ans * (l - i) % MOD; } printf("Case #%d: %d\n", ++cas, ans); } return 0; }
F:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 105; const int INF = 0x3f3f3f3f; int n, m, a[N], Max[N][55][2], Min[N][55][2], num[2]; char str[N]; int main() { num[0] = 1; num[1] = -1; int cas = 0; while (~scanf("%d", &n)) { scanf("%s%d", str + 1, &m); memset(Max, -INF, sizeof(Max)); memset(Min, INF, sizeof(Min)); for (int i = 1; i <= n; i++) a[i] = str[i] - 'A'; Max[0][0][0] = 0; Min[0][0][0] = 0; for (int i = 0; i < n; i++) { for (int j = 0; j <= m; j++) { for (int k = 0; k < 2; k++) { if (a[i + 1]) { Max[i + 1][j][!k] = max(Max[i + 1][j][!k], Max[i][j][k]); Max[i + 1][j + 1][k] = max(Max[i + 1][j + 1][k], Max[i][j][k] + num[k]); Min[i + 1][j][!k] = min(Min[i + 1][j][!k], Min[i][j][k]); Min[i + 1][j + 1][k] = min(Min[i + 1][j + 1][k], Min[i][j][k] + num[k]); } else { Max[i + 1][j + 1][!k] = max(Max[i + 1][j + 1][!k], Max[i][j][k]); Max[i + 1][j][k] = max(Max[i + 1][j][k], Max[i][j][k] + num[k]); Min[i + 1][j + 1][!k] = min(Min[i + 1][j + 1][!k], Min[i][j][k]); Min[i + 1][j][k] = min(Min[i + 1][j][k], Min[i][j][k] + num[k]); } } } } int ans1 = INF, ans2 = -INF; int st = m % 2; for (int i = st; i <= m; i += 2) { ans1 = min(ans1, Min[n][i][0]); ans1 = min(ans1, Min[n][i][1]); ans2 = max(ans2, Max[n][i][0]); ans2 = max(ans2, Max[n][i][1]); } int ans = -INF; ans = max(ans2, -ans1); printf("Case #%d: %d\n", ++cas, ans); } return 0; }
G:
#include <cstdio> #include <cstring> #include <string> #include <iostream> using namespace std; string str; int main() { while (cin >> str) { string a, b, c; a = "000000000000000000000000032767"; b = "000000000000000000002147483647"; c = "000000000009223372036854775807"; int s = 0; int n = str.length(); if (str[0] == '-') { n--; s++; a = "000000000000000000000000032768"; b = "000000000000000000002147483648"; c = "000000000009223372036854775808"; } string tmp = ""; for (int i = 30 - n; i > 0; i--) tmp += '0'; for (int i = s; i < n + s; i++) tmp += str[i]; str = tmp; if (str <= a) printf("short\n"); else if (str <= b) printf("int\n"); else if (str <= c) printf("long long\n"); else printf("It is too big!\n"); } return 0; }
#include <cstdio> #include <cstring> #include <cmath> const double eps = 1e-9; const double pi = acos(-1.0); double a, b, c, d; double solve() { if (fabs(a) < eps) return 0.0; if (fabs(c) < eps) return 0.0; if (fabs(b) < eps) return c; if (fabs(d) < eps) return b + c; a = a / 180 * pi; b = b / 180 * pi; c = c / 180 * pi; d = d / 180 * pi; double AB = 1.0; double AOB = pi - b - c; double ADB = pi - a - b - c; double AEB = pi - b - c - d; double A = a + b, B = c + d; double AO = AB * sin(c) / sin(AOB); double BO = AB * sin(b) / sin(AOB); double BD = AB * sin(A) / sin(ADB); double AE = AB * sin(B) / sin(AEB); double DO = BD - BO; double EO = AE - AO; double DE = sqrt(DO * DO + EO * EO - cos(AOB) * 2 * DO * EO); double cosx = (DE * DE + EO * EO - DO * DO) / 2 / DE / EO; double ans = acos(cosx) * 180 / pi; return ans; } int main() { while (~scanf("%lf%lf%lf%lf", &a, &b, &c, &d)) { printf("%.2lf\n", solve()); } return 0; }
I:
#include <cstdio> #include <cstring> int gcd(int a, int b) { while (b) { int tmp = a % b; a = b; b = tmp; } return a; } int n; int main() { while (~scanf("%d", &n)) { int a, b; for (int i = 0; i < n; i++) { scanf("%d%d", &a, &b); int mu = b + 1; int d = gcd(a, mu); a /= d; mu /= d; if (mu < 0) { a = -a; mu = -mu; } if (mu == 1) printf("%d", a); else { printf("%d/%d", a, mu); } printf(" "); printf("%d", b + 1); printf("%c", i == n - 1 ? '\n' : ' '); } } return 0; }
J:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 1000005; int t, n, m, parent[N]; struct Block { int id, h; } d[N]; int q[N], vis[N], out[N], on; int find(int x) { return x == parent[x] ? x : parent[x] = find(parent[x]); } void merge(int u, int v) { int pa = find(u); int pb = find(v); if (pa != pb) parent[pb] = pb; } bool cmp(Block a, Block b) { return a.h > b.h; } int main() { int cas = 0; scanf("%d", &t); while (t--) { scanf("%d%d", &n, &m); d[0].h = d[n + 1].h = -1; vis[0] = vis[n + 1] = 0; for (int i = 1; i <= n; i++) { vis[i] = 0; parent[i] = i; scanf("%d", &d[i].h); d[i].id = i; } sort(d + 1, d + n + 1, cmp); for (int i = 0; i < m; i++) scanf("%d", &q[i]); int l = 1; int ans = 0; on = 0; printf("Case #%d:", ++cas); for (int i = m - 1; i >= 0; i--) { while (l <= n && q[i] < d[l].h) { if (vis[d[l].id - 1] && vis[d[l].id + 1]) { merge(d[l].id, d[l].id - 1); merge(d[l].id, d[l].id + 1); ans--; } else if (vis[d[l].id - 1]) merge(d[l].id, d[l].id - 1); else if (vis[d[l].id + 1]) merge(d[l].id, d[l].id + 1); else ans++; vis[d[l].id] = 1; l++; } out[on++] = ans; } for (int i = on - 1; i >= 0; i--) printf(" %d", out[i]); printf("\n"); } return 0; }
ACdream原创群赛(18)のAK's dream
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。