NOIP做题练习（day5）

A - 中位数图

题面

题解

先找出题意中的\(b\)所在的位置。

再以这个位置为中心，向右\(for\)一遍有多少个大于/小于该数的数

大于就\(++cs\) 小于就\(--cs\)。

因为这个数是中位数，所以大于它的数小于它的数的数量是一样的。

然后每次以\(cs\)为下标的数\(++\)。

因为\(cs\)可能小于零，

所以需要将\(cs\)加上\(100000\)后再\(++\)。

统计答案时直接加上下标为\(0-cs+100000\)的数的值即可。

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <cctype>

#include <map>

#define int long long

#define gI gi

#define itn int

#define File(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)

using namespace std;

inline int gi()

{

    int f = 1, x = 0; char c = getchar();

    while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}

    while (c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}

    return f * x;

}

int n, b, a[100003], p[100003], c, s[100003], cs, cj, sum, ans, pp[200003];

signed main()

{

	//File("A");

	n = gi(), b = gi();

	for (itn i = 1; i <= n; i+=1)

	{

		a[i] = gi();

		if (a[i] == b) c = i;

	}

	for (int i = c; i <= n; i+=1)

	{

		if (a[i] > b) ++cs;

		if (a[i] < b) --cs;

		++pp[cs + 100000];

	}

	for (int i = c; i >= 1; i-=1)

	{

		if (a[i] > b) ++cj;

		if (a[i] < b) --cj;

		ans = ans + pp[0 - cj + 100000];

	}

	printf("%lld\n", ans);

	return 0;

}

B - 树

题面

题解

直接暴力\(dfs\)即可\(AC\)。

数据很水啊……

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <cctype>

#define gI gi

#define itn int

#define File(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)

using namespace std;

inline int gi()

{

    int f = 1, x = 0; char c = getchar();

    while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}

    while (c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}

    return f * x;

}

int n, m, s, a[100003], fa[100003], ans;

int tot, head[300003], nxt[300003], ver[300003];

inline void add(int u, int v)

{

	ver[++tot] = v, nxt[tot] = head[u], head[u] = tot;

}

void dfs(int u, int fa, int w)

{

	if (w > s) return;

	if (w == s) {++ans; return;}

	for (int i = head[u]; i; i = nxt[i])

	{

		int v = ver[i];

		if (v == fa) continue;

		dfs(v, u, w + a[v]);

	}

}

int main()

{

	//File("B");

	n = gi(), s = gi();

	for (int i = 1; i <= n; i+=1) a[i] = gi();

	for (int i = 1; i < n; i+=1)

	{

		int u = gi(), v = gI();

		add(u, v);

		fa[v] = u;

	}

	for (int i = 1; i <= n; i+=1)

	{

		dfs(i, fa[i], a[i]);

	}

	printf("%d\n", ans);

	return 0;

}

C - 松鼠的新家

题面

题解

倍增\(LCA+\)树上差分一遍过。

注意要判断两个房间是不是存在祖先关系。

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <cctype>

#include <vector>

#define gI gi

#define itn int

#define File(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)

using namespace std;

inline int gi()

{

    int f = 1, x = 0; char c = getchar();

    while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}

    while (c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}

    return f * x;

}

itn n, a[300003], dep[300003], w[300003], fa[300003][23], sum, ans, tot, head[1200003], nxt[1200003], ver[1200003];

int f[300003], logn;

inline void add(int u, int v)

{

	ver[++tot] = v, nxt[tot] = head[u], head[u] = tot;

}

void dfs(int u, int baba, int step)

{

	dep[u] = step; fa[u][0] = baba;

	for (int i = 1; i <= logn; i+=1)

	{

		fa[u][i] = fa[fa[u][i - 1]][i - 1];

	}

	for (int i = head[u]; i; i = nxt[i])

	{

		int v = ver[i];

		if (v == baba) continue;

		dfs(v, u, step + 1);

	}

}

inline void getlca(int u, int v)

{

	if (dep[u] < dep[v]) swap(u, v);

	int x = u, y = v;

	while (dep[u] > dep[v])

	{

		for (int i = logn; i >= 0; i-=1)

		{

			if (dep[fa[u][i]] > dep[v]) u = fa[u][i];

		}

		u = fa[u][0];

	}

	if (u == v)

	{

		++w[x], --w[fa[u][0]]; return;

	}

	for (itn i = logn; i >= 0; i-=1)

	{

		if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];

	}

	u = fa[u][0];

	++w[x], ++w[y], --w[u], --w[fa[u][0]];

}

void getans(int u)

{

	f[u] = w[u];

	for (int i = head[u]; i; i = nxt[i])

	{

		int v = ver[i];

		if (v == fa[u][0]) continue;

		getans(v);

		f[u] = f[u] + f[v];

	}

}

int main()

{

	//File("C");

	n = gi();

	while ((1 << logn) < n) ++logn;

	for (int i = 1; i <= n; i+=1)

	{

		a[i] = gi();

	}

	for (int i = 1; i < n; i+=1)

	{

		int u = gi(), v = gi();

		add(u, v); add(v, u);

	}

	add(0, a[1]);

	dfs(0, 0, 1);

	for (int i = 1; i < n; i+=1)

	{

		getlca(a[i], a[i + 1]);

	}

	getans(a[1]);

	for (int i = 1; i <= n; i+=1)

	{

		printf("%d\n", (i == a[1]) ? (f[i]) : (f[i] - 1));

	}

	return 0;

}

总结

为什么每次时间内\(0AC\)，时间结束之后再切题呢？

思维要更活跃一点啊。

巴特西

NOIP做题练习（day5）

A - 中位数图

题解

代码

B - 树

题解

代码

C - 松鼠的新家

题解

代码

总结

最新文章

热门文章