前行 - USACO2017 Dec | Lucky_Glass's Blog

以心为名，名为爱惜

0%

前行 - USACO2017 Dec

发表于 更新于 分类于 Valine：

为了让我们恢复正常学习的状态，教练把金组的题拉给我们做了一下……（$3$道题，不知道全不全）
当一个小测试，还是挺简单的（相较而言）

总的来说思维难度不高，只是A题写起来有点困难……

『A : A Pie for a Pie』 〔传送门〕

「题目」

两只牛，牛A和牛B，他们对水果派的品味不同，每个人都有 $n(n\leq 10^5)​$ 个派，每个派都有两种得分 $a_i,b_i​$，其中 $a_i​$ 是牛A对该派的评分，$b_i​$ 是牛B的评分 $(0 \leq a_i, b_i \leq 10^9)​$。
两只牛开始礼尚往来，从牛A开始，它选一个派 $i​$ 给牛B，设这个派的评分是 $(a_i, b_i)​$。此时牛B为了不失礼节，要选出一个派 $j​$ 满足 $b_j \in [b_i, b_i+d]​$ 给A。同理，A又要选出一个派 $k​$ 满足 $ a_k\in [a_j, a_j+d]​$ 给B，如此往复。每个派都只能传递一次。如果A收到了一个A评分为 $0​$ 的派，或者B收到了一个B评分为 $0​$ 的派，那么礼尚往来就愉快的结束了。否则，就不愉快结束（即一个人无法选出合法的派给对方时）。
下面让你输出，对于A的每一个派，如果第一轮A把这个派交给B，礼尚往来最少可以几轮愉快结束？如果无法愉快结束，就输出 $-1​$。

「解析」

由于我们要让牛A从每一个派开始都做一遍……这样的话“起点”就太多了。但是我们知道最后结束要么是 A 给了一个B评分为 $0$ 的派，要么是 B 给了一个A评分为 $0$ 的派。
所以想到如果设 $ans[i][0]$ 和 $ans[i][1]$ 分别表示：从A给出第 $i$ 个派开始的答案和从B给出第 $i$ 个派开始的答案，就可以从“终点”出发得到 $ans$ 。

大致思路是：
① 将 A 的派 和 B的派 分别看成 二分图 的两个部；
② 根据题目要求：

如果 A的派$i$ 和 B的派$j$ 满足 $b_j\in[b_i,b_i+d]$ ，则将 $i$ 到 $j$ 连长度为 $1$ 的有向边；
B的派同理……
此时从 $i$ 到 $j$ 的边的含义为“如果一头牛给出它的第 $i$ 个派，另一头牛可以给出它的第 $j$ 个派”；

③ 将所有边反向 —— 此时 $i$ 到 $j$ 的边的含义就是“如果一头牛给的是它的第 $i$ 个派，上一次另一头牛给的可能是它的第 $j$ 个派”，这样就实现了从“终点”倒着求解；
④ 从“终点”开始BFS求出每个点到任意一个“终点”的最短距离；

[一些小细节]
① 很有可能出现环，但是因为边权为正数，不影响；
② 因为每个点只会遍历一次，求答案的时间复杂度为总点数 $O(2n)$；
③ 连边的时候利用连续区间的性质，可以先将 A 和 B 的派分别排序，再二分判断每个派可以和另一头牛的哪一段派连边；（具体见代码，有一点难写）
④ 我写的代码没有将边反向的部分，而是直接计算出反向边；
Tab. 总的时间复杂度为 $O(2nlog_2n)$ （$log$ 是二分）

「源代码」

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
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e5;
struct COW{int key[2],id;}Ca[N+3],Cb[N+3];
bool cmpCa(COW A,COW B){return A.key[1]<B.key[1];}
bool cmpCb(COW A,COW B){return A.key[0]<B.key[0];}
int n,d;
int ans[N+3][2];
struct QUEUE{
	int tag,id,val;
	QUEUE(int _tag,int _id,int _val):tag(_tag),id(_id),val(_val){}
};
queue<QUEUE> que;
int print[N+3];
int SearchLef(COW *num,int val,int tag){
	int lef=1,rig=n;
	if(num[rig].key[tag]<val) return (1<<30);
	while(lef+1<rig){
		int mid=(lef+rig)>>1;
		if(num[mid].key[tag]>=val) rig=mid;
		else lef=mid;
	}
	if(num[lef].key[tag]>=val) return lef;
	return rig;
}
int SearchRig(COW *num,int val,int tag){
	int lef=1,rig=n;
	if(num[lef].key[tag]>val) return -1;
	while(lef+1<rig){
		int mid=(lef+rig)>>1;
		if(num[mid].key[tag]<=val) lef=mid;
		else rig=mid;
	}
	if(num[rig].key[tag]<=val) return rig;
	return lef;
}
int main(){
	scanf("%d%d",&n,&d);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&Ca[i].key[0],&Ca[i].key[1]),Ca[i].id=i;
	for(int i=1;i<=n;i++)
		scanf("%d%d",&Cb[i].key[0],&Cb[i].key[1]),Cb[i].id=i;
	sort(Ca+1,Ca+1+n,cmpCa);
	sort(Cb+1,Cb+1+n,cmpCb);
	memset(ans,0x3f,sizeof ans);
	int INF=ans[0][0];
	for(int i=1;i<=n;i++){
		if(!Ca[i].key[1]) ans[i][0]=1,que.push(QUEUE(0,i,1));
		if(!Cb[i].key[0]) ans[i][1]=1,que.push(QUEUE(1,i,1));
	}
	while(!que.empty()){
		QUEUE u=que.front();que.pop();
		int lef,rig;
		if(u.tag)
			lef=SearchLef(Ca,Cb[u.id].key[1]-d,1),
			rig=SearchRig(Ca,Cb[u.id].key[1],1);
		else
			lef=SearchLef(Cb,Ca[u.id].key[0]-d,0),
			rig=SearchRig(Cb,Ca[u.id].key[0],0);
		for(int i=lef;i<=rig;i++){
			if(ans[i][!u.tag]<=u.val+1) continue;
			ans[i][!u.tag]=u.val+1;
			que.push(QUEUE(!u.tag,i,u.val+1));
		}
	}
	for(int i=1;i<=n;i++) print[Ca[i].id]=ans[i][0]==INF? -1:ans[i][0];
	for(int i=1;i<=n;i++) printf("%d\n",print[i]);
	return 0;
}

『B : Barn Painting』 〔传送门〕

「题目」

给你一颗大小为 $n(n\leq 10^5)$ 的树，三种颜色，每个点涂一种颜色，相邻点不能同色。下面告诉你一些点已经被涂色，并且告诉你是哪一种颜色，问你涂完整棵树有多少种方法? 答案取模 $1000000007$。

「解析」

比较老套的树形DP了……设 $dp[u][k]$ 表示给 节点$u$ 的子树全部涂色且 节点$u$ 涂第 $k$ 种颜色的方案数。

只要考虑 节点$u$ 和它的子节点颜色不同。如果题目限制 节点$u$ 的颜色，则 $dp[u][]$ 除了第 $k$ 种颜色，其余颜色的 DP值 都赋值为 $0$。

最后答案统计在根节点的 dp 数组里。

「源代码」

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
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1e5,MOD=1e9+7;
vector<int> edg[N+3];
int n,m;
int col[N+3];
long long dp[N+3][3];
void DP(int pnt,int pre){
	if(col[pnt]) dp[pnt][col[pnt]-1]=1;
	else dp[pnt][0]=dp[pnt][1]=dp[pnt][2]=1;
	for(int i=0;i<edg[pnt].size();i++){
		int v=edg[pnt][i];
		if(v==pre) continue;
		DP(v,pnt);
		dp[pnt][0]*=dp[v][1]+dp[v][2];
		dp[pnt][1]*=dp[v][0]+dp[v][2];
		dp[pnt][2]*=dp[v][0]+dp[v][1];
		dp[pnt][0]%=MOD;dp[pnt][1]%=MOD;dp[pnt][2]%=MOD;
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++){
		int u,v;scanf("%d%d",&u,&v);
		edg[u].push_back(v);
		edg[v].push_back(u);
	}
	for(int i=1;i<=m;i++){
		int pnt,_col;scanf("%d%d",&pnt,&_col);
		col[pnt]=_col;
	}
	DP(1,0);
	printf("%lld\n",(dp[1][0]+dp[1][1]+dp[1][2])%MOD);
	return 0;
}

『C : Haybale Feast』 〔传送门〕

「题目」

给长度为 $n(n\leq 10^5)$ 的两个序列 $f,s$ $(0<s_i,f_i\leq 10^9)$ 和一个 $M$。
如果 $[1, n]$ 的一个子区间 $[a, b]$ 满足 $f_a+f_{a+1}+…+f_b \ge M$， 我们就称 $[a, b]$ 合法，一个合法区间 $[a, b]$ 的代价为 $max(s_a, s_{a+1}, …, s_b)$。
让你求出可能的合法区间最小代价为多少。

「解析」

求区间容易想到滑动窗口，下面就按照这个思路来试一试。

假设当前的窗口的区间是 $[L,R]$ ，如果区间内总和（可以动态维护或者前缀和）小于 $M$ ，则向右边扩展 $R++$；
当 $[L,R]$ 的总和大于等于 $M$ 时，因为区间越扩展，最大值只可能变大，所以应该尽量让区间的范围小，即在总和大于等于 $M$ 的前提下尽可能的缩小左边 $L++$；
此时我们就得到了一个当前最优的区间，这样的区间有很多个，我们将每个这样的区间对应的答案取最小值。

至于怎么求区间最大值……考试的时候脑子一抽写了个线段树，之后想到可以用 单调队列、STL的优先队列、ST表 等很多方法，代码量似乎小很多，但是也懒得改了 QwQ。

「源代码」

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
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5;
int keys[N+3],num[N+3];
struct TREE{
	struct NODE{
		int lef,rig,val;
	}nod[N*7];
	void Update(int x){nod[x].val=max(nod[x<<1].val,nod[x<<1|1].val);}
	void Build(int L,int R,int x){
		nod[x].lef=L,nod[x].rig=R;
		if(L==R){
			nod[x].val=keys[L];
			return;
		}
		int M=(L+R)>>1;
		Build(L,M,x<<1);
		Build(M+1,R,x<<1|1);
		Update(x);
	}
	int Query(int L,int R,int x){
		if(nod[x].rig<L || nod[x].lef>R) return -1;
		if(L<=nod[x].lef && nod[x].rig<=R) return nod[x].val;
		return max(Query(L,R,x<<1),Query(L,R,x<<1|1));
	}
}tre;
int n;
long long req;
int main(){
	scanf("%d%lld",&n,&req);
	for(int i=1;i<=n;i++) scanf("%d%d",&num[i],&keys[i]);
	tre.Build(1,n,1);
	int lef=1,rig=1;
	long long sum=0,ans=(1ll<<60);
	while(rig<=n+1){
		while(sum<req && rig<=n)
			sum+=num[rig++];
		while(sum-num[lef]>=req && lef<=rig)
			sum-=num[lef++];
		ans=min(ans,(long long)tre.Query(lef,rig,1));
		sum+=num[rig++];
	}
	printf("%lld\n",ans);
	return 0;
}

The End

Thanks for reading!

Email: lucky_glass@foxmail.com ，欢迎提问~