UOJ#206. 【APIO2016】Gap(交互,乱搞)

2018-06-17 20:42:10来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

有 NN 个严格递增的非负整数 a1,a2,,aNa1,a2,…,aN(0a1<a2<?<aN10180≤a1<a2<?<aN≤1018)。你需要找出 ai+1aiai+1−ai(0iN10≤i≤N−1)里的最大的值。

你的程序不能直接读入这个整数序列,但是你可以通过给定的函数来查询该序列的信息。关于查询函数的细节,请根据你所使用的语言,参考下面的实现细节部分。

你需要实现一个函数,该函数返回 ai+1aiai+1−ai(0iN10≤i≤N−1)中的最大值。

实现细节

本题只支持 C/C++/Pascal。

C/C++

你需要包含头文件 gap.h。

你需要实现一个函数 findGap(T, N),该函数接受下面的参数,并返回一个 long long 类型的整数:

  • TT:子任务的编号(11 或者 22)
  • NN:序列的长度

你的函数 findGap 可以调用系统提供的查询函数 MinMax(s, t, &mn, &mx),该函数的前两个参数 ss 和 tt 是 long long 类型的整数,后两个参数 &mn 和 &mx 是 long long 类型的整数的指针(mn 和 mx 是 long long 类型的整数)。当 MinMax(s, t, &mn, &mx) 返回时,变量 mn 将会存储满足 ai[s,t]ai∈[s,t] 中 aiai 的最小值,变量 mx 将会存储满足 ai[s,t]ai∈[s,t],aiai 的最大值。如果区间 [s,t][s,t] 中没有序列中的数,则 mn 和 mx 都将存储 1−1。在查询时需要满足 sts≤t,否则程序将会终止,该测试点计为 00 分。

Pascal

你需要使用单元 graderhelperlib。

你需要实现一个函数 findGap(T, N),该函数接受下面的参数,并返回一个 Int64 类型的整数:

  • TT:子任务的编号(11 或者 22)(Integer 类型)
  • NN:序列的长度(LongInt 类型)

你的函数 findGap 可以调用系统提供的查询函数 MinMax(s, t, mn, mx),该函数的前两个参数 ss 和 tt 是 Int64 类型的整数,后两个参数 mn 和 mx 是传引用方式的 Int64 类型的整数(过程内部对这两个变量的修改会影响到外部的对应变量的值)。当 MinMax(s, t, mn, mx) 执行完毕时,变量 mn 将会存储满足 ai[s,t]ai∈[s,t] 中 aiai 的最小值,变量 mx 将会存储满足 ai[s,t]ai∈[s,t],aiai 的最大值。如果区间 [s,t][s,t] 中没有序列中的数,则 mn 和 mx 都将存储 1−1。在查询时需要满足 sts≤t,否则程序将会终止,该测试点计为 00 分。

样例一

C/C++

考虑 N=4,a1=2,a2=3,a3=6,a4=8N=4,a1=2,a2=3,a3=6,a4=8。

则答案应该是 33,可以通过下面的几组对 MinMax 的询问获得:

  • 调用 MinMax(1, 2, &mn, &mx),则 mn 和 mx 皆返回 22。
  • 调用 MinMax(3, 7, &mn, &mx),则 mn 返回 33,mx 返回 66。
  • 调用 MinMax(8, 9, &mn, &mx),则 mn 和 mx 皆返回 88。

Pascal

考虑 N=4,a1=2,a2=3,a3=6,a4=8N=4,a1=2,a2=3,a3=6,a4=8。

则答案应该是 33,可以通过下面的几组对 MinMax 的询问获得:

  • 调用 MinMax(1, 2, mn, mx),则 mn 和 mx 皆返回 22。
  • 调用 MinMax(3, 7, mn, mx),则 mn 返回 33,mx 返回 66。
  • 调用 MinMax(8, 9, mn, mx),则 mn 和 mx 皆返回 88。

样例评测方式

样例测评系统从标准输入中读入两行。第一行包含两个整数,子任务编号 TT,和序列长度 NN。第二行包含 NN 个严格递增的非负整数。然后该程序会向标准输出中写入两行,第一行为 findGap 的返回值,第二行为花费 MM 的值。

下面的输入描述了上面的样例:

2 4
2 3 6 8

限制与约定

对于所有的测试点,有 2N1000002≤N≤100000。

每一个测试点开始测试之前,MM 都将被初始化为 00。

子任务 1(30 分):每一次调用 MinMax 都将使 MM 加 11。为了获得所有分数,需要满足对于该子任务下的所有测试点,都有 MN+12M≤N+12。

子任务 2(70 分):定义 kk 为调用 MinMax 时,区间 [s,t][s,t] 中的序列中数的数量。每次调用 MinMax,将使 MM 加上 k+1k+1。对于每一个测试点,如果 M3NM≤3N,你将得到 70 分,否则将得到 60M/N+1√160M/N+1−1 分。你的该子任务的得分是其下所有测试点中的最低分。

交互式类型的题目怎么本地测试

时间限制:1s1s

空间限制:256MB256MB

下载

样例及测评库下载

 

人生中第一道交互

30分的做法比较简单(然而想了半个小时。。)。

每次询问两端的最大值,然后不断往中间缩,这样就能把原序列恢复出来

100分做法:

首先这一部分对询问次数没有限制,这样我们考虑从最小的点开始,慢慢询问

这里用到一个非常神奇的性质

对于最大值为$r$,最小值为$l$的区间,答案的最小值为$\frac{r-l}{N-1}$

考场上想不出来,不过看到之后觉得还是挺显然的

这样我们只需要关注长度大于它的区间就可以了,直接for循环往后推

 

#include "gap.h" 
#include<queue>
#include<algorithm>
#define LL long long 
const int MAXN = 1e6 + 10;
LL a[MAXN];
long long findGap(int T, int N) {
    if(T == 1) {
        LL l = 0, r = 1e22;
        LL minn, maxn;
        int now = 0;
        while(l <= r) {
            MinMax(l + 1, r - 1, &minn, &maxn);
            if(minn == maxn && minn != -1) {a[++now] = minn;break;}
            if(minn == -1) break;
            a[++now] = minn, a[N - now + 1] = maxn;
            if(now == (N + 1)/2) break;
            l = minn, r = maxn;
        }
        LL ans = 0;
        for(int i = 2; i <= N; i++)
            ans = std::max(ans, a[i] - a[i - 1]);
        return ans;        
    }
    else  {
        LL l = 0, r = 1e22, last = -1;
        MinMax(l, r, &l, &r);
        LL len = (r - l + N - 2) / (N - 1);
        if(N == 2) return (r - l); 
        for(LL i = l; i <= r;) {
            LL s = i, t = i + len;
            MinMax(s, t, &s, &t); i += len + 1;
            if(last != -1 && s != -1) len = std::max(len, s - last);
            if(t != -1) last = t;
        } 
        return len;
    }
}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:欧拉路和欧拉回路

下一篇:folly无锁队列正确性说明