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$框架。