UOJ Logo root的博客

博客

题解:“剑锋OI”普及组多校联盟系列赛(04)

2017-09-17 18:40:52 By root

T1 - 数字的特权

本题算法: 模拟

考察能力: 代码基础

解题思路: 使用一层 for 循环枚举每一座城市的编号,再根据题目的条件判断该城市归哪位大臣管理。因此只需要 O(n) 的时间复杂度,总用时是绰绰有余的。

代码实现:

#include <cstdio>
int n , x , y , sx = 0 , sy = 0;
int main(){
    scanf("%d%d%d" , &n , &x , &y);
    for(int i = 1 ; i <= n ; i++)
        if(x % i == y % i)
            if(x > y)
                sx++;
            else
                sy++;
            // 如果余数相同,取特权值大的一方
        else
            if(x % i > y % i)
                sx++;
            else
                sy++;
            // 否则取余数大的一方
    printf("%d %d" , sx , sy); 
    return 0;
}

T2 – 砌砖墙

本题算法: 模拟

考查能力: 观察能力,推算能力,分析能力

解题思路: 经过研究砖块的排布规律,我们发现 第奇数层 的砖块有 m 个, 第偶数层 的砖块有 m – 1 个,我们可以视两层为一循环,即一次循环使用了 2m – 1 个砖块。 输入两个砖块编号,首先我们要看是否越界。我们设一共有 p 个砖块,不难推出 p 的通项式: p = n * m – n / 2 只有 1 ~ p 的编号是合法的,一次 if 判断输出再加上 continue 即可。 接下来,我们需要分类讨论。为了便于讨论,输入两个编号中,令较小的为 x,较大的为 y。 不难发现如果 y 在 x 右边,则有 y = x + 1;如果 y 在 x 左上角,则有 y = x + m – 1;如果 y 在 x 右上角,则有 y = x + m。接下来,我们以砖块 x 为研究对象,y 用来判断相对关系。 我们上面使两层砖块为一次循环,再次观察砖块排布,我们可以将任何砖块分成 6 类: 1.砖块位于 第奇数层,且位于该层最左边。 2.砖块位于 第奇数层,且位于该层最右边。 3.砖块位于 第奇数层,且不位于该层边缘。 4.砖块位于 第偶数层,且位于该层左侧或中间。 5.砖块位于 第偶数层,且位于该层最右边。 怎么判断砖块位于 第奇数层 还是 第偶数层 呢?上面提到一次循环有 2m – 1 个砖块,那必定和取模和判断脱不了干系,继续分析,我们设砖块 x 属于一次循环的第 t 个砖块,有: t = x % (2m - 1) 特别地,如果 t = 0,表示砖块 x 属于一次循环的 第偶数行 的末尾。如果需要一次表示,有: t = (x - 1) % (2m - 1) + 1 很显然根据性质“第奇数层 的砖块有 m 个砖块, 第偶数层 的砖块有 m – 1 个砖块”,如果 t 小于等于 m,则属于 第奇数层,否则属于 第偶数层。继续根据 t,根据若干的 if 得出砖块 x 是哪一类砖块。 例如,如果 t = 1,则是第 1 类砖块,观察排布,我们发现仅当砖块 y 在砖块 x 右上角或右边一个时,砖块 x 和 y 相邻。 同理,如果 t = m,则是第 2 类砖块,再次观察排布,我们发现仅当砖块 y 在砖块 x 左上角时,砖块 x 和 y 相邻。 对于如何求出 y 在 x 的右边一个还是左右上角,我们在之前已经介绍。接下来 3 类砖块也是使用类似的方法判断关系,在这里就不一一列出方法了。 值得注意的是数据范围,有些变量要开 long long,避免出现不必要的错误。 每组砖块编号我们只需要一些 if 判断再处理,因此时间复杂度是 O(m)

代码实现:

#include <cstdio>
bool flag;
int n , m , k;
long long x , y , p , f , t;
// 注意数据范围,有些变量不得不用 long long 存 
int main(){
    scanf("%d%d%d" , &n , &m , &k);
    p = (long long)n * m - n / 2; // 算出一共有多少砖(最大编号)
    for(int i = 1 ; i <= k ; i++){
        scanf("%lld%lld" , &x , &y);
        if(x > y)
            t = x , x = y , y = t; // 把较小的编号放入 x
        if(x <= 0 || y > p){
            printf("-1\n"); // 任意一个编号超出范围,直接结束本次循环 
            continue;
        }
        // 接下来分类讨论,代码可以长,但是思路要清晰 
        f = (x - 1) % (m + m - 1) + 1;
        // 因为砖块按 多-少-多-少 排列,所以我们以两个为一循环,先找出所在层是少还是多 
        flag = false;
        if(f <= m){
            // 属于砖块多的层,再出现新的分支,下面的条件请结合原题的图思考 
            if(f == 1)
                flag = (y == x + 1 || y == x + m);
            else if(f == m)
                flag = (y == x + m - 1);
            else
                flag = (y == x + 1 || y == x + m - 1 || y == x + m);
        }else{
            // 属于砖块少的层,同样有分支,其中最左边的砖块由于性质和中间的砖块一样,合并了 
            if(f == m + m - 1)
                flag = (y == x + m - 1 || y == x + m);
            else
                flag = (y == x + 1 || y == x + m - 1 || y == x + m);
        }
        printf("%d\n" , flag); // 最后输出问题的结果 
    }
    return 0;
}

T3 – 断肠崖

本题算法: 二分 + 递推

考查能力: 分析能力,优化能力

解题思路: 只要是做二分题做多的人,从“最大……的最小值”应该已经能判断出这题的正解是二分了。我们发现,最大跳跃距离决定着能否通关,很显然,如果最大跳跃距离越大,就越有机会通关。这其中有两个因素:首先关卡有限时,如果能跳的越远,到终点的时间也自然少了;其次悬崖的宽度也决定着关卡能否通过,如果最大跳跃距离选定为 4,而有一个宽度为 5 的悬崖,此时也只能望洋兴叹了。 因此我们只需要使用二分枚举最大跳跃距离。接下来就是看能否按要求通关且用时最小了。经过仔细分析,可以得出任何一个平台,都只能从之前的平台花 1 秒跳跃而来,很明显的递推或者说线性dp思想。我们初始化 f 数组为 inf,如果平台 x 能跳到平台 y,有以下转移方程: f[y] = min{f[y] , f[x] + 1} 至于如何判断平台 x 能跳到平台 y,之前已经用二分枚举出最大跳跃距离,判断两个平台之间的相对位置是否小于等于这个距离就行了。 最后,f[n] 即是最小的总用时。如果 f[n] 仍然是 inf(无法通关)或者 大于限时 m,则不能通关,尝试增大最大跳跃距离,否则说明可以通关,缩小最大跳跃距离。 综上所述,二分时间复杂度 O(log(a[n])),check函数时间复杂度 O(n ^ 2),因此总需时间复杂度为 O(log(a[n]) n ^ 2) 实际上,check 函数还能进行优化,用一个单调队列维护能跳到接下来平台的最小的一个 f[i],即可以直接转移。总复杂度可以将为 O(log(a[n]) n),这是一个很大的优化。但是由于本算法超纲,没有列入标程。

代码实现:

#include <cstdio>
#include <cstring>
int n , m , a[801] , v[801];
int l , r , mid , res , ansx , ansy;
int Solve(int d){
    // 测试选定最大跳跃距离为 d 能否通关且通关所需最少时间 
    memset(v , 0x7f , sizeof(v)); // 清空 dp 数组为 inf
    v[1] = 0; // 初始化起点边界 
    for(int i = 2 ; i <= n ; i++)
        for(int j = i - 1 ; j >= 1 ; j--)
            if(a[i] - a[j] <= d){
                // 先看平台 j 能否跳到平台 i,再进行状态转移 
                if(v[i] > v[j] + 1)
                    v[i] = v[j] + 1;
            }else
                break;
    return v[n];
}
int main(){
    scanf("%d%d" , &n , &m);
    for(int i = 1 ; i <= n ; i++)
        scanf("%d" , &a[i]);
    l = 1 , r = ansx = a[n] - a[1]; // 最大能直接从起点跳到终点
    while(l <= r){
        mid = (l + r) / 2; // 二分枚举最大跳跃距离
        res = Solve(mid);
        if(res > m)
            l = mid + 1; // 无法通关,向上二分
        else
            r = mid - 1 , ansx = mid , ansy = res; // 可以通关,向下二分 
    }
    printf("%d\n%d" , ansx , ansy);
    return 0;
}

T4 木块迷盒

这道题有一个很显然的性质,每一次倾斜之后,木块都是紧靠着一边一块一块叠起来的,也就是说都是连续的一行(或一列)。由于木块都是一样的,所以只要知道木块每行有几个,每列有几个,最后一次操作是哪个方向,就可以输出答案。 令h[i]表示第i行木块的个数,z[i]表示第i列木块的个数。当执行1和2操作的时候,需要修改的就是h[i]数组。下面以1操作为例: 首先清空h数组,然后对于每个z[i](除了z[n]以外,因为有一个固定块),对应的h[z[i]]++,因为当前列只能到第z[i]行,对于z[n],h[z[n]+1]++,即算上固定块的高度。到现在我们记录的h数组表示到h行结束的列的个数,显然h[i]应该是h[i]+h[i+1]+…+h[n],也就是当前结束的列和还没结束的列的个数和,所以一遍后缀和即可。要注意的是,计算的时候h[1]把固定块也算进去了,所以要-1 。 其他操作也类似。单次操作为O(n)。 输出的时候,用对应的数组,靠某一边,都由最后一次操作决定,判断一下是否在木块范围内就行了。

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。