csp认证：2020年12月试题刷题记录（1）

• 一、第一题：期末预测之安全指数
• 二、第二题：期末预测之最佳阈值
• 总结

题目链接：http://118.190.20.162/view.page?gpid=T123
第一题是个很简单的题目，采用了机器学习常用的ReLU函数觉得挺亲切，下面是代码：

#include 
using namespace std;
int ReLU(int a)
{
    if(a>0)
        return a;
    else
        return 0;
}
int main() {
    int n,score,w,y,sum=0;
    cin>>n;
    for(int i = 1;i<=n;i++)
    {
        cin>>score>>w;
        sum+=w*score;
    }
    y= ReLU(sum);
    cout< 
二、第二题：期末预测之最佳阈值 
题目链接：http://118.190.20.162/view.page?gpid=T122
 这个题目对刚做完第一题的表示有点没反应过来哈哈。这个题目应该是第一题的后续，也有点机器学习预测的味道。难点在于时间复杂度的优化，开始时我用了两层for循环暴力求解，事实证明只有70分（开始的想法太单纯了…）于是得考虑如何简化O(n*2)的时间复杂度。
 感觉降低时间复杂度其实就是得动脑筋想一想题目里有没有一层我还没有发现的隐藏关系，第一想法就是把阈值排个序，这样的话预测正确的次数就比较清晰了，也就是小于这个阈值且flag为0的个数加上大于这个阈值且flag为1的个数，如果这个阈值的flag是1，那么次数要再加1。
 首先引入结构体：
 
struct test
{
    int a;//表示阈值
    int flag;//表示是否挂科
};
 
接下来采用升序排序，为sort做铺垫的cmp函数：
 
bool cmp(test test1,test test2)
{
    if(test1.a!=test2.a)
        return test1.a 
这里阈值相等按flag升序排序
 设定了zero和one两个int分别表示当前阈值下flag为0的预测正确数目和1的预测正确数目。初始化就是zero和one都是0，one在赋值的时候flag为1则加1：
 
for(int i=0;i
        cin>>stu[i].a>>stu[i].flag;
        if(stu[i].flag==1)
            one++;
    }
 
之后遍历排好序的数组：flag为0那么zero加1，flag为1那么one减1
 如果阈值一样的话那么one减1zero不变，预测正确的数目一定变小，直接跳过，如果不一样那么用一个临时变量存储，并与最大值比较，更新索引。
 
if (stu[j].a > stu[j-1].a) {
            temp_correct= one + zero;
            if (temp_correct >= correct) {
                correct = temp_correct;
                temp_correct = 0;
                index = stu[j].a;
            }
        }
 
这样就通过了！完整代码如下：
 
#include 
#include 
using namespace std;
const int N = 100005;
struct test
{
    int a;//表示阈值
    int flag;//表示是否挂科
};
bool cmp(test test1,test test2)
{
    if(test1.a!=test2.a)
        return test1.a
    int n;
    cin>>n;
    test stu[N];
    int one=0,zero=0;
    int temp_correct=0;
    int correct=0;
    int index;
    for(int i=0;i
        cin>>stu[i].a>>stu[i].flag;
        if(stu[i].flag==1)
            one++;
    }
    sort(stu,stu+n,cmp);
    correct= zero+one;
    index = stu[0].a;
    for(int j=1;j
        if (stu[j-1].flag==1) {
            one--;
        } else if (stu[j-1].flag==0) {
            zero++;
        }
        if (stu[j].a > stu[j-1].a) {
            temp_correct= one + zero;
            if (temp_correct >= correct) {
                correct = temp_correct;
                temp_correct = 0;
                index = stu[j].a;
            }
        }
    }
    cout< 
总结 
这两道题做完感觉没那么难，第二题一开始想法单纯两层循环，后来没满分就冷静想了一下隐含的逻辑关系，设置了zero和one这两个变量，这样只需要一个排序的复杂度，就是O(n*logn)，快多了。