洛谷做题笔记

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

洛谷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;
}

总结

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

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