A

模拟

问能否删除一些字符后重新排列，能组成给定的字符串。

可以排列，所以只要传力每种字符的出现次数，都比目标串更多即可，这可以 $map$ 统计，然后枚举目标串的 $map$

void solve(){
	int n;
	cin>>n;
	string s="Kato_Shoko";
	string t;
	cin>>t;
	
	map<char,int>mp1,mp2;
	for(char c:s)mp1[c]++;
	for(char c:t)mp2[c]++;
	bool ok=1;
	for(auto &[k,v]:mp1){
		if(mp2[k]<v)ok=0;
	}
	if(ok){
		cout<<"YES "<<t.size()-s.size();
	}
	else{
		cout<<"NO";
	}
}

B

贪心排序

有 $n$ 个真人，活跃度为 $a_i$ ，每个真人可以建立 $b_i$ 个复制，要使得总活跃度不少于 $t$ ，问最少需要复制多少次？

显然先复制较大的，经典贪心，如果当前真人全复制了也不够，就全复制，否则复制到刚好超过 $t$

void solve(){
	int n,k;
	cin>>n>>k;
	vi a(n+1),b(n+1);
	rep(i,1,n)cin>>a[i];
	rep(i,1,n)cin>>b[i];
	
	vvi c;
	rep(i,1,n){
		c.push_back({a[i],b[i]});
	}
	sort(c.begin(),c.end());
	reverse(c.begin(),c.end());
	int sum=0;
	rep(i,1,n){
		sum+=a[i];
	}
	if(sum>=k){
		cout<<0;
		return;
	}
	int ans=0;
	for(auto &t:c){
		int a=t[0],b=t[1];
		if(sum+a*b<=k){
			sum+=a*b;
			ans+=b;
		}
		else{
			ans+=(k-sum+a-1)/a;
			sum=k;
			break;
		}
	}
//	cout<<sum<<' '<<ans<<'\n';
	if(sum>=k){
		cout<<ans;
	}
	else{
		cout<<-1;
	}
}

C

枚举

问从一个数字组成的串李任选，组成一个整数，问能被 $d$ 整除的最小整数？

串很短，考虑枚举选中的数字集合，然后对他们枚举全排列，这样就是得到了全部可以得到的数字，可能带前导零，转换成整型可以直接 $stoi()$

这里是 $dfs$ 枚举，也可以二进制枚举

void solve(){
	int n,k;
	cin>>n>>k;
	string s;
	cin>>s;
	
	string t;
	int ans=1e9;
	auto &&dfs=[&](auto &&dfs,int i)->void{
		if(i==n){
			int m=t.size();
			vi p(m);
			rep(i,0,m-1){
				p[i]=i;
			}
			do{
				string q;
				for(int x:p){
					q+=t[x];
				}
				if(!q.size())continue;
				int x=stoi(q);
				if(x%k==0){
					ans=min(ans,x);
				}
			}while(next_permutation(p.begin(),p.end()));
			return;
		}
		t.push_back(s[i]);
		dfs(dfs,i+1);
		t.pop_back();
		dfs(dfs,i+1);
	};
	dfs(dfs,0);
	if(ans<1e9){
		cout<<ans;
	}
	else{
		cout<<-1;
	}
}

D

位运算结论

每次选两个元素 $x,y$ 删掉，把 $x \oplus y$ 加入集合， $2(a \wedge b)$ 加入答案，直到集合之剩一个元素，问答案最小多少

需要知道 $a+b=a \oplus b +2(a \wedge b)$

那么我们把所有元素都加起来就是 $\sum a_i=\bigoplus a_i +2\bigwedge a_i$

而我们进行这个操作过程中，就是把 $\bigoplus a_i$ 留在集合里，把 $2\bigwedge a_i$ 加到答案，那么答案其实就是 $\sum a_i -\bigoplus a_i$

操作顺序实际不影响答案，也就是最小是个诈骗

E

互异分拆数

分拆数 $P_n$ 就是把 $n$ 拆分成多个非负整数，且他们大小非严格递增的方案数。互异分拆数在此基础上要求严格递增，也就是所有数都不能相同

计算可以 $dp$ ，注意到由于互异，和为 $n$ ，最多有 $O(\sqrt n)$ 项，那么可以把项数放在状态里，如果能 $O(1)$ 转移，复杂度就是 $O(n\sqrt n)$ ，

也就是 $dp(i,j)$ 表示和为 $i$ ，有 $j$ 项的方案数。转移也就是要从规模较小的分拆数，映射到规模较大的分拆数的过程。一个显然的映射是，在最后加一个比原本最后更大的数，这个映射当然是对的，但是需要知道原本最后元素的值，这个信息只能放在状态里，导致状态数过多，不行。

另一个比较巧妙的映射是，分类讨论一个分拆的最小元素是不是1，如果是，把1删掉，然后把剩余元素减一，就得到了一个长度减一，和减 $j$ 的分拆，如果开头不是1，直接把所有元素减一，得到了一个长度仍未 $j$ ，和减 $j$ 的方案数。这个映射不需要知道最后一个元素的值，只用知道元素和，元素个数。

也就是 $dp(i,j)=dp(i-j,j-1)+dp(i-j,j)$

void solve(){
	int n,m;
	cin>>n>>m;
	
	vvi dp(n+1,vi(500));
	
	dp[0][0]=1;
	rep(i,1,n){
		rep(j,1,450){
			if(i-j<0)continue;
			if(j*(j+1)>2*n)continue;
			dp[i][j]=(dp[i-j][j-1]+dp[i-j][j])%M1;
		}
	}
	
	int ans=0;
	rep(i,1,450){
		ans=(ans+dp[n][i]*m%M1*qpow(m-1,i-1,M1)%M1)%M1;
	}
	cout<<ans;
}

F

$logtrick$ ， $dp$

划分子区间，每个子区间的贡献是区间元素的按位与，按位或的异或起来，总贡献是每个子区间的贡献加起来。问总贡献最小值

整体肯定是一个划分型 $dp$ ， $dp_i$ 表示完成了对长度 $i$ 的前缀的划分，的最优答案。但问题是可以从前面所有位置转移过来，

也就是 $dp(i)=\max_{j=1}^{i-1}(dp_j+val(j+1,i))$

复杂度 $O(n^2)$ ，必须加速转移

这种时候一般就要从这个 $val$ 的定义入手，如果是加减法，可以把所有含 $j$ 项用线段树维护，然后 $O(\log n)$ 查询，这里的定义是按位与和按位或，想把他们加速到 $O(\log n)$ ，思路则是 $logtrick$ ，也就是按位与，按位或在元素增加时变化都是单调的，又由于二进制位只有 $30$ 个，最多只会变化 $O(\log n)$ 次，每两次变化中间的 $val$ 都是一样的，只要取区间内的的 $max(dp_j)$ 即可，着最简单的做法是线段树，当然注意到 $dp_j$ 是随 $j$ 不减的，所以最大值一定是每个区间的右端点。

由于有按位与，按位或两个，实际上会有 $60$ 个分界点，划分出 $60$ 个区间，每个区间作上述转移

小白月赛121

A

B

C

D

E

F