ccf-csp两道前缀和的题目
一维前缀和——期末预测之最佳阈值
题目
考虑到安全指数是一个较大范围内的整数、小菜很可能搞不清楚自己是否真的安全，顿顿决定设置一个阈值 θ，以便将安全指数 y 转化为一个具体的预测结果——“会挂科”或“不会挂科”。
因为安全指数越高表明小菜同学挂科的可能性越低，所以当 y≥θ 时，顿顿会预测小菜这学期很安全、不会挂科；反之若 y<θ ，顿顿就会劝诫小菜：“你期末要挂科了，勿谓言之不预也。”
那么这个阈值该如何设定呢？
顿顿准备从过往中寻找答案。
具体来说，顿顿评估了 m 位同学上学期的安全指数，其中第 i（1≤i≤m）位同学的安全指数为 yi，是一个 [0,108] 范围内的整数；同时，该同学上学期的挂科情况记作 resulti∈{0,1}，其中 0 表示挂科、1 表示未挂科。
相应地，顿顿用 predictθ(y) 表示根据阈值 θ 将安全指数 y 转化为的具体预测结果。
如果 predictθ(yj) 与 resultj 相同，则说明阈值为 θ 时顿顿对第 j 位同学是否挂科预测正确；不同则说明预测错误。
predictθ(y)={0 (y<θ)1 (y≥θ)
最后，顿顿设计了如下公式来计算最佳阈值 θ?:
θ?=maxargmaxθ∈yi∑j=1m(predictθ(yj)==resultj)
该公式亦可等价地表述为如下规则：
最佳阈值仅在 yi 中选取，即与某位同学的安全指数相同；
按照该阈值对这 m 位同学上学期的挂科情况进行预测，预测正确的次数最多（即准确率最高）；
多个阈值均可以达到最高准确率时，选取其中最大的。
输入格式
输入的第一行包含一个正整数 m。
接下来输入 m 行，其中第 i（1≤i≤m）行包括用空格分隔的两个整数 yi 和 resulti，含义如上文所述。
输出格式
输出一个整数，表示最佳阈值 θ?。
数据范围
70% 的测试数据保证 m≤200；
全部的测试数据保证 2≤m≤105。
输入样例1：
6
0 0
1 0
1 1
3 1``
5 1
7 1
输出样例1：
3
样例1解释
按照规则一，最佳阈值的选取范围为 {0,1,3,5,7}。
θ=0 时，预测正确次数为 4；
θ=1 时，预测正确次数为 5；
θ=3 时，预测正确次数为 5；
θ=5 时，预测正确次数为 4；
θ=7 时，预测正确次数为 3。
阈值选取为 1 或 3 时，预测准确率最高；所以按照规则二，最佳阈值的选取范围缩小为 {1,3}。
依规则三，θ?=max{1,3}=3。
输入样例2：
8
5 1
5 0
5 0
2 1
3 0
4 0
100000000 1
1 0
输出样例2：
100000000
题目解析
本题的要点就是找出一个阈值，其判断准确的次数最大。
对于判断准确，可以有如下定义：
1.小于该阈值的安全指数结果为0
2.大于该阈值的安全指数结果为1
所以我们的目的就是统计出＜的0的个数于大于的1的个数。
由于题目中m最大为1e5，使用O（n2）算法一定会超时，所以不难想出对题目中所给出的安全指数先排序再进行预处理的方法。
在这里进行的预处理就是一维的前缀和。
for(int i = 1; i <= n; i++){
sum[i] = sum[i - 1] + p[i].second;//前缀和数组，sum
}
完整代码
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<utility>
using namespace std;
typedef pair<int,int> pp;
const int maxn = 100005;
pp p[maxn];
int sum[maxn];
set<int> quchong;
int main(){
int n; cin >> n;
for(int i = 1; i <= n; i++){
int s, r; cin >> s >> r;
p[i] = pair<int, int>(s,r);
}
sort(p+1,p+n+1);
for(int i = 1; i <= n; i++){
sum[i] = sum[i - 1] + p[i].second;
}
int res = 0, cnt = 0;
for(int i = 1; i <= n; i++){
if(quchong.count(p[i].first)) continue;
quchong.insert(p[i].first);
int cntz = i - 1 - sum[i - 1];
int cnto = sum[n] - sum[i - 1];
if(cnt <= cntz + cnto){
cnt = cntz + cnto;
res = p[i].first;
}
}
cout<< res;
}
二维前缀和——邻域均值
题目
顿顿在学习了数字图像处理后，想要对手上的一副灰度图像进行降噪处理。
不过该图像仅在较暗区域有很多噪点，如果贸然对全图进行降噪，会在抹去噪点的同时也模糊了原有图像。
因此顿顿打算先使用邻域均值来判断一个像素是否处于较暗区域，然后仅对处于较暗区域的像素进行降噪处理。
待处理的灰度图像长宽皆为 n 个像素，可以表示为一个 n×n 大小的矩阵 A，其中每个元素是一个 [0,L) 范围内的整数，表示对应位置像素的灰度值。
对于矩阵中任意一个元素 Aij（0≤i,j<n），其邻域定义为附近若干元素的集和：
Neighbor(i,j,r)={Axy|0≤x,y<n and |x?i|≤r and |y?j|≤r}
这里使用了一个额外的参数 r 来指明 Aij 附近元素的具体范围。
根据定义，易知 Neighbor(i,j,r) 最多有 (2r+1)2 个元素。
如果元素 Aij 邻域中所有元素的平均值小于或等于一个给定的阈值 t，我们就认为该元素对应位置的像素处于较暗区域。
下图给出了两个例子，左侧图像的较暗区域在右侧图像中展示为黑色，其余区域展示为白色。
1.png
现给定邻域参数 r 和阈值 t，试统计输入灰度图像中有多少像素处于较暗区域。
输入格式
输入共 n+1 行。
输入的第一行包含四个用空格分隔的正整数 n、L、r 和 t，含义如前文所述。
第二到第 n+1 行输入矩阵 A。第 i+2（0≤i<n）行包含用空格分隔的 n 个整数，依次为 Ai0,Ai1,?,Ai(n?1)。
输出格式
输出一个整数，表示输入灰度图像中处于较暗区域的像素总数。
数据范围
70% 的测试数据满足 n≤100、r≤10。
全部的测试数据满足 0<n≤600、0<r≤100 且 2≤t<L≤256。
输入样例1：
4 16 1 6
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
输出样例1：
7
输入样例2：
11 8 2 2
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 7 0 0 0 7 0 0 7 7 0
7 0 7 0 7 0 7 0 7 0 7
7 0 0 0 7 0 0 0 7 0 7
7 0 0 0 0 7 0 0 7 7 0
7 0 0 0 0 0 7 0 7 0 0
7 0 7 0 7 0 7 0 7 0 0
0 7 0 0 0 7 0 0 7 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
输出样例2：
83
题目思路
本题目要求我们求二维数组的前缀和。二维数组前缀和构造过程用到了动态规划的思想。同时使用容斥原理将重复的部分减去。
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> matx[i][j];
prex[i][j] = prex[i - 1][j] + prex[i][j - 1] + matx[i][j] - prex[i - 1][j - 1];
}
}
二维前缀和在求区间和的时候也用到了容斥原理。
int sum(sq s1, sq s2) {
return prex[s2.first][s2.second] - prex[s1.first - 1][s2.second]
- prex[s2.first][s1.second - 1] + prex[s1.first - 1][s1.second - 1];
}
完整代码
#include<iostream>
#include<utility>
#include<vector>
using namespace std;
typedef pair<int, int> sq;
const int maxn = 605;
int n, L, r, t;
int prex[maxn][maxn];
int matx[maxn][maxn];
int sum(sq s1, sq s2) {
return prex[s2.first][s2.second] - prex[s1.first - 1][s2.second]
- prex[s2.first][s1.second - 1] + prex[s1.first - 1][s1.second - 1];
}
int main() {
cin >> n >> L >> r >> t;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> matx[i][j];
prex[i][j] = prex[i - 1][j] + prex[i][j - 1] + matx[i][j] - prex[i - 1][j - 1];
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
//int x1 = i - r > 0 ? i - r : 1;
//int y1 = j - r > 0 ? j - r : 1;
//int x2 = i + r <= n ? i + r : n;
//int y2 = j + r <= n ? j + r : n;
int x1 = max(1, i - r); int y1 = max(1, j - r);
int x2 = min(n, i + r); int y2 = min(n, j + r);
sq s1(x1, y1); sq s2(x2, y2);
int num = (x2 - x1 + 1) * (y2 - y1 + 1);
int s = sum(s1, s2);
if (s<=num*t) ans++;
}
}
cout << ans;
}