UOJ Logo sharpland的博客

博客

2021年4月 月赛题解

2021-04-19 10:02:31 By sharpland

T1 矩形

认真审题,

如果红色被蓝色遮住的部分为整个长或整个宽,那么新矩形面积肯定就是剩下的红色举行面积。

否则输出整个红色矩形的面积

T2 三个数

数学题

7个数排一下序,你可以用任何的方法来排序。

最小的为x, 第二小的为y。 最大的为 x+y+z.

本题得到解决。

第三小的不一定是z,有可能是x+y

T3 区间

用两重循环 来 枚举所有区间,i枚举起点,j枚举终点

​ 可以用第三重循环求区间平均值

​ 再用一重循环来查找是否有数是平均值

这样我们用三重循环来解决,本题可以得到完美解决。

另外,思考一下,如果数据量扩大到5000,如何做?

T4 咒语

本题,如果枚举找$j-i\neq k-j$ 三元组,必然需要三重循环,必然超时。

本着正难则反的原则,我们考虑没有条件约束的所有三个颜色不同的三元组的个数

    for(int i=0;i<n;++i){
        if(s[i]=='R') r++;
        else if(s[i]=='G') g++;
        else b++;
    }
r*g*b 就是所求sum

然后再找出$j-i= k-j$ 符合条件的三元组个数为cnt。因为间距相等,我们只需要枚举i,再枚举j,即可求出。

    for(int i=0;i<n;++i){
        for(int j=i+1;j<n;++j){
            int k=j+(j-i);
            if(k>n-1) break;
            if(s[i]!=s[j] && s[j]!=s[k] && s[i]!=s[k]) cnt++;
        }
    }

最后 sum-cnt 就是所求。 时间复杂度为 $O(n^2)$

T5 排课

观察数据规模,本题显然需要枚举所有的方案。

每个人 有3个班级可以选择,一共有$N$ 个人,时间复杂度为 $O(3^N)$ 之后再验证是否存在矛盾

当然,更高效的是,当枚举到第$i$ 个人所属的班级,我们让其与前$i-1$的方案进行判断,看是否出现矛盾,这就是搜索中的可行性剪枝。

学过递归的同学,应该要能写出基础$dfs$框架。

评论

Zhangbotao_2026
qp
liuhanwen_2022
我giao。。。
Flux_dubes
T3可以用前缀和做
stu2020_26
YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY
fengweichen27
七扭八歪

发表评论

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