蒟蒻求调

huangrenheluogu @ 2023-11-20 14:15:29

by huangrenheluogu @ 2023-11-20 14:15:47

#include<bits/stdc++.h>
using namespace std;
const int N = 105;
int n, a[N][N], x = 1, fir[N], nxt[N * N], son[N * N], tot, col[N], cnt, f[N], ans = 105, ans1[N], ans2[N], cnt1, cnt2;
bool vis[N], dp[N][N], g[N][N];
vector<int>b[N][2], c[2];
inline void add(int x, int y){
    nxt[++tot] = fir[x];
    fir[x] = tot;
    son[tot] = y;
}
inline void dfs(int x){
    vis[x] = 1;
    b[tot][col[x]].push_back(x);
    if(col[x]) cnt++;
    else cnt--;
    for(int i = fir[x]; i ; i = nxt[i]){
        if(vis[son[i]]){
            if(col[son[i]] != col[x] ^ 1){
                printf("No solution");
                exit(0);
            }
            continue ;
        }
        col[son[i]] = col[x] ^ 1;
        dfs(son[i]);
    }
}
inline void query(int x, int y){
    if(x == 0) return ;
    if(g[x][y] == 1){
        for(auto i : b[x][1]) ans1[++cnt1] = i;
        for(auto i : b[x][0]) ans2[++cnt2] = i;
        y -= f[x];
    }
    else{
        for(auto i : b[x][0]) ans1[++cnt1] = i;
        for(auto i : b[x][1]) ans2[++cnt2] = i;
        y += f[x];
    }
    query(x - 1, y);
}
inline void print(int x){
    for(auto j : b[x][0]) printf("%d ", j);
    printf("\n");
    for(auto j : b[x][1]) printf("%d ", j);
    printf("\n\n");
}
int main(){
    scanf("%d", &n);
    if(n == 1){
        cout << "No solution";
        return 0;
    }
    for(int i = 1; i <= n; i++, x = 1){
        scanf("%d", &x);
        while(x){
            a[i][x] = 1;
            scanf("%d", &x);
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = i + 1; j <= n; j++){
            if(!(a[i][j] && a[j][i])){
                add(i, j);
                add(j, i);
            }
        }
    }
    tot = 0;
    for(int i = 1; i <= n; i++){
        if(!vis[i]){
            cnt = 0;
            tot++;
            dfs(i);
            if(cnt < 0){
                c[1].clear();
                c[0].clear();
                for(auto j : b[tot][1]) c[1].push_back(j);
                for(auto j : b[tot][0]) c[0].push_back(j);
                b[tot][0].clear(), b[tot][1].clear();
                for(auto j : c[0]) b[tot][1].push_back(j);
                for(auto j : c[1]) b[tot][0].push_back(j);
                cnt = -cnt;
            }
            f[tot] = cnt;
        }
    }
    dp[0][0] = 1;
    for(int i = 1; i <= tot; i++){
        for(int j = f[i]; j <= n; j++){
            if(dp[i - 1][j - f[i]] == 1){
                g[i][j] = 1;
                dp[i][j] = 1;
                if(i == tot) ans = min(ans, j);
            }
        }
        for(int j = 0; j <= n - f[i] + 1; j++){
            if(dp[i - 1][j + f[i]] == 1){
                g[i][j] = 0;
                dp[i][j] = 1;
                if(i == tot) ans = min(ans, j);
            }
        }
    }
    query(tot, ans);
    sort(ans1 + 1, ans1 + cnt1 + 1);
    sort(ans2 + 1, ans2 + cnt2 + 1);
    printf("%d ", cnt1);
    for(int i = 1; i <= cnt1; i++) printf("%d ", ans1[i]);
    printf("\n%d ", cnt2);
    for(int i = 1; i <= cnt2; i++) printf("%d ", ans2[i]);
    return 0;
}

by huangrenheluogu @ 2023-11-20 18:05:08

这道题可以开放数据下载吗？

by huangrenheluogu @ 2023-11-20 18:36:24

@RSY @Maxmilite @离散小波变换° @feecle6418 @minstdfx @_bzy @realskc

管理们，可以开放本题数据吗？

谢谢。

管理员名单 里没有 11 月的，就先 @ 10 月的了，麻烦了。

（NOIP 过去几天了，应该可以 @ 了吧）