202309 CSP认证 | 梯度求解

梯度求解

这道题是直接在考场上面做的。当然因为去年九月的我过于稚嫩,基本的字符串操作都没有完成好。
当然这次再写我发现,我的思路和在考场上面一模一样,导致还是无法下手…

无法下手的原因就是我一直在思考应该以什么样的结构来存储以及处理输入的后序表达式。先入为主的思维就是将函数的形式写成我们直观感受到的那种,然后就会发现复杂无比…每一个表达式有哪些变元?这些变元的指数是多少?表达式的系数是多少?期间还要设计到乘法操作,而且对于最后的表达式还有加法求导、减法求导和乘法求导,觉得复杂无比然后无法下手。

这道第三题的难点在思路而不是优化,有点像登机牌那道题,就是你应该如何实现。
和之前那篇博客一样(原先博客链接:202309 CSP认证),我还是参考的这位博主的代码,思路简洁,代码简单:CSP 202309-3 梯度求解

简述一下代码的思路,也就是我觉得很厉害的地方,极大程度上简化了这个问题

  1. 关于求偏导的总体思路:先直接存储表达式,不做处理,每次输入一个主元后,再按照后序栈的方式处理表达式,此时将其余变元视作和常数等同,最后的表达式只含主元。 其实在求导过程中异常复杂的地方就是涉及到太多变元的运算。如果我们想整理出一个完整的表达式,也就是在输入表达式后就做出处理,此时存储和运算就会很复杂,因为我们不能丢掉任何一个变元。而按照博主的思路,在得到主元后,我们只需要关注到主元,其他的变元直接带入赋值变成常量。此时表达式会简洁很多,也就是一个表达式中只含有(非连续次的)含主元项,以及常数项。此时加法和乘法运算都会方便很多(乘法:系数相乘指数相加;加法:重复项系数相加指数不变,非重复项直接相加
  2. 对表达式中每一项的存储结构:采用map<ll, ll>的方式存储。在第一问的基础上,此时表达式的每一项极为简洁,都可以表示为系数 x 主元^(次数)。因此一个完整的表达式只需要包含多个pair对,其中一个为指数(次数)一个为系数,很明显我们将次数作为key字段。 因此一个计算式里面包含这样一些pair<指数,系数>对,将这些pair对用map存储

在这种思路和存储模式下该题就变得简单很多,对于存储的表达式的每项元素:
如果为变元:

  • 判断是否为主元
    • 如果是主元:初始化系数为1,指数为1,压入expr栈中
    • 如果不为主元:初始化指数为0,系数直接带入赋值(视为常数项)

如果为三个操作符号中的一种,弹出栈顶的两个表达式

  • 如果为加法 :重复项系数相加指数不变,非重复项直接相加
  • 如果为减法:重复项系数相减指数不变,非重复项直接相加(注意弹出的两个表达式是哪个减去哪个)
  • 如果为乘法 :遍历每个pair对,系数相乘指数相加

满分代码+注释如下:

#include<bits/stdc++.h>
#define key first
#define value second
using namespace std;
typedef long long ll;  //为了防止计算过程中的溢出用ll存储
const int MOD = 1e9 + 7;
const int N = 110;
int n;
vector<string> vec;  //存储一个表达式
int coef[N];  //存储每个变量的取值

int to_int(string str)
{
    stringstream ssin(str);
    int x;
    ssin >> x;
    return x;
}
void handle(int to_solve)
{
    stack<map<ll, ll> > expr;
    //该代码解决此问题的核心思路:先收到要求导的变元再处理表达式,此时在处理表达式的时候只关注需要求导的变元,其他的变元直接带入数据变成一个常数
    //这样可以简化我们的存储和后续处理,只关注我们需要求导的元
    //核心结构:用一个map<ll,ll> 来存储一个表达式,其中key字段是指数,也就是次数; value字段是该次数前面的系数

    for(auto str : vec){
        map<ll, ll> temp;

        if(str[0] == 'x'){   //此时是个变元
            int index = to_int(str.substr(1));
            if(index == to_solve){     //如果是目标变元
                temp[1] = 1;           //系数为1,指数为1
            }else{    //如果不是
                temp[0] = coef[index] % MOD;  //相当于一个常数项,指数为0,系数为其取值
            }
        }

        else if(str == "+" || str == "-" || str == "*"){  //如果是符号
            map<ll, ll> pre = expr.top(); expr.pop();
            map<ll, ll> suf = expr.top(); expr.pop();  //取出两个表达式
            if(str == "+"){
                //两个表达式里面的内容做集合,指数相同的系数需要相加
                for(auto x : pre){
                    temp[x.key] = x.value % MOD;
                }

                for(auto x : suf){
                    temp[x.key] = (temp[x.key] + x.value) % MOD; //若有相同指数的是系数相加
                }
            }else if(str == "-"){
                for(auto x : suf){
                    temp[x.key] = (x.value) % MOD;
                }
                for(auto x : pre){   //注意pre是被减数
                    temp[x.key] = (temp[x.key] - x.value) % MOD;
                }
            }else{
                for(auto x : pre){
                    for(auto y : suf){   //分别相乘
                        ll xs = (x.value * y.value) % MOD; //系数相乘
                        ll zs = (x.key + y.key);           //指数相加
                        temp[zs] = (temp[zs] + xs) % MOD;  //指数相同的部分要合一而不是覆盖
                    }
                }
            }
        }
        else{   //如果是常数
            int con = to_int(str);
            temp[0] = con % MOD;  //指数为0,系数为其值
        }
        expr.push(temp);
    }

    if(expr.size() != 1) {cout << "error\n";return;}  //出错了

    ll res = 0;  //最终结果
    map<ll, ll> final_expr = expr.top(); expr.pop();  //取出最终的表达式,此时这个表达式只和指定变元相关

    for(auto item : final_expr){   //对于里面的每一个pair对,其中key是对应的指数,value该次项前面的系数
        //cout << item.key << " 一组数值   " << item.value << endl;
        //指数放下来乘系数(变成求导后的系数),指数减一(变成求导后的指数)
        ll ans = (item.value * item.key) % MOD;   //key为指数,value为系数
        ll zs = item.key - 1;  //降次
        for(int i = 0;i < zs;i ++){
            ans = (ans * coef[to_solve]) % MOD;
        }
        res += ans;
        res %= MOD;
    }

    res %= MOD;
    res = (res + MOD) % MOD;
    cout << res << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int m;
    cin >> n >> m;
    string line, str; getline(cin, line);
    getline(cin, line);

    //先不对表达式做处理,直接存入
    stringstream ssin(line);
    while(ssin >> str){
        vec.push_back(str);
    }

    while(m --){
        int index; cin >> index;
        for(int i = 1;i <= n;i ++){
            cin >> coef[i];
        }
        handle(index);  //开始求导
    }
    return 0;
}

官网结果:
在这里插入图片描述

在写题过程中在类似于62行最开始很疑惑,因为我认为访问Map里面没有的key字段是会报错的,所以我之前一直都是先调用count方法再访问,其实不需要,我测试了以下代码:

int main()
{
    map<int, int> m;
    cout << m.count(1)<<endl;
    cout<<m[1];
    cout << endl;
    cout << m.count(1);
    return 0;
}

得到输出如下:

0
0
1

好了OVER,这道题现在算是写了两次了吧,还是满经典的这道题!我觉得!要掌握这种化简的思路!!!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/472795.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

bezier曲线拟合椭圆弧线

椭圆弧线用bezier曲线拟合 。 先计算出 椭圆中心 起始角度 旋转角度 S t e p 1 : C o m p u t e ( x 1 ′ , y 1 ′ ) Step 1: Compute(x_1, y_1) Step1:Compute(x1′​,y1′​) ( x 1 ′ y 1 ′ ) ( cos ⁡ φ sin ⁡ φ − sin ⁡ φ cos ⁡ φ ) ⋅ ( x 1 − x 2 2 y 1 −…

JMH微基准测试框架学习笔记

一、简介 JMH&#xff08;Java Microbenchmark Harness&#xff09;是一个用于编写、构建和运行Java微基准测试的框架。它提供了丰富的注解和工具&#xff0c;用于精确控制测试的执行和结果测量&#xff0c;从而帮助我们深入了解代码的性能特性。 二、案例实战 在你的pom文件…

2024最新自动化测试面试题合集 (附答案)

1、你会封装自动化测试框架吗&#xff1f; 这个问得最多&#xff0c;甚至有很多公司直接写在招聘要求中&#xff01; 当然可以&#xff0c;自动化框架主要的核心框架就是分层PO模式&#xff1a;分别为&#xff1a;基础封装层BasePage&#xff0c;PO页面对象层&#xff0c;Tes…

Linux系统

yum 命令 安装软件 1.安装yum包&#xff1a; $ yum install PACKAGE_NAME Bash 2.yum包装&#xff1a; $ yum remove PACKAGE_NAME Shell 3.重新安装一个yum包&#xff1a; $ yum reinstall PACKAGE_NAME Bash 4.搜索yum包&#xff1a; $ yum search PACKAGE_NAME …

媒体发稿途径,怎么样去网络媒体投稿,媒体发布一般价格多少钱?

在信息爆炸的时代&#xff0c;媒体作为传递信息的重要渠道&#xff0c;成为企业推广的重要手段。然而&#xff0c;如何去网络媒体投稿&#xff0c;以及媒体发布的价格却是困扰很多企业和个人的问题。今天&#xff0c;我们将会为大家介绍一种简单易行的方式&#xff1a;媒介多多…

蓝桥杯练习05水果摆盘

水果摆盘 介绍 目前CSS3中新增的Flex弹性布局已经成为前端页面布局的首选方式&#xff0c;这次试题将利用Flex实现经典布局效果。 准备 开始答题前&#xff0c;需要先打开本题的项目代码文件夹&#xff0c;目录结构如下&#xff1a; 其中&#xff1a; index.css是本次需要补…

Visual Studio 2013 - 重置窗口布局

Visual Studio 2013 - 重置窗口布局 1. Microsoft Visual Studio 2013 - 重置窗口布局References 1. Microsoft Visual Studio 2013 - 重置窗口布局 窗口 -> 重置窗口布局 References [1] Yongqiang Cheng, https://yongqiang.blog.csdn.net/

闭包机制的底层实现原理

说明:此次分享不涉及ES6的let,const,块级作用域,这些其实都是对本次分享内容的扩展。 闭包的重要性 JS的内功心法,闭包是JavaScript中非常重要的核心概念,关系着JS里很多核心的机制,理解了它,很多问题都会迎刃而解,不理解闭包用JS永远像隔着一层窗户纸。 前端发展日新…

2 使用GPU理解并行计算

2.1 简介 本章旨在对并行程序设计的基本概念及其与GPU技术的联系做一个宽泛的介绍。本章主要面向具有串行程序设计经验&#xff0c;但对并行处理概念缺乏了解的读者。我们将用GPU的基本知识来讲解并行程序设计的基本概念。 2.2 传统的串行代码 绝大多数程序员是在串行程序占据…

备战蓝桥杯D33 - 真题 - 松散子序列

题目描述 解题思路 ps&#xff1a;思路是我看了大佬的题解后自己的理解&#xff0c;自己给自己捋清楚思路。 1.设置输入&#xff0c;将字符串输入 2.因为输入的是字符&#xff0c;但要找出字符的最大价值&#xff0c;所以先将字符串转化成对应的数值。 这时候就要用到ord函…

中国(京津冀)太阳能光伏展

中国(京津冀)太阳能光伏展是一场关于太阳能光伏技术和产业的展览会&#xff0c;主要在中国的京津冀地区举办。该展览会旨在推动太阳能光伏产业的发展&#xff0c;促进技术交流和商业合作。 在中国&#xff0c;太阳能光伏产业一直是重点发展的领域之一。中国政府制定了一系列政策…

水电能源智能化监控系统

水电能源智能化监控系统是利用现代信息技术&#xff0c;对水电站的运行状态、设备性能、环境参数等进行实时监测和管理的一种智能化系统。随着我国水电能源事业的快速发展&#xff0c;水电能源智能化监控系统在水电能源行业中的应用越来越广泛&#xff0c;为我国水电能源事业的…

【Qt学习笔记】(六)界面优化

界面优化 1 QSS1.1 背景介绍1.2 基本语法1.3 QSS设置方式1.3.1 指定控件样式设计1.3.2 全局样式设置1.3.3 使用 Qt Designer 编辑样式 1.4 选择器1.4.1选择器概况1.4.2 子控件选择器&#xff08;Sub-Controls&#xff09;1.4.3伪类选择器(Pseudo-States) 1.5 样式属性1.5.1 盒模…

[C++]20:unorderedset和unorderedmap结构和封装。

unorderedset和unorderedmap结构和封装 一.哈希表&#xff1a;1.直接定址法&#xff1a;2.闭散列的开放定址法&#xff1a;1.基本结构&#xff1a;2.insert3.find4.erase5.补充&#xff1a;6.pair<k,v> k的数据类型&#xff1a; 3.开散列的拉链法/哈希桶&#xff1a;1.基…

PyTorch 深度学习(GPT 重译)(四)

第二部分&#xff1a;从现实世界的图像中学习&#xff1a;肺癌的早期检测 第 2 部分的结构与第 1 部分不同&#xff1b;它几乎是一本书中的一本书。我们将以几章的篇幅深入探讨一个单一用例&#xff0c;从第 1 部分学到的基本构建模块开始&#xff0c;构建一个比我们迄今为止看…

图书馆RFID(射频识别)数据模型压缩/解压缩算法实现小工具

1. 前言 最近闲来无聊&#xff0c;看了一下《图书馆射频识别数据模型第1部分&#xff1a;数据元素的设置及应用规则》以及《图书馆射频识别数据模型第2部分&#xff1a;基于ISO/IEC 15962的数据元素编码方案》&#xff0c;决定根据上面的编码方法实现一下该算法&#xff0c;于…

算法沉淀——贪心算法四(leetcode真题剖析)

算法沉淀——贪心算法四 01.最长回文串02.增减字符串匹配03.分发饼干04.最优除法 01.最长回文串 题目链接&#xff1a;https://leetcode.cn/problems/longest-palindrome/ 给定一个包含大写字母和小写字母的字符串 s &#xff0c;返回 通过这些字母构造成的 最长的回文串 。 …

【软件测试】如何设计自动化测试脚本

企业中如何设计自动化测试脚本呢&#xff1f;今天我们就来为大家分享一些干货。 一、线性设计 线性脚本设计方式是以脚本的方式体现测试用例&#xff0c;是一种非结构化的编码方式&#xff0c;多数采用录制回放的方式&#xff0c;测试工程师通过录制回访的访问对被测系统进行…

在ComfyUI中,IP-Adapter的一大堆模型应该怎么放?

&#x1f381;背景介绍 IP-Adapter有一大堆的模型&#xff0c;那么这个模型在ComfyUI中&#xff0c;这些模型到底应该怎么放呢&#xff1f;这篇文章简单介绍一下。 首先&#xff0c;大家需要到huggingface上找到对应的模型&#xff0c;把所有的模型先下载下来。 huggingface…

vue2 项目认识 vue2 各个文件夹作用 vue工程文件作用 main.js是什么 package.json是什么

1. node_modules : 项目依赖文件夹&#xff0c;相当于java类库。依赖包 2. public 文件夹: 一般放置一些静态资源&#xff08;图片&#xff09;&#xff0c;注意&#xff1a; 放在public文件夹内的文件&#xff0c;webpack打包时候&#xff0c;会原封不动打包到dist文件夹中 …