A http://acm.hdu.edu.cn/showproblem.php?pid=5112
输入n个时刻和位置，问那两个时刻间速度最快。
解法：按照时间排序，然后依次求相邻两个之间的速度，速度=ds/dt
#include<cstdio>
#include<algorithm>
using namespace std;
const int M=1e4+;
struct G{
int t,x;
friend bool operator <(const G &a,const G &b){
return a.t<b.t;
}
}g[M];
int main(){
int t,n;
while(~scanf("%d",&t)){
int cas=;
while(t--){
scanf("%d",&n);
for(int i=;i<n;i++){
scanf("%d%d",&g[i].t,&g[i].x);
}
sort(g,g+n);
double ans=;
for(int i=;i<n-;i++){
ans=max(ans,abs(g[i].x-g[i+].x)*1.0/(g[i+].t-g[i].t));
}
printf("Case #%d: %.2f\n",cas++,ans);
}
}
return ;
}
D http://acm.hdu.edu.cn/showproblem.php?pid=5115
有n只狼排成一排，每一步消灭一只，每次消灭花费当前这只狼的a，以及左右两边最近的两只的b，ai+bleft+bright。问消灭所有狼最小花费。
解法：若暴力，可以n！，算花费取最小值。优化一点状态压缩，可以从二进制111-》000，最后dp【0】的最小值就是答案。复杂度2^n.再优化
定义dp【i】【j】表示消灭i到j最小花费。答案就是dp【1】【n】。转移时枚举i到j中最后一个被杀的，假设是k，那么转移就是
dp【i】【j】=min（dp【i】【j】，dp【i】【k-1】+dp【k+1】【j】+a【k】+b【i-1】+b【j+1】）；
#include<cstdio>
#include<algorithm>
using namespace std;
const int M=;
const int inf=0x3f3f3f3f;
int a[M],b[M],dp[M][M];
int main(){
int t,n;
while(~scanf("%d",&t)){
int cas=;
while(t--){
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=;i<=n;i++){
scanf("%d",&b[i]);
}
b[]=b[n+]=;
for(int i=;i<=n;i++){
for(int j=i;j<=n;j++){
dp[i][j]=inf;
}
}
for(int len=;len<=n;len++){
for(int i=;i+len-<=n;i++){
for(int j=i;j<i+len;j++){
int cost=a[j]+b[i-]+b[i+len];
if(j>i){
cost+=dp[i][j-];
}
if(j<i+len-){
cost+=dp[j+][i+len-];
}
dp[i][i+len-]=min(dp[i][i+len-],cost);
}
}
}
printf("Case #%d: %d\n",cas++,dp[][n]);
}
}
return ;
}
H http://acm.hdu.edu.cn/showproblem.php?pid=5119
有40个数，问选一个子集异或之和大于等于m的有多少种选法。
解法：朴素算法，暴力所有子集验证答案，2^40的时间复杂度，01背包
定义dp【i】【j】表示前n个异或和为j的情况数，则答案为dp【n】【j】，j>=m。
转移就两个 ，选或者不选。
#include<cstdio>
typedef long long LL;
const int M=;
int a[M];
LL dp[M][<<];
int main(){
int t,n,m;
while(~scanf("%d",&t)){
int cas=;
while(t--){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
}
int big=<<;
for(int i=;i<=n;i++){
for(int j=;j<big;j++){
dp[i][j]=;
}
}
dp[][]=;
for(int i=;i<=n;i++){
for(int j=;j<big;j++){
if(!dp[i][j]) continue;
dp[i+][j^a[i+]]+=dp[i][j];
dp[i+][j]+=dp[i][j];
}
}
LL ans=;
for(int j=m;j<big;j++){
ans+=dp[n][j];
}
printf("Case #%d: %I64d\n",cas++,ans);
}
}
return ;
}
I http://acm.hdu.edu.cn/showproblem.php?pid=5120
问两个圆环交的面积。
解法：容斥原理？算两个大圆面积交，扣掉左边大圆与右边小圆的交，再扣掉左边小圆与右边大圆的交，再把两个小圆的交加回来。
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const double eps=1e-;
const double pi=acos(-1.0);
struct point {
double x,y;
} c1,c2;
double Distance(point p1,point p2) {
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
point intersection(point u1,point u2,point v1,point v2) {
point ret=u1;
double t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x)) /((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x));
ret.x+=(u2.x-u1.x)*t;
ret.y+=(u2.y-u1.y)*t;
return ret;
}
void intersection_line_circle(point c,double r,point l1,point l2,point& p1,point& p2) {
point p=c;
double t;
p.x+=l1.y-l2.y;
p.y+=l2.x-l1.x;
p=intersection(p,c,l1,l2);
t=sqrt(r*r-Distance(p,c)*Distance(p,c))/Distance(l1,l2);
p1.x=p.x+(l2.x-l1.x)*t;
p1.y=p.y+(l2.y-l1.y)*t;
p2.x=p.x-(l2.x-l1.x)*t;
p2.y=p.y-(l2.y-l1.y)*t;
}
void intersection_circle_circle(point c1,double r1,point c2,double r2,point& p1,point& p2) {
point u,v;
double t;
t=(+(r1*r1-r2*r2)/Distance(c1,c2)/Distance(c1,c2))/;
u.x=c1.x+(c2.x-c1.x)*t;
u.y=c1.y+(c2.y-c1.y)*t;
v.x=u.x+c1.y-c2.y;
v.y=u.y-c1.x+c2.x;
intersection_line_circle(c1,r1,u,v,p1,p2);
}
double xmult(point p1,point p2,point p0) {
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
double area_triangle(point p1,point p2,point p3) {
return fabs(xmult(p1,p2,p3))/;
}
int same_side(point p1,point p2,point l1,point l2) {
return xmult(l1,p1,l2)*xmult(l1,p2,l2)>eps;
}
double area_circle_circle(point a,double r1,point b,double r2) {
if(r1<eps||r2<eps)return 0.0;
double temp=Distance(a,b);
point p1,p2;
double co1,co2,ret=0.0,du1,du2,z;
if(temp+eps>=r1+r2) {
return 0.0;
} else if(temp-eps<=fabs(r1-r2)) {
temp=min(r1,r2);
return pi*temp*temp;
} else {
intersection_circle_circle(a,r1,b,r2,p1,p2);
temp=Distance(p1,p2);
co1=(r1*r1*2.0-temp*temp)/(2.0*r1*r1);
du1=acos(co1);
z=(r1*r1*du1/2.0-area_triangle(p1,p2,a));
if(same_side(a,b,p1,p2)&&r1<r2)z=pi*r1*r1-z;
ret+=z;
co2=(r2*r2*2.0-temp*temp)/(2.0*r2*r2);
du2=acos(co2);
z=(r2*r2*du2/2.0-area_triangle(p1,p2,b));
if(same_side(a,b,p1,p2)&&r2<r1)z=pi*r2*r2-z;
ret+=z;
return ret;
}
}
int main() {
int t;
double r,R;
while(~scanf("%d",&t)) {
int cas=;
while(t--) {
scanf("%lf%lf%lf%lf%lf%lf",&r,&R,&c1.x,&c1.y,&c2.x,&c2.y);
printf("Case #%d: %.6f\n",cas++,area_circle_circle(c1,R,c2,R)-area_circle_circle(c1,r,c2,R)-area_circle_circle(c1,R,c2,r)+area_circle_circle(c1,r,c2,r));
}
}
return ;
}
K http://acm.hdu.edu.cn/showproblem.php?pid=5122
输入n的一个排列，问最少多少次操作能将其从小到大排好序， 每次操作可以任意选一个数，不断的往后交换直至后一个大于他停止。
解法：首先选必须要从大往小选，这样最多n次就能排好序，就是逆序的情况。因为如果选个中间的，他往后换的过程可能会遇到一个较大的使得他停下，没达到需要到的位置，从大到小选就避免了这种情况，是最优的方法。问题转化为如何统计步数。我们定义一个需求need，表示当前需要选的数，定义一个指针p，表示当前位置，指针从最后一个位置开始，需求从n开始。每次迭代，若指针的位置的值a【p】恰好等于need，则我们不需要浪费步数，数就在他应该在的位置。若a【p】小于need，说明这个位置应该放的是need，我们需要消耗一步，将前面的need移动至此，但我们不需改动数组的值，因为改动的复杂度是on的。此时我们只需要记录ans++，need--，p不动。若a【p】大于need，说明这个值已经处理过了，p--。
#include<cstdio>
#include<algorithm>
using namespace std;
const int M=1e6+;
int a[M];
int main(){
int t,n;
while(~scanf("%d",&t)){
int cas=;
while(t--){
scanf("%d",&n);
for(int i=;i<n;i++){
scanf("%d",&a[i]);
}
int ans=;
int p=n-;
for(int i=n;i>=;i--){
if(a[p]==i){
p--;
continue;
}
if(a[p]>i){
p--;
i++;
continue;
}
ans++;
}
printf("Case #%d: %d\n",cas++,ans);
}
}
return ;
}
end