7.5 模拟赛

, ,

Day 2

T1. script

Description

$n\le 10^5$

1s , 512MB

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
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 200005
#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;
int fa[maxn],n,las[maxn];
vector<int>to[maxn];
int ans=1;
inline int dfs(int x) {
	if (to[x].size()==0) return 1;
	int max=0,nums=0;
	for (auto y:to[x]) {
		int tmp=dfs(y);
		if (tmp>max) max=tmp,nums=1;
		else if (tmp==max) nums++;
	}
	return max+(nums>1);
}
inline void solve(void) {
	int i;ans=1;
	read(n);
	for (i=1;i<=n;i++) to[i].clear();
	for (i=1;i<=n;i++) read(fa[i]),to[fa[i]].push_back(i);
	printf("%d\n",dfs(1));
}
signed main(void){
 	freopen("script.in","r",stdin);
	freopen("script.out","w",stdout);
	int T;
	read(T);
	while (T--) solve();
	return 0;
}

T2. deletion

Description

Natsuzora 有一个长度为 $n$ 的排列 $a$。他想要将序列中的 $m$ 个数删除。

魔法工具也有 $m$ 种，其中，第 $i$ 种魔法工具能够将排列中任意一个的长度为 $l_i$ 的区间中最大的数删除。每个魔法工具最多只能使用 $1$ 次。

每次删除操作后，序列的长度将减少 $1$，且删去的数的右边所有数的下标减少 $1$。

$n\le 2\times 10^5$

1s , 512MB

Solution

$l_i$ 更大的要越先用掉。如果一个数包含另外一个数，则这个数比另外一个数更先用掉。

两个单调栈维护一下即可。

我写的是 $n^2$ 暴力过去了，就不贴了。

T3. candy

Description

P8746 [蓝桥杯 2021 省 A] 分果果

Solution

外面枚举最小值 $minn$ ，考虑求最大值。

一个显然的性质是任意两个人取糖果的区间不包含。考虑两个区间 $l1<l2<r2<r1$，如果换为 $[l1,r2],[l2,r1]$ 这样的极差显然更小。

令 $f[i][j][k]$ 表示，第 $i$ 个区间，上一个取一颗糖果的位置为 $j$ ，上一个取两颗糖果的位置为 $k$。$j\ge k$。最大值最小为 $f[i][j][k]$。

  • 两颗糖果的位置不取，$f[i][j][k]\Leftarrow f[i][j][l-1]$ ，这也说明 $f[i][j][k]$ 关于 $k$ 单调递减。
  • 在 $t\le k$ 取，$f[i][j][k]\Leftarrow \max(f[i-1][k][t],s[j]-s[t])$ 把 $\max$ 中的两项当作两个关于 $t$ 的函数，可以发现两者都关于 $t$ 递减。所以取 $t$ 最大的即可。但是注意要满足 $s[j]-s[t]\ge minn$
  • 在 $k+1\le t\le j$ 之间取。这在之后会在第二种情况算到，所以可以不需要转移。因为转移两次的一定小于等于转移一次。如果转移两次的继续取，等到大于转移一次的位置，转移一次的位置就成了转移两次的。

这样只需要一个指针维护即可。$dp$ 的复杂度为 $n^2\times m$

外面枚举的最小值复杂度是 $O(\dfrac{sum}{m})$ ，具体的，枚举的上界是 $\dfrac{2nw}{m}$

总的复杂度就是 $O(n^3w)$

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
#include<bits/stdc++.h>
using namespace std;
int m,n,w[105],base;
int f[55][105][105];
int stac[106],tot,ans=1e9; 
inline void solve(int minn) {
	int i,j,k,pp,p;
	memset(f,0x3f,sizeof(f));
	f[0][0][0]=minn;
	for (i=1;i<=m;i++) {
		for (k=0;k<=n;k++) {
			p=tot=0;
			for (j=k;j<=n;j++) {
				if (k>0) f[i][j][k]=min(f[i][j][k],f[i][j][k-1]);
				while (w[j]-w[p]>=minn) p++;
				if ((pp=min(p-1,k))>=0) f[i][j][k]=min(f[i][j][k],max(f[i-1][k][pp],w[j]-w[pp]));
			}
		}
	}
	ans=min(ans,f[m][n][n]-minn);
}
signed main(void){
  	freopen("candy.in","r",stdin);
  	freopen("candy.out","w",stdout);
	int i;
	cin>>n>>m;
	for (i=1;i<=n;i++) cin>>w[i],w[i]+=w[i-1];
	base=w[n]*2/m;
	for (i=1;i<=base;i++) solve(i);
	printf("%d",ans);
	return 0;
}

T4. twotypes

Description

给你一张 $n$ 个点、$m$ 条边的有向无环图，图中的每条边有黑和白两种颜色。保证从 $1$ 号点出发可以到达任意一点。
共有 $q$ 次询问，在第 $i$ 次询问中，给定 $a_i$、$b_i$ 和 $x_i$，表示设黑边边权为 $a_i$，白边边权为 $b_i$，在这种条件下，请你求出从 $1$ 到 $x_i$ 的最短路径。

$n,q\le 5\times 10^4,m\le 1\times 10^5$

1s , 1024MB

Solution

考虑一个点对答案可能有贡献的路径，用黑边条数和白边条数 $(x,y)$ 。目标 $\min Ax+By$，令 $Ax+By=k$，化为 $y=-\dfrac{A}{B}x+\dfrac{k}{B}$ 。根据几何意义，即在原图中的下 $\dfrac{1}{4}$ 的凸包上。可以证明，值域在 $n$ 的点构成的凸包的最大点数为 $O(n^{2/3})$ 级别的。实际上这个上界很松。

具体维护凸包。每次凸包合并。由于这个图是 DAG，合并的次数最多只有 $m$ 次。

查询的时候没必要二分。直接扫过去。

总复杂度 $O((m+q)n^{2/3})$

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
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 50005
#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;
struct node{
	int x,y;
	node(int a=0,int b=0) {x=a;y=b;}
	node operator +(const int &z) const{
		if (z==0) return node(x+1,y);
		else return node(x,y+1);
	}
};
vector<node>g[maxn];
node O[maxn];
int head=1,h[maxn],n,m;
struct yyy{
	int to,z,w;
	inline void add(int x,int y,int val) {
		to=y,z=h[x],h[x]=head;w=val;
	}
}a[maxn*2];
int in[maxn];
queue<int>q;
inline double slope(node x,node y) {return 1.0*(y.y-x.y)/(y.x-x.x);}
inline void merge(int y,int x,int z) {
	int i,tot=0;
	int l1=g[x].size(),l2=g[y].size(),cnt1=0,cnt2=0;
	while (cnt1<l1&&cnt2<l2) {
		node tmp1=g[x][cnt1]+z,tmp2=g[y][cnt2];
		if (tmp1.x==tmp2.x) {
			if (tmp1.y<tmp2.y) cnt2++;
			else cnt1++;
			continue;
		}
		if (tmp1.x<tmp2.x) {
			while (tot>=2&&(slope(O[tot-1],O[tot])>=slope(O[tot],tmp1))) tot--;
			O[++tot]=tmp1;cnt1++;
		}
		else {
			while (tot>=2&&(slope(O[tot-1],O[tot])>=slope(O[tot],tmp2))) tot--;
			O[++tot]=tmp2;cnt2++;
		}
	}
	while (cnt1<l1) {
		node tmp1=g[x][cnt1]+z;
		while (tot>=2&&(slope(O[tot-1],O[tot])>=slope(O[tot],tmp1))) tot--;
		O[++tot]=tmp1;cnt1++;
	}
	while (cnt2<l2) {
		node tmp2=g[y][cnt2];
		while (tot>=2&&(slope(O[tot-1],O[tot])>=slope(O[tot],tmp2))) tot--;
		O[++tot]=tmp2;cnt2++;
	}
//	vector<node>().swap(g[y]); 
	g[y].clear(); 
//	assert(tot<=2000);
	for (i=1;i<=tot;i++) g[y].push_back(O[i]); 
}
inline void topo(void) {
	int i,x;
	q.push(1);g[1].push_back(node(0,0)); 
	while (!q.empty()) {
		x=q.front();q.pop();
		for (i=h[x];i;i=a[i].z) {
			merge(a[i].to,x,a[i].w);
			if (!--in[a[i].to]) q.push(a[i].to);
		}
	}
}
signed main(void){
//  freopen("2.in","r",stdin);
  	freopen("twotypes.in","r",stdin);
  	freopen("twotypes.out","w",stdout);
	int i,x,y,z;
	read(n);read(m);
	for (i=1;i<=m;i++) {
		read(x),read(y),read(z);
		++in[y];a[++head].add(x,y,z);
	}
	topo();
	int tmp1,tmp2,q;
	read(q); 
	while (q--) {
		read(tmp1),read(tmp2),read(x);
		int ans=1e9;
		for (auto tmp:g[x]) ans=min(ans,tmp1*tmp.x+tmp2*tmp.y);
		printf("%d\n",ans);
	}
	return 0;
}