HDU 3784 继续xxx定律
HDU 2578 Dating with girls(1)
做3748之前要先做xxx定律 对于一个数n，如果是偶数，就把n砍掉一半；如果是奇数，把n变成 3*n+ 1后砍掉一半，直到该数变为1为止。
当n为3时，我们在验证xxx定律的过程中会得到一个序列，3，5，8，4，2，1，将3称为关键数，5，8，4，2称为覆盖数。现在输入n个数字a[i]，根据关键数与覆盖数的理论，我们只需要验证其中部分数就可以确定所有数满足xxx定律，输出输入的n个数中的关键数。如果其中有多个关键数的话按照其输入顺序的逆序输出。
所以只需把n个数都当做关键数，一一标记a[i]的覆盖数，最后在这数列中找到未被标记的，逆序输出。
15 ms
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
int main()
{
int a[],b[],i,n,x,y,c[]; //a为原数列，b为未被标记的数列,c为标记，记得c要开很大，因为要（x*3+1）/2可能很大
while(~scanf("%d",&n)&&n)
{
memset(c,,sizeof(c)); //清零
for(i=;i<=n;i++)
scanf("%d",&a[i]);
for(i=;i<=n;i++)
{
x=a[i];
if(!c[x]) //未被标记，若已被标记那么x的覆盖数已全被标记
while(x!=)
{
if(x%==)
{
x/=;
c[x]=;
}
else
{
x=(*x+)/;
c[x]=;
}
}
}
y=;
for(i=;i<=n;i++)
if(c[a[i]]==) //未被标记
b[++y]=a[i];
for(i=y;i>=;i--) //逆序输出
printf("%d ",b[i]);
printf("%d\n",b[]);
}
return ;
}
第二题 2578
大意是：给出n个数，满足x属于n，y属于n，x+y=k的方案数。 PS；1+3和3+1算两种，2+2只算一种
刚开始想用母函数做.....后来发现k<2^31，数组开不了这么大T^T
后来是周XX说用二分= =，想想也是......
然后各种改，错了6次！！！！ 406MS
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
using namespace std;
int main()
{
int T,n,k,i,a[],l,r,sum,x,mid,y;
scanf("%d",&T);
while(T--)
{
sum=;
y=;
scanf("%d%d",&n,&k);
for(i=;i<=n;i++)
{
scanf("%d",&a[i]);
if(k%==&&a[i]==k/) //如果存在k/2这个数，则方法数+1
y=;
}
a[]=-;
sort(a+,a+n+); //排序
for(i=;i<=n;i++)
if(a[i]<(k+)/ && a[i]!=a[i-]) //先1,3；3,1只算一种，不要重复算 ①
{
x=k-a[i]; //找y
l=;
r=n+; //②
mid=(l+r)/;
while(r-l>) //③
{
mid=(l+r)/;
if(a[mid]>x)
r=mid;
if(a[mid]<x)
l=mid;
if(a[mid]==x)
break;
}
if(a[mid]==x)
sum++;
}
sum=sum*+y; //sum*2+是否有x=y这种情况
printf("%d\n",sum);
}
return ;
}
做的时候有几个易错的地方： ①②③
还有一组很难过得数据：
3 4
1 2 3
两道这样的题做了那么久.......╭(╯^╰)╮