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",&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],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,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,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,rson(x)); pushup(x); } void add(int l,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,lson(x)); if (r > mid) add(l,rson(x)); pushup(x); } int query(int l,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,lson(x)); if (r > mid) ans += query(l,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; }