NOIP模拟赛 11.05 by FXT and ZJ

, , , , ,

前言

感觉这场全力打了三个小时，T4 的暴力没想出来有点可惜，然后 T3 确实难，但是自己数组开小也很 dinner 啊。

T1

Description

image-20231105193748922

$n\le 2000$。

Solution

很典的树上背包啊。记录 $x$ 子树内产生贡献的点个数 $j$，$x$ 的状态：没被选也没有产生贡献，没被选但是被儿子产生贡献，选了。然后转移一下就好了。

复杂度 $O(n^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
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 2005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    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();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
const int mod=1e9+7;
void add(int &x,int y) {x=(x+y)%mod;}
int n,siz[maxn],f[maxn][maxn][3],g[maxn][3];
vector<int>to[maxn];
void dfs(int x,int pre) {
	int i,j;siz[x]=1;f[x][0][0]=1,f[x][1][2]=1;
	for (auto y:to[x]) if (y^pre) {
		dfs(y,x);
		for (i=0;i<=siz[x];i++) {
			for (j=0;j<3;j++) g[i][j]=f[x][i][j],f[x][i][j]=0;
		}
		for (i=0;i<=siz[x];i++) {
			for (j=0;j<=siz[y];j++) {
				add(f[x][i+j][0],g[i][0]*(f[y][j][0]+f[y][j][1]));
				add(f[x][i+j+1][1],g[i][0]*f[y][j][2]);
				add(f[x][i+j][1],g[i][1]*(f[y][j][0]+f[y][j][1]+f[y][j][2]));
				add(f[x][i+j][2],g[i][2]*(f[y][j][1]+f[y][j][2]));
				add(f[x][i+j+1][2],g[i][2]*f[y][j][0]);
			}
		}
		siz[x]+=siz[y];
	}
}
signed main(void){
	int i,x,y;
	read(n);
	for (i=1;i<n;i++) {
		read(x),read(y);
		to[x].push_back(y);
		to[y].push_back(x);
	}
	dfs(1,0);
	for (i=0;i<=n;i++) printf("%lld\n",(f[1][i][0]+f[1][i][1]+f[1][i][2])%mod);
	return 0;
}

T2

Description

https://qoj.ac/contest/1322/problem/7077

image-20231105193957676

Solution

这种仙人掌屌题一般从链，树，基环树一步步考虑过去。

链式平凡的。树就是经典算一条边的贡献。

如果有环的话发现就是经典 分金币，只不过带权了，所以求带权中位数就好了。

先要仙人掌转圆方树，然后对每个环计算一下就好了。

赛时 $O(n^2)$ 冲过去了。/cf

复杂度 $O(n\log n)/O(n)$，看具体对中位数的实现。

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
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 200005
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
    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();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int n,m,k,siz[maxn];
int dfn[maxn],low[maxn],tot,vis[maxn],cnt,times;
pair<int,int>stac[maxn];
int h[maxn],head=1;
struct yyy {
	int to,z,w;
	void add(int x,int y,int val) {
		to=y;z=h[x];h[x]=head;w=val;
	}
}a[maxn*2];
vector<pair<int,int> >to[maxn];
void add(int x,int y,int w) {
//	gdb(x,y,w);
	to[x].push_back(mk(y,w));
	to[y].push_back(mk(x,w));
}
void tarjan(int x,int pre,int pw) {
	int i,j;
	low[x]=dfn[x]=++times,stac[++tot]=mk(x,pw),vis[x]=1;
	for (i=h[x];i;i=a[i].z) if ((i^1)^pre) {
		if (!dfn[a[i].to]) {
			tarjan(a[i].to,i,a[i].w),low[x]=min(low[x],low[a[i].to]);
			int y=a[i].to;
			if (low[y]>=dfn[x]) {
				++cnt;
				int u=stac[tot].fi;
				while (1) {
					add(cnt,stac[tot].fi,stac[tot].se);
					vis[stac[tot].fi]=0;
					if (stac[tot--].fi==a[i].to) break;
				}
				int res=0;
				for (j=h[u];j;j=a[j].z) {
//					gdb(u,x,a[j].to,h[u],a[h[u]].to);
					if (a[j].to==x) res=a[j].w;
				}
				add(cnt,x,res);
//				gdb(x,u,a[i].to,res);
			}
		}
		else if (vis[a[i].to]) {
			low[x]=min(low[x],dfn[a[i].to]);
		}
	}
}
int ans;
void dfs(int x,int pre) {
	for (auto y:to[x]) if (y.fi^pre) 
		dfs(y.fi,x),siz[x]+=siz[y.fi];
}
int id[maxn],s[maxn];
pair<int,int>r[maxn];
const int inf=1e14;
void calc(int x,int pre) {
	int i,j,res=0;
	tot=0;
	for (auto tmp:to[x]) {
		id[++tot]=tmp.se;
		s[tot]=(tmp.fi==pre?-siz[x]:siz[tmp.fi]);
	}
	for (i=1;i<=tot;i++) id[i+tot]=id[i],s[i+tot]=s[i];
	int tmp=0,sum=0;
	for (i=1;i<=tot;i++) r[i]=mk(r[i-1].fi+s[i],id[i]),tmp+=id[i];
	tmp=(tmp+1)/2;
	sort(r+1,r+1+tot);
	for (i=1;i<=tot;i++) 
		if (r[i].se<tmp) tmp-=r[i].se;
		else {res=r[i].fi;break;}
	for (i=1;i<=tot;i++) sum+=r[i].se*abs(res-r[i].fi);
	ans+=sum;//带权中位数
//	int sum=inf;
//	for (i=1;i<=tot;i++) {
//		int res=0,nums=0;
//		for (j=i;j<i+tot;j++) {
//			nums+=s[j];
//			res+=abs(nums)*id[j];
//		}
//		sum=min(sum,res);
//	}
//	ans+=sum;//赛时n^2
}
void dfs2(int x,int pre) {
	for (auto tmp:to[x]) if (tmp.fi^pre) {
		int y=tmp.fi;
		dfs2(y,x);
		if (x<=n&&y<=n) ans+=abs(siz[y])*tmp.se;
	}
	if (x>n) {
		calc(x,pre);
	} 
}
map<pair<int,int> ,int>mp;
signed main(void){
	int i,x,y,z;
	read(n);read(m);read(k);cnt=n;
	for (i=1;i<=k;i++) read(x),siz[x]++;
	for (i=1;i<=k;i++) read(x),siz[x]--;
	for (i=1;i<=m;i++) {
		read(x),read(y),read(z);
		if (x>y) swap(x,y);
		if (!mp[mk(x,y)]) mp[mk(x,y)]=z;
		else mp[mk(x,y)]=min(mp[mk(x,y)],z);
	} 
	for (auto tmp:mp) {
		a[++head].add(tmp.fi.fi,tmp.fi.se,tmp.se);
		a[++head].add(tmp.fi.se,tmp.fi.fi,tmp.se);
	}
	for (i=1;i<=n;i++) if (!dfn[i]) tarjan(i,0,0);
	dfs(1,0);
	dfs2(1,0);
	printf("%lld",ans);
	return 0;
}

T3

Description

https://qoj.ac/contest/1237/problem/6545

Solution

这题的部分分非常有启发性啊，良心搬题人。

我会 $O(n^3)$！考虑令 $f(l,r)$ 为区间 $l,r$ 内的最大值，转移就从 $\max\limits_{k=i}^j f(l,k)+f(k,r)$ 转移一下，记录一下转移位置即可。

我还会所有数互不相同！答案是 $2n-3$。

但是搬题人很坏啊，$O(n^3)$ 对答案没有一点启发性。

考虑转化题目，先把 $(i,i+1)$ 能连就连，然后依次删除 $[2,n-1]$ ，删除 $i$ 的时候检验 $(i-1,i+1)$ 是否可以连边。直到最后剩下两个点。容易发现这样可以构造出任意方案。也说明上界是 $2n-3$。

然后观察 $a_i$ 随机的性质，也就是说有很大的概率会出现整个序列中只有单独一个的 $a_i$，只需要找到他，然后把他向左删，向右删，每次删都会增加一条边，最后剩下三个点的时候检验一下第一个和第三个能否删掉第二个的情况。因为每次都能增加一条边，所以一定最优。

但是还有不单独一个 $a_i$ 的情况。我们考虑先删可以使 $(i-1,i+1)$ 连边的点，删到出现这样单独一个的 $a_i$ 情况为止，容易发现如果颜色数 $\ge 3$ ，这样是肯定有解的。

如果颜色 $=2$，删到没的删的情况而且找不到单独的 $a_i$，最后的形式一定是 $1,2,1,2,\dots,2,1$ 这样，发现删两个会多 $1$ 的连边，随便搞搞就好了。

这题的关键就在于转化题目，把连边除端点相交的情况转化为删点，感觉很妙啊。

维护可以删的点需要的操作有加点，删点，查询这个数在不在集合中，查询集合中的任意一个点。数据结构学傻的可以用 set，没学傻的可以用栈。删除用链表即可。复杂度 $O(n\log n)/O(n)$

下面是数据结构学傻的人的代码：

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
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 200005
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
    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();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int n,m,a[maxn];
int pre[maxn],nex[maxn];
int cnt,vis[maxn];
pair<int,int>ans[maxn*2];
set<int>t;
int del(int x) {
//	gdb(x,pre[x],nex[x],a[pre[x]],a[nex[x]],cnt);
	if (pre[x]&&nex[x]<=n) {
		if (a[pre[x]]!=a[nex[x]]) 
			ans[++cnt]=mk(pre[x],nex[x]);
	} 
	vis[a[x]]--;
	int tmp1=pre[x],tmp2=nex[x];
//	gdb(x,tmp1,tmp2);
//	assert(tmp1&&tmp2<=n);
//	gdb(x,tmp1,tmp2);
	if (tmp1) {
		int fl1=0;
		auto it=t.lower_bound(tmp1);
		if (it!=t.end()&&(*it)==tmp1) fl1=1;
		if (a[tmp2]!=a[pre[tmp1]]&&!fl1&&pre[tmp1]) t.insert(tmp1);
		if (a[tmp2]==a[pre[tmp1]]&&fl1&&pre[tmp1])  t.erase(tmp1);
	}
	if (tmp2<=n) {
		int fl2=0;
		auto it=t.lower_bound(tmp2);
		if (it!=t.end()&&(*it)==tmp2) fl2=1;
		if (a[tmp1]!=a[nex[tmp2]]&&!fl2&&nex[tmp2]<=n) t.insert(tmp2);
		if (a[tmp1]==a[nex[tmp2]]&&fl2&&nex[tmp2]<=n)  t.erase(tmp2);  
	}		
	nex[pre[x]]=nex[x];
	pre[nex[x]]=pre[x];
	return vis[a[x]]==1;
}
int id[maxn],tot;
void calc(void) {
	int i;
	while (!t.empty()) {
		auto tmp=*t.begin();t.erase(tmp);
		del(tmp);
	}
	tot=0;
	int now=nex[0];
//	gdb(now,nex[now]);
	while (nex[now]<=n) id[++tot]=now,now=nex[now];
//	for (i=1;i<=tot;i++) gdb(i,id[i]);
	for (i=2;i<=tot;i++) del(id[i]);
	for (printf("%d\n",cnt),i=1;i<=cnt;i++) printf("%d %d\n",ans[i].fi,ans[i].se);
}
void print(int x) {
	int now=pre[x],i;
//	gdb(now,x);
	while (pre[now]) del(now),now=pre[now];
	now=nex[x];
	while (nex[now]<=n) del(now),now=nex[now];
	if (a[pre[x]]!=a[nex[x]]&&pre[x]&&nex[x]<=n) ans[++cnt]=mk(pre[x],nex[x]);
	for (printf("%d\n",cnt),i=1;i<=cnt;i++) printf("%d %d\n",ans[i].fi,ans[i].se);
}
void solve(void) {
	int i,nums=0;cnt=0;
	read(n);read(m);
	for (i=1;i<=m;i++) vis[i]=0;t.clear();
	for (i=1;i<=n;i++) read(a[i]),vis[a[i]]++,nums+=(vis[a[i]]==1);
	for (i=1;i<=n;i++) nex[i]=i+1,pre[i]=i-1;
	nex[0]=1;nex[n+1]=n+1;pre[n+1]=n;a[n+1]=m+1;
	for (i=1;i<n;i++) if (a[i]!=a[i+1]) ans[++cnt]=mk(i,i+1);
	for (i=2;i<n;i++) if (a[i-1]!=a[i+1]) t.insert(i);
//	gdb(nums);
	if (nums<=2) return calc(),void();
	int flag=0;
	for (i=1;i<=n;i++) if (vis[a[i]]==1) {flag=i;break;}
//	gdb(flag);
	if (flag) return print(flag),void();
	while (!t.empty()) {
		auto tmp=*t.begin();t.erase(tmp);
		flag=del(tmp);
		if (flag) {
			int now=nex[0];
			while (nex[now]<=n) {
				if (a[tmp]==a[now]) return print(now),void();
				now=nex[now];
			}
		}
	}
}
signed main(void){
	int T;
	read(T);
	while (T--) solve();
	return 0;
}

T4

http://211.140.156.254:2333/problem/95

太高妙了，有空再补。