题解区中的 O(3m) 加剪枝做法可以被卡掉(本地跑了一分多钟,我写的 O(2mm2) 跑了 4 秒,可以作为参考),数据生成器如下:
#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) 做法,无论是考虑 FMT 的过程还是直接钦定顺序判重,都达到了紫题难度(至少严格难于本场金组的三题),所以建议评紫。
不知道该 at 谁。