NOIP集训-10.30总结

水题一套...比Noip还水..
---------------------------------------------------------------------------------------
 
Change:SuperOjP978
只需要枚举分界线,某个位置的答案就是这个位置之前小写字母的个数加这个位置之后大写字母的个数
---------------------------------------------------------------------------------------
Count:SuperOjP979
莫队即可,线段树也行
---------------------------------------------------------------------------------------
Road:SuperOj980
把某个点对的按照题目的规则删边,最后一条删除的边(也就是权值最大的一条)叫做这个点对的的“关键边”
不难发现每条边出现的次数就是权值大于等于这条边的边作为关键边出现次数之和
另外,可以把边按权值排序后从大到小添加,一个边添加的时候若两边有点不连通,那么这个边就是一条关键边,
且其作为关键边的出现次数就是两边联通块大小之积,只需要用并查集维护一下,记录一下块的大小即可
---------------------------------------------------------------------------------------