HDU 2199：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=20576
输入一个 y ，求使得 8 ∗ x 4 + 7 ∗ x 3 + 2 ∗ x 2 + 3 ∗ x + 6 ＝ y 的 x 的值， 0 ≤ x ≤ 100 。二分查找答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| #include<cstdio>
#include<cmath>
using namespace std;
const double EPS=1e-5;
inline double f(double x){
return 8*x*x*x*x+7*x*x*x+2*x*x+3*x+6;
}
int main(){
int t;scanf("%d",&t);
while(t--){
double k;scanf("%lf",&k);
if(f(0)>k||f(100)<k){
printf("No solution!\n");
continue;
}
double l=0,r=100,m=50;
while(fabs(f(m)-k)>EPS){
if(f(m)>k) r=m;
else l=m;
m=(l+r)/2;
}
printf("%.4f\n",m);
}
return 0;
}
|
HDU 2899：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=20577
给出函数 F ( x ) = 6 ∗ x 7 + 8 ∗ x 6 + 7 ∗ x 3 + 5 ∗ x 2 − y ∗ x ，输入 y ，求函数最小值。
首先对该函数求导，然后二分查找使导函数为0的值 x 0 ，输出 F ( x 0 ) 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| #include<cstdio>
#include<cmath>
using namespace std;
const double EPS=1e-6;
double y;
inline double f(double x){
return 6*x*x*x*x*x*x*x+8*x*x*x*x*x*x+7*x*x*x+5*x*x-y*x;
}
inline double f2(double x){
return 42*x*x*x*x*x*x+48*x*x*x*x*x+21*x*x+10*x-y;
}
int main(){
int t;scanf("%d",&t);
while(t--){
scanf("%lf",&y);
double l=0,r=100,m=50;
while(fabs(f2(m))>EPS){
if(f2(m)>0) r=m;
else l=m;
m=(l+r)/2;
}
printf("%.4lf\n",f(m));
}
return 0;
}
|
HDU 1969：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=23123
给出 n 、 m ，有 n 个蛋糕， m + 1 个人，每个蛋糕都可以切开，求每人分一整块蛋糕的最大值。求出蛋糕大小总和，然后进行二分查找，对二分的值进行验证。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include<cstdio>
#include<cmath>
using namespace std;
const double EPS=1e-6;
const double PI=acos(-1);
const int maxn=10010;
int n,f;
double a[maxn];
inline double c(double r){
return PI*r*r;
}
bool ok(double x){
int sum=0;
for(int i=0;i<n;++i){
sum+=floor(a[i]/x);
}
return sum>=f+1;
}
int main(){
int t;scanf("%d",&t);
while(t--){scanf("%d%d",&n,&f);
double sum=0;
for(int i=0;i<n;++i){
scanf("%lf",&a[i]);
a[i]=c(a[i]);
sum+=a[i];
}
double l=0,r=sum,m=(l+r)/2;
while(r-l>EPS){
if(ok(m)) l=m;
else r=m;
m=(l+r)/2;
}
printf("%.4f\n",m);
}
return 0;
}
|
HDU 1905：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=40853
输入 p 、 a ，如果 p 不为素数且 a p % p = = a 输出yes，否则输出no。
2 < p ≤ 1000000000 ， 1 < a < p
首先打出0~ p ‾ ‾ √ 的素数表，然后对每个 p 进行素性测试，再用快速幂求 a p % p 判断输出。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include<cstdio>
#include<cmath>
using namespace std;
typedef long long LL;
const double EPS=1e-6;
const double PI=acos(-1);
const int maxn=100010;
int isp[maxn],pre_p;
bool np[maxn]={true,true};
void pre(){
for(int i=2;i<maxn;++i){
if(!np[i]) isp[pre_p++]=i;
for(int j=0;j<pre_p&&i*isp[j]<maxn;++j){
np[i*isp[j]]=true;
if(!(i%isp[j])) break;
}
}
return;
}
bool isprime(LL n){
double k=sqrt(n);
for(int i=0;isp[i]<=k;++i)
if(n%isp[i]==0) return false;
return true;
}
LL modexp(LL a,LL b,LL mod){
LL cur=1,tmp=a;
while(b){
if(b&1) cur=cur*tmp%mod;
tmp=tmp*tmp%mod;
b>>=1;
}
return cur;
}
int main(){
pre();
LL n,a;
while(~scanf("%lld%lld",&n,&a)&&(n||a)){
if(isprime(n)){printf("no\n");continue;}
else{
if(modexp(a,n,n)==a) printf("yes\n");
else printf("no\n");
}
}
return 0;
}
|
HDU 2648：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=18590
给出多个店的价格和每周上涨的价格，输出每周memory这家店的价格排名。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| #include<iostream>
#include<string>
#include<map>
using namespace std;
map<string,int> a;
int main(){
int n,m,k;
while(cin>>n){
a.clear();
string s;
for(int i=0;i<n;++i) cin>>s,a[s]=0;
cin>>m;
for(int i=0;i<m;++i){
int aim=0,ans=1;
for(int j=0;j<n;++j){
cin>>k>>s;
a[s]+=k;
if(s=="memory") aim=a[s];
}
for(map<string,int>::iterator it=a.begin();it!=a.end();++it)
if(it->second>aim) ++ans;
cout<<ans<<endl;
}
}
return 0;
}
|
HDU 2446：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=11791
一开始枚举前缀和再进行二分查找。结果内存超限了。
不会优化，看了结题报告才知道可以用公式做。
http://blog.csdn.net/zxy_snow/article/details/6721066
公式： ( n 3 − n ) 6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=3810779;
LL a[maxn],sum[maxn];
int main(){
for(int i=1;i<maxn;++i) a[i]=a[i-1]+i,sum[i]=sum[i-1]+a[i];
int t;scanf("%d",&t);
while(t--){
LL n;scanf("%lld",&n);
int l=0,r=0,c=0;
l=int(upper_bound(sum,sum+maxn,n)-sum);
if(sum[l-1]==n) --l;
n-=sum[l-1];
r=int(upper_bound(a,a+maxn,n)-a);
if(a[r-1]==n) --r;
c=int(n-a[r-1]);
printf("%d %d %d\n",l,r,c);
}
return 0;
}
|
HDU 2141：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=18481
给出 a 、 b 、 c 三个数组，然后输入 s ，输出是否存在 a i 、 b j 、 c k 使得 a i + b j + c k = s 。
对两个数组进行预处理，然后在另一个中枚举，在预处理后的数组中二分查找。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=550;
LL a[maxn],b[maxn],c[maxn],k[maxn*maxn];
int main(){
int l,n,m,t=0;
while(~scanf("%d%d%d",&l,&n,&m)){
for(int i=0;i<l;++i) scanf("%lld",&a[i]);
for(int i=0;i<n;++i) scanf("%lld",&b[i]);
for(int i=0;i<m;++i) scanf("%lld",&c[i]);
int pos=0;
for(int i=0;i<l;++i)
for(int j=0;j<n;++j)
k[pos++]=a[i]+b[j];
sort(c,c+m),sort(k,k+pos);
printf("Case %d:\n",++t);
int s;scanf("%d",&s);
while(s--){
LL x;scanf("%lld",&x);
bool flag=false;
for(int i=0;i<m;++i)
if(binary_search(k,k+pos,x-c[i])){flag=true;break;}
puts(flag?"YES":"NO");
}
}
return 0;
}
|
HDU 2298：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=19904
给出物体下落点的坐标和发射初始速度，求角度。物理题推公式求根。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const double g=9.8;
const double PI=acos(-1);
int main(){
int t;scanf("%d",&t);
while(t--){
double x,y,v;
scanf("%lf%lf%lf",&x,&y,&v);
double a=g*x*x,b=-2*v*v*x,c=2*v*v*y+g*x*x,dt=b*b-4*a*c;
if(dt<0){printf("-1\n");continue;}
double x1=atan((-1*b+sqrt(dt))/(2*a)),x2=atan((-1*b-sqrt(dt))/(2*a)),ans=PI/2;
if((x1<0||x1>PI/2)&&(x2<0||x2>PI/2)){printf("-1\n");continue;}
if(x1>=0&&x1<=PI/2) ans=min(ans,x1);
if(x2>=0&&x2<=PI/2) ans=min(ans,x2);
printf("%.6f\n",ans);
}
return 0;
}
|
HDU 2289：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=15721
给出一个圆台容器，给出水的体积，求水在圆台容器中的体积。
利用圆台体积公式，二分高度，输出。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include<cstdio>
#include<cmath>
using namespace std;
const double PI=acos(-1);
const double EPS=1e-7;
double GetVolume(double r,double R,double h,double H)
{
double u = h/H*(R-r) + r;
return PI/3*(r*r+r*u+u*u)*h;
}
int main(){
int t;scanf("%d",&t);
while(t--){
double r,R,H,V;scanf("%lf%lf%lf%lf",&r,&R,&H,&V);
double hl=0,hr=H,h=(hl+hr)/2;
while(hr-hl>EPS){
if(GetVolume(r,R,h,H)>V) hr=h;
else hl=h;
h=(hl+hr)/2;
}
printf("%.6f\n",h);
}
return 0;
}
|
HDU 1010：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=16336
给出一个地图，问能不能在 t 步之内从起点走到终点，不能重复走过同一个格子。
因为是恰好走到，所以是DFS的题，而不是BFS。
要进行剪枝，否则会超时。首先进行奇偶性剪枝，起点终点间的距离要和 t 的奇偶性相同，然后再查找的过程中如果当前点到终点的距离小于剩余时间就回溯。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
const int maxn=10;
const int go[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
char g[maxn][maxn];
bool vis[maxn][maxn];
int n,m,t,bx,by,ex,ey;
bool dfs(int x,int y,int cur){
if(cur==t){
if(x==ex&&y==ey) return true;
return false;
}
if(abs(x-ex)+abs(y-ey)>t-cur) return false;
for(int i=0;i<4;++i){
int a=x+go[i][0],b=y+go[i][1];
if(!vis[a][b]&&(g[a][b]=='.'||g[a][b]=='D')){
vis[a][b]=true;
if(dfs(a,b,cur+1)) return true;
vis[a][b]=false;
}
}
return false;
}
int main(){
while(~scanf("%d%d%d",&n,&m,&t)&&!(!n&&!m&&!t)){
for(int i=1;i<=n;++i){
scanf("%s",g[i]+1);
for(int j=1;j<=m;++j){
if(g[i][j]=='S') bx=i,by=j;
if(g[i][j]=='D') ex=i,ey=j;
}
}
if(abs(bx-ex)+abs(by-ey)>t||(abs(bx-ex)+abs(by-ey)+t)&1){puts("NO");continue;}
memset(vis,0,sizeof(vis));
vis[bx][by]=true;
puts(dfs(bx,by,0)?"YES":"NO");
}
return 0;
}
|
** 本文迁移自我的CSDN博客，格式可能有所偏差。 **