Codeforces Round #238 (Div. 1)__Toy Sum

时间：2014-03-23 20:05:39 收藏：0 阅读：406

题目大意：
1到1e6数字中，有A、B两个集合，A中的每个数减一的和与B中数乘以负一加1e6(1e6 - x)的和相同。现在给n个A集合中的数，求B的数（任意一组即可）
思路：
比赛时看大家都是很快1A，差不多想到了是找规律的构造。苦于一直想不到方法。。。。
这个题元素之间是没有联系的（乍一看），那么如果可以对于每个元素都能找到等价的就可以。先想到的自然是分拆成两个数的和，可是也不能保证一定能分，如果不能分拆，那么就麻烦了。所以应该换一种思路：找到每个元素的“替代品”。
对于数x，计算和的时候变成x-1，对应的B中的数应该是1e6-x+1，所以如果这个数不在A中就可以等价了。问题来了，如果这个数存在了呢？考虑一下，这个时候我们有数x和数1e6-x+1，这两个数是有联系的（打破了一开始的判断），那么这时候就应该把有联系的数放在一起考虑。他俩的和应该是1e6+1，这里就应该敏感了，与x是无关的！！！也就是说，这样的数的和是一定的，那么这一对数就可以用其他类似的数对（一个为x，一个为1e6-x+1）来代替。然后要考虑，这个代替是否一定成立呢？显然，给定的数只有5 * 1e5，最多有2.5 * 1e5对这样的，肯定会剩下而且够用。到此，分析结束。
关键：
认识到是用构造法；分析出每个数如何找到对应的数；对于特殊的数对如何处理

const int MAXN = 1000010;

int vis[MAXN];
const int MID = 1000001;

int main()
{
//    freopen("in.txt", "r", stdin);
    int n, t;
    while (~RI(n))
    {
        CLR(vis, 0);
        REP(i, n)
        {
            RI(t);
            vis[t]++;
        }
        vector<int> ans;
        int need = 0;
        FE(i, 1, 1000000)
        {
            if (vis[i])
            {
                if (!vis[MID - i])
                    ans.push_back(MID - i);
                else
                    need++;
            }
        }
        need /= 2;

        int len = ans.size();
        REP(i, len)
            vis[ans[i]]++;
        for (int i = 1; need && i <= 1000000; i++)
        {
            if (!vis[i] && !vis[MID - i])
            {
                need--;
                ans.push_back(i);
                ans.push_back(MID - i);
            }
        }
        if (need)
            ans.push_back(1000000);
        len = ans.size();
        WI(len);
        REP(i, len)
        {
            if (i != 0)
                putchar(‘ ‘);
            printf("%d", ans[i]);
        }
        puts("");
    }
    return 0;
}

Codeforces Round #238 (Div. 1)__Toy Sum,布布扣,bubuko.com

原文：http://blog.csdn.net/wty__/article/details/21873913