目前打得最好的一集。
A
考虑如果 \(\le 0\) 还会减一,那么花掉的钱就是,\(1+2+\cdots +(n-1)\)。现在的问题就是,可能少花掉一些。
最多花掉 \(\mathcal{O}(n^2)\),所以考虑计数这个。发现其实,花掉的是 \(\sum_{i=1}^n \min(p_i-1,a_{p_i})\)。
对于 \(\min(p_i-1,a_{p_i})=k\) 设计状态,\(dp_{i,sum,cnt}\) 为:从大到小,现在 \(k=i\),和是 \(sum\),\(cnt\) 个处理完了。
考虑转移:
-
\(\min(p_i-1,a_{p_i})=a_{p_i}=k\)。这个就是当前一些枚举选择几个。
-
\(\min(p_i-1,a_{p_i})=p_i-1=k\)。只可能 \(+1\),\(0/1\) 枚举。
可以用组合数计算出来。具体的,选择几个 \(a_i=k\) 的组合数,对应的大的 \(p\) 的组合数等。
复杂度是 \(\mathcal{O}(n^4)\),因为枚举选择个数,一共只会有 \(\mathcal{O}(n)\) 次枚举。
B
构造题,难死了。
考虑 \(n\le 5\) 构造不出来。
查看样例,发现正好不可到达的点对为 \((1,n),(2,n-1),\cdots\)。如果 \(n\) 是偶数就这个样子构造。
具体的,有一个二分图。左边是 \(1\sim n/2\),右边的是 \(n/2+1\sim n\)。对于 \(i\le n/2\),给所有的 \(j>n/2,i+j\neq n+1\) 连边。这样子是对的,因为所有连了边的右部点可以到达,所有左部点可以到达,没有连边的右部点至少要 \(3\) 次(二分图!)所以是对的。
考虑 \(n\) 是奇数:\(1+(n-1)=n\),那么留下一个 \(n\) 不能到达自己就好了。
C
比较简单。
题目相当于,把原来的序列划分成若干段,每一段的或是不下降的,最大化段数。
考虑段的或,一共只有 \(n\log n\) 种值(经典)。
设 \(f_x\) 为 \(1\sim i\),现在最后一段权值是 \(x\),的最大段数。
考虑加入 \(a_{i+1}\)。有两种:
-
\(a_{i+1}\) 加入上一个段尾。直接或上,转移。
-
以 \(l=i+1\) 开一个新的段,要求新的段的结尾 \(r\),满足 \(l\sim r\) 的或更大。
直接枚举 \(r\) 是不行的,但是发现有第一种转移,找到一个最小的 \(r\) 就可以转移到其他的。那么二分+ST 表就可以,复杂度两个 \(\log\)。