HDU 2011 菜鸟杯
A:该题写了很久，一直TLE，主要是枚举到n/2时间复杂度实在太高了，其实嘛，这道题就是因式分解，所以就是i*i=n，也就是sqrt（n）
#include<stdio.h>
#include<math.h>
int main()
{
int n,T,i;
int a,b;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(i=sqrt(1.0*n); i>=1; i--)
{
if(n%i==0)
{
a=i;
b=n/i;
if(a<b) {int t=a;a=b;b=t;}
if((a+b)%2==0 && (a-b)%2==0 && a!=b)//拆分后，组成二元一次方诺
{
break;
}
}
}
if(i==0) printf("-1\n");
else printf("%d\n",(a-b)/2);
}
return 0;
}B:纯水
#include<stdio.h>
#include<math.h>
int Is_what(char ch)
{
if(ch>='0' && ch<='9') return 1;
return 0;
}
int main()
{
char str[10010];
int i,j,ans,T;
while(scanf("%d",&T)!=EOF)
{
scanf("%s",str);
for(i=0; str[i]; i+=5)
{
ans=0;
for(j=i; j<5+i; j++)
{
int t=Is_what(str[j]);
if(t==1) ans+=pow(2,4-j+i);
}
printf("%c",ans+65);
}
printf("\n");
}
}C：给两个炮台和许多个敌人的坐标，问两个炮台的射程分别是多少的时候，可以既覆盖所有敌点，又花费最少（R1^2+R2^2）
错误思路：刚开始是依次求出每个点到炮台disA和disB，比较两个大小，若A>B，则将该点赋予B炮台，这种思路是错的，比如AB距离为100，他们中点旁边各有1个敌人，根据这种思路得到的距离为49*49 + 49 * 49 = 4802，而如果只用A，则只需要51 * 51 = 2601.所以这种思路是错误的。（这种反例数据很好）。
正确思路：将所有敌人距离A的距离从大到小排序，然后枚举A的半径，则B的半径就是A无法覆盖的点中距离B最远的距离。然后用一个变量维护A和B距离的最小值即可。
#include<stdio.h>
#include<algorithm>
using namespace std;
const int MAXN=100010;
struct PNT
{
int x,y;
int disA,disB;
}p1,p2,pnt[MAXN];
int _dist(PNT a,PNT b)
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
bool cmp(PNT a,PNT b)
{
return a.disA>b.disA;
}
int main()
{
int T,n;
int i;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d%d",&p1.x,&p1.y,&p2.x,&p2.y);
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d%d",&pnt[i].x,&pnt[i].y);
pnt[i].disA=_dist(p1,pnt[i]);
pnt[i].disB=_dist(p2,pnt[i]);
}
sort(pnt,pnt+n,cmp);
int res=pnt[0].disA;
int ans=0;
/*由于A已经排序了，所以没有涉及的地方就是没有覆盖的，因为他必定比临界的那点要大
所以可以直接查找那些没涉及的B的最大值（当前的点，以前最大的记录点）
*/
for(i=1;i<n;i++)
{
ans=max(ans,pnt[i-1].disB);
res=min(res,ans+pnt[i].disA);
}
//A一个点都没有涉及
ans=max(pnt[n-1].disB,ans);
res=min(res,ans);
printf("%d\n",res);
}
}D:
E:水题ABC分别代表不同的值，给你几窜ABC求几窜中的一窜总和最小的
还是wa的找不出来错误，错在当把ABC的记过预处理的，数组ch必须定义成int而不是char
#include<stdio.h>
#include<algorithm>
int main()
{
char ch[100];
int n,B,D,f,F;
char str[1000000];
while(scanf("%d",&n)!=EOF)
{
scanf("%d%d%d%d",&B,&D,&f,&F);
int res=10000000;
getchar();
while(n--)
{
gets(str);
int ans=0;
for(int i=0; str[i]; i++)
{
if(str[i]=='A') ans+=B+D+f;
if(str[i]=='B') ans+=B*2+D*2+F;
if(str[i]=='C') ans+=B*3+D*3+F*2;
}
if(res>ans) res=ans;
}
printf("%d\n",res);
}
return 0;
}F:这个坑爹。。。。规律完全看不出来，看解题报告后恍然大悟，
S(1)=1, S(2)=11,（1个1） S(3)=21,（2个1） S(4)=1211,（1个2，1个1） S(5)=111221,（1个1，1个2，2个1） S(6)=312211,
规律一出来 ，纯水
#include<stdio.h>
#include<string.h>
int num[50];
char str[35][5000];
int Find(int t,char ss[])
{
int i;
for(i=t;ss[i];i++)
{
if(ss[i]!=ss[i+1]) return i;
}
return i;
}
void init()
{
strcpy(str[1],"1");
// printf("%s\n",str[1]);
num[1]=1;
for(int i=2;i<=30;i++)
{
int cas=0;
for(int j=0;str[i-1][j];j++)
{
int t=Find(j,str[i-1]);
int cnt=t-j+1;
str[i][cas++]=cnt+'0';
str[i][cas++]=str[i-1][j];
j=t;
}
str[i][cas]='\0';
// printf("%s\n",str[i]);
num[i]=strlen(str[i]);
}
}
int main()
{
int n;
init();
while(scanf("%d",&n)!=EOF)
{
if(n==0) break;
printf("%d\n",num[n]);
}
return 0;
}G:这道题是我认为，新生赛中出的最好的，并没涉及算法，但是思路真的很不错，开阔了思维，隐藏的信息十分巧妙
现在给出我的理解，将所有数全部转换成二进制，进行一位一位的判断。
现假设8个数字分别为x1，x2。。。x8，总和为sum。
当8个数字的相同位上的数的1有奇数个（需考虑进位），那么无论这8个数字相加后依旧是奇数，所以此时若判断sum的同位置就可以，若sum的该位为0，则m的该位1，
若sum的该位0，则sum的该位为0;(假若进位的数是奇数，该位的1也是奇数，相加后是偶数，则说明该位的1本就是偶数个的)
由此推断：
1的个数偶数，sum同位为0，m的同位置为0，1的个数是1
sum同位为0，m的同位置为1，0的个数是1
奇数，sum同位为0，m的同位置为1，0的个数是1
sum同位为0，m的同位置为0，1的个数是1
关键是进位：若m为1,则进位的1，是1^其同一位置的0得到的，8-p就是0的个数
#include<stdio.h>
#include<math.h>
int main()
{
int T,i,sum;
int x[9];
int ans[100];
scanf("%d",&T);
while(T--)
{
for(i=0; i<8; i++)
scanf("%d",&x[i]);
scanf("%d",&sum);
int p;//记录有几个1
int t=0;//记录需要进位的
int cas=0;
int flag;
while(1)
{
flag=0;
p=0;
for(i=0; i<8; i++)
{
if(x[i]&1)
{
p++;
}
if(x[i]!=0) flag=1;
x[i]>>=1;
}
if(flag==0 && t==0) break;
if((t+p)%2==0)//偶数
{
if(sum&1)//sum为1，则sum该位为1
{
t=(8-p+t)/2;
ans[cas++]=1;
}
else
{
t=(t+p)/2;
ans[cas++]=0;
}
}
else
{
if(sum&1)
{
t=(t+p)/2;
ans[cas++]=0;
}
else
{
t=(t+8-p)/2;
ans[cas++]=1;
}
}
sum>>=1;
}
int m=0,res=1;
//printf("%d\n",cas);
for(i=0; i<cas; i++)
{
m+=res*ans[i];
res*=2;
}
printf("%d\n",m);
}
return 0;
}H:求a窜中最多含多少个b窜，暴力~~~~
#include<stdio.h>
#include<string.h>
const int MAXN=1000010;
char str1[MAXN],str2[10];
int Find(int t)
{
int cas=0,i;
for(i=0;str2[i];i++)
{
if(str2[i]!=str1[t++]) return -1;
}
return i;
}
int main()
{
int T;
int i,t;
scanf("%d",&T);
while(T--)
{
int ans=0;
scanf("%s%s",str1,str2);
int len2=strlen(str2);
for(i=0;str1[i];i++)
{
if(str1[i]==str2[0])
{
t=Find(i);
if(t==len2)
{
ans++;
i+=t-1;
}
}
}
printf("%d\n",ans);
}
return 0;
}I:这道题也很好，通过这道题，让我明白了，原来二分还可以这么用，数组a的下标记录的结果，而数组a的结果记录的输入值，是不是这个就是反哈希思路~~，二分也不单简简单 单的就是用”==“break，也可以让二分完。
还有就是memset不要乱用，造成MLE，由于hash数组开的大了也造成MLE，所以说一定要仔细分析题目，
#include<stdio.h>
#include<string.h>
const int MAXN=10000000;
int a[MAXN],hash[10];
int tot;
void init()
{
int i,j;
tot=1;
for(i=1;i<=10000000;i++)
{
j=i;
memset(hash,0,sizeof(hash));
while(j)
{
if(hash[j%10]) break;
hash[j%10]=1;
j/=10;
}
if(j==0) a[tot++]=i;
}
}
int main()
{
int n,res;
init();
while(scanf("%d",&n)!=EOF)
{
if(n<1) {printf("0\n"); continue;}
int begin=1;
int end=tot-1;
int mid;
while(begin<=end)
{
mid=(begin+end)/2;
if(a[mid]<n)
{
res=mid;
begin=mid+1;
}
else end=mid-1;
}
printf("%d\n",res);
}
return 0;
}J: