UOJ NOI Round-UNR(chao)解题报告
i207M
2019-07-08 18:56:49
# UNR #3
## Day 1
### 鸽子固定器
**观察题**
简化题意：pair(a,b)
正常人的做法：
把pair按b排序，然后考虑暴力：
枚举右端点（b的最大值）然后枚举左端点，用堆维护前m大，显然？如果右端点出队了肯定不优。
显然？我们可以直接跳到下一次堆中元素改变的位置。
~~显然~~这样做的复杂度就是$O(nm\log n)$
证明：假设在以i为右端点向左扫描时j被入堆了，就记录有序对(j,i)。我们把有序对(a,b)分成两类：$vb\le va$的叫做第一类有序对，vb>va的叫做第二类有序对。
1. 对于第一类有序对(a,b)，一个b最多对应m个a。（否则b会被出堆）
2. 对于第二类有序对(a,b)，一个a最多对应m个b。（否则在扫描到a的时候，堆里至少有m个比a大的数，也就是说，a不会被入堆）
具体实现可以用链表维护“下一次堆中元素改变的位置”，如果实际上没改变我们就把这个位置删了。可以用线性做法代替堆。
有一个神仙的链表做法。
### To Do Tree
猜结论
### 配对树
线段树合并水题。卡空间可以用dfs on tree/splay合并
## Day 2
### 白鸽
鸽了。
### 百鸽笼
~~真的有这个地名！？~~
我们发现每个位置的概率和还剩多少个集合有关。首先有一个状压DP是$f[i][S]$表示填了i个位置，S这个集合空了。对于每个位置，我们可以枚举这是哪一个集合的最后一个。
但是这个DP无法优化。正解我们考虑容斥。（这真的是神仙容斥）
比方说我们要算第1列的答案。我们考虑钦定S这个集合在1后完成。那么，**不在S中的列可以忽略掉**，因为容斥时不对他们做出限制。这里又有一个神奇的性质：既然我们忽略了不在S的集合，而1在S前完成，设序列长度为L，则概率就是$1/(|S|+1)^L$！
于是我们容斥里只需要记录$|S|,L$这些信息就可以了。这其实是一种二维生成函数卷积，我们暴力做就行。我们计算i的答案时把i除掉即可。
```cpp
int f[N][M];
void Mul(int n,int m,int s)
{
for(ri i=n;i>=0;--i)
for(ri j=m;j>=0;--j)
if(f[i][j]) for(ri k=0;k<s;++k)
inc(f[i+1][j+k],md-(LL)f[i][j]*C[j+k][k]%md);
}
void Div(int n,int m,int s)
{
for(ri i=0;i<n;++i)
for(ri j=0;j<=m;++j)
if(f[i][j]) for(ri k=0;k<s;++k)
inc(f[i+1][j+k],(LL)f[i][j]*C[j+k][k]%md);
}
signed main()
{
#ifdef M207
freopen("in.in","r",stdin);
//freopen("ot.out","w",stdout);
#endif
in(n);
for(ri i=1;i<=n;++i) in(a[i]);
init(900,30);
f[0][0]=1;
int s=0;
for(ri i=1;i<=n;++i) Mul(i-1,s,a[i]),s+=a[i];
for(ri i=1,ans;i<=n;++i)
{
Div(n,s-a[i],a[i]);
ans=0;
for(ri j=0;j<n;++j)
for(ri k=0;k<=s-a[i];++k)
ans=(ans+(LL)f[j][k]*ipw[j+1][k+a[i]]%md*C[k+a[i]-1][a[i]-1])%md;
out(ans,' ');
Mul(n-1,s-a[i],a[i]);
}
return 0;
}
```
~~T3消失了~~
# UNR #2
### UOJ拯救计划
二分图判定水题
### 排兵布阵
哇，这道题的思路很强！
我们统计出每行的点数和每列的点数，对于一个点，如果所在行的点数大于列的，我们把它作为列关键点。这样，每行每列关键点的个数就是$O(\sqrt{n})$
对于每种操作，如果是行加，关键点暴力，更新对应列的非关键点最大值，非关键点打标记。如果是列查，关键点暴力查对应行的标记，非关键点直接取最大值。
这里的标记一直是不能下传的。
如何合并？我们并不能暴力合并，也不能暴力下放标记，我们可以对行列分别维护并查集，同时维护自己到父亲的标记的差的信息，这样标记解决了。然后考虑行合并之后，可能行关键点变成列关键点了，我们需要遍历一遍关键点看看是否变化。
我们还要解决关键点去重的问题，当然可以写Hash表，但是优雅的写法是当我们发现一行的关键点数$>2\sqrt{n}$就用map暴力去重，每次至少会减少$\sqrt{n}$个关键点，所以这不是瓶颈。
这里并查集的复杂度不是瓶颈...很神奇。
~~T3消失了~~
## Day 2
### 积劳成疾
降智好题...感觉忘记了某一类DP最经典的套路了：既然**贡献和最大值有关，那么就枚举最大值！**，我们记$f[n][m]$表示填长度为n的序列，最大值$\le m$的贡献和，考虑有没有=m的数。如果有，我们枚举第一个等于m的数在哪里，然后我们就把问题分成了两半，根据期望的线性性，就可以做了。
*见到填最大值，不要总是想着从小往大/从前往后填。我们可以限制最大值的大小，直接枚举最大值的位置！*
```cpp
for(ri i=0;i<=n;++i) f[0][i]=1;
for(ri i=1;i<=n;++i) // length
for(ri j=1;j<=n;++j) // max
{
f[i][j]=f[i][j-1];
for(ri k=1;k<=i;++k)
f[i][j]=(f[i][j]+(LL)f[k-1][j-1]*pw[j][max(0,min(i-m+1,k)-max(1,k-m+1)+1)]%md*f[i-k][j])%md;
}
```
### 梦中的题面
似乎暴力数位DP就行了。
~~T3消失了~~