不知道教练哪里找来的一套老题，虽然题目比较的陈旧，但是还是非常与水平的一套题，废话不多说。
(color{blue} ext {斜率})
(color{blue} ext {【题目描述】})
给定平面上 n 个点的坐标，求所有经过这些点中至少两个点的直线的最大斜率。
(color{blue} ext {【输入】})
第一行一个整数 n，表示点的个数。
接下来 n 行，每行两个正整数 x,y，描述每个点的坐标。
(color{blue} ext {【输出】})
一行一个实数表示答案，保留小数点后 3 位。
(color{blue} ext {【输入样例】})
3
1 2
2 3
3 4
(color{blue} ext {【输出样例】})
1.000
(color{blue} ext {【提示】})
【样例 2】
见选手目录下 slope.in/slope.ans下载
【数据范围与约定】
对于 20%的数据，n≤10
对于 50%的数据，n≤10^3
对于 100%的数据，n≤5×10^5，坐标，没有两点横坐标相同。
(color{blue} ext {【解题思路】})
这道题其实是一道结论题，当时考试的时候我也不知道为什么自己就推这个结论推了这么旧，但是最后好在还是A了他，并且成功的绕开了他的坑点，这道题的结论就是我们斜率的最大值只可能是在我们对于每一个点进行x轴排序然后找任意两个相隔最近的两个点之间来产生这个斜率的最大值，如果不信的话可以自己去画一个图推导一下。
下面说一下本题目的坑点，就是说他的斜率有可能是一个负的，所以说我们初始化答案ans变量一定是把他初始成一个负数，否则会GG，我的运气比较好，我只把他初始到-1然后就卡过去了，大家一定要初始到更小的值去。
AC code：
#include<bits/stdc++.h>
#define gc() getchar()//caution!!!
#define N 500005
using namespace std;
/*inline char gc() {
static char buf[1<<18],*fs,*ft;
return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?EOF:*fs++;
}*/
template<class T>
inline void read(T &aa) {
register int k=0,f=1;
register char c=gc();
for (;!isdigit(c);c=gc()) if(c=='-')f=-1;
for (;isdigit(c);c=gc()) k=(k<<3)+(k<<1)+(c-'0');
aa=k*f;
}
template<class T>
inline void out(T x){if(x>9)out(x/10);putchar(x%10+'0');}
struct sd{
int x,y;
}p[N];
int n;double ans=-1;
double slope(int x1,int y1,int x2,int y2){
return (double)(y2-y1)/(double)(x2-x1);
}
void check1(){
for(int i=1;i<=n;++i){
for(int j=i+1;j<=n;++j){
double now=slope(p[i].x,p[i].y,p[j].x,p[j].y);
ans=max(ans,now);
}
}
printf("%.3lf",ans);
}
bool cmp(sd a,sd b){if(a.x<b.x) return true; return false; }
int main()
{
// freopen("slope.in", "r", stdin);freopen("slope.out", "w", stdout);
scanf("%d",&n);for(int i=1;i<=n;++i){scanf("%d%d",&p[i].x,&p[i].y);}
sort(p+1,p+1+n,cmp);
/*for(int i=1;i<=n;++i){
printf("%d %d
",p[i].x,p[i].y);
}*/
if(n<=1000){check1();return 0;}
for(int i=1;i<n;++i){
double now=slope(p[i].x,p[i].y,p[i+1].x,p[i+1].y);
ans=max(now,ans);
}
printf("%.3lf",ans);
// fclose(stdin);fclose(stdout);
return 0;
}
/*
3
1 2
2 3
3 4
*/
(color{blue} ext {最优路线})
(color{blue} ext {【题目描述】})
一个 n 个点 m 条边的无重边无自环的无向图，点有点权，边有边权，定义一条路径的权值为路径经过的点权的最大值乘边权最大值。求任意两点间的权值最小的路径的权值。
(color{blue} ext {【输入】})
第一行两个整数 n,m，分别表示无向图的点数和边数。
第二行 n 个正整数，第 i 个正整数表示点 i 的点权。
接下来 m 行每行三个正整数 ui,vi,wi，分别描述一条边的两个端点和边权。
(color{blue} ext {【输出】})
n 行每行 n 个整数，第 i 行第 j 个整数表示从 i 到 j 的路径的最小权值，如果从 i 不能到达 j，则该值为−1。特别地，当 i=j 时输出 0。
(color{blue} ext {【输入样例】})
3 3
2 3 3
1 2 2
2 3 3
1 3 1
(color{blue} ext {【输出样例】})
0 6 3
6 0 6
3 6 0
(color{blue} ext {【提示】})
【样例 2】
见选手目录下 path.in/path.ans下载。
【数据范围与约定】
对于 20%的数据，n≤5,m≤8。
对于 50%的数据，n≤50
对于 100%的数据，n≤500,m≤n×(n−1)/2，边权和点权不超过 10^9。
(color{blue} ext {【解题思路】})
这道题应该算是本套题中最难的一道题了，思路也并不是那么的好想，但是可以肯定的一点就是这道题大家一看就应该知道是一道DP,具体实现方法就是弗洛伊德算法的改装版，我们定义一个叫做dis[][]数组的东西作为我们的转移变量，分别存储的是从i号点到j号点的最小的最大路径长度乘上路径上的最大点权，我们对点权进行从小到大的排序，那么我们就可以保证我们每一次加进去的点（作为我们Floyd算法的中转点，都是最优秀的，当然我们对于该条路径上的最大值一定还是要和该路径上两边的点的点权进行比较，我们可以保证中间的点一定是比现在的中转点的点权要小一些的，因为我们在构建这条路径的时候一定是先把这些点加进去了，而我们是从小到大排的序！）相信大家应该都懂了，具体一些操作的实现可以见代码，代码还是写的比较清楚的！
AC code：
/*
Name: path
Copyright: LPA
Author: Mudrobot
Date: 2018/10/17 16:26:01
Description: Dynamic Programming + Floyd
*/
#include<bits/stdc++.h>
#define gc() getchar()//caution!!!
#define LL long long
#define N 505
using namespace std;
/*inline char gc() {
static char buf[1<<18],*fs,*ft;
return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?EOF:*fs++;
}*/
template<class T>
inline void read(T &aa) {
register int k=0,f=1;
register char c=gc();
for (;!isdigit(c);c=gc()) if(c=='-')f=-1;
for (;isdigit(c);c=gc()) k=(k<<3)+(k<<1)+(c-'0');
aa=k*f;
}
template<class T>
inline void out(T x){if(x>9)out(x/10);putchar(x%10+'0');}
struct sd{LL val,loc;}poi[N];
LL n,m,mp[N][N],val[N],dis[N][N];
bool cmp(sd a,sd b){if(a.val<b.val) return true;return false;}
void clear(){
memset(mp,63,sizeof(mp));memset(dis,63,sizeof(dis));
}
int main()
{
//freopen("path.in", "r", stdin);freopen("path.out", "w", stdout);
read(n);read(m);clear();LL a,b,c;
for(int i=1;i<=n;++i) read(poi[i].val),val[i]=poi[i].val,poi[i].loc=i,mp[i][i]=0;
for(int i=1;i<=m;++i){
read(a);read(b);read(c);
mp[a][b]=mp[b][a]=c;
dis[b][a]=dis[a][b]=min(dis[a][b],mp[a][b]*max(val[a],val[b]));
}
sort(poi+1,poi+1+n,cmp);
for(int u=1;u<=n;++u){
LL k=poi[u].loc;
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
if(mp[i][j]>max(mp[i][k],mp[k][j])){
mp[i][j]=max(mp[i][k],mp[k][j]);
dis[i][j]=min(dis[i][j],max(max(val[i],val[j]),val[k])*mp[i][j]);
}
}
}
}
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
if(i==j) printf("0 ");
else if(dis[i][j]==dis[0][0])printf("-1 ");
else printf("%lld ",dis[i][j]);
}
printf("
");
}
//fclose(stdin);fclose(stdout);
return 0;
}
/*
3 3
2 3 3
1 2 2
2 3 3
1 3 1
*/
(color{blue} ext {小 G 的线段树})
(color{blue} ext {【题目描述】})
小 G 是一名 OIer，他最近学习了一种高级数据结构——线段树，
做题时，他遇到了如下的问题：
维护一个序列，要求支持三种操作：
1.区间加上一个数 x
2.区间赋值为一个数 x
3.求一个区间的和
小 G 是一个爱思考的同学。他在做出来了这题之后，又提出了一个新的问题：如果把所有的操作随机打乱，那么每个询问的期望输出是多少呢？注意，随机打乱既所有 m!种操作排列的出现概率均等。
为了方便，我们假设询问在最后且不参与随机打乱。
考虑到精度问题，只要你的答案和标程答案的相对误差不超过10^−8 就算正确。
(color{blue} ext {【输入】})
第一行两个整数 nmq，分别表示序列长度、修改数和询问数
接下来一行 n 个整数 ai，表示序列的初始值
接下来 m 行，每行 4 个整数 c,l,r,x
若 c=1，则表示把区间[l,r]的元素加上 x
若 c=2，则表示把区间[l,r]的元素全赋为 x
接下来 q 行，每行 2 个整数 l,r，代表每次询问的左右端点。
(color{blue} ext {【输出】})
q 行，每行一个实数，按照输入顺序分别为 q 个询问的期望答案
答案保留 3 位小数
(color{blue} ext {【输入样例】})
5 4 8
2 3 3 3 3
1 1 3 2
1 3 5 1
2 2 4 1
2 1 3 4
1 1
2 2
3 3
4 4
5 5
1 3
2 5
1 5
(color{blue} ext {【输出样例】})
5.000
3.167
3.500
1.500
4.000
11.667
12.167
17.167
(color{blue} ext {【提示】})
【样例 2】
见选手目录下 segment.in/segment.ans下载
【数据范围与约定】
对于 30%的数据，n≤10,m≤10
对于 60%的数据，n≤1000,m≤1000
对于另外 10%的数据，没有操作 1
对于另外 10%的数据，q=1
对于 100%的数据，n,m,q≤100000，1≤ai≤100000，1 操作中的x≤100，2 操作中的 x≤100000。
(color{blue} ext {【解题思路】})
这道题千万不要被题目所忽悠，并不是一道线段树的题目，只是一道数学题加上差分的优化，在这里主要讲一下数学的思路，差分大家可以自己脑补或者看我的AC code，数学思路主要是这样，千万不要想的太复杂，我们首先先把所有重置操作抽取出来，想象他们十一块一块的隔板，那么如果有k个重置操作那么就有k+1个空格，然后我们就把所有的区间加操作随机的加入进去，但是我们发现只有把这些操作插入到最后一个隔板后面时才能对最后的结果造成影响，所以说我们关于所有区间加法的期望就非常好算了，对于每一个点就是，在他上面进行的加法的和乘上1/（k+1）即可，然后我们呢在考虑一下对于区间重置对答案所作的贡献，就是所有区间贡献的总和乘上1/k因为每一种都有1/k的概率成为最后一块隔板，然后把这两个期望相加就是我们那个点上的答案，然后这道题就结束了，最主要的就是要考虑当前点如果没有区间重置操作时的情况，非常容易错，然后这道题讲到这里相信大家都能AC了：
AC code：
/*
Name: Segment
Copyright: njc
Author: Mudrobot
Date: 2018/10/17 15:28:03
Description: Mathmatics
*/
#include<bits/stdc++.h>
#define gc() getchar()//caution!!!
#define N 100005
#define LL long long
using namespace std;
/*inline char gc() {
static char buf[1<<18],*fs,*ft;
return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?EOF:*fs++;
}*/
template<class T>
inline void read(T &aa) {
register int k=0,f=1;
register char c=gc();
for (;!isdigit(c);c=gc()) if(c=='-')f=-1;
for (;isdigit(c);c=gc()) k=(k<<3)+(k<<1)+(c-'0');
aa=k*f;
}
template<class T>
inline void out(T x){if(x>9)out(x/10);putchar(x%10+'0');}
LL n,m,q,ini[N],add[N],sset[N],cnt[N];
double sum[N];
int main()
{
//freopen(".in", "r", stdin);freopen(".out", "w", stdout);
scanf("%lld%lld%lld",&n,&m,&q);
for(int i=1;i<=n;++i) scanf("%lld",&ini[i]);
LL a,b,c,d;
for(int i=1;i<=m;++i){
scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
if(a==1){
add[b]+=d;add[c+1]-=d;
}
else{
sset[b]+=d;sset[c+1]-=d;cnt[b]++;cnt[c+1]--;
}
}
a=0;b=0;c=0;
for(int i=1;i<=n;++i){
a+=add[i];b+=sset[i];c+=cnt[i];
if(!c){
sum[i]=(double)ini[i]+(double)a;
}
else{
sum[i]=(double)b/c+(double)a/(c+1);
}
}
for(int i=1;i<=n;++i)sum[i]+=sum[i-1];
for(int i=1;i<=q;++i){
scanf("%lld%lld",&a,&b);
printf("%.3lf
",sum[b]-sum[a-1]);
}
//fclose(stdin);fclose(stdout);
return 0;
}
/*
5 4 8
2 3 3 3 3
1 1 3 2
1 3 5 1
2 2 4 1
2 1 3 4
1 1
2 2
3 3
4 4
5 5
1 3
2 5
1 5
*/
By njc