Good Bye 2014 A B C D E
來源：程序員人生 發布時間：2015-01-13 08:29:10 閱讀次數：3625次
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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
