Wuyanru's blog
0%

[QOJ9449] New School Term

发表于 分类于 ，

我愿称之为脑瘫题。

脑瘫做不出来的题。

题目链接。

题意

现在有 个学生，需要给他们分成两个班，每个班恰好 人。

现在有 个条件，第 个条件是，第 个学生和第 个学生不应分在同一个班，如果不满足条件，将会带来 的不满意度。

构造一组方案，使总不满意度最小。

，。

题解

首先一定是从后往前按位贪心，尽可能的满足条件，问题在于如何判断能否让两个人分开。

假设没有两个班个需要 人的条件，那么直接就是一个种类并查集，随便并一并就好了。

再加上这个条件，就要额外考虑，并掉两个连通块之后，能否再拼出 人的班级出来了。

设 表示考虑了前 组人，能否使得总人数为 ，每一次判断能否合并的时候，都跑一遍 dp 看，这样直接做复杂度是 的。

考虑使用待删背包之类的技巧，使用 表示，按照当前的分组，选出 人的方案数对一个大质数 取模的结果。

假设当前我们要判断两组人 能否合并，我们就现在背包里把他们扬了，再加入一组 ，然后看 是否有值就好了，这样做复杂度是 的。

还是没有办法通过，因为我们对于每一次询问，都需要 的时间来 check，如果次次都不能合并，这就寄了。

考虑这么一个事情，如果 不能合并成 ，我们就可以直接给他合并成 ，这样的话我们一共只会进行至多 次 check，与 次 dp 数组的更改，这样就很对了。

时间复杂度 。

代码

没写按秩合并，复杂度是 的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline ll lread()
{
    ll s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
const ll mod=114514191981011453ll;
int ans[20001];
ll dp[10001];
ll fp[10001];
ll tp[10001];
int siz[20001];
int fa[20001];
int x[1000001];
int y[1000001];
int n,m;
inline void Add(ll &a,ll b)
{
    a+=b;
    if(a>=mod) a-=mod;
}
inline void run(ll *dp,ll *fp,int x,int y)
{
    memset(fp,0,sizeof(ll)*(n+1));
    for(int i=0;i<=n;i++)
    {
        if(i>=x) Add(fp[i],dp[i-x]);
        if(i>=y) Add(fp[i],dp[i-y]);
    }
}
inline void unr(ll *dp,ll *fp,int x,int y)
{
    memset(dp,0,sizeof(ll)*(n+1));
    if(x>y) swap(x,y);
    if(x==y)
    {
        for(int i=n;i>=x;i--)
        {
            if(fp[i]&1) dp[i-x]=(fp[i]+mod)/2;
            else dp[i-x]=fp[i]/2;
        }
    }
    else
    {
        for(int i=n;i>=y;i--)
        {
            ll val=fp[i];
            Add(val,mod-dp[i-x]);
            dp[i-y]=val;
        }
    }
}
inline int find(int num)
{
    if(fa[num]==num) return num;
    return fa[num]=find(fa[num]);
}
inline void merge(int x,int y)
{
    x=find(x),y=find(y);
    fa[x]=y,siz[y]+=siz[x];
}
inline void output()
{
    for(int i=1;i<=2*n;i++) printf("i=%d : fa=%d fsiz=%d\n",i,fa[i],siz[find(i)]);
    for(int i=0;i<=n;i++) printf("%lld%c",dp[i]," \n"[i==n]);
}
int main()
{
    n=read()*2,m=read();
    for(int i=1;i<=2*n;i++) fa[i]=i,siz[i]=i<=n;
    for(int i=1;i<=m;i++) x[i]=read(),y[i]=read();

    dp[0]=1;
    for(int i=1;i<=n;i++)
    {
        run(dp,fp,1,0);
        memcpy(dp,fp,sizeof(dp));
    }
    // output();
    for(int i=m;i;i--)
    {
        if(find(x[i])==find(y[i])) continue;
        if(find(x[i]+n)==find(y[i])) continue;

        int A=siz[find(x[i])],B=siz[find(x[i]+n)];
        int C=siz[find(y[i])],D=siz[find(y[i]+n)];

        unr(fp,dp,A,B);
        unr(tp,fp,C,D);
        run(tp,dp,A+D,B+C);

        if(dp[n/2]) merge(x[i],y[i]+n),merge(x[i]+n,y[i]);
        else run(tp,dp,A+C,B+D),merge(x[i],y[i]),merge(x[i]+n,y[i]+n);
    }

    int rest0=n/2;
    for(int i=1;i<=n;i++) if(find(i)==i)
    {
        if(find(i+n)<i) continue;
        int A=siz[i],B=siz[find(i+n)];

        unr(fp,dp,A,B),memcpy(dp,fp,sizeof(dp));
        if(A<=rest0&&dp[rest0-A]) ans[find(i+n)]=1,rest0-=A;
        else rest0-=B,ans[find(i)]=1;
    }

    for(int i=1;i<=n;i++) printf("%d",ans[find(i)]);
    return 0;
}