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;
}