这次比上次多A了一道，但做得太慢，rating还是降了。
Problem A Choose Two Numbers
题意：给出两个集合A,B,从A,B中分别选出元素a,b使得a+b既不属于集合A，又不属于集合B
数据范围：1<=集合A,B的大小<=100 1<=a,b<=200
我的做法是直接模拟就好了,复杂度：O(nm(n+m))
题解的做法是分别取集合A，集合B中的最大值a,b就可以了,显然此时的a+b既不属于A，也不属于B
#include <iostream>
#include <cstdio>
using namespace std;
int n,m;
int a[210],b[210];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
scanf("%d",&m);
for(int j=1;j<=m;j++)scanf("%d",&b[j]);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
int x=a[i]+b[j];
int pd1=0,pd2=0;
for(int ii=1;ii<=n;ii++)
{
if(x==a[ii])
{
pd1=1;break;
}
}
if(pd1==1)continue;
for(int jj=1;jj<=m;jj++)
{
if(x==b[jj])
{
pd2=1;break;
}
}
if(!pd1&&!pd2)
{
printf("%d %d
",a[i],b[j]);return 0;
}
}
}
return 0;
}
Problem B Make Product Equal One
给出n个数a1,a2,...,an,你可以用一点花费使得a[i]加一或减一,求最小的花费使得a1 *a2 *a3 *... *an=1。
数据范围：1<=n<=1e5 -1e9<=a[i]<=1e9
贪心，从1枚举到n，如果一个数为正，把它变为1，如果为负，变为0，同时记录负数的个数，如果为0，则花费加1，这个0因为可以变成1也可以变成-1，所以可以用来调节正负（只需要一个0就可以调节正负） 统计完以后，如果0的个数为0(即不能调节正负)，且负数的个数为奇数，则答案+=2
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int n;
int main()
{
int tot1=0;
scanf("%d",&n);
long long ans=0;
int tot2=0;
for(int i=1;i<=n;i++)
{
int x;scanf("%d",&x);
if(x<0)
{ans+=-1-x;tot1++;}
else
{
if(x==0){tot2++;ans+=1;}
else{ans+=x-1;}
}
}
if(tot1%2==1&&tot2==0)ans+=2;
cout<<ans;
return 0;
}
Problem C Almost Equal
题意：给出一个数字n，由1,2,3,...,2*n按一定顺序组成一个圆环，求出一种顺序使得以下成立：将圆环上的每n个连续数字累加起来得到一个和，将这个和写在黑板上，写完2n个和以后，使得黑板上任意两个和的差小于等于1。
举例：
当n=3的情况：
在左图中，1+4+5=10,4+5+2=11,5+2+3=10,2+3+6=11,3+6+1=10,6+1+4=11
|11-10|<=1,满足题意。
在右图中，1+5+6=12,3+2+4=9, |12-9|>=3,不满足题意
输入：一个正整数n,(1<=n<=100000)
输出：如果没有解决方案，输出“NO”
如果有解决方案，输出“YES”，下一行输出2n个正整数，表示满足题意的任意一种顺序
构造题,这道题一开始我毫无思路，再后来观察发现了一个性质，第i个数和第i+n个数的差一定小于等于1，
然后我用爆搜打了个表找规律
1: YES 1 2
2: NO
3: YES 1 4 5 2 3 6
4: NO
5: YES 1 4 5 8 9 2 3 6 7 10
6: NO
7: YES 1 4 5 8 9 12 13 2 3 6 7 10 11 14
然后规律就很明显了：
偶数输出NO
一个简单的证明是：
2n个数字的和为n*(2n+1)，如果n为偶数，那么和为偶数，能够被分成两个相等的和x
又因为第i个数和第i+n个数的差一定为1，则必定存在x+1和x-1两种和
奇数输出YES，并且奇数的排列可以从上一个奇数转化过来
比如 3:1 4 5 2 3 6
由第i个数和第i+n个数的差一定小于等于1
那么我们把3这个式子转化一下：0 1 0 1 0 1
5就是：0 1 0 1 0 1 0 1 0 1
所以就很容易构造出答案了,时间复杂度：O（n*2）
for(int i=1;i<=n;i++)//输出前n个数
{
if(i%2==1)//i是奇数
{
printf("%d ",i*2-1);
}
if(i%2==0)//i是偶数
{
printf("%d ",i*2);
}
}
for(int i=1;i<=n;i++)//输出第n+1到第2*n个数
{
if(i%2==1)
{
printf("%d ",i*2);
}
if(i%2==0)
{
printf("%d ",i*2-1);
}
}