Codeforces Round #238 (Div. 2) D. Toy Sum
Little Chris is very keen on his toy blocks. His teacher, however, wants Chris to solve more problems, so he decided to play a trick on Chris.
There are exactly s blocks in Chris's set, each block has a unique number from 1 to s. Chris's teacher picks a subset of blocks X and keeps it to himself. He will give them back only if Chris can pick such a non-empty subset Y from the remaining blocks, that the equality holds:
"Are you kidding me?", asks Chris.
For example, consider a case where s = 8 and Chris's teacher took the blocks with numbers 1, 4 and 5. One way for Chris to choose a set is to pick the blocks with numbers 3 and 6, see figure. Then the required sums would be equal: (1 - 1) + (4 - 1) + (5 - 1) = (8 - 3) + (8 - 6) = 7.
However, now Chris has exactly s = 106 blocks. Given the set X of blocks his teacher chooses, help Chris to find the required set Y!
The first line of input contains a single integer n (1 ≤ n ≤ 5·105), the number of blocks in the set X. The next line contains n distinct space-separated integers x1, x2, ..., xn (1 ≤ xi ≤ 106), the numbers of the blocks in X.
Note: since the size of the input and output could be very large, don't use slow output techniques in your language. For example, do not use input and output streams (cin, cout) in C++.
In the first line of output print a single integer m (1 ≤ m ≤ 106 - n), the number of blocks in the set Y. In the next line output m distinct space-separated integers y1, y2, ..., ym (1 ≤ yi ≤ 106), such that the required equality holds. The sets X and Y should not intersect, i.e. xi ≠ yj for all i, j (1 ≤ i ≤ n; 1 ≤ j ≤ m). It is guaranteed that at least one solution always exists. If there are multiple solutions, output any of them.
3
1 4 5
2
999993 1000000
1
1
1
1000000
讲解:题目大意是说,范围为大于等于 1 ,小于等于 1000000 ;首先从中选出 n 个数,每个数减去 1 ,假设和为 ans ;
然后需要你从中取出 m 个数,且不能与给的数重复,用1000000减去你选出的每个数,然后求和,和也为 ans ;
然后就寻找吧,唉,这题咋这么绕呢,看着简单,好难写啊;
#include <set>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = ;
int a[N];
bool mark[N];
int main(){
int n;
cin>>n;
int s= ;
set<int>y;
vector<int>notexist;
for(int i=;i<n;i++){
scanf("%d",&a[i]);
mark[a[i]] = true;
}
for(int i=;i<=s;i++){
if(mark[i]&&!mark[s+-i]) //已经标记过了,并且差没出现过,则存入容器;
{
y.insert(s+-i);
}
if(!mark[i]&&!mark[s+-i]) //都没出现过;
notexist.push_back(i);
}
int j = ;
for(int i=; i<=s/; i++){
if(mark[i] && mark[s+-i])//说明,需要重新插入连个没有被标记的数,固定的和为 s+1 ;
{
y.insert(notexist[j]);
y.insert(s+-notexist[j]);
j++;
}
}
cout<<n<<endl;
set<int>::iterator it = y.begin();
while(it!=y.end())
{
printf("%d ",*it);
it++;
}
return ;
}
最新文章
- JavaScript语法
- easyui propertygrid 动态绑定
- noi题库(noi.openjudge.cn) 1.8编程基础之多维数组T21——T25
- 黄聪:mysql 存在该记录则更新,不存在则插入记录的sql
- WebService测试工具SoapUI
- poj 2935 Basic Wall Maze
- Unity3d—做一个年月日选择器(Scroll Rect拖动效果优化)— 无限滚动 + 锁定元素
- Sublime text 3编辑python时出现方框的解决办法
- ImageMagick 使用经验
- C# 错误:空对象不能转换为值类型
- Dynamics 365 Customer Engagement中插件的调试
- MongoDB的安全写入GetLastError
- requests简单应用
- git在本地回退
- 第32课 Linux内核链表剖析
- CQ3
- JSP面试知识
- java基础-BigInteger类常用方法介绍
- .net HttpCrawler
- springMVC源码分析--HttpMessageConverter参数read操作(二)