CSP2024 前集训：多校A层冲刺NOIP2024模拟赛11

卡布叻_周深 / 2024-11-10 / 原文

前言

T1 不知道啥是冒泡排序，理解了一会儿题面代码发现是啥意思了于是就签了。

后面的题都不是很可做，T2、T4 计数，T3 高级玩意看不懂。

但是 T2 有点可做，但我的 DP 不知道哪儿假了，暴力还打挂了，不然加个 bitset 就操过去了。

T1 冒泡排序

$i$ 只能和 $i+k,i+2k,……$ 换，对于每一个模 $k$ 的余数拎出来放 vector 里排序即可。

点击查看代码

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=1e6+10;
template<typename Tp> inline void read(Tp&x)
{
	x=0;register bool z=true;
	register char c=getchar_unlocked();
	for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0;
	for(;isdigit(c);c=getchar_unlocked()) x=(x<<1)+(x<<3)+(c^48);
	x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar_unlocked((x%10)+'0');}
template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);}
int n,k,a[N]; vector<int>b[N];
signed main()
{
	freopen("bubble.in","r",stdin),freopen("bubble.out","w",stdout);
	read(n,k); for(int i=1;i<=n;i++) read(a[i]);
	for(int i=1;i<=k;i++)
	{
		for(int j=i;j<=n;j+=k) b[i].push_back(a[j]);
		sort(b[i].begin(),b[i].end(),[](int x,int y){return x>y;});
	}
	for(int i=1;i<=n;i++)
	{
		write(b[(i-1)%k+1].back()),b[(i-1)%k+1].pop_back();
		putchar_unlocked(' ');
	}
}

T2 染色

当最后的数列为原数列的子序列，最后的数列是合法的，（1 1 1 2 2 3 3 视为 1 2 3），这是显然的。

$f_{i,j,k}$ 表示处理到第 $i$ 位，子序列长度为 $j$，结尾为 $k$ 的方案数，有：

\[f_{i,j,a_i}=[j=1]+\sum_{k=1}^{i-1}\sum_{h=1}^m[a_i\ne h]f_{k,j-1,h} \]

直接前缀和优化成 $O(nm)$ 的，bitset 优化成 $O(\frac{nm}{w})$。

插板法，最后答案为 $\sum\limits_{i=1}^nC_{n-1}^{i-1}\sum\limits_{j=1}^mf_{n,i,j}$。

关于 $C_n^m$ 的奇偶性，有 $C_n^m\bmod 2=[n\&m=m]$，lucas 定理直接证。

点击查看代码

#include<bits/stdc++.h>
#pragma GCC optimize(3)
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=1e5+10,M=2e4+10;
template<typename Tp> inline void read(Tp&x)
{
	x=0;register bool z=true;
	register char c=getchar_unlocked();
	for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0;
	for(;isdigit(c);c=getchar_unlocked()) x=(x<<1)+(x<<3)+(c^48);
	x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar_unlocked((x%10)+'0');}
template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);}
int T,n,m,len,a[N]; bitset<N>f[M],g,tmp; bool ans;
inline bool C(int n,int m) {return (n&m)==m;}
signed main()
{
	freopen("color.in","r",stdin),freopen("color.out","w",stdout);
	for(read(T);T;T--)
	{
		read(n,m),ans=0,g=0; for(int i=1;i<=m;i++) f[i]=0;
		for(int i=1;i<=n;i++) read(a[i]); len=unique(a+1,a+1+n)-a-1;
		for(int i=1,x;i<=len;i++)
			tmp=g^f[x=a[i]],f[x]=tmp<<1,f[x][1]=1,g=tmp^f[x];
		for(int i=1;i<=len;i++) ans^=g[i]&C(n-1,i-1);
		putchar_unlocked(ans?'1':'0');
	}
}