洛谷做题笔记

2021/7/24 6:11:47

本文主要是介绍洛谷做题笔记,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

洛谷P1311选择客栈

题意化简:寻找两个点a,b (ia<ib),满足color[a]==color[b] , price[c]<=max price (ia<=ic<=ib),求方案数
题目给的范围n<=10^5,从而确定只能枚举一个点
易得方案数只与a,b的位置有关,与c无关,故枚举b点,寻找与b匹配的a的个数

  • 对于color[a]==color[b],由题color count<=50,故设桶静态记录or动态记录颜色的个数,bclr[i][j]表示点区间[1, i ]中颜色为j的点的个数
int bclr[200010][60];
for(int j=0;j<clrc;++j)
	bclr[i][j]=bclr[i-1][j];
++bclr[i][clr[i]];
  • 对于price[c]<=max price (ia<=ic<=ib),确保每一对a,b均被选到,则c为离b最近的合法的点,记ok[i]为离i最近的合法点的编号
if(prc[i]<=mxp)
	ok[i]=i;
else ok[i]=ok[i-1];
  • 对于答案的统计,由于bclr的定义(那么定义是为了方便状态转移),bclr可能会包括b点,但是b不能与自己匹配,故需特判
for(int i=1,k;i<=n;++i){
	ans+=bclr[ok[i]][clr[i]];
	if(ok[i]==i)--ans;
}

总结

  • 对于线性数据的维护可采用动态规划的思想,记录每个状态下的数据,通过上一次状态转移到本次状态
  • 对于答案统计的偏差,可在统计之前除去,亦或是统计之后补齐
  • 对于范围小(离散化),要求统计出现次数的数据,考虑桶


这篇关于洛谷做题笔记的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程