请求升紫 & hack
查看原帖
请求升紫 & hack
380042
piggy123楼主2023/8/22 19:06

题解区中的 O(3m)O(3^m) 加剪枝做法可以被卡掉(本地跑了一分多钟,我写的 O(2mm2)O(2^mm^2) 跑了 44 秒,可以作为参考),数据生成器如下:

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;

vector<ll> cc[66],op;

int main(){
	freopen("hack.out","w",stdout);
	ll n=100000,m=20;
	cout<<n<<" "<<m<< endl;
	for (ll i=0;i<=(1<<m)-1;i++){
		cc[__builtin_popcount(i)].push_back(i);
	}
	for (ll i=m;i>=0;i--){
		for (ll j:cc[i]){
			n--;
			op.push_back(j);
			if (n==0)break;
		}
		if (n==0)break;
	}
	for (ll i=0;i<m;i++){
		for (ll j:op){
			cout<<(j>>i&1?'H':'E');
		}
		cout<< endl;
	}
	return 0;
}

此外,本题的优于 O(3m)O(3^m) 做法,无论是考虑 FMT 的过程还是直接钦定顺序判重,都达到了紫题难度(至少严格难于本场金组的三题),所以建议评紫。

不知道该 at 谁。

2023/8/22 19:06
加载中...