当前位置: 首页 > 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; 可以解决父类指针释放子类对象都需要有…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)

前言&#xff1a; 最近在做行为检测相关的模型&#xff0c;用的是时空图卷积网络&#xff08;STGCN&#xff09;&#xff0c;但原有kinetic-400数据集数据质量较低&#xff0c;需要进行细粒度的标注&#xff0c;同时粗略搜了下已有开源工具基本都集中于图像分割这块&#xff0c…...

Java毕业设计:WML信息查询与后端信息发布系统开发

JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发&#xff0c;实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构&#xff0c;服务器端使用Java Servlet处理请求&#xff0c;数据库采用MySQL存储信息&#xff0…...

并发编程 - go版

1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程&#xff0c;系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...

C++ 设计模式 《小明的奶茶加料风波》

&#x1f468;‍&#x1f393; 模式名称&#xff1a;装饰器模式&#xff08;Decorator Pattern&#xff09; &#x1f466; 小明最近上线了校园奶茶配送功能&#xff0c;业务火爆&#xff0c;大家都在加料&#xff1a; 有的同学要加波霸 &#x1f7e4;&#xff0c;有的要加椰果…...

省略号和可变参数模板

本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...