当前位置: 首页 > news >正文

CSP-31补题日记--梯度求解

202309-3-梯度求解

题目链接

http://118.190.20.162/view.page?gpid=T173

最近刚刚在上数据结构二叉树
跟这道题真的是强相关
然后在就是涉及到了数学求导
这基本上是我复学两个月做的最久的题了
感觉做完这道题对栈和二叉树理解比以前清晰了很多
不摆了
上代码

** 题目思路:
题意是给我们一个后缀表达式
显然,我们就可以写出这个表达式
那么怎么来实现求导呢?
不妨讨论,常数求导equal 0;
偏导的未知数求导equal 1 ;
其他符号 a (±)b求导equal
a导 (±
)b导
这样我们是不是就可以递归实现求导呢!
分析可得做题步骤
1:利用栈来建立二叉树存表达式,因为是后缀表示,所以唯一可以考虑只使用一个栈
2:dfs遍历求导,并将结果存在二叉树里面
3:带入计算,最重要的是要取模运算(可恶)
**

/*
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef  pair<int,int> pi ;
#define if1(x) for(int i =1 ;i<=x;i++)
#define if0(x) for(int i = 0;i<x;i++)
#define jf0(x) for(int j = 0;j<x;j++)
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
int m,n,idx;
struct node{int vis_num;//1表示他是数字,0表示他是未知数,//2表示他是操作符号,3表示求偏导的未知数int x;ll val;char op;//既然要存树,那么不妨使用数组来存树int fa;int l;int r;int myself;
};
node tree[550];
//vector<node> tree;
vector<int> xs(200);
int xans;//存储偏导未知数的位置
string s;
node retu0,retux,retu1;
stack<node> sta_num;
void push_num(string x){int num = stoi(x);node te = *new(node);te.vis_num=1;te.val =num;te.fa = te.l = te.r =-1;tree[idx] = te;te.myself = idx++;// tree.push_back(te)sta_num.push(te);}
node dfs(node root){
//分析讨论vis的三种状态
//当节点未数字时,求导直接返回0;if(root.vis_num==1) return retu0;//数字求导的结果就是0//当节点遇到x时,求导时应该分两种情况判断else if(root.vis_num==0){
//若x是我们所求的偏导,我们就应该返回retuxif(root.x==xans) return retu1;   
//若x不是是我们所求未知数的偏导,
//则我们应该视为常数我们就应该返回0else return retu0;}//ok写到这里,应该是此代码最复杂的一部分
//(a*b)求导=a导*b+b导*aelse if(root.op=='*'){//注意,我们还应该给新分配的三个节点一个idx来存下来node rnode = *new(node);node lnode = *new(node);node father = *new(node);// tree.push_back(rnode);// tree.push_back(lnode);// tree.push_back(father);//先写一下左边巴lnode.vis_num=2;lnode.op = '*';lnode.l = root.l;lnode.r = dfs(tree[root.r]).myself;lnode.fa = father.myself;tree[idx]  = lnode;lnode.myself = idx++;//写右边rnode.vis_num = 2;rnode.op='*';rnode.r = root.r;rnode.l = dfs(tree[root.l]).myself;rnode.fa = father.myself;tree[idx] = rnode;rnode.myself = idx++;//写她爹father.vis_num = 2;father.op = '+';father.r = rnode.myself;father.l = lnode.myself;tree[idx] = father;father.myself = idx++;return father;}//op是+-的时候,很明显就是l导+-r导else{node father = *new(node);father.fa = father.l = father.r = -1;father.vis_num=2;father.op = root.op;father.r = dfs(tree[root.r]).myself;father.l = dfs(tree[root.l]).myself;father.myself = idx;tree[idx++] = father;return father;}
}
void init(){retu0.fa = retu0.l=retu0.r=-1;retu0.vis_num=1;retu0.val=0;retu0.myself = -2;//特殊给0;retu1.fa = retu1.r=retu1.l=-1;retu1.vis_num=1;//特殊给一个。retu1.val = 1;retu1.myself=-4;retux.fa = retux.l = retux.r=-1;retux.vis_num = 3;retux.myself = -3;//特殊给未知数的下标;return;
}
ll caculate(node root){if(root.vis_num==1)return root.val;//遇到计算偏导x时else if(root.vis_num==3)return xs[xans];//通过处理,我们可以肯定dfs后再无vis——num=0,就是未知数的情况了//写在后面,根本特殊处理不了一点点//因为它有些是在*+-里面的未知数else if(root.vis_num==0) return xs[root.x];else{//现在就是开始运算了,ll a , b ;if(root.l<0){if(root.l == -2) a=0;else if(root.l == -3) a = xs[xans];else if(root.l==-4) a = 1;}else a = caculate(tree[root.l]);if(root.r<0){if(root.r == -2) b=0;else if(root.r == -3) b = xs[xans];else if(root.r== -4) b = 1;}else b = caculate(tree[root.r]);if(root.op=='+'){return ((a%mod)+(b%mod))%mod;}else if(root.op=='-'){return ((a%mod)-(b%mod))%mod;}else{return (a%mod)*(b%mod)%mod;}}
}
void solve(){init();cin>>n>>m;//n-自变量,m-求偏导的次数getchar();getline(cin,s);int le = s.size();if0(le){//split 操作int j = i+1;while(s[j]!=' '&&j<le)j++;string temp = s.substr(i,j-i);//为数字if((temp[0]>='0'&&temp[0]<='9')||temp[0]=='-'&&j>i+1){push_num(temp);}//为未知数的时候else if(temp[0]=='x'){int te = stoi(temp.substr(1,temp.size()-1));node tt = *new(node);tt.vis_num=0;tt.x=te;tt.fa = tt.l = tt.r =-1;tree[idx]=tt;tt.myself = idx++;//tree.push_back(tt);sta_num.push(tt);}else {//通过简单分析哈,我们在遇到操作符号的时候可以更新//一下树,不如直接存树?node te = *new(node);te.vis_num=2;te.op = temp[0];te.fa =-1;te.r = sta_num.top().myself;sta_num.pop();te.l = sta_num.top().myself;sta_num.pop();tree[idx] = te;te.myself = idx++;sta_num.push(te);}i=j;//1st--bug,因为for它自己已经加一辣}//存树结束if0(m){int temp_idx = idx;//考虑后面我们可以释放一波内存//既然写的这么认真了,那么在内存方面也可以考虑变得更优。cin>>xans;//读入偏导xjf0(n)cin>>xs[j+1];//读入x的赋值,因为我们在建树的时候//我们直接存的是x的下标,所以未便于调用,从1开始存。//简单讨论,最后栈的唯一元素便是根节点。node ans = dfs(sta_num.top());ll res = caculate(ans)%mod;res = (res+mod)%mod;cout<<res<<endl;idx = temp_idx;}}
int main(){solve();// getchar();return 0;
}

相关文章:

CSP-31补题日记--梯度求解

202309-3-梯度求解 题目链接 http://118.190.20.162/view.page?gpidT173 最近刚刚在上数据结构二叉树 跟这道题真的是强相关 然后在就是涉及到了数学求导 这基本上是我复学两个月做的最久的题了 感觉做完这道题对栈和二叉树理解比以前清晰了很多 不摆了 上代码 ** 题目思路&am…...

MySQL 8.0.32 union 语句中文查不到数据

关键字 MySQL union 语句&#xff0c;中文查不到数据 问题描述 MySQL 8.0.32 union 语句&#xff0c;中文查不到数据 解决问题思路 1、Create a table test with two fields, such as id and name mysql>create table test ( id int unsigned auto_increment key, name…...

FlinkCDC系列:通过skipped.operations参数选择性处理新增、更新、删除数据

在flinkCDC源数据配置&#xff0c;通过debezium.skipped.operations参数控制&#xff0c;配置需要过滤的 oplog 操作。操作包括 c 表示插入&#xff0c;u 表示更新&#xff0c;d 表示删除。默认情况下&#xff0c;不跳过任何操作&#xff0c;以逗号分隔。配置多个操作&#xff…...

高压检测设备

比如&#xff1a;高压数字表、高压差分探头、指针式高压表、电流探枪、高压探棒 这些设备都是用来测量高压的&#xff0c;有的测电压&#xff0c;有的测电流。 高压数字表&#xff1a; 单独使用&#xff0c;功能很简单&#xff0c;有2个正负极探爪&#xff0c;把2个探爪连接到…...

Vue3问题:如何实现组件拖拽实时预览功能?

前端功能问题系列文章&#xff0c;点击上方合集↑ 序言 大家好&#xff0c;我是大澈&#xff01; 本文约3000字&#xff0c;整篇阅读大约需要5分钟。 本文主要内容分三部分&#xff0c;第一部分是需求分析&#xff0c;第二部分是实现步骤&#xff0c;第三部分是问题详解。 …...

基于jsp的采购管理系统的分析与实现

物资采购管理系统是针对内部而设计的&#xff0c;应用于的局域网&#xff0c;这样可以使得内部管理更有效的联系起来。企业采购管理系统是将IT技术用于企业采购信息的管理, 它能够收集与存储企业采购的档案信息&#xff0c;提供更新与检索企业采购信息档案的接口&#xff1b;提…...

react配置二级路由

1.在createBrowserRouter上添加basename属性&#xff0c;比如 const RouterRender createBrowserRouter([{path: /,element: <App><Login></Login></App>},...SystemRouter,...InventoryRouter,...FlowManageRouter,{path: "*",element: &…...

C++ 模板特化

非类型模板参数 定义&#xff1a;对于函数模板和类模板&#xff0c;模板参数并不局限于类型&#xff0c;普通值也可以作为模板参数 非类型模板参数定义的是常量 template<typename T, size_t N> class array; //T&#xff1a;类型模板参数 //N&#xff1a;非类型模板参…...

Spring-createBean部分源码

createBean源码&#xff1a; /*** Central method of this class: creates a bean instance,* populates the bean instance, applies post-processors, etc.* see #doCreateBean*/ Override protected Object createBean(String beanName, RootBeanDefinition mbd, Nullable …...

2015年亚太杯APMCM数学建模大赛C题识别网络中的错误连接求解全过程文档及程序

2015年亚太杯APMCM数学建模大赛 C题 识别网络中的错误连接 原题再现 网络是描述真实系统结构的强大工具——社交网络描述人与人之间的关系&#xff0c;万维网描述网页之间的超链接关系。随着现代技术的发展&#xff0c;我们积累了越来越多的网络数据&#xff0c;但这些数据部…...

js:可选链运算符(?.)和空值合并运算符(??)

文档&#xff1a; 可选链运算符&#xff08;?.&#xff09;https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Operators/Optional_chaining空值合并运算符&#xff08;??&#xff09;https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Referenc…...

【Java 进阶篇】Java ServletContext功能:获取文件服务器路径

Java ServletContext是Java EE中的一个核心接口&#xff0c;用于与Servlet容器进行通信&#xff0c;提供了许多有用的功能&#xff0c;包括获取文件服务器路径。在本文中&#xff0c;我们将详细介绍如何使用ServletContext来获取文件服务器路径&#xff0c;并提供示例代码以帮助…...

Android startActivity流程

1.常规调用 startActivity(new Intent(this,MainActivity.class)); 进入Activity的startActivity方法 /*** Same as {link #startActivity(Intent, Bundle)} with no options* specified.** param intent The intent to start.** throws android.content.ActivityNotFoundExc…...

Qt实验室

前言 本系列文章是研究和记录Qt开发过程中遇到的各种问题的集合 由于Qt是一个庞大的开发体系&#xff0c;很难用有限的文案对其做全面深入细致的讲解&#xff0c;因此市面上大多数Qt开发相关的教程都显得极其粗浅入门&#xff0c;通常只能作为最基本的入门教程。但是实际项目…...

diffusers-Load adapters

https://huggingface.co/docs/diffusers/main/en/using-diffusers/loading_adaptershttps://huggingface.co/docs/diffusers/main/en/using-diffusers/loading_adapters 有几种训练技术可以个性化扩散模型&#xff0c;生成特定主题的图像或某些风格的图像。每种训练方法都会产…...

CVI 串口调试助手

基于Labwindows CVI 2017编写的一个简单的串口调试助手&#xff0c;附带接收一个00–99的两位数并进行波形绘制的功能&#xff0c;编写过程可见&#xff1a;https://blog.csdn.net/Stark_/article/details/129003839 #include <ansi_c.h> #include <rs232.h> #incl…...

【蓝桥杯选拔赛真题48】python最小矩阵 青少年组蓝桥杯python 选拔赛STEMA比赛真题解析

目录 python最小矩阵 一、题目要求 1、编程实现 2、输入输出 二、算法分析...

如何在家庭网络中开启 IPv6内网穿透

随着互联网的不断发展&#xff0c;IPv4地址资源逐渐枯竭&#xff0c;而IPv6作为它的继任者&#xff0c;为网络连接提供了更多的IP地址。启用IPv6对于家庭网络来说变得越来越重要&#xff0c;因为它可以提供更稳定、更安全、更快速的互联网连接。本文将指导如何在家庭网络中启用…...

CodeWhisperer 的安装及体验

CodeWhisperer 是亚马逊出品的一款基于机器学习的通用代码生成器&#xff0c;可实时提供代码建议。类似 Cursor 和 Github Copilot 编码工具。 官网&#xff1a;aws.amazon.com/cn/codewhis… 在编写代码时&#xff0c;它会自动根据您现有的代码和注释生成建议。从单行代码建…...

【C/C++】虚析构和纯虚析构

纯虚析构的问题 多态使用时&#xff0c;如果子类中有属性开辟到堆区&#xff0c;那么父类指针在释放时无法调用到子类的析构代码。 解决方式&#xff1a;将父类中的析构函数改为虚析构或者纯虚析构 虚析构和纯虚析构共性&#xff1a; 可以解决父类指针释放子类对象都需要有…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

【Veristand】Veristand环境安装教程-Linux RT / Windows

首先声明&#xff0c;此教程是针对Simulink编译模型并导入Veristand中编写的&#xff0c;同时需要注意的是老用户编译可能用的是Veristand Model Framework&#xff0c;那个是历史版本&#xff0c;且NI不会再维护&#xff0c;新版本编译支持为VeriStand Model Generation Suppo…...

从实验室到产业:IndexTTS 在六大核心场景的落地实践

一、内容创作&#xff1a;重构数字内容生产范式 在短视频创作领域&#xff0c;IndexTTS 的语音克隆技术彻底改变了配音流程。B 站 UP 主通过 5 秒参考音频即可克隆出郭老师音色&#xff0c;生成的 “各位吴彦祖们大家好” 语音相似度达 97%&#xff0c;单条视频播放量突破百万…...

Django RBAC项目后端实战 - 03 DRF权限控制实现

项目背景 在上一篇文章中&#xff0c;我们完成了JWT认证系统的集成。本篇文章将实现基于Redis的RBAC权限控制系统&#xff0c;为系统提供细粒度的权限控制。 开发目标 实现基于Redis的权限缓存机制开发DRF权限控制类实现权限管理API配置权限白名单 前置配置 在开始开发权限…...

Netty自定义协议解析

目录 自定义协议设计 实现消息解码器 实现消息编码器 自定义消息对象 配置ChannelPipeline Netty提供了强大的编解码器抽象基类,这些基类能够帮助开发者快速实现自定义协议的解析。 自定义协议设计 在实现自定义协议解析之前,需要明确协议的具体格式。例如,一个简单的…...

Neo4j 完全指南:从入门到精通

第1章&#xff1a;Neo4j简介与图数据库基础 1.1 图数据库概述 传统关系型数据库与图数据库的对比图数据库的核心优势图数据库的应用场景 1.2 Neo4j的发展历史 Neo4j的起源与演进Neo4j的版本迭代Neo4j在图数据库领域的地位 1.3 图数据库的基本概念 节点(Node)与关系(Relat…...

篇章一 论坛系统——前置知识

目录 1.软件开发 1.1 软件的生命周期 1.2 面向对象 1.3 CS、BS架构 1.CS架构​编辑 2.BS架构 1.4 软件需求 1.需求分类 2.需求获取 1.5 需求分析 1. 工作内容 1.6 面向对象分析 1.OOA的任务 2.统一建模语言UML 3. 用例模型 3.1 用例图的元素 3.2 建立用例模型 …...

Linux 中替换文件中的某个字符串

如果你想在 Linux 中替换文件中的某个字符串&#xff0c;可以使用以下命令&#xff1a; 1. 基本替换&#xff08;sed 命令&#xff09; sed -i s/原字符串/新字符串/g 文件名示例&#xff1a;将 file.txt 中所有的 old_text 替换成 new_text sed -i s/old_text/new_text/g fi…...