noip模拟赛分组

分析：暴力分挺多，也挺好想的，个人感觉两个特殊性质没什么卵用.

对于K=1，n ≤ 1024的情况，从后往前贪心地分，如果能和上一组分在一起就分在一起，否则就再开一组，这样可以保证字典序最小.ai ≤ 2就看前面有没有2.有就不能分在一组.n ≤ 131072就不能再这样二重循环枚举了，因为两个数的和顶多只有262114 = 512^2,从1枚举到512，看看它的平方有没有被占用就可以了，就把问题从序列上转化到了值域上.

对于K=2,其实做法和K=1没什么两样，只是每一组可以分成两个对立的小组，非常像noip2010关押罪犯，加一个并查集就好了.用一个vector存每个值的兔子的位置，判断一下有没有冲突就好了.

暴力+正解：

#include <cmath>

#include <vector>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn = ;

vector <int>E[maxn *  + ];

int n, k, a[], ans[], cnt, fa[], vis[], T;

bool flag = true;

bool check2(int x)

{

    for (int i = ; i <= ; i++)

    {

        if (i * i - x >=  && vis[i * i - x])

            return false;

    }

    return true;

}

int find(int x)

{

    if (x == fa[x])

        return x;

    return fa[x] = find(fa[x]);

}

bool check(int x, int y)

{

    int t = x + y;

    int p = sqrt(t);

    if (p * p == t)

        return false;

    return true;

}

void solve1()

{

    if (n <= )

    {

        int cur = n;

        for (int i = n; i >= ; i--)

        {

            for (int j = i + ; j <= cur; j++)

            {

                if (!check(a[i], a[j]))

                {

                    ans[++cnt] = i;

                    cur = i;

                }

            }

        }

        printf("%d\n", cnt + );

        for (int i = cnt; i >= ; i--)

            printf("%d ", ans[i]);

        printf("\n");

    }

    else

        if (flag)

        {

        int cur = n;

        bool flag2 = false;

        for (int i = n; i >= ; i--)

        {

            if (flag2 && a[i] == )

            {

                ans[++cnt] = i;

                cur = i;

            }

            if (a[i] == )

                flag2 = ;

        }

        printf("%d\n", cnt + );

        for (int i = cnt; i >= ; i--)

            printf("%d ", ans[i]);

        printf("\n");

        }

        else

        {

            int cur = n;

            for (int i = n; i >= ; i--)

            {

                if (!check2(a[i]))

                {

                    for (int j = i + ; j <= cur; j++)

                        vis[a[j]] = ;

                    ans[++cnt] = i;

                    cur = i;

                }

                vis[a[i]] = ;

            }

            printf("%d\n", cnt + );

            for (int i = cnt; i >= ; i--)

                printf("%d ", ans[i]);

            printf("\n");

        }

}

void hebing(int x, int y)

{

    x = find(x), y = find(y);

    fa[x] = y;

}

bool check3(int x)

{

    for (int i = ; i <= ; i++)

    {

        if (i * i - a[x] >=  && vis[i * i - a[x]] == T)

        {

            int now = i * i - a[x];

            for (int j = ; j < E[now].size(); j++)

            {

                if (find(x) == find(E[now][j]))

                    return false;

                hebing(x + n, E[now][j]);

                hebing(x, E[now][j] + n);

            }

        }

    }

    return true;

}

void solve2()

{

    if (flag)

    {

        int flag2 = ;

        for (int i = n; i >= ; i--)

        {

            if (flag2 ==  && a[i] == )

            {

                ans[++cnt] = i;

                flag2 = ;

            }

            if (a[i] == )

                flag2++;

        }

        printf("%d\n", cnt + );

        for (int i = cnt; i >= ; i--)

            printf("%d ", ans[i]);

        printf("\n");

    }

    else

        if (n <= )

        {

        for (int i = ; i <= n * ; i++)

            fa[i] = i;

        int cur = n;

        for (int i = n; i >= ; i--)

        {

            for (int j = i + ; j <= cur; j++)

            {

                if (!check(a[i], a[j]))

                {

                    if (find(i) == find(j))

                    {

                        ans[++cnt] = i;

                        cur = i;

                    }

                    else

                    {

                        int xx = find(i + n), yy = find(j + n);

                        fa[i] = yy;

                        fa[j] = xx;

                    }

                }

            }

        }

        printf("%d\n", cnt + );

        for (int i = cnt; i >= ; i--)

            printf("%d ", ans[i]);

        printf("\n");

        }

        else

        {

            T = ;

            for (int i = ; i <= n * ; i++)

                fa[i] = i;

            for (int i = n; i >= ; i--)

            {

                if (!check3(i))

                {

                    T++;

                    ans[++cnt] = i;

                }

                    if (vis[a[i]] != T)

                    {

                        vis[a[i]] = T;

                        E[a[i]].clear();

                    }

                    E[a[i]].push_back(i);

            }

            printf("%d\n", cnt + );

            for (int i = cnt; i >= ; i--)

                printf("%d ", ans[i]);

            printf("\n");

        }

}

int main()

{

    scanf("%d%d", &n, &k);

    for (int i = ; i <= n; i++)

    {

        scanf("%d", &a[i]);

        if (a[i] > )

            flag = false;

    }

    if (k == )

        solve1();

    if (k == )

        solve2();

    return ;

}

巴特西

noip模拟赛分组

最新文章

热门文章

巴特西

noip模拟赛 分组

最新文章

热门文章

noip模拟赛分组