ZJOI 2022 题目选做
树
题目描述
点此看题
解法
考虑这样的一个计数方法：对于一个点，我们考虑其在第一棵树上是叶子，第二棵树上是非叶子；或者在第一棵树上是非叶子，第二棵树上是叶子的状态。那么记录第一棵树前面的非叶节点个数，记录第二棵树后面的非叶节点个数，就可以方便地计算方案数。
但是这样做会出现一个明显的问题：我们的非叶节点可能并没有被连边，解决这个问题可能需要记录更多的状态。但是我们可以容斥没有被连边的非叶节点数量，每多一个这样的点就记上 \(-1\) 的容斥系数。
设 \(f[j][k]\) 表示考虑到当前点，第一棵树前面有 \(j\) 个非叶节点，第二棵树后面有 \(k\) 个非叶节点，状态中的非叶节点是不包含 \(1/n\) 的，所以计算方案数的时候还要把连向它们的边考虑到，转移：
- 点 \(i\) 在第一棵树上是叶子，第二棵树上是非叶子：\(f[j][k]\leftarrow (j+1)\cdot (k+1)\cdot f[j][k+1]\)；如果在第二棵树上是没有被连边的非叶子：\(f[j][k]\leftarrow -(j+1)\cdot (k+1)\cdot f[j][k]\)
- 点 \(i\) 在第一棵树上是非叶子，第二棵树上是叶子：\(f[j][k]\leftarrow j\cdot (k+1)\cdot f[j-1][k]\)；如果在第一棵树上是没有被连边的非叶子：\(f[j][k]\leftarrow -(j+1)\cdot (k+1)\cdot f[j][k]\)
时间复杂度 \(O(n^3)\)
总结
一开始我直接对不合法的状态容斥（都是叶子，都是非叶子），结果复杂度爆炸。
所以事实证明容斥不只有直接容斥这一种思考方向，本题的逻辑就是先给出一种会算重的计数方法，然后找出这种计数方法算重的原因，然后对这个算重的原因容斥就得到了复杂度很美妙的做法。
#include
const int M = 505;
#define int long long
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,MOD,f[M][M],g[M][M];
signed main()
{
n=read();MOD=read();
for(int i=0;i<=n;i++) f[0][i]=i+1;
puts("1");
for(int i=2;i
众数
题目描述
点此看题
解法
众数问题基本上不能 \(poly\ log\)，所以我们着重考虑一些根号算法。
可以对不同颜色的出现次数根号分治，称出现次数 \(\geq \sqrt n\) 的为大颜色，否则为小颜色。
首先考虑大颜色对其他颜色的贡献，可以把大颜色打在原来的序列上，做完前缀和之后枚举其他颜色，按顺序扫描，记录前缀最小值就可以做到 \(O(n)\)，这一部分总时间 \(O(n\sqrt n)\)
然后考虑小颜色对其他颜色的贡献，这时候要抓住关键性质：选取的区间众数应当 \(\leq \sqrt n\)，那么我们外层枚举众数大小 \(x\)，然后双指针就可以获得 \(p_r\) 表示右端点 \(r\) 对应最大左端点，使得众数为 \(x\)，得到这个数组之后我们枚举颜色 \(y\)，对于 \(y\) 的每一个点，我们双指针维护最大的左端点使得两点间区间众数为 \(x\)，贡献就便于计算了，这一部分时间复杂度也是 \(O(n\sqrt n)\)
#include
#include
#include
#include
#include
using namespace std;
const int M = 200005;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int T,n,m,k,a[M],b[M],c[M],s[M],ans[M],p[M],mi[M];
vector g[M];
void work()
{
n=read();k=sqrt(n);
for(int i=1;i<=n;i++)
a[i]=b[i]=read(),c[i]=ans[i]=0,g[i].clear();
sort(b+1,b+1+n);m=unique(b+1,b+1+n)-b-1;
for(int i=1;i<=m;i++) g[i].push_back(0);
for(int i=1;i<=n;i++)
{
c[a[i]=lower_bound(b+1,b+1+m,a[i])-b]++;
g[a[i]].push_back(i);
}
for(int i=1;i<=m;i++) g[i].push_back(n+1);
for(int x=1;x<=m;x++) if(c[x]>=k)
{
for(int i=1;i<=n;i++)
s[i]=s[i-1]+(a[i]==x);
s[n+1]=s[n];
for(int y=1;y<=m;y++) if(x^y)
{
int mn=0;
for(int i=1;i=1;x--)
{
for(int i=1;i<=m;i++) s[i]=0;
for(int r=1,l=1;r<=n;r++)
{
s[a[r]]++;
while(s[a[r]]>=x) s[a[l]]--,l++;
p[r]=l;
}
for(int y=1;y<=m;y++) if(ans[y] &t=g[y];
for(int i=1,j=0,k=0;i
相关