2019中山纪念中学夏令营-Day21[JZOJ]
提高组（B组模拟赛）Team_B
（由于本人太弱，并没有订正完题目）
（题解大部分是从官方题解文件上摘来的）
日常膜拜大神：じやゆん蒟蒻
正文部分：
T1：最小比例（JZOJ3514） Time Limits: 1000 ms Memory Limits: 131072 KB
题解&思路：
官方题解：
这是一个相对简单的题。由于n很小，所以直接用递归的方法枚举所有C(n,m)种m个点的取法，对于每一种取法构成的子图，求其最小生成树，记录边权和比点权和最小的那棵树即可。
这个题是2008年ACM亚洲区北京站的简单题。作为NOIP模拟的第一题代码量有一些高，还有，那30%的数据，也只是为枚举边而设计，有些牵强，最小生成树算法对大家应该不是问题。
但是现场264次提交，仅仅通过71队的情况，可以看出，这题也是有一个小陷阱，希望引起大家注意的：实数精度的问题。看似数值不大的两个整数相除，即使double直接相除，也会出现浮点精度误差。如果碰到这类需要比较实数除的情况，可以采用保留分子分母，或者设置一个较小eps=1e-8当做0的情况。此题中，n较大的数据都是用浮点除法和交叉相乘两个程序对拍生成的。
详解：
我们可以先用一个电风扇（DFS）来枚举选m个点的情况
对于电风扇枚举完的每m个点，我们对这m个点跑一遍最小生成树，即可求得答案。
原理：
题目要求 最小，而我们枚举完m个点后，这m个点的node weight是固定的（点已经确定了），分母确定了，就让分子尽量小就行了（即跑一遍最小生成树）
代码：
#include <cstdio>
#include <algorithm>
#define rr register
using std::sort;
int choose[],pw[],head[],n,m,tot,minn[],fa[],a[][];
long long minpw=,minew=0x3f3f3f3f;
struct Edge{
int to,nxt,w,from;
}edge[];
void add(int x,int y,int length)
{
tot++;
edge[tot].to=y;
edge[tot].w=length;
edge[tot].nxt=head[x];
edge[tot].from=x;
head[x]=tot;
}
int getfa(int x)
{
if(fa[x]==x)
return x;
return fa[x]=getfa(fa[x]);
}
bool cmp(Edge x,Edge y)
{
return x.w < y.w;
}
void kruskal()
{
int edgeweight=;
int pointweight=;
for(rr int i=;i<=n;i++)
fa[i]=i;
tot=;
for(rr int i=;i<=m;i++)
for(rr int j=;j<=m;j++)
{
if(i == j)
continue;
add(pw[i],pw[j],a[pw[i]][pw[j]]);
}
for(rr int i=;i<=m;i++)
pointweight+=choose[pw[i]];
sort(edge+,edge+tot+,cmp);
int num=;
for(rr int i=;num != m-;i++)
{
int x=getfa(edge[i].from) ,y=getfa(edge[i].to);
if(x != y)
{
fa[x]=getfa(y);
num++;
edgeweight+=edge[i].w;
}
}
if(edgeweight*minpw < minew*pointweight)
{
minpw=pointweight;
minew=edgeweight;
for(rr int i=;i<=m;i++)
minn[i]=pw[i];
}
}
void dfs(int x,int k)
{
if(k == m+)
{
kruskal();
return;
}
if(x > n)
return ;
pw[k]=x;
dfs(x+,k+);
dfs(x+,k);
}
signed main()
{
freopen("ratio.in","r",stdin);
freopen("ratio.out","w",stdout);
scanf("%d %d",&n,&m);
for(rr int i=;i<=n;i++)
scanf("%d",&choose[i]);
for(rr int i=;i<=n;i++)
for(rr int j=;j<=n;j++)
scanf("%d",&a[i][j]);
dfs(,);
sort(minn+,minn+m+);
for(rr int i=;i<=m;i++)
printf("%d ",minn[i]);
}
T2 软件公司(JZOJ3515) Time Limits: 1000 ms Memory Limits: 131072 KB
思路&题解:
官方题解：
普通的动态规划应该比较容易发现。
f[i][j][k]表示前i个人，完成了j个1项目，k个2项目。转移为：
f[i][j][k]=max{f[i][j-s][k-t],s*A[i]+t*B[i]}，不过一算复杂度O(n*m^4),只能通过30%的数据。
开始优化，再分析一下题目和样例。为什么不能是17？在17时，第二个人就会耗时18。想到这里应该不难发现，耗时小于18都是不可行的，大于等于18都是存在可行方案的，耗时最多的人的时间最小。答案是线性的。
二分这个答案！在最大时间已知的情况下，f[i][j][k]就可以用bool表示成是否能在答案内完成。这时，转移的时候就不需要两个项目都枚举了。只要枚举一个，另外一个的最大值会自动产生。转移少了一维，复杂度变为O(n*m^3*log10000)。60%的数据。
优化到这里，也可以有一些感觉，f[i][j][k]就用来表示0,1两种值，是否有些浪费？直接将第三维体现在状态值里面，改造一下状态：
f[i][j]代表到前i个人，在1项目做了j个的情况下，2项目能做的最多的个数。转移为：
这样，时间复杂度就O（n*m^2*log(10000))。可以通过所有数据。
这是一道2004年ACM亚洲区德黑兰站的预赛题。可能比较老的题目了。拿出这个题目想和大家一起探讨一下近几年NOIP题中出现的一个较热门的思想，二分答案！10年的关押罪犯，11年的聪明的质监员，12年的借教室，都有二分答案的方法。而且都是区分水平的关键题。
我们可以总结一下，当碰到所求问题是最小值最大，最大值最小，答案存在线性的临界点的时候，我们都可以二分这个答案，然后根据二分的值设计判断答案可行性的函数。
我的思路：
（其实我也是按官方题解的思路打的）
代码实现：
#include <cstdio>
#define rr register
const int inf = (<<);
int n,m,a[],b[],f[][];
int max(int x,int y)
{
if(x > y)
return x;
return y;
}
int binarysearch(int l,int r)
{
if(l > r)
return l;
int mid = (l+r)/;
for(rr int i=;i<=n;i++)
{
for(rr int j=;j<=m;j++)
f[i][j]=-inf;
f[i][]=;
}
for(rr int i=;i<=n;i++)
for(rr int j=;j<=m;j++)
for(rr int k=;k<=j;k++)
if(k*a[i] <= mid)
f[i][j]=max(f[i][j],f[i-][j-k]+(mid-k*a[i])/b[i]);
if(f[n][m] >= m)
return binarysearch(l,mid-);
return binarysearch(mid+,r);
}
signed main()
{
freopen("company.in","r",stdin);
freopen("company.out","w",stdout);
scanf("%d %d",&n,&m);
for(rr int i=;i<=n;i++)
scanf("%d %d",&a[i],&b[i]);
printf("%d",binarysearch(,));
}
T3 空间航行（JZOJ3517） Time Limits: 1000 ms Memory Limits: 262144 KB
题解&思路：
官方题解：
100% 的算法 易知，在两个球的之间航行的时间等于两个球心之间的距离减去两个球的半径。 将每个球的球心当作点建图，然后运行最短路算法即可。 无论是 Floyd 算法还是 Dijkstra 算法都可以在限定时间内解决。需要注意的是不要弄出负 的航行时间。
本人思路（详解）
这道题可以先把起点和终点预处理成一个星系（半径为零）
然后跑一遍起点到终点的最短路即可（由于数据范围太水，Floyed也可以过）
如何求各个星系间的最短路：
1.转换成图
计算出每个星系到其他所有星系的距离，然后令该星系和其他所有星系间加一条边权为它们距离的边，图的转化就完成了。
距离计算公式：
当然，当两个星系有交集时，这个距离求出来是负的，这时我们就要将两星系间的距离设为0，再跑最短路。
即综合式子：
另外一个细节性问题：
题目要求取整到最近的整数，而C++自带的只有向下取整，因此，要自己用代码实现这个功能。
代码实现：
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#define rr register
int x[],y[],z[],r[],n;
using namespace std;
double map[][];
int changed(double a)//四舍五入
{
int b=a;
double c=a-b;
if(c < 0.5)
return b;
else
return b+;
}
signed main()
{
freopen("warp.in","r",stdin);
freopen("warp.out","w",stdout);
while()
{
scanf("%d",&n);
if(n == -)
return ;
for(rr int i=;i<=n;i++)
{
scanf("%d %d %d %d",&x[i],&y[i],&z[i],&r[i]);
}
for(rr int i=n+;i<=n+;i++)
{
scanf("%d %d %d",&x[i],&y[i],&z[i]);
r[i]=;
}
for(rr int i=;i<=n+;i++)
for(rr int j=;j<=n+;j++)
{
map[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])+(z[i]-z[j])*(z[i]-z[j]))-r[i]-r[j];
if(map[i][j] < )
map[i][j]=;
}
n+=;
for(rr int k=;k<=n;k++)
for(rr int i=;i<=n;i++)
for(rr int j=;j<=n;j++)
if(map[i][j] > map[i][k]+map[k][j])
map[i][j]=map[i][k]+map[k][j];
map[n-][n]*=;
printf("%d\n",changed(map[n-][n]));
}
}
T4 摧毁巴士站（JZOJ3516）Time Limits: 1000 ms Memory Limits: 131072 KB
JZOJ官方题解：
这是一个存在多种解法的题目。本题存在比较复杂的网络流解法，但用此法来解此题颇为小题大做，浪费了赛场上的很多时间。因为，计算时间复杂度可以看出，如果使用网络流来做此题，复杂度大约为O（nm），那么出题者完全可以增大数据范围，而实际数据范围仅为n<=50，这个数据范围暗示着此题是经过优化和剪枝的搜索算法能够通过的题。
最朴素的搜索方法是枚举所有删除点的方案，每找到一种方案，就求一次从1号点到n号点的最短路径，看看其长度是否超过k。每个点有删除和不删除两种状态，所以方案总数最多就是2^48种。这样的搜索时非常盲目的，显然会导致超时。
解决办法是有选择性的进行删点。基本的思路就是，一条长度不超过k的最短路径上的点，至少有一个是要被删掉的（至于删除哪个好，可以枚举尝试），删掉一个点后再重新求最短路，如果新求出的最短路径长度仍然不超过k，那么就在新的最短路径上再找出一个点删掉，然后再求最短路径……直到求出的最短路径长度超过k，那么就找到了一个解。但这个解未必是最优的，所以要用递归的方法搜索多组解，以确保能搜到最优解。具体步骤如下。
递归进行下列操作：
- 寻找起点到终点的最短路径，如果最短路径长度超过k，则表示已找到一种删点方案。记录该方案下的删点数目，回溯再找出下一种方案；否则进入下一步。
- 枚举最短路径中的除1号点和n号点外的某一个点，将其删除。
- 回到1递归继续搜索。
这样的搜索顺序使得枚举的点的数量得到控制。搜索的每一层会从L-2个点中选择一个进行删除，L是当前找到的最短路径的长度。如果当前找到的最短路径很长，虽然在这一层我们需要枚举很多个点进行删除，但也说明起点到终点的距离已经很长了，我们离答案已经很接近了。一般来说，在50个点的图中，答案应该不超过20。那么L<20。并且L比较大的情况只会出现在搜索的最后几层。这么想来，这个搜索的时间复杂度是可以接受的。
当然，我们还可以通过一些其他的方法优化这个搜索。在上述方法中，还可以用迭代加深的方法来搜索。也就是说，先找到删除1个点的方案，看是否存在；如果不存在，则再找到删除2个点的方案；如果还是不存在，则继续找到删除3个点的方案……由于删除的点数增加1，搜索的范围就会成倍增长，虽然这样看似重复搜索了很多遍，但实际上搜索的深度（删除的点数）是有限的，因此搜索的总范围不会非常大。实际测试的结果表明，使用迭代加深的方法搜索能够缩短很多的时间。
以上是出题人的原版题解。这个题目同样是ACM08年北京站的题目，现场赛25次提交，4队通过，应该是难题了。其实，对OIer来说，搜索的技巧更是需要不断通过难题来积累的。记得以前常问不少大神，某某题是怎么做的，无数次得到的回答是：暴搜！当然，此暴搜肯定是经过了许多的优化，而这些优化在高手日积月累的搜索技巧面前就是家常便饭了。在OI中，同样的题目，都采用搜索，有些就只能拿基本分，而有些就可以拿下大部分，甚至AC，这种情况很常见。搜索技巧在很多时候也成了区分OI选手水平的重要标志。要提高也只能通过不断的做题，了解不同类型题目的搜索剪枝技巧，还有就是尝试一些IDDFS，A*等不同的搜索方式。水平有限，也希望大神们可以总结一些好的搜索攻略。
这题还可以用最小割的做法，图论熟练的同学，应该比较容易想到。广搜之后，求起点到终点的点割集即可。每个点权为1，转为边权后最大流即可。
此题数据不是官方的，可能不太全面，请大家谅解。
本人思路：电风扇（DFS）+不分手（BFS）（咕咕咕）
代码实现：
咕咕咕