抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

NOIP毒瘤题讲解

发布于：2019年11月9日

P1600 天天爱跑步

这道题细节多比较烦人。

对于一个观察员uu，考虑哪些跑步者可以对他被他观察到。

性质1

（搞笑情况）

$s \in subtree(u) \ t \notin subtree(u) \to 从从s$出发，在上行路线上被观察到

$t \in subtree(u) \ s \notin subtree(u) \to 在在t$结束，在下行路线上被观察到

s,t∈subtree(u)s,t \in subtree(u)，全部缩在uu子树里面，只可能u==lca(s,t)u==lca(s,t)时观察到

如果不是：

性质2

在上行路线上被看到

在下行路线上被看到

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <bits/stdc++.h>
#define MAXN 300005
#define MAXM 25
using namespace std;
inline int read() {
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9') {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9') {
        x=(x*10)+(ch-'0');
        ch=getchar();
    }
    return x*f;
}
vector<int>G[MAXN];
inline void AddEdge(int u,int v){
	G[u].push_back(v);
}
namespace L__C__A__Desu{//简单LCA
	int anc[MAXN][MAXM],dep[MAXN];
	void dfs(int u,int father){
		anc[u][0]=father;
		for (register int i=1;i<MAXM;++i) anc[u][i]=anc[anc[u][i-1]][i-1];
		for (register int i=0;i<G[u].size();++i){
			int v=G[u][i];
			if (v!=father){
				dep[v]=dep[u]+1;
				dfs(v,u);
			}
		}
	}
	inline int LCA(int u,int v){
		if (u==v) return u;
		if (dep[u]<dep[v]) swap(u,v);
		for (register int i=MAXM-1;i>=0;--i){
			if (dep[anc[u][i]]>=dep[v]) u=anc[u][i];
		}
		if (u==v) return u;
		for (register int i=MAXM-1;i>=0;--i){
			if (anc[u][i]!=anc[v][i]) u=anc[u][i],v=anc[v][i];
		}
		return anc[u][0];
	}
}
using namespace L__C__A__Desu;
struct buc{//更加好用的桶
	int cnt[MAXN*2];
	inline void Init(){
		memset(cnt,0,sizeof(cnt));
	}
	int &operator [](int i){//重载运算符
		return cnt[i+MAXN];
	}
}B;
vector<int>Start[MAXN],End[MAXN],Lca[MAXN];
//以i为结束点的路线组成的集合为End[i]
//....
//....
int dist[MAXN];//编号为i的路线的长度，即dist(s[i],t[i])
int ans[MAXN],w[MAXN];
int s[MAXN],t[MAXN];
void Solve1(int u,int father){//统计上行路线的贡献
	int temp=B[w[u]+dep[u]];//原来的已经有的（要减去）
	for (register int i=0;i<G[u].size();++i){
		int v=G[u][i];
		if (v!=father) Solve1(v,u);
	}
	for (register int i=0;i<Start[u].size();++i){
		int id=Start[u][i];
		B[dep[s[id]]]++;
	}
	ans[u]+=B[w[u]+dep[u]]-temp;
	for (register int i=0;i<Lca[u].size();++i){
		int id=Lca[u][i];
		B[dep[s[id]]]--;//要减去，以后会完全包含于u的子树
	}
}
void Solve2(int u,int father){
	int temp=B[dep[u]-w[u]];
	for (register int i=0;i<G[u].size();++i){
		int v=G[u][i];
		if (v!=father) Solve2(v,u);
	}
	for (register int i=0;i<End[u].size();++i){
		int id=End[u][i];
		B[dep[t[id]]-dist[id]]++;
	}
	ans[u]+=B[dep[u]-w[u]]-temp;
	for (register int i=0;i<Lca[u].size();++i){
		int id=Lca[u][i];
		B[dep[t[id]]-dist[id]]--;
	}
}
int main(){
	int n=read(),m=read();
	for (register int i=1;i<n;++i){
		int u=read(),v=read();
		AddEdge(u,v);
		AddEdge(v,u);
	}
	for (register int i=1;i<=n;++i) w[i]=read();
	dep[1]=1;
	dfs(1,1);
	for (register int i=1;i<=m;++i){
		s[i]=read(),t[i]=read();
		int lca=LCA(s[i],t[i]);
		dist[i]=dep[s[i]]+dep[t[i]]-dep[lca]*2;
		Start[s[i]].push_back(i);
		End[t[i]].push_back(i);
		Lca[lca].push_back(i);
		if (dep[s[i]]-dep[lca]==w[lca]) ans[lca]--;//减去lca上面重复算的
	}
	B.Init(),Solve1(1,1);
	B.Init(),Solve2(1,1);
	for (register int i=1;i<=n;++i) printf("%d ",ans[i]);
}

P3958 奶酪

一开始看这道题感觉有点意思，但是发现n≤1000n\le 1000就屑了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>
#define MAXN 1005
#define ll long long
using namespace std;
struct BCJ
{
    int fa[MAXN];
    void init(int n){
        for (int i = 0; i <= n; i++){
            fa[i] = i;
        }
    }
    int find(int x){
        return (x == fa[x]) ? x : (fa[x] = find(fa[x]));
    }
    void link(int i, int j){
        fa[find(i)] = find(j);
    }
}Set;
struct point{
    ll x, y, z;
    void read(){
        scanf("%lld%lld%lld", &x, &y, &z);
    }
} p[MAXN];
ll calc(ll a, ll b)
{
    return (a - b) * (a - b);
}
ll r;
bool check(point a, point b)
{
    long double dist = sqrt(calc(a.x, b.x) + calc(a.y, b.y) + calc(a.z, b.z));
    return (dist <= (2.0 * r));
}
vector<ll> Up, Down;
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        ll n;
        ll h;
        scanf("%lld%lld%lld", &n, &h, &r);
        Set.init(n);
        Up.clear();
        Down.clear();
        for (ll i = 0; i < n; i++)
        {
            p[i].read();
            if ((p[i].z - r) <= 0)
            {
                Down.push_back(i);
            }
            if ((p[i].z + r) >= h)
            {
                Up.push_back(i);
            }
        }
        for (ll i = 0; i < n; i++)
        {
            for (ll j = i + 1; j < n; j++)
            {
                if (check(p[i], p[j]))
                {
                    Set.link(i, j);
                }
            }
        }
        bool flag = false;
        for (ll i = 0; i < Up.size(); i++)
        {
            for (ll j = 0; j < Down.size(); j++)
            {
                if (Set.find(Up[i]) == Set.find(Down[j]))
                {
                    printf("Yes\n");
                    flag = true;
                    break;
                }
            }
            if (flag)
                break;
        }
        if (!flag)
        {
            printf("No\n");
        }
    }
}

P5020 货币系统

玄学代码（NOIP时写的）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define N 5000005
#define MAXN 105
using namespace std;
inline void read(int &x){
	int f=1;
	char ch=getchar();
	while (ch<'0'||ch>'9'){
		if (ch=='-') f=-1;
		ch=getchar();
	}
	x=0;
	while (ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	x*=f;
}
int A[MAXN],vis[MAXN];
int n,lst;
int vis_sum[N];
void dfs(int i,int sum){
	if (vis_sum[sum]>lst){
		return ;
	}
	else {
		vis_sum[sum]=lst;
	}
	if (i==n+1||sum>A[n]){
		return ;
	}
	for (register int j=0;;++j){
		int v=sum+A[i]*j;
		if (v<=A[n]){
			bool flag=0;
			int templst=lst;
			if (j!=0) lst=i;
			if (A[lst]==v){flag=1;}
			if (!flag){
				int pos=lower_bound(A+1,A+1+n,v)-A;
				if (A[pos]==v){
					vis[pos]=1;
				}
			}
			dfs(i+1,v);
			lst=templst;
		}
		else{
			break;
		}
	}
}
inline int Calc(){
	memset(vis,0,sizeof(vis));
	sort(A+1,A+1+n);
	lst=0;
	memset(vis_sum,~0x3f,sizeof(vis_sum));
	dfs(1,0);
	int ans=0;
	for (register int i=1;i<=n;++i){
		ans+=(vis[i]==0);
	}
	printf("%d\n",ans);
	return 0;
}
int main(){
	freopen("money.in","r",stdin);
	freopen("money.out","w",stdout);
	int t;
	scanf("%d",&t);
	while (t--){
		scanf("%d",&n);
		for (register int i=1;i<=n;++i){
			read(A[i]);
		}
		if (n==1){
			printf("1\n");
			continue;
		}
		Calc();
	}
	return 0;
}

感觉洛谷第一个题解是在扯淡。

定义(∣A∣,A)(|A|,A)和(∣B∣,B)(|B|,B)是等价的，称为A⇔BA \Leftrightarrow B，注意到等价是相互的，具有传递性。

显然等价具有传递性，即A⇔B,B⇔CA \Leftrightarrow B,B \Leftrightarrow C 推出A⇔CA \Leftrightarrow C。

将题目给的aa数组排序，假设已经选出了jj个数b[]b[]，显然a[1...i]⇔b[1..j]a[1...i] \Leftrightarrow b[1..j]。

考虑加上一个数，使得a[1..i+1]⇔b[1...j]a[1..i+1] \Leftrightarrow b[1...j]

如果a[i+1]a[i+1]能够被b[1...j]b[1...j]表示，则跳过。

如果b[j+1]>a[i+1]b[j+1]>a[i+1]，想想就不可能，因为b[j+1]b[j+1]不可能参与到a[i+1]a[i+1]的表达中。

如果b[j+1]<a[i+1]b[j+1]<a[i+1]：

如果b[j+1]b[j+1]能够被b[1...j]b[1...j]表示，那么再来一个b[j+1]b[j+1]是没用的，而且不能表示出a[i+1]a[i+1]。

如果b[j+1]b[j+1]不能被b[1...j]b[1...j]表示，注意到等价性是相互的，g′⇔r′g' \Leftrightarrow r'，表示b[j+1]b[j+1]可以在a[1...i+1]a[1...i+1]中得到表达，而因为b[j+1]<a[i+1]b[j+1] < a[i+1]，所以a[i+1]a[i+1]不会参加b[j+1]b[j+1]的表达，说明b[j+1]b[j+1]可以在a[1....i]a[1....i]中得到表达。

但是注意到等价的传递性，b[1...j]⇔a[1...i]b[1...j] \Leftrightarrow a[1...i]，所以b[j+1]b[j+1]可以在b[1...j]b[1...j]中得到表达。

再看一下我们的假设，发生矛盾。

于是b[j+1]==a[i+1]b[j+1]==a[i+1]

我们证明了如下算法的正确性：

1
2
3
4
5
6
7
void Solve(){
    Ans={};
    sort(a);
    for (x in a){
        if (x不能被Ans中的数表达) Ans.insert(x);
    }
}

令dp[x]dp[x]表示xx能不能被表达，可以推出dpdp方程dp[j]∣=dp[j−a[i]]dp[j]|=dp[j-a[i]]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// luogu-judger-enable-o2
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 105
#define M 25005
using namespace std;
int money[N],dp[M];
int main(){
	freopen("money.in","r",stdin);
	freopen("money.out","w",stdout);
	int t;
	scanf("%d",&t);
	while (t--){
		memset(dp,0,sizeof(dp));
		int n;
		scanf("%d",&n);
		for (register int i=1;i<=n;++i){
			scanf("%d",&money[i]);
		}
		int ans=0;
		sort(money+1,money+1+n);
		dp[0]=1;
		for (register int i=1;i<=n;++i){
			if (dp[money[i]]) {
				continue;
			}
			ans++;
			for (register int j=money[i];j<=money[n];++j){//只用考虑大于当前数的
				dp[j]|=dp[j-money[i]];
			}
		}
		printf("%d\n",ans);
	}
}
相关文章
LibreOJ NOIP Round 1 DNA 序列 字符串哈希AT1219 歴史の研究AT3621 Small MultipleBZOJ 1195 [HNOI2006]最短母串基本概念

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://gaisaiyuno.github.io/archives/2f7462de.html

更新于：2022年6月14日

题解

水

评论