Java教程

8月做题笔记

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

LG P7165

题意:给一颗无根树,任意割两条边,使得最大的连通块与最小的连通块相差尽可能小。\(n=10^5\)

Sol:先枚举删除的第一条边,考虑如何快速选出第二条边。很显然剩下的两块应该尽可能接近。
随便选个根,记一开始选的子树大小是\(size_i\),那么剩下两块应该接近\(\frac{n-size_i}{2}\)。开一个multiset存所有的\(size\),然后直接在上面二分。
考虑一个特殊的情况,当第二次选的是第一次的祖先时,第一次的不能算进去。所以祖先一侧的应该接近\(\frac{n+size_i}{2}\),所以再开一个multiset,在枚举第一次的时候不断把经过的祖先从原来的set移到这个set里,两个set分别算,讨论一下。

LG P7166(待补)

题意:给\(n\)的三个排列\(A,B,C\),对于某一组\((i,j)【要求i在j前面】\),定义它的归属是:

  • 首选\(i\)靠前的
  • 其次选\(j\)靠前的
  • 都一样按\(ABC\)的顺序
    求\(A,B,C\)得到的二元组数目以及 对于每一个\(i\),可能的\(j\)有多少个。

Sol:
首先记录一个东西:\(pos_i,gr_i\)分别表示每个数第一次出现的位置和第一次出现所在的组别。
考虑每个\(i\)对答案的贡献。
对于那些排在后面的人,肯定是赢的,用一个前/后缀和算出组别的答案就行
然后考虑和它排一起的人。
枚举胜负关系比较一下就可以了。
有点难写。

LG P1350

题意:给一个\(L\)形的棋盘,求放车的方案数。
Sol:考虑分割成三块。枚举中间一块填了几个,分别会影响角落两块的行和列,减一下就可以。
对于一个矩形\((x,y)\),放置\(k\)个车的方案数是:$$A_x^k* C_x^k$$

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