Good Bye 2014 A B C D E

#include <cstdio> #include <cstdlib> const int N = 30005; int n, t, a[N]; int main() { scanf("%d%d", &n, &t); for (int i = 1; i <= n - 1; i++) scanf("%d", &a[i]); int bo = 0; for (int i = 1; i <= t;) { if (i == t) { bo = 1; break; } i += a[i]; } printf("%s ", bo ? "YES" : "NO"); return 0; }

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 305; int n, a[N], g[N][N], vis[N]; char str[N]; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); for (int i = 0; i < n; i++) { scanf("%s", str); for (int j = 0; j < n; j++) g[i][j] = str[j] - '0'; g[i][i] = 1; } for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { g[i][j] |= (g[i][k]&g[k][j]); } } } for (int i = 0; i < n; i++) { int Min = n; for (int j = 0; j < n; j++) { if (g[j][i] && !vis[a[j]]) { Min = min(Min, a[j]); } } vis[Min] = 1; printf("%d ", Min); } return 0; }

#include <cstdio> #include <cstring> const int N = 505; typedef long long ll; int n, m, w[N], vis[N][N]; int v; ll sum = 0; int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf("%d", &w[i]); for (int i = 1; i <= m; i++) { scanf("%d", &v); for (int j = 1; j <= n; j++) sum += w[j] * vis[v][j]; memset(vis[v], 0, sizeof(vis[v])); for (int j = 1; j <= n; j++) { if (v == j) continue; vis[j][v] = 1; } } printf("%lld ", sum); return 0; }

#include <cstdio> #include <cstring> #include <vector> using namespace std; const int N = 100005; int n; struct Edge { int u, v, id, num; double len; Edge(){} Edge(int u, int v, int id) { this->u = u; this->v = v; this->id = id; } } e[N]; vector<Edge> g[N]; int dfs(int u, int p) { int sz = 1; for (int i = 0; i < g[u].size(); i++) { int v = g[u][i].v; if (v == p) continue; int tmp = dfs(v, u); sz += tmp; e[g[u][i].id].num = tmp; } return sz; } int main() { scanf("%d", &n); int u, v; double w; for (int i = 1; i <= n - 1; i++) { scanf("%d%d%lf", &u, &v, &w); e[i].len = w; g[u].push_back(Edge(u, v, i)); g[v].push_back(Edge(v, u, i)); } dfs(1, 0); int q; scanf("%d", &q); int id, vv; double sum = 0; for (int i = 1; i <= n - 1; i++) { sum += (double)(n - 2) * (e[i].num) * (n - e[i].num) * (e[i].len); } double c1 = (double)n * (n - 1) * (n - 2) / 2 / 3; while (q--) { scanf("%d%d", &id, &vv); sum -= (double)(n - 2) * (e[id].num) * (n - e[id].num) * (e[id].len - vv); e[id].len = vv; printf("%.10lf ", sum / c1); } return 0; }

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 200005; struct query { int l, r, id; } s[N], q[N]; int n, ans[N]; bool cmp(query a, query b) { return a.l > b.l; } int hash[N * 2], hn; int find(int x) { return lower_bound(hash, hash + hn, x) - hash; } #define lson(x) ((x<<1)+1) #define rson(x) ((x<<1)+2) struct Node { int l, r, len, lazy; void gao() { lazy = 1; len = 0; } } node[N * 8]; void pushup(int x) { node[x].len = node[lson(x)].len + node[rson(x)].len; } void pushdown(int x) { if (node[x].lazy) { node[x].lazy = 0; node[lson(x)].gao(); node[rson(x)].gao(); } } void build(int l, int r, int x = 0) { node[x].l = l; node[x].r = r; node[x].lazy = 0; if (l == r) { node[x].len = hash[r + 1] - hash[l]; return; } int mid = (l + r) / 2; build(l , mid, lson(x)); build(mid + 1, r, rson(x)); pushup(x); } void add(int l, int r, int x = 0) { if (node[x].l >= l && node[x].r <= r) { node[x].gao(); return; } pushdown(x); int mid = (node[x].l + node[x].r) / 2; if (l <= mid) add(l, r, lson(x)); if (r > mid) add(l, r, 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].len; int mid = (node[x].l + node[x].r) / 2; int ans = 0; pushdown(x); if (l <= mid) ans += query(l, r, lson(x)); if (r > mid) ans += query(l, r, rson(x)); pushup(x); return ans; } int main() { scanf("%d", &n); hn = 0; for (int i = 0; i < n; i++) { scanf("%d%d", &s[i].l, &s[i].r); s[i].r += s[i].l; hash[hn++] = s[i].l; hash[hn++] = s[i].r; } sort(hash, hash + hn); hn = unique(hash, hash + hn) - hash; build(0, hn - 2); int qn; scanf("%d", &qn); for (int i = 0; i < qn; i++) { scanf("%d%d", &q[i].l, &q[i].r); q[i].l--; q[i].r--; q[i].l = s[q[i].l].l; q[i].r = s[q[i].r].l; q[i].id = i; } sort(q, q + qn, cmp); int now = n - 1; for (int i = 0; i < qn; i++) { while (s[now].l >= q[i].l && now >= 0) { add(find(s[now].l), find(s[now].r) - 1); now--; } ans[q[i].id] = query(find(q[i].l), find(q[i].r) - 1); } for (int i = 0; i < qn; i++) printf("%d ", ans[i]); return 0; }