前行 - USACO2017 Dec

为了让我们恢复正常学习的状态,教练把金组的题拉给我们做了一下……($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 ,欢迎提问~

0%