洛谷P8048 题解

发表于
带有一定迷惑性质的题

仔细读题，会发现，向右的变色龙在碰撞前后是没有改变颜色的。

抓住这一点，产生了本题的做法：

暴力

对于每一只向右的变色龙，只需要在该颜色中加上这只变色龙走的路程。

对于每一只向左的变色龙，我们枚举在它左边的向右的变色龙，然后依次更新答案、更新颜色。

这样做复杂度是 $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
#define int long long
using namespace std;
int n,k,l,cnt;
double ans[45];
struct monola{
	int st,cl;
	char tp;
}ml[100005],yml[100005];
bool cmp(monola x,monola y){
	return x.st>y.st;
}
signed main(){
	cin>>n>>k>>l;
	for(int i=1;i<=n;i++){
		scanf("%lld%lld%s",&ml[i].st,&ml[i].cl,&ml[i].tp);
		if(ml[i].tp=='D'){
			ans[ml[i].cl]+=l-ml[i].st;
			yml[++cnt]=ml[i];
		}
	}
	sort(yml+1,yml+cnt+1,cmp);
	for(int i=1;i<=n;i++){
		if(ml[i].tp=='D')continue;
		double pre=ml[i].st,nxt;
		int nowcl=ml[i].cl;
		for(int j=1;j<=cnt;j++){
			if(ml[i].st<yml[j].st)continue;
			nxt=(ml[i].st+yml[j].st)*1.0/2;
			ans[nowcl]+=pre-nxt;
			pre=nxt;
			nowcl=(nowcl+yml[j].cl)%k;
		}
		ans[nowcl]+=pre;
	}
	for(int i=0;i<k;i++){
		printf("%.1lf\n",ans[i]);
	}
	return 0;
}

正解

这样做的瓶颈在于，我们每一只向左的变色龙都需要枚举。然而我们其实并不关心到底是哪只变色龙贡献的答案，因此我们可以用计数器记下当前位置每种颜色向左的变色龙的数目。

具体地说，我们从右往左枚举每一只向右的变色龙，若两只向右的变色龙中间的距离为 $dis$，则每种颜色的答案应该加上 $dis/2\times num_i$，其中 $num_i$ 为颜色 $i$ 的向左的变色龙初始位置在当前枚举的向右的变色龙右边的数目。然后我们不断更新 $num_i$。

由于每只向左的变色龙只会被加进计数器一次，所以总的复杂度降到了 $O(n\times k)$ 。

实现细节

注意每只向左的变色龙在遇到最左边的向右变色龙后还要走到木板左端，此时需要加上这部分的答案。可以预处理出每只向左的变色龙最后的颜色进行计算。

丑陋的代码

#define int long long
using namespace std;
int n,k,l,cnt,cmt,num[45],lint[45],newcl,lastcl[100005];
double ans[45];
struct monola{
    int st,cl;
    char tp;
}ml[100005],yml[100005],zml[100005];
bool cmp(monola x,monola y){
    return x.st>y.st;
}
signed main(){
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
    cin>>n>>k>>l;
    for(int i=1;i<=n;i++){
        scanf("%lld%lld%s",&ml[i].st,&ml[i].cl,&ml[i].tp);
        if(ml[i].tp=='D'){
            ans[ml[i].cl]+=l-ml[i].st;
            yml[++cnt]=ml[i];
            newcl=(newcl+ml[i].cl)%k;
        }
        else {
            zml[++cmt]=ml[i];
            if(cnt)ans[(ml[i].cl+newcl)%k]+=(ml[i].st+yml[1].st)*1.0/2;
            else ans[ml[i].cl]+=ml[i].st;
        }
    }
    sort(yml+1,yml+cnt+1,cmp);
    sort(zml+1,zml+cmt+1,cmp);
    int i=1;
    while(i<=cmt&&zml[i].st>yml[1].st){
        ans[zml[i].cl]+=(zml[i].st-yml[1].st)*1.0/2;
        num[(zml[i].cl+yml[1].cl)%k]++;
        i++;
    }
    for(int j=2;j<=cnt;j++){
        for(int r=0;r<k;r++){
            ans[r]+=num[r]*(yml[j-1].st-yml[j].st)*1.0/2;
        }
        while(i<=cmt&&zml[i].st>yml[j].st){
            ans[zml[i].cl]+=(zml[i].st-yml[j].st)*1.0/2;
            num[zml[i].cl]++;
            i++;
        }
        for(int r=0;r<k;r++){
            lint[(r+yml[j].cl)%k]=num[r];
        }
        for(int r=0;r<k;r++)num[r]=lint[r];
    }
    
    for(int i=0;i<k;i++){
        printf("%.1lf\n",ans[i]);
    }
    return 0;
}