题目I - Osu! - HDU 5078
题目分析：最水的一道题吧，求两点间的距离和时间差值的最大比值
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std; const int MAXN = ;
const double EPS = 1e-; struct Point
{
double x, y, time;
};
double Dist(Point a, Point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int main()
{
int T; scanf("%d", &T); while(T--)
{
int i, N;
double ans = ;
Point p[MAXN]; scanf("%d", &N); for(i=; i<N; i++)
{
scanf("%lf%lf%lf", &p[i].time, &p[i].x, &p[i].y);
if(i == )
ans = Dist(p[i], p[i-]) / (p[i].time-p[i-].time);
else if(i > )
ans = max(ans, Dist(p[i], p[i-]) / (p[i].time-p[i-].time));
} printf("%.10f\n", ans);
} return ;
}
E - Hatsune Miku - HDU 5074
题目分析：把前后等于-1的情况分别讨论一下，就是一个简单的dp了.....
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
using namespace std; const int MAXN = ;
const int oo = 1e9+; int main()
{
int T; scanf("%d", &T); while(T--)
{
int i, j, k, N, M;
int dp[MAXN][MAXN], a[MAXN], val[MAXN][MAXN]; memset(dp, , sizeof(dp)); scanf("%d%d", &N, &M); for(i=; i<=M; i++)
for(j=; j<=M; j++)
scanf("%d", &val[i][j]); for(i=; i<=N; i++)
scanf("%d", &a[i]); for(i=N-; i>; i--)
{
if(a[i] == - && a[i+] == -)
{
for(j=; j<=M; j++)
for(k=; k<=M; k++)
dp[i][j] = max(dp[i][j], val[j][k]+dp[i+][k]);
}
else if(a[i] == -)
{
for(j=; j<=M; j++)
dp[i][j] = max(dp[i][j], val[j][a[i+]]+dp[i+][a[i+]]);
}
else if(a[i+] == -)
{
for(j=; j<=M; j++)
dp[i][a[i]] = max(dp[i][a[i]], val[a[i]][j]+dp[i+][j]);
}
else
dp[i][a[i]] = val[a[i]][a[i+]] + dp[i+][a[i+]];
} int ans = ; for(i=; i<=M; i++)
ans = max(ans, dp[][i]); printf("%d\n", ans);
} return ;
}
D - Galaxy - HDU 5073
题目分析：首先注意输入的是无序....（为此WA一次），题意就是让求去掉K个点后，剩余的点到中心的平方和，中心点计算是 所有数的位置和 / 剩余点数，转变成了求一些数的方差之和，然后化简公式可以发现可以直接计算出来结果，只需要遍历一遍即可（剩余点数一定是连续的，很容易求证）。设剩余点数M，剩余点数的平方和是 sum，剩余点数的位置和是cnt，那么 ans = sum - cnt * cnt / sum， 求出来最小的ans。
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
using namespace std; const int MAXN = 1e5+;
const int oo = 1e9+; double loc[MAXN]; int main()
{
int T; scanf("%d", &T); while(T--)
{
int i, N, M, K; scanf("%d%d", &N, &K); for(i=; i<N; i++)
scanf("%lf", &loc[i]);
sort(loc, loc+N); if(K + >= N)
{
printf("0\n");
continue;
} M = N - K;
double cnt=, ans, sum=; for(i=; i<M; i++)
{
cnt += loc[i];
sum += loc[i]*loc[i];
} ans = sum - cnt*cnt/M; for(i=M; i<N; i++)
{
sum = sum + loc[i]*loc[i] - loc[i-M]*loc[i-M];
cnt = cnt + loc[i] - loc[i-M]; ans = min(ans, sum-cnt*cnt/M);
} printf("%.10f\n", ans);
} return ;
}