社区讨论

How T4

LLele_Programmer
学术版参与者 2已保存回复 3

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@mdk202qg
此快照首次捕获于
2025/07/26 17:34
7 个月前
此快照最后确认于
2025/11/04 03:41
4 个月前
查看原帖
我的思路大概是这样的，如果 nn 是奇数就无解，否则就枚举一下子集数量 kk，记录剩下还没放的数有 remrem 个，子集大小为奇数的放在 BB，偶数的放在 AA，在剩余的足以将所有 BB 填满的情况下，尽可能将 AA 转化为 BB，然后剩下 remrem 个数以及 BB 中只有 remrem 个子集时，把剩下的这些数一一放进 remrem 个子集里面，如果每一次操作后有数剩下，就无解让 kk 加一。
不知道这个思路错在哪里，有没有大佬帮忙 hack 一下，或者给个 hack 数据，谢谢
CPP
const int N=1005;

int T,n;
int s[N];
unordered_set<int> ans[N];
unordered_map<int,int> cnt;
vector<pii> vec;
vector<int> A,B;

bool cmp(const pii& a,const pii& b) {
    return a.second>b.second;
}

int main() {
    // FRR("D.in");
    read(T);
    while (T--) {
        memset(s,0,sizeof(s));
        read(n);
        _rep(i,1,n) read(s[i]);
        if (n&1) puts("-1");
        else {
            cnt.clear(),vec.clear();
            _rep(i,1,n) cnt[s[i]]++;
            _iter(it,cnt) vec.emplace_back(pii{it->first,it->second});
            sort(vec.begin(),vec.end(),cmp);
            int k=1;
            while (k<=n) {
                _rep(i,1,n) ans[i].clear();
                A.clear(),B.clear();
                _rep(i,1,k) A.emplace_back(i);
                int rem=n;
                bool ok=true;
                _iter(it,vec) {
                    int a=it->first,b=it->second;
                    while (b && rem>B.size() && !A.empty()) {
                        int pos=A.back(); A.pop_back();
                        ans[pos].emplace(a); b--,rem--;
                        B.emplace_back(pos);
                    }
                    vector<int> tmp;
                    while (b && !B.empty()) {
                        int pos=B.back(); B.pop_back(); tmp.emplace_back(pos);
                        if (ans[pos].count(a)) continue;
                        ans[pos].emplace(a); b--,rem--;
                        A.emplace_back(pos); tmp.pop_back();
                    }
                    while (!tmp.empty()) B.emplace_back(tmp.back()),tmp.pop_back();
                    if (b) {
                        ok=false;
                        break;
                    }
                }
                if (!ok) {
                    k++;
                    continue;
                }
                writeln(k);
                _rep(i,1,k) {
                    writesp(ans[i].size());
                    _iter(it,ans[i]) writesp(*it);
                    putchar(10);
                }
                break;
            }
            if (k==n+1) puts("-1");
        }
    }
    return 0;
}

回复

共 3 条回复，欢迎继续交流。

正在加载回复...