Preface
本着刷遍（只刷一遍）各大OJ的原则我找到了一场UOJ的比赛
无奈UOJ一般的比赛难度太大，我就精选了UER中最简单的一场打了一下，就当是CSP前的练习吧
A. 【UER #5】万圣节的南瓜灯
一看就是要搞个结论的题目。首先我们看出来所有没有坏的格子要形成一棵树
那么对于\(n,m\le 1000\)的数据我们直接暴力连边并查集判断即可
然后考虑\(n,m\)较大时怎么做，我们发现树一定满足边数+1=点数，换句话说就是边数小于点数
那么我们容易发现对于\(2nm-m-4K<nm-k\)，那么我们粗略地估计一下就会发现当\(nm\ge 400000\)的时候一定无解，否则使用上述过程即可
`#include<cstdio>
#include<cctype>
#define RI register int
#define CI const int&
#define Tp template <typename T>
const int N=400005,dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
int t,n,m,p,ans,x[N],y[N]; bool mpl[N],*a[N],flag;
class FileInputOutput
{
private:
static const int S=1<<21;
#define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)
char Fin[S],*A,*B;
public:
Tp inline void read(T& x)
{
x=0; char ch; while (!isdigit(ch=tc()));
while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));
}
#undef tc
}F;
inline int id(CI x,CI y)
{
return (x-1)*m+y;
}
class UnionFindSet
{
private:
int fa[N];
inline int getfa(CI x)
{
return x!=fa[x]?fa[x]=getfa(fa[x]):x;
}
public:
inline void init(CI n)
{
for (RI i=1;i<=n;++i) fa[i]=i;
}
inline void link(CI x,CI y)
{
int fx=getfa(x),fy=getfa(y);
if (fx==fy) return (void)(flag=0); ++ans; fa[fx]=fy;
}
}S;
inline void clear(void)
{
for (RI i=1;i<=p;++i) a[x[i]][y[i]]=0;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i,j,k; for (F.read(t);t;--t)
{
F.read(n); F.read(m); F.read(p); ans=0;
if (1LL*n*m>400000)
{
for (i=1;i<=p;++i) F.read(x[i]),F.read(y[i]);
puts("No"); continue;
}
for (a[1]=mpl,i=2;i<=n;++i) a[i]=a[i-1]+m;
for (i=1;i<=p;++i) F.read(x[i]),F.read(y[i]),a[x[i]][y[i]]=1;
//for (i=1;i<=n;++i) for (j=1;j<=m;++j) printf("%d%c",a[i][j]," \n"[j==m]);
for (S.init(n*m),flag=i=1;i<=n;++i) for (j=1;j<=m;++j)
if (!a[i][j]) for (k=0;k<4;++k)
{
int x=i+dx[k],y=j+dy[k]; if (!y) y=m; if (y>m) y=1;
if (x&&x<=n&&!a[x][y]&&id(i,j)<id(x,y)) S.link(id(i,j),id(x,y));
}
if (!flag) { puts("No"); clear(); continue; }
if (ans+1==n*m-p) puts("Yes"); else puts("No"); clear();
}
return 0;
}
B. 【UER #5】万圣节的数列
可以说是非常良心的一道题了，思路很顺畅
我们先考虑排列的部分分，猜测有一种构造使得它只存在长度小于等于\(2\)的等差序列
那么推广到一般的数列，那么就是不可能出现公差不为零的长度\(\ge 3\)的等差子序列
考虑怎么构造，首先就想到分治。考虑我们如果能避免所有公差的长度\(\ge 3\)的等差子序列出现就一定可行（废话），那么怎么实现对于所有公差都能成立的构造
当然要请到神奇的二进制了。我们考虑对于一个区间\([l,r]\)，现在在处理二进制下的第\(k\)位
我们把二进制下第\(k\)位为\(1\)的丢到这个区间的左边，第\(k\)位为\(0\)的都扔到右边，然后递归处理两个子区间，将\(k\)增加一位即可
因为这样当前公差能表示的等差序列必然一个端点在一侧，无法构成长度为\(3\)的，因此是合法的
复杂度\(O(n\log n)\)（大雾跑\(500\)）
#include<cstdio>
#define RI register int
#define CI const int&
using namespace std;
const int N=505;
int n,a[N],p[N],odd[N],even[N];
inline void solve(CI l=1,CI r=n,CI s=0)
{
if (l>=r||s>30) return; RI p1=0,p2=0,i;
for (i=l;i<=r;++i) if ((a[p[i]]>>s)&1) odd[++p1]=p[i]; else even[++p2]=p[i];
for (i=1;i<=p1;++i) p[l+i-1]=odd[i]; for (i=1;i<=p2;++i) p[l+p1+i-1]=even[i];
solve(l,l+p1-1,s+1); solve(l+p1,r,s+1);
}
int main()
{
RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]),p[i]=i;
for (solve(),i=1;i<=n;++i) printf("%d ",p[i]); return 0;
}
C. 【UER #5】万圣节的糖果
这么多年的一道DP题了放在当下看还是会令人感觉很妙
（注意一下的算法无视集合的顺序进行计算，最后乘上\(m!\)即可）
首先我们能想出\(O(n^3)\)的DP，设\(f_{i,j,k}\)为前\(i\)个数中，有\(j\)个集合的最后一个糖果奇偶性与\(i\)相同，有\(k\)个集合的最后一个糖果的奇偶性与\(i\)不同的方案数
很显然地我们有\(f_{i,j,k}=(k+1)\times f_{i-1,k+1,j-1}+f_{i-1,k,j-1}\)
但是这样的复杂度是\(O(n^3)\)的，不足以通过此题（然后我就不会了，以下都是题解的绝妙做法）
这是一个很有趣的故事（参见题解算法四）
我们考虑把DP改一下，变成求每个集合中糖果奇偶性相同的方案数
则\(dp_{i,j,k}=s_{\lceil\frac{i}{2}\rceil,j}\times s_{\lfloor\frac{i}{2}\rfloor,k}\)，其中\(dp\)的维数表示与\(f\)一致，\(s\)表示第二类斯特林数
那么我们有以下性质：\(f_{i,j,k}=dp_{i+1,k+1,j}\)，证明如下：
当\(i=1\)时，显然只有\(j=1,k=0\)的时候方案数为\(1\)，否则为\(0\)
当\(i>1\)时，将上面的等式稍稍变形就有：\(f_{i-1,j,k}=dp_{i,k+1,j}\)，则：
\]
（最后一步利用第二类斯特林数的收缩把系数收回去）
那么我们只要\(O(n^2)\)次计算就可以得出答案
·#include<cstdio>
#define RI int
#define CI const int&
using namespace std;
const int N=6005,mod=998244353;
int n,m,g[N][N],ans;
inline int sum(CI x,CI y)
{
int t=x+y; return t>=mod?t-mod:t;
}
inline int dp(CI x,CI y,CI z)
{
return 1LL*g[(x>>1)+1][y]*g[x+1>>1][z]%mod;
}
int main()
{
RI i,j; for (scanf("%d%d",&n,&m),g[0][0]=i=1;i<=(n+1>>1)+1;++i)
for (j=1;j<=i;++j) g[i][j]=sum(g[i-1][j-1],1LL*j*g[i-1][j]%mod);
for (i=0;i<=m;++i) ans=sum(ans,dp(n,m-i+1,i));
for (i=1;i<=m;++i) ans=1LL*ans*i%mod; return printf("%d",ans),0;
}
Postscript
我还菜啊对于计数题毫无还手之力