学步园

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