17.7.24 校内赛解题报告【二分答案】【记忆化搜索】【数据结构】

本文主要是介绍17.7.24 校内赛解题报告【二分答案】【记忆化搜索】【数据结构】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.计算几何
题目描述：

解题报告：
这道题有几个问题。
首先我们要解决，如何配对坐标轴上的点使得n条线段没有交点。由于题目的承诺，我们sort一遍就行了。
其次我们要搞出点在直线另一侧的判定方程，这个方程是：
b*y+a*x>=x*y
然后我们就会想，有没有优于n^2的方法来统计点在哪些线段的同侧。由于我们sort一遍之后这些线段是又内及外的，所以我们想到了二分。那么二分确定的方向是什么呢？由于我们想要答案尽量小，所以是向左移的方向。
代码如下：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define NAME "geometry"
const int N=1e5;
int n,m;
long long x_1,y_1;
long long x[N+5],y[N+5];
int main()
{freopen(NAME".in","r",stdin);freopen(NAME".out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&x[i]);for(int i=1;i<=n;i++)scanf("%d",&y[i]);sort(x+1,x+1+n);sort(y+1,y+1+n);scanf("%d",&m);for(int i=1;i<=m;i++){scanf("%d%d",&x_1,&y_1);int lf=1,rg=n;while(lf<=rg){int mid=(lf+rg)>>1;if(x[mid]*y_1+y[mid]*x_1>=x[mid]*y[mid])lf=mid+1;//判定是否相交 else rg=mid-1;}printf("%d\n",rg);}return 0;
}

2.花花的聚会
题目描述：

解题报告：
这道题题意就是叫我们找从在买票的前提下，从非根节点跑到根节点所需要的最小价值。
由于查询的过程中很肯能会经过重复的点，所以我们希望把找到的这些点到根节点的代价记下来。这也就是记忆画搜索的套路。
还有一些细节上的东西，就是我们用临界表存储这颗树是毫无意义的，还不如用一个简单的father数组就可以满足其转移的条件。那我们用临界表干什么呢？我们用它来存储通行券。这样就可以方便的便利能在一个城市买到的所有通行券。
代码如下：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define NAME "party"
const int N=1e5;
const int inf=1e9;
int head[N+5],num;
int father[N+5];
struct edge
{int k,w;int next;
}ed[N+5];
void build(int v,int k,int w)
{ed[++num].k=k;ed[num].w=w;ed[num].next=head[v];head[v]=num;
}
int n,m,q;
int dp[N+5];
int dfs(int u)
{if(u==1)return 0;if(dp[u]!=-1)return dp[u];//记忆化搜索 dp[u]=inf;for(int i=head[u];i!=-1;i=ed[i].next)//枚举这个城市能买到的通行券 {int tot=1,now=father[u],k=ed[i].k;while(now>=1&&tot<=k){dp[u]=min(dp[u],dfs(now)+ed[i].w);//dp方程 now=father[now];//保证限制条件逐步更新 tot++;}}return dp[u];
}
int main()
{freopen(NAME".in","r",stdin);freopen(NAME".out","w",stdout);memset(dp,-1,sizeof(dp));memset(head,-1,sizeof(head));scanf("%d%d",&n,&m);for(int i=1;i<=n-1;i++){int u,v;scanf("%d%d",&u,&v);father[u]=v;//一棵树记下father足够了 }for(int i=1;i<=m;i++){int v,k,w;scanf("%d%d%d",&v,&k,&w);build(v,k,w);//图里边存储的是通行券 }scanf("%d",&q);for(int i=1;i<=q;i++){int u;scanf("%d",&u);printf("%d\n",dfs(u));}return 0;
}
/*
7 7
3 1
2 1
7 6
6 3
5 3
4 3
7 2 3
7 1 1
2 3 5
3 6 2
4 2 4
5 3 10
6 1 20
3
5
6
7
*/