默认分类 – 第 67 页

[ZOJ3340 The Stars My Destination]海伦公式和勾股定理的妙用

【题目大意】
空间坐标系中(x,y,z)中：
给出一个射线和N个点。
求出和这个射线最远的点和射线的距离是多少。
【算法分析】
首先围观一下点到直线的距离怎么搞？
+_+。。。直接弄垂线不好搞啊。
于是弄一个三角形面积。再除以底边的长度，就可以得到高了。
面积可以用海伦公式。这样就什么都不需要了，只需要点与点之间的长度计算。

然后再YY一下射线，如果是高飘出射线，那个特定的角就会变钝角。（划一下就可以知道哪个角）
然后利用勾股定理a^2+b^2#include #include #include #include const int N=100005;
struct Point{int x,y,z;}pl[N],p1,p2;
int n;
double ans;

void input(){
scanf("%d%d%d",&p1.x,&p1.y,&p1.z);
scanf("%d%d%d",&p2.x,&p2.y,&p2.z);
for (int i=1;i<=n;i++)
scanf("%d%d%d",&pl[i].x,&pl[i].y,&pl[i].z);
}

inline double Sqr(double x){return x*x;}
inline double max(double x,double y){
if (x>y) return x;
else return y;
}
inline double min(double x,double y){
if (x else return y;
}

inline double dis(Point A,Point B){
return sqrt(Sqr(A.x-B.x)+Sqr(A.y-B.y)+Sqr(A.z-B.z));
}

inline void swap(double &x,double &y){
double tmp=x; x=y; y=tmp;
}

inline bool DunJiao(double a,double b,double c){
if (Sqr(a)+Sqr(b) return false;
}

void solve(){
int i,j,k;
double p,S,a,b,c,now;
ans=0;
for (i=1;i<=n;i++){
a=dis(p1,pl[i]); b=dis(p1,p2); c=dis(p2,pl[i]);
p=0.5*(a+b+c);
S=sqrt(p*(p-a)*(p-b)*(p-c));
now=min(a,c);
if (!DunJiao(a,b,c))
now=min(now,S*2/b);
ans=max(ans,now);
}
printf("%.2lfn",ans);
}

int main(){
while (scanf("%d",&n)!=EOF){
input();
solve();
}
}

[ZOJ3335 Filtering]矩阵维护类型的题目

【题目大意】
给出一个a[i][j]。
然后ans[i][j]=以(i , j)为中心的一个m*n的矩形内所有数字的中位数。
如果m*n超出了边框。那么ans[i][j]=a[i][j]。
0<=a[i][j]<256。
【算法分析】
首先，注意到键值的范围为[0，255]。
我们容易想到弄一个桶来维护。或许桶里还可以搞个线段树什么的。
然后显然ans[i][j]和ans[i][j-1]所包含的数里，只有两列不同。于是我们可以在O(p*q*n)里维护一个所包含数字的桶。
有这个桶呢，暴力找中位数，那么复杂度是O(p*q*(n+256))。
但是依然MS可能超时。
于是我们可以加入一个优化：
ans[i][j]和ans[i][j-1]一般相差不是很远。
那么我们就在ans[i][j]的基础上，先前滑动和向后滑动，一般而言就可以很快出解了。
【时间复杂度】O(p*q*(n+256)) 一般达不到。
【CODE】
#include #include #include const int N=505;
int a[N][N],b[N][N],T[256];
int m,n,p,q,L;

void input(){
int i,j;
for (i=1;i<=m;i++)
for (j=1;j<=n;j++)
scanf("%d",&a[i][j]);
scanf("%d%d",&p,&q);
L=p*q/2+1;
}

int Cal(int x,int y){
int i,j;
for (i=x-p;i<=x+p;i++)
for (j=y-q;j<=y+q;j++)
T[a[i][j]]++;
j=0;
for (i=0;i<256;i++){
j+=T[i];
if (j>=L) return i;
}
}

void solve(){
p/=2; q/=2;
int i,j,k,pre,next;
for (i=1;i<=m;i++)
for (j=1;j<=n;j++)
b[i][j]=-10000;
bool first;
for (i=1+p;i+p<=m;i++){
memset(T,0,sizeof(T));
first=true;
for (j=1+q;j+q<=n;j++)
if (first){
first=false;
b[i][j]=Cal(i,j);
pre=0; next=0;
for (k=0;k for (k=b[i][j]+1;k<256;k++) next+=T[k];
}else{
int &t=b[i][j];
t=b[i][j-1];
for (k=i-p;k<=i+p;k++){
T[a[k][j-q-1]]–;
if (a[k][j-q-1] if (a[k][j-q-1]>t) next–;
T[a[k][j+q]]++;
if (a[k][j+q] if (a[k][j+q]>t) next++;
}
while (pre>=L){
next+=T[t];
t–;
pre-=T[t];
}
while (next>=L){
pre+=T[t];
t++;
next-=T[t];
}
}
}
}

void output(){
for (int i=1;i<=m;i++)
for (int j=1;j<=n;j++){
if (b[i][j]<0) b[i][j]=a[i][j];
printf("%d",b[i][j]);
if (j==n) putchar(‘n’);
else putchar(‘ ‘);
}
putchar(‘n’);
}

int main(){
while (scanf("%d%d",&m,&n)!=EOF){
input();
solve();
output();
}
}

[ZOJ3338 Map]爬山法

【题目大意】
给出两个矩形，让你求一个点，使之满足在两个矩形里的比例位置是一样的。
【算法分析】
Orz。。。比赛时想爬山。但是弄成直接爬那个重合点，然后以他们比例差作为估价函数。
于是果断写不出，然后挂了。
然后赛后问师傅。。。师傅说直接爬外面的，再算在里面的对应位置就可以了。
当时当场Orz自己的傻×无限次。

然后其中一种正确的做法是：
在外面爬，然后算在里面的对应位置，估价函数就设为这两个对应点的距离。

于是一爬就过。。。Orz。。。
【CODE】
#include #include #include #include #include using namespace std;
const double eps=1e-5;
struct Point{double x,y;}a[5],st,xXL,yXL;
double ratex,ratey;

inline double sqr(double x){return x*x;}
inline double dis(Point A,Point B){return sqrt(sqr(A.x-B.x)+sqr(A.y-B.y));}

void input(){
scanf("%lf%lf",&st.x,&st.y);
for (int i=1;i<=4;i++)
scanf("%lf%lf",&a[i].x,&a[i].y);
ratex=dis(a[1],a[2])/st.x;
ratey=dis(a[1],a[4])/st.y;

xXL.x=a[2].x-a[1].x;
xXL.y=a[2].y-a[1].y;

yXL.x=a[4].x-a[1].x;
yXL.y=a[4].y-a[1].y;
}

double w(double x,double y){
if (x<0 || x>st.x || y<0 || y>st.y) return 1e50;
double rx=x/st.x,ry=y/st.y;
Point m,tmp;
tmp.x=x; tmp.y=y;

m.x=rx*xXL.x+ry*yXL.x+a[1].x;
m.y=rx*xXL.y+ry*yXL.y+a[1].y;
return dis(m,tmp);
}

void work(){
double step=1.0,x=0,y=0;
bool flag;
for (;step>eps;step/=2){
for (flag=true;flag;){
flag=false;
if (w(x+step,y) if (w(x-step,y) if (w(x,y+step) if (w(x,y-step) }
}
printf("%.2lf %.2lfn",x,y);
}

int main(){
int Tc,i;
scanf("%d",&Tc);
for (i=1;i<=Tc;i++){
input();
work();
}
}

[FOJ1902 Graduate]动态规划

【题目大意】
给出N个人，他们高度各不相同，让他们站两排，满足：
1、同一个位置的人中，前面的比后面的矮。
2、最终没有一排是空的，而且后面那排的人数<=前面那排。
3、如果i站在j的左边，那么i比j矮。
问有多少种方案。
结果mod 20100501
【算法分析】
dp
F[i][j]表示前面那排排了i个人，后面那排排了j个人。
那么方程就是F[i][j]=F[i-1][j]+F[i,j-1]。（i>=j && i+j<=n）
初始F[0][0]=1。
【时间复杂度】O(n^2)
【CODE】
#include #include #include int a[105];
int f[105][105];

void init(){
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
}

void dp(){
memset(f,0,sizeof(f));
f[0][0]=1;
int i,j;
for (i=0;i<=n;i++)
for (j=0;i+j<=n && j<=i;j++)
if (i+j>0){
if (i) f[i][j]+=f[i-1][j];
if (j) f[i][j]+=f[i][j-1];
f[i][j]%=20100501;
}
int ans=0;
for (i=1;i<=n/2;i++){
ans+=f[n-i][i];
ans%=20100501;
}
printf("%dn",ans);
}

int main(){
int Tc;
scanf("%d",&Tc);
for (int i=1;i<=Tc;i++){
printf("Case #%d: ",i);
init();
dp();
}
}

[FOJ1903 Regular Brackets]贪心、无权修改括号序列、O(n)

【题目大意】
给定一个括号序列，让你修改最少的次数，使之成为一个合法的括号序列。
输出这个修改次数，并输出最终字典序最小的修改后的结果。
【算法分析】
Orz。。。这类题是我最不擅长的。。。应该说直觉不够好么。。。
下面引用lcc大牛的做法：

先从左向右扫一旦扫到一个失配的’)’就将左边第一个’）’强转‘（’ 然后反过来做一遍这样得到的一定是最小转化而且是最小字典序

一开始我也想到个类似的，然后我居然去想，这第一个’)’会不会不能转呢。。。
= =，晕，在正向枚举的时候，stack本来就可以超过0。本就不需要考虑失配。
太SB了。。。然后就这样。
【复杂度】O(n)
【CODE】
#include #include #include const int N=1000005;
int Tc,n,ans;
int Q[N];
char S[N];

void solve1(){
int stack=0,h=1,t=0,i;
for (i=1;i<=n;i++)
if (S[i]=='(‘) stack++;
else{
Q[++t]=i;
if (!stack){
S[Q[h++]]='(‘;
ans++;
stack++;
}
else stack–;
}
}

void solve2(){
int stack=0,h=1,t=0,i;
for (i=n;i>=1;i–)
if (S[i]==’)’) stack++;
else{
Q[++t]=i;
if (!stack){
S[Q[h++]]=’)’;
ans++;
stack++;
}
else stack–;
}
}

int main(){
scanf("%d",&Tc);
for (int i=1;i<=Tc;i++){
scanf("%s",S+1);
n=strlen(S+1);
ans=0;
solve1();
solve2();
printf("Case #%d: %dn",i,ans);
puts(S+1);
}
}