HDU3400 三分查找

题目大意

HDU3400.在二维平面上有两条线段AB、CD。AB上的速度是P,CD上是Q,平面上的其他区域上速度为R。求A->D的最少时间。


思路

由于我们必须在A出发,在D结束,所以我们必然会在两条线段上行走一段距离。而知道在这两条线段上分别应当走多少距离,就是这道题的关键。我们设点q,p分别是在AB CD上的两个点,暴力枚举这两个点的位置(即距离A、D的距离)显然是不行的。而面对求一个极值(在这题里是最短时间)的问题二分也不适用,于是我们就有了三分查找。


三分简介

三分查找与二分相似。从名字就可以看出,三分的每次操作就是用两个点把当前的区间分成三个区间。即在二分查找的基础上,在右区间(或左区间)再进行一次二分。该算法通常用来迅速确定最值。二分查找所面向的搜索序列的要求是:具有单调性。而三分查找所面向的搜索序列的要求是:序列为一个凸性函数。即该序列必须有一个最大值(或最小值),在极值的左侧序列,必须满足不严格单调递增(递减),右侧序列必须满足不严格单调递减(递增)。如下图,表示一个有最大值的凸性函数:

    

算法流程

(1)与二分法类似,先取整个区间的中间值mid。

 

(2)再取右侧区间的中间值midmid,从而把区间分为三个小区间。

(3)如果mid比midmid更靠近最值,我们就舍弃右区间,否则我们舍弃左区间。

比较mid与midmid谁最靠近最值,只需要确定mid所在的函数值与midmid所在的函数值的大小。当最值为最大值时,mid与midmid中较大的那个自然更为靠近最值。最值为最小值时同理。

(4)重复(1)(2)(3)直至找到最值。

代码

挖个坑以后再填(逃)

总结

因为大多数题不用单独写judge函数,所以总体上看三分比二分更水。但是每个算法都有它的必要性,三分也是如此。(众:这就是你又水了一贴的理由?)

NOIp 2014 Day2 题解

T1 无线网络发射器选址

先看数据范围,128*128?果断直接暴力模拟发射器的位置,但是在计算在(x-d,y-d)到(x+d,y+d)中的之和时要注意边界和范围。什么?代码呢?这么斯波的题自己去写。

T2 联合权值

这道题记得很早以前就做过。条件1如何解决是这道题的难点。如果直接对每个点进行判断能否抵达终点显然会超时的。那么既然我们要判断哪些点能到终点,为啥不从终点反着广搜一遍,看看终点能到哪些点呢?于是思路就显而易见了。将所有路径反向,从终点开始做一遍BFS标记出哪些点是可以作为合法路径,再做一遍spfa(其实貌似BFS也能过)就搞定了。


#include<bits/stdc++.h>
#define N 200005
#define inf 0x3f3f3f3f
using std::queue;

struct Edge{
    int v,nxt;
}e[N],E[N];

int n,m,s,t;
int head[N],tot;
int h[N],tol;

void AddEdge(int u,int v){
    e[++tot]=(Edge){v,head[u]};head[u]=tot;//正向边
    E[++tol]=(Edge){u,h[v]};h[v]=tol;//反向边
}

int vis[N];//表示这个点能直接到达终点
int be[N];//if be[i]== true 表示i没有被删除
int tt;

int dfs(int x,int f){//反向遍历
    vis[x]=true;
    for(int i=h[x];i;i=E[i].nxt){//反向边
        int to=E[i].v;
        if(to==f)continue;
        if(vis[to])continue;
        dfs(to,x);
    }
}

int init(){//删除不能存在于路径上的点
    for(int i=1;i<=n;++i){
        if(!vis[i])continue;bool flag=0;
        for(int j=head[i];j;j=e[j].nxt){
            int to=e[j].v;
            if(!vis[to])flag=true;
        }
        if(!flag)be[i]=true;
    }
}

int dis[N];

int spfa(int s,int t){// 从起点到终点的最短路
    memset(dis,0x3f,sizeof(dis));
    memset(vis,false,sizeof(vis));
    int top,to;
    dis[s]=0;queue<int>que;que.push(s);vis[s]=true;
    while(!que.empty()){
        top=que.front();
        que.pop();
        for(int i=head[top];i;i=e[i].nxt){
            to=e[i].v;
            if(!be[to])continue;           
            int l;
            if(dis[top]+1<dis[to]){
                dis[to]=dis[top]+1;
                if(!vis[to]){
                    vis[to]=true;
                    que.push(to);
                }
            }
        }
    }
    return dis[t];
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        int u,v;
        scanf("%d%d",&u,&v);
        AddEdge(u,v);
    }
    scanf("%d%d",&s,&t);
    dfs(t,0);
    init();
    int ans=spfa(s,t);
    if(ans==inf)ans=-1;
    printf("%d\n",ans);
    return 0;
}

T3 解方程

狗比数学题。如果我们有个一元四次方程a0+a1x+a2x^2+a3x^4+a4x^4=0,那么其显然等于(x(x(xa4+a3)+a2)+a1)+a0=0。这就是一个叫做秦九韶的人提出的imba解法(这货是宋朝人!)。换句话讲,对于一个多项式,维护一个初始值为0的sum,每一次先加上当前的系数a,再自乘x,这个多项式如果和为0,则这是方程的一个解。但是这个a比较大(dark),高精度又容易被卡常,于是我们就可以先给a取模。这里我要介绍一个非常excited的素数:19260817,据信这个素数可以极大的优化程序的运行时间,通常为1s。


#include<bits/stdc++.h>
#define maxn 105
#define MOD1 23333
#define MOD2 19260817
using namespace std;
int n,m,a1[maxn],a2[maxn],vis[1000005];
vector<int>ans;
void read(int pos){
    char c=getchar();
    int x1=0,x2=0,f=1;
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x1=(x1*10+c-'0')%MOD1;
        x2=(x2*10+c-'0')%MOD2;
        c=getchar();
    }
    a1[pos]=x1*f;
    a2[pos]=x2*f;
}
int check(int f[],int x,int mod) {
            int y=0;
            for(int i=n;i>=0;i--)
            y=((long long)y*x+f[i])%mod;                       
            return (!y)? 1:0;
}
int main(){
    freopen("equation.in","r",stdin);
    freopen("equation.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n;i++)read(i);
    for(int i=1;i<=MOD1;i++)
       if(check(a1,i,MOD1))
           for(int j=i;j<=m;j+=MOD1)
             if(check(a2,j,MOD2))
                    vis[j]=1;
    for(int i=1;i<=m;i++)
         if(vis[i])ans.push_back(i);
    printf("%d\n",ans.size());
    for(int i=0;i<ans.size();i++)printf("%d\n",ans[i]);
    return 0;
}

以上

NOIp 2014 Day1 题解

T1 生活大爆炸版石头剪刀布

一看就是一道水题。根据得分关系列一张二维表,然后按题意循环就OK了。代码没必要贴。

T2 联合权值

不难看出这是一颗无根树。因为没有环,所以如果两个点同时于另一个点相连,则它们不可能再有边相连,即它们之间的距离为2。于是我们可以枚举每一个点,取其任意两个点,然后进行组合,然后两两相乘,得到最大值与他们的和。将所有值统计一下,输出的时候答案不要忘记乘二。
代码如下:


#include<bits/stdc++.h>
using namespace std;
int head[200010],ll,v[200010];
struct st{int to,nxt;}a[400010];
int n,ans,x,y,maxans;
void add(int x,int y){
	a[++ll].to=y,a[ll].nxt=head[x],head[x]=ll;
}
int main(){
	freopen("link.in","r",stdin);
 	freopen("link.out","w",stdout);
	cin>>n;
	for (int i=1;i<n;i++){
		cin>>x>>y;
		add(x,y); add(y,x);
	}
	for (int i=1;i<=n;i++) cin>>v[i];
	for (int i=1;i<=n;i++){
		int sum=0,ma=0,m=0;
		for (int k=head[i];k>0;k=a[k].nxt){
			if (v[a[k].to]>ma) m=ma,ma=v[a[k].to];
			else if (v[a[k].to]>m) m=v[a[k].to];
			ans=(ans+sum*v[a[k].to]) % 10007;
			sum=(sum+v[a[k].to]) % 10007;
		}
		maxans=max(maxans,ma*m);
	}
	cout<<maxans<<" "<<(ans*2)%10007;
}

T3 飞扬的小鸟

为了理解这道题,我特地去下了一个Flappy Bird。真·休闲游戏(摔)。废话不多说,我们来看题。这道题明眼人一看就知道是道DP,而且因为每个时刻可以按很多下,你们想到了什么算法?对,就是完全背包。注意下落的时候还要搞一遍01背包。说说不难,其实小细节非常多。比如场景的高度有限制,有些优化其实会WA等等,就不一一列举了,请自行体会XD

代码如下:


#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=10005,maxm=1005;
int n,m,p;
int clic[maxn],uncl[maxn],L[maxn],H[maxn];
int f[maxn][maxm],cnt,INF;
inline int read(){
    int x=0; char ch=getchar();
    while (ch<'0'||ch>'9') ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}
int main(){
    freopen("bird.in","r",stdin);
    freopen("bird.out","w",stdout);
    n=read(),m=read(),p=read();
    for (int i=1; i<=n; i++) clic[i]=read(),uncl[i]=read();
    for (int i=1; i<=n; i++) L[i]=0,H[i]=m+1;
    for (int i=1; i<=p; i++){
        int x=read(); L[x]=read(),H[x]=read();
    }
    memset(f,63,sizeof f),INF=f[0][0],cnt=0;
    for (int i=0; i<=m; i++) f[0][i]=0;
    for (int i=1; i<=n; i++){
        for (int j=1; j<H[i]; j++) if (j>=clic[i]&&j!=m)
        f[i][j]=min(f[i][j],min(f[i-1][j-clic[i]]+1,f[i][j-clic[i]]+1));
        for (int j=1; j<H[i]; j++) if (j+uncl[i]<=m&&j>=L[i]+1)
        f[i][j]=min(f[i][j],f[i-1][j+uncl[i]]);
        if (H[i]==m+1)
            for (int j=m; j>=max(1,m-clic[i]); j--) f[i][m]=min(f[i][m],min(f[i-1][j]+1,f[i][j]+1));
        bool flythr=0;
        for (int j=L[i]+1; j<H[i]; j++) if (f[i][j]<INF){flythr=1; break;}
        for (int j=0; j<=L[i]; j++) f[i][j]=INF;
        if (!flythr){printf("0\n%d",cnt); return 0;}
        if (L[i]>0||H[i]<m) cnt++;
    }
    int ans=1<<30;
    for (int i=1; i<=m; i++) ans=min(ans,f[n][i]);
    printf("1\n%d",ans);
    return 0;
}


以上。