首页 > 代码库 > Codeforces Round #271 (Div. 2)
Codeforces Round #271 (Div. 2)
Codeforces Round #271 (Div. 2)
题目链接
A:水题,分LR考虑一下即可,脸滚键盘可以滚出字符串
B:就是预处理一下,然后每次询问输出即可
C:暴力旋转,判断正方形即可
D:递推dp[i] = dp[i - 1] + dp[i - k]
E:先把高度hash,每次多一个高度,就利用二分去找满足对应的hash值,找出这些最大值,这步用线段树维护,然后记录每个位置答案用来输出
F:每个区间最小值才会满足,并且如果最小值不等于整个区间gcd答案就为0了,如果等于就可以找出这个区间对应这个最小值有几个,用数组记录二分即可
代码:
#include <cstdio> #include <cstring> #include <iostream> #include <string> using namespace std; string str[3]; string A, sb; int mv; char get(char sb) { for (int i = 0; i < 3; i++) { for (int j = 0; j < str[i].length(); j++) { if (str[i][j] == sb) return str[i][j + mv]; } } } int main() { str[0] = "qwertyuiop"; str[1] = "asdfghjkl;"; str[2] = "zxcvbnm,./"; cin >> A >> sb; if (A[0] == 'L') mv = 1; else mv = -1; for (int i = 0; i < sb.length(); i++) { cout << get(sb[i]); } cout << endl; return 0; }
B:
#include <cstdio> #include <cstring> const int N = 1000005; int n, a, vis[N]; int main() { scanf("%d", &n); int s = 0; for (int i = 1; i <= n; i++) { scanf("%d", &a); for (int j = 0; j < a; j++) { s++; vis[s] = i; } } int m; scanf("%d", &m); while (m--) { scanf("%d", &a); printf("%d\n", vis[a]); } return 0; }
C:
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; const int INF = 0x3f3f3f3f; int n; double x[4], y[4], a[4], b[4]; double sx[4], sy[4]; int ans; void rote(double &x, double &y, double a, double b) { x -= a; y -= b; double x1 = -y; double y1 = x; x = x1 + a; y = y1 + b; } double save[10]; int sn; double dis(double x1, double y1, double x2, double y2) { double dx = x1 - x2; double dy = y1 - y2; return sqrt(dx * dx + dy * dy); } bool eq(double a, double b) { return fabs(a - b) < 1e-9; } bool judge() { sn = 0; for (int i = 0; i < 4; i++) { for (int j = i + 1; j < 4; j++) { save[sn++] = dis(sx[i], sy[i], sx[j], sy[j]); } } sort(save, save + sn); if (fabs(save[0]) < 1e-9) return false; for (int i = 0; i < 3; i++) if (!eq(save[i], save[i + 1])) return false; if (!eq(save[4], save[5])) return false; if (!eq(save[3] * sqrt(2.0), save[4])) return false; return true; } void dfs(int u, int sum) { if (sum >= ans) return; if (u == 4) { if (judge()) ans = min(ans, sum); return; } double xx = x[u], yy = y[u]; for (int i = 0; i <= 3; i++) { sx[u] = xx; sy[u] = yy; dfs(u + 1, sum + i); rote(xx, yy, a[u], b[u]); } } int solve() { ans = INF; dfs(0, 0); if (ans == INF) ans = -1; return ans; } int main() { scanf("%d", &n); while (n--) { for (int i = 0; i < 4; i++) scanf("%lf%lf%lf%lf", &x[i], &y[i], &a[i], &b[i]); printf("%d\n", solve()); } return 0; }
D:
#include <cstdio> #include <cstring> const int MOD = 1e9 + 7; typedef long long ll; const int N = 100005; int t, k, a, b; int dp[N]; int main() { dp[0] = 1; scanf("%d%d", &t, &k); for (int i = 1; i < N; i++) { dp[i] = dp[i - 1]; if (i >= k) dp[i] = (dp[i] + dp[i - k]) % MOD; } for (int i = 1; i < N; i++) dp[i] = (dp[i] + dp[i - 1]) % MOD; int m; while (t--) { scanf("%d%d", &a, &b); printf("%d\n", ((dp[b] - dp[a - 1]) % MOD + MOD) % MOD); } return 0; }
E:
#include <cstdio> #include <cstring> #include <map> #include <algorithm> using namespace std; typedef long long ll; const int INF = 0x3f3f3f3f; const int N = 100005; int n, hn; ll d, h[N], hh[N]; int dp[N]; map<ll, int> hash; map<ll, int>::iterator it; #define lson(x) ((x<<1)+1) #define rson(x) ((x<<1)+2) struct Node { int l, r, Max; } node[N * 4]; ll abss(ll x) { if (x < 0) return -x; return x; } void build(int l, int r, int x = 0) { node[x].l = l; node[x].r = r; node[x].Max = 0; if (l == r) { return; } int mid = (l + r) / 2; build(l, mid, lson(x)); build(mid + 1, r, rson(x)); } void pushup(int x) { node[x].Max = max(node[lson(x)].Max, node[rson(x)].Max); } void add(int v, int val, int x = 0) { if (node[x].l == node[x].r) { node[x].Max = max(node[x].Max, val); return; } int mid = (node[x].l + node[x].r) / 2; if (v <= mid) add(v, val, lson(x)); if (v > mid) add(v, val, rson(x)); pushup(x); } int query(int l, int r, int x = 0) { if (node[x].l >= l && node[x].r <= r) return node[x].Max; int ans = -INF; int mid = (node[x].l + node[x].r) / 2; if (l <= mid) ans = max(ans, query(l, r, lson(x))); if (r > mid) ans = max(ans, query(l, r, rson(x))); return ans; } int out[N], on = 0; int main() { scanf("%d%lld", &n, &d); for (int i = 1; i <= n; i++) { scanf("%lld", &h[i]); hh[i] = h[i]; } sort(h + 1, h + n + 1); for (int i = 1; i <= n; i++) { if (hash.count(h[i])) continue; hash[h[i]] = hn++; } build(0, hn - 1); for (int i = 1; i <= n; i++) { dp[i] = 1; it = hash.upper_bound(hh[i] - d); if (it != hash.begin()) { it--; int l = it->second; int tmp = query(0, l); if (tmp) dp[i] = max(dp[i], tmp + 1); } it = hash.lower_bound(hh[i] + d); if (it != hash.end()) { int r = it->second; int tmp = query(r, hn - 1); if (tmp) dp[i] = max(dp[i], tmp + 1); } add(hash[hh[i]], dp[i]); } int ans = 0, ans_v; for (int i = 1; i <= n; i++) { if (ans < dp[i]) ans = dp[i], ans_v = i; } printf("%d\n", dp[ans_v]); int tot = dp[ans_v]; ll pre = hh[ans_v]; out[0] = ans_v; on = 1; tot--; for (int i = ans_v; i >= 1; i--) { if (dp[i] == tot && abss(hh[i] - pre) >= d) { out[on++] = i; pre = hh[i]; tot--; } } for (int i = on - 1; i >= 0; i--) printf("%d%c", out[i], i == 0 ? '\n' : ' '); return 0; }
F:
#include <cstdio> #include <cstring> #include <map> #include <vector> #include <algorithm> using namespace std; const int N = 100005; int n, s[N]; map<int, vector<int> > g; #define lson(x) ((x<<1)+1) #define rson(x) ((x<<1)+2) struct Node { int l, r, gcd, Min; } node[N * 4]; int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } void pushup(int x) { node[x].gcd = gcd(node[lson(x)].gcd, node[rson(x)].gcd); node[x].Min = min(node[lson(x)].Min, node[rson(x)].Min); } void build(int l, int r, int x = 0) { node[x].l = l; node[x].r = r; if (l == r) { node[x].Min = node[x].gcd = s[l]; return; } int mid = (l + r) / 2; build(l, mid, lson(x)); build(mid + 1, r, rson(x)); pushup(x); } const int INF = 0x3f3f3f3f; int gc, an, cnt[N]; void query(int l, int r, int x = 0) { if (node[x].l >= l && node[x].r <= r) { if (an > node[x].Min) { an = node[x].Min; } gc = gcd(gc, node[x].gcd); return; } int mid = (node[x].l + node[x].r) / 2; if (l <= mid) query(l, r, lson(x)); if (r > mid) query(l, r, rson(x)); } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &s[i]); if (g[s[i]].size() == 0) cnt[i] = 0; else cnt[i] = cnt[g[s[i]][g[s[i]].size() - 1]] + 1; g[s[i]].push_back(i); } build(1, n); int m; scanf("%d", &m); int l, r; while (m--) { scanf("%d%d", &l, &r); an = INF; gc = 0; query(l, r); if (an != gc) printf("%d\n", r - l + 1); else { int left = *lower_bound(g[an].begin(), g[an].end(), l); int right = *--upper_bound(g[an].begin(), g[an].end(), r); left = cnt[left]; right = cnt[right]; printf("%d\n", r - l - right + left); } } return 0; }
Codeforces Round #271 (Div. 2)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。