NOIP2018 总结

发表于

闲扯

昨年的 $NOIP$ 试题，今天又重新考了一次，结果 $D1T3,D2T1$ 全都出锅了。。。

$D1T1$

Solution

原题。

考虑贪心，如果 $val_i<=val_{i-1}$ ，那么我们一定可以在操作 $i-1$ 的时候顺带着操作掉，所要我们只需要对 $val_i>val_{i-1}$ 的加入 $val_i-val_{i-1}$ 的贡献即可。

Code

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
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define re register
#define ri re int
#define rl re ll
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define INF 0x3f3f3f3f
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
using namespace std;
template<class T>il read(T &x){
	x=0;int f=1;char k=getchar();
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=x*10+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x>9) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
int n,ans,val,now;
int main(){
	freopen("road.in","r",stdin);
	freopen("road.out","w",stdout);
	read(n),read(ans),now=ans;
	for(ri i=2;i<=n;++i){
		read(val);
		if(val>now) ans+=val-now;
		now=val;
	}
	print(ans);
	return 0;
}

$D1T2$

Solution

我们将数组排个序，然后挨个加入。

如果当前面值能被前面的表示出来，那么我们就忽略掉，否则加入最后的答案中，并且并入当前的背包。

排序是为了保证每一个数尽可能的能被前面的表示出来。

Code

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
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define re register
#define ri re int
#define rl re ll
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define INF 0x3f3f3f3f
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
using namespace std;
template<class T>il read(T &x){
	x=0;int f=1;char k=getchar();
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=x*10+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x>9) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
const int MAXN = 105;
int T,n,val[MAXN],ans;
char vis[25005];
il solve(){
	read(n),ans=0;
	for(ri i=1;i<=n;++i) read(val[i]);
	sort(val+1,val+1+n);
	for(ri i=1;i<=val[n];++i) vis[i]=0;
	for(ri i=1;i<=n;++i){
		if(vis[val[i]]) continue;
		for(ri j=0;j+val[i]<=val[n];++j)
			if(vis[j])
				vis[j+val[i]]=1;
		++ans;
	}
	print(ans),puts("");
}
int main(){
	freopen("money.in","r",stdin);
	freopen("money.out","w",stdout);
	read(T),vis[0]=1;
	for(ri i=1;i<=T;++i) solve();
	return 0;
}

$D1T3$

Solution

求最小的最大，考虑二分答案。

左边界为 $0$ ，右边界不能直接选择将所有的边权加上，而是选择树的直径或者是 $\frac{sum}{k}$ 。

考虑怎么判断合法。

发现每个子树只能传一条边上去，我们把所有能单独成立的边和能配对边删去后，传一个最大值上去即可。

注意配对要在所有的子树都遍历之后，最后来计算，每次找最小的满足条件的即可。

Code

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
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define re register
#define ri re int
#define rl re ll
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define INF 0x3f3f3f3f
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
using namespace std;
template<class T>il read(T &x){
	x=0;int f=1;char k=getchar();
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=x*10+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x>9) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
const int MAXN = 5e4+5;
int n,m,u,v,w,head[MAXN],num_edge,sum,dis[MAXN],l,r;
struct Edge{
	int next,to,dis;
	Edge(){}
	Edge(int next,int to,int dis):next(next),to(to),dis(dis){}
}edge[MAXN<<1];
il add_edge(int u,int v,int dis){
	edge[++num_edge]=Edge(head[u],v,dis),head[u]=num_edge;
	edge[++num_edge]=Edge(head[v],u,dis),head[v]=num_edge;
}
multiset<int> s[MAXN];
multiset<int>::iterator ite;
it DFS(int u,int fa,int lim){
	s[u].clear();
	for(ri i=head[u];i;i=edge[i].next){
		if(edge[i].to==fa) continue;
		ri k=DFS(edge[i].to,u,lim)+edge[i].dis;
		if(k>=lim) ++sum;
		else s[u].insert(k);
	}
	ri mx=0;
	while(!s[u].empty()){
		if(s[u].size()==1) return max(mx,*s[u].begin());
		ite=s[u].lower_bound(lim-*s[u].begin());
		if(ite==s[u].begin()&&s[u].count(*s[u].begin())==1) ite++;
		if(ite==s[u].end()) mx=max(mx,*s[u].begin()),s[u].erase(*s[u].begin());
		else sum++,s[u].erase(ite),s[u].erase(s[u].begin());
	}
	return mx;
}
it chk(int lim){
	sum=0;
	DFS(1,0,lim);
	return sum>=m;
}
int main(){
	freopen("track.in","r",stdin);
	freopen("track.out","w",stdout);
	read(n),read(m);
	for(ri i=1;i<n;++i){
		read(u),read(v),read(w);
		add_edge(u,v,w),r+=w;
	}
	r/=m;
	while(l<r){
		if(chk(mid+1)) l=mid+1;
		else r=mid;
	}
	print(l);
	return 0;
}

$D2T1$

对于 $m=n-1$ 的情况，我们直接贪心的走即可。

对于 $m=n$ 的情况，我们有两种做法。

  1. 因为数据范围小，所以我们直接 $O(n^2)$ 枚举删掉那条边，然后找一个最小的答案即可。
  2. 存在环的情况可以对环上的点有一次反悔的机会，所以我们讨论一下，看是否需要，什么时候反悔即可。

Code

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
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define re register
#define ri re int
#define rl re ll
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define INF 0x3f3f3f3f
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
using namespace std;
template<class T>il read(T &x){
	x=0;int f=1;char k=getchar();
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=x*10+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x>9) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
const int MAXN = 5e3+5;
int n,m,u,v,ans[MAXN],cnt,fla,pos;
char vis[MAXN],ring[MAXN];
vector<int> G[MAXN];
il DFS(int u,int fa){
	ans[++cnt]=u;
	for(ri i=0;i<(int)G[u].size();++i){
		if(G[u][i]==fa) continue;
		DFS(G[u][i],u);
	}
}
int dep[MAXN];
il DFS1(int u,int fa){
	dep[u]=dep[fa]+1;
	for(ri i=0;i<(int)G[u].size();++i){
		if(fla||G[u][i]==fa) continue;
		if(dep[G[u][i]]&&dep[G[u][i]]<dep[u]) fla=1,pos=G[u][i];
		if(!fla) DFS1(G[u][i],u);
		if(fla&&dep[u]>=dep[pos]) ring[u]=1;
	}
}
il DFS2(int u){
	ans[++cnt]=u,vis[u]=1;
	if(!ring[u]){
		for(ri i=0;i<(int)G[u].size();++i){
			if(vis[G[u][i]]) continue;
			DFS2(G[u][i]);
		}
	}
	else{
		ri flag=0;
		for(ri i=0;i<(int)G[u].size();++i){
			if(fla) break;
			if(vis[G[u][i]]) continue;
			if(ring[G[u][i]]){
				ri j=i+1;
				while(j<(int)G[u].size()&&vis[G[u][j]]) ++j;
				if(j<(int)G[u].size()) pos=G[u][j];
				else if(G[u][i]>pos) fla=1,flag=1;
				break;
			}
		}
		for(ri i=0;i<(int)G[u].size();++i){
			if(vis[G[u][i]]) continue;
			if(ring[G[u][i]]&&flag) continue;
			DFS2(G[u][i]);
		}
	}
}
int main(){
	freopen("travel.in","r",stdin);
	freopen("travel.out","w",stdout);
	read(n),read(m);
	for(ri i=1;i<=m;++i) read(u),read(v),G[u].push_back(v),G[v].push_back(u);
	for(ri i=1;i<=n;++i) sort(G[i].begin(),G[i].end());
	if(n-1==m) DFS(1,0);
	else DFS1(1,0),fla=0,pos=INF,DFS2(1);
	for(ri i=1;i<=n;++i) printf("%d ",ans[i]);
	return 0;
}

$D2T2$

打表，找到了 $n=2$ 的规律，然后走人，拿到了 $50pts$ 的好成绩。

Code

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
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define re register
#define ri re int
#define rl re ll
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define INF 0x3f3f3f3f
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
using namespace std;
template<class T>il read(T &x){
	x=0;int f=1;char k=getchar();
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=x*10+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x>9) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
it qpow(int x,int m,int mod){
	ri res=1,bas=x;
	while(m){
		if(m&1) res=1ll*res*bas%mod;
		bas=1ll*bas*bas%mod,m>>=1;
	}
	return res;
}
const int mod = 1e9+7;
int n,m,ans,val[5][5];
it mul(int x,int y){return 1ll*x*y%mod;}
it add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
int main(){
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	read(n),read(m);
	if(n==3&&m==3) return print(112),0;
	if(n==1) return print(qpow(2,m,mod)),0;
	if(n==2) return print(mul(4,qpow(3,m-1,mod))),0;
	if(m==1) return print(qpow(2,n,mod)),0;
	if(m==2) return print(mul(4,qpow(3,n-1,mod))),0;
	return 0;
}

Solution

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
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define re register
#define ri re int
#define rl re ll
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define INF 0x3f3f3f3f
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
using namespace std;
template<class T>il read(T &x){
	x=0;int f=1;char k=getchar();
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=x*10+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x>9) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
it qpow(int x,int m,int mod){
	ri res=1,bas=x;
	while(m){
		if(m&1) res=1ll*res*bas%mod;
		bas=1ll*bas*bas%mod,m>>=1;
	}
	return res;
}
const int mod = 1e9+7;
int n,m,ans,val[5][5];
it mul(int x,int y){return 1ll*x*y%mod;}
it add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
int main(){
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	read(n),read(m);
	if(n==3&&m==3) return print(112),0;
	if(n==1) return print(qpow(2,m,mod)),0;
	if(n==2) return print(mul(4,qpow(3,m-1,mod))),0;
	if(m==1) return print(qpow(2,n,mod)),0;
	if(m==2) return print(mul(4,qpow(3,n-1,mod))),0;
	return 0;
}

$D2T3$

Solution

有一种 $n\log n$ 的倍增做法，不过没看懂（没看），所以学了一下动态 $DP$ ，然后就可以直接上模板了。

我们有最小权覆盖集 $=$ 全集 $-$ 最大权独立集。

所以我们按照模板题只需要求出最大权独立集，然后减一下即可。

对于强制要求选的点，我们将权值加上 $-INF$ ，这样最大权独立集一定不会选这个点；同理，我们将强制要求不选的点权值加上 $INF$ ，这样最大权独立集一定会选它。

不过直接先树剖的复杂度是 $O(n\log^2n)$ ，可能会被卡常。

可以用全局平衡二叉树或者 $LCT$ 优化成 $O(n\log n)$ ，但是这两个都还没学过，就暂时不管了。

Code

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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res;
}
const ll INF = 1e11;
const int MAXN = 1e5+5;
int n,m,val[MAXN],u,v,x,y,head[MAXN],num_edge;
ll dp[MAXN][2],sum;
char s[3];
struct Edge{
	int next,to;
	Edge(){}
	Edge(int next,int to):next(next),to(to){}
}edge[MAXN<<1];
il add_edge(int u,int v){
	edge[++num_edge]=Edge(head[u],v),head[u]=num_edge;
	edge[++num_edge]=Edge(head[v],u),head[v]=num_edge;
}
ill max1(ll x,ll y){return x>y?x:y;}
it max(int x,int y){return x>y?x:y;}
struct Matrix{
	ll val[2][2];
	Matrix(){for(ri i=0;i<2;++i)for(ri j=0;j<2;++j)val[i][j]=-INF;}
	ll *operator [](int x){return val[x];}
	Matrix operator * (Matrix t){
		Matrix res;
		for(ri i=0;i<2;++i)
			for(ri k=0;k<2;++k)
				for(ri j=0;j<2;++j)
					res[i][j]=max1(res[i][j],val[i][k]+t[k][j]);
		return res;
	}
}Val[MAXN];
int f[MAXN],son[MAXN],sz[MAXN],top[MAXN],ed[MAXN],id[MAXN],rk[MAXN],cnt;
il DFS1(int u,int fa){
	f[u]=fa,sz[u]=1;
	for(ri i=head[u];i;i=edge[i].next){
		ri v=edge[i].to;
		if(v==fa) continue;
		DFS1(v,u),sz[u]+=sz[v];
		if(sz[v]>sz[son[u]]) son[u]=v;
	}
}
il DFS2(int u,int t){
	top[u]=t,id[u]=++cnt,rk[cnt]=u,ed[t]=max(ed[t],id[u]);
	dp[u][0]=0,dp[u][1]=val[u];
	Val[u][0][0]=Val[u][0][1]=0;
	Val[u][1][0]=val[u];
	if(!son[u]) return ;
	DFS2(son[u],t);
	dp[u][0]+=max1(dp[son[u]][0],dp[son[u]][1]);
	dp[u][1]+=dp[son[u]][0];
	for(ri i=head[u];i;i=edge[i].next){
		ri v=edge[i].to;
		if(v==f[u]||v==son[u]) continue;
		DFS2(v,v);
		dp[u][0]+=max1(dp[v][0],dp[v][1]);
		dp[u][1]+=dp[v][0];
		Val[u][0][0]+=max1(dp[v][0],dp[v][1]);
		Val[u][0][1]=Val[u][0][0];
		Val[u][1][0]+=dp[v][0];
	}
}
#define lc (cur<<1)
#define rc (cur<<1|1)
struct Seg_Tree{
	Matrix val;
}T[MAXN<<2];
il pushup(int cur){T[cur].val=T[lc].val*T[rc].val;}
il build_tree(int cur,int l,int r){
	if(l==r) return T[cur].val=Val[rk[l]],void();
	build_tree(lc,l,mid),build_tree(rc,mid+1,r);
	pushup(cur);
}
il updata(int cur,int l,int r,int pos){
	if(l==r) return T[cur].val=Val[rk[l]],void();
	if(mid>=pos) updata(lc,l,mid,pos);
	else updata(rc,mid+1,r,pos);
	pushup(cur);
}
inl Matrix query(int cur,int l,int r,int L,int R){
	if(l==L&&r==R) return T[cur].val;
	if(mid>=R) return query(lc,l,mid,L,R);
	else if(L>mid) return query(rc,mid+1,r,L,R);
	else return query(lc,l,mid,L,mid)*query(rc,mid+1,r,mid+1,R);
}
il updata_path(int u,ll w){
	Val[u][1][0]+=w;
	Matrix bef,aft;
	while(u){
		bef=query(1,1,n,id[top[u]],ed[top[u]]);
		updata(1,1,n,id[u]);
		aft=query(1,1,n,id[top[u]],ed[top[u]]);
		u=f[top[u]];
		Val[u][0][0]+=max1(aft[0][0],aft[1][0])-max1(bef[0][0],bef[1][0]);
		Val[u][0][1]=Val[u][0][0];
		Val[u][1][0]+=aft[0][0]-bef[0][0];
	}
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(n),read(m),scanf("%s",s);
	for(ri i=1;i<=n;++i) read(val[i]),sum+=val[i];
	for(ri i=1;i<n;++i) read(u),read(v),add_edge(u,v);
	DFS1(1,0),DFS2(1,1),build_tree(1,1,n);
	for(ri i=1;i<=m;++i){
		read(u),read(x),read(v),read(y);
		if(!(x+y)&&(f[u]==v||f[v]==u)){
			puts("-1");
			continue;
		}
		updata_path(u,x?-INF:INF),updata_path(v,y?-INF:INF);
		Matrix ans=query(1,1,n,id[1],ed[1]);
		rl res=max1(ans[0][0],ans[1][0]);
		res+=x?0:-INF,res+=y?0:-INF;
		print(sum-res),puts("");
		updata_path(u,x?INF:-INF),updata_path(v,y?INF:-INF);
	}
	return 0;
}