Good Bye 2014 A B C D E

本文主要是介绍Good Bye 2014 A B C D E，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A：签到，从左往右走一遍判断下有没有遇到t即可

B：先利用floyd求出传递闭包，然后利用这个传递闭包贪心小的尽量往前放即可

C：贪心的策略，放的顺序其实根据拿的顺序就可以确定的，所以只要在拿的顺序上从左往右扫一遍即可

D：先DFS预处理出每条边两边点的个数，然后三元组对于每个边经过都是n - 2次，所以一个边都会被计算到n - 2 * 一边点 * 另一边点个数

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\n", 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\n", 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\n", 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\n", ans[i]);return 0;
}

这篇关于Good Bye 2014 A B C D E的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---