当前位置：首页 > news >正文

HDU之算法初步

news 2025/6/6 12:21:35

1.排序题与sort函数

sort函数在C++的algorithm库
sort(addr1, addr2, cmp);

>表示从大到小排序，<表示从小到大排序


struct S {int a, b, c;
};
bool cmp(S s1, S s2) {if (s1.a != s2.a) return s1.a > s2.a;else if (s1.b != s2.b) return s1.b > s2.b;else if (s1.b != s2.b) return s1.b > s2.b;
}
S ss[n];
sort(ss, ss+n, cmp);

HDU1225 Football Score

#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;
struct node
{char name[150];int s1;int s2;int s3;
}a[50000];
bool cmp(node a,node b)
{if(a.s1!=b.s1)return a.s1>b.s1;if(a.s2!=b.s2)return a.s2>b.s2;if(a.s3!=b.s3)return a.s3>b.s3;return a.name<b.name;
}
int t;
int find(char str[])  
{if(t==-1){strcpy(a[0].name,str);t=0;return t;}for(int i=0;i<=t;i++)if(strcmp(a[i].name,str)==0)return i;t++;strcpy(a[t].name,str);return t;
}
int main(){int n,x,y,p,q;char str1[100],str2[40],str3[100];while(~scanf("%d",&n)){t=-1;memset(a,0,sizeof(a));for(int i=0;i<n*(n-1);i++){scanf("%s",str1);x=find(str1);scanf("%s",str2);scanf("%s",str3);y=find(str3);scanf("%d:%d",&p,&q);a[x].s3+=p;a[y].s3+=q;a[x].s2+=p-q;a[y].s2+=q-p;if(p>q){a[x].s1+=3;}else if(p==q){a[x].s1+=1;a[y].s1+=1;}else{a[y].s1+=3;}}sort(a,a+n,cmp);for(int i=0;i<n;i++){printf("%s %d\n",a[i].name,a[i].s1);}printf("\n");}return 0;
}

2.Hash标记

HDU1496 Equations （方程匹配）

#include <iostream>
using namespace std;
int Hash[2000010];
int main(){int a,b,c,d,sum;while(~scanf("%d%d%d%d",&a,&b,&c,&d)){if((a>0&&b>0&&c>0&&d>0)||(a<0&&b<0&&c<0&&d<0)){printf("0\n");continue;}else{memset(Hash,0,sizeof(Hash));for(int x1=1;x1<=100;x1++)for(int x2=1;x2<=100;x2++)Hash[1000000+a*x1*x1+b*x2*x2]++;sum=0;for(int x3=1;x3<=100;x3++)for(int x4=1;x4<=100;x4++)sum+=Hash[1000000-(c*x3*x3+d*x4*x4)];printf("%d\n",sum*16);}}return 0;
}
//（1）将方程式写成a * x1 * x1 + b * x2 * x2 = - （c * x3 * x3 + d * x4 * x4）的形式； 
//（2）使用hash命名数组会编译错误，所以命名为Hash； 
//（3）50 * 100 *100 + 50 *100 *100=1000000，所以hash数组至少要2000000； 
//（4）a * x1 * x1 + b * x2 * x2最小为-1000000，所以数组要加上1000000的偏移量，以保证数组下标最小为0，而不是负数； 
//（5）因为正负号不同不影响平方的效果，所以只枚举正数，最后乘以2的4次方（16），表示正负不同的组合。

3.二分

二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。

每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。

int binarySearch(int A[],int left,int right,int x){int mid;while(left<=right){mid=(right+left)/2;//避免溢出可写成：mid=left+(right-left)/2;if(A[mid]==x)return mid;else if(A[mid]>x)right=mid-1;else left=mid+1;}return -1;
}

1.查找第一个值等于给定值的元素

//(left,right],初值[0,n]
int solve(int A[],int left,int right,int x){int mid;while(left+1<right){mid=(right+left)/2;//避免溢出：mid=left+(right-left)/2;if(A[mid]>x条件成立)right=mid;elseleft=mid+1;}return left;//夹出来
}

2.查找第一个大于等于给定值的元素

//[left,right],初值[0,n]
int lower_bound(int A[],int left,int right,int x){int mid;while(left<right){mid=(right+left)/2;//避免溢出：mid=left+(right-left)/2;if(A[mid]>=x)right=mid;elseleft=mid+1;}return left;//夹出来
}

3.查找第一个大于给定值的元素

//[left,right],初值[0,n]
int upper_bound(int A[],int left,int right,int x){int mid;while(left<right){mid=(right+left)/2;//避免溢出：mid=left+(right-left)/2;if(A[mid]>x)right=mid;elseleft=mid+1;}return left;//夹出来
}

HDU4145 The Special Number

4.快速幂

快速幂的迭代写法

typedef long long LL;
LL binaryPow(LL a,LL b,LL m){LL ans=1;while(b>0){if(b&1){//如果b的二进制末尾为1  或:if(b%2==1)ans=ans*a%m;}a=a*a%m;b>>=1;//b的二进制右移一位，即b=b>>1 或 b=b/2}return ans;
}

HDU6027 Easy Summation

#include<iostream>
using namespace std;
long long mod=1e9+7;
long long fun(long long a,int b)
{long long res=1;while(b>0){if(b%2==1)res=(res*a)%mod;a=(a*a)%mod;b=b/2;}return res;
}
int main()
{int T;scanf("%d",&T);while(T--){long long ans=0;int n,k;scanf("%d%d",&n,&k);for(int i=1;i<=n;i++){ans=(ans+fun(i,k))%mod;	}	printf("%lld\n",ans);}
}//在很多算法题中，大的数值结果题目都要求对1e9+7取模。
//原因如下: 
//1. 1e9+7是10位最小质数。 
//2. 1e9+7相加不爆int(-2147483648～2147483647:10位)，
//相乘不爆long long(-9223372036854775808~9223372036854775807:十九位)，
//大数mod 1e9+7可以保证数值在永远在int内。
//大数相乘的时候，因为(a∗b)%c=((a%c)∗(b%c))%c，

5.贪心

HDU1735 字数统计（作业本最小污浊字数）

#include<iostream>
#include<algorithm>
using namespace std;
int a[110],b[10010];
int main(){int N,L,M,ed;while(~scanf("%d%d%d",&N,&L,&M)){int ans=0;int num=0;//上一行尾端的空白数int ed=0;//可能作为段尾的行数for(int i=1;i<=N;i++){for(int j=1;j<=L;j++){scanf("%d",&a[j]);if(a[j]==0)ans+=1;}if(a[1]==0&&a[2]==0)b[++ed]=num;//上一行作为尾端for(int j=L;j>=1;j--){if(a[j]==1){num=L-j;//算出这一行尾端的空白字数break;}}}ans-=2*M;//去掉段首ans-=num;//去掉尾段尾sort(b+1,b+ed+1);//至少... 故要排序for(int i=ed;i>=ed-M+2;i--)ans-=b[i];printf("%d\n",ans);}return 0;
}