对称性——cf405d

以后碰到这种题就应该往对称性想：设x的对称数x‘是1e6-x+1

对于任意一组对称数x+x'-2=1e6-1,2e6-(x+x')=1e6-1,即X集合Y集合同时加上任意一组对称数都是可以的

枚举每个xi,如果其对称数1e6-xi+1不在集合X中，那么在Y中添加这个对称数即可，正确性显然

反之如果对称数在集合X中，则X集合的和多了1e6，我们再去找一组不在集合中的对称数，将这组数加入集合Y中，等价于Y集合的数和也多了1e6

#include <bits/stdc++.h>

#define maxn 2000010

#define maxm 110

using namespace std;

int S, n, m, a[maxn], vis[maxn], ans[maxn], v[maxn];

inline int read(){

    int s = , w = ;

    char c = getchar();

    for (; !isdigit(c); c = getchar()) if (c == '-') w = -;

    for (; isdigit(c); c = getchar()) s = (s << ) + (s << ) + (c ^ );

    return s * w;

}

int main(){

    S = , n = read();

    for (int i = ; i <= n; ++i) a[i] = read(), v[a[i]] = ;

    for (int i = , j = ; i <= n; ++i){

        if (vis[a[i]]) continue;

        if (!v[S +  - a[i]]) ans[++m] = S +  - a[i]; else{

            while (v[j] || v[S +  - j]) ++j;

            ans[++m] = j, ans[++m] = S +  - j;

            vis[S +  - a[i]] = ;

            ++j;

        }

    }

    printf("%d\n", m);

    for (int i = ; i <= m; ++i) printf("%d ", ans[i]);

    return ;

}

巴特西

对称性——cf405d

最新文章

热门文章