Good Bye 2014 A B C D E

A:签到,从左往右走1遍判断下有无遇到t便可

B:先利用floyd求出传递闭包,然后利用这个传递闭包贪心小的尽可能往前放便可

C:贪心的策略,放的顺序其实根据拿的顺序就能够肯定的,所以只要在拿的顺序上从左往右扫1遍便可

D:先DFS预处理出每条边两边点的个数,然后3元组对每一个边经过都是n – 2次,所以1个边都会被计算到n – 2 * 1边点 * 另外一边点个数

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;
}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 本站源码并不保证全部能正常使用,仅供有技术基础的人学习研究,请谨慎下载
8. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » Good Bye 2014 A B C D E

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡