想查看其他题的真题及题解的同学可以前往查看:CCF-CSP真题附题解大全

试题编号:202309-3
试题名称:梯度求解
时间限制:1.0s
内存限制:512.0MB
问题描述:

背景

西西艾弗岛运营公司近期在大力推广智能化市政管理系统。这套系统是由西西艾弗岛信息中心研发的。它的主要目的是,通过详细评估岛上各处的市政设施的状况,来指导市政设施的维护和更新。这套系统的核心是一套智能化的传感器网络,它能够自动地对岛上的市政设施进行评估。对市政设施的维护是需要一定成本的,而年久失修的市政设施也可能给岛上的居民造成损失。为了能够平衡成本和收益,信息中心研发了一款数学模型,描述这些变量和损益之间的复杂数学关系。要想得到最优化的成本,就要依靠梯度下降算法来求解。

梯度下降算法中,求解函数在一点处对某一自变量的偏导数是十分重要的。小 C 负责实现这个功能,但是具体的技术实现,他还是一头雾水,希望你来帮助他完成这个任务。

问题描述

设被求算的函数u=f(x1,x2,…,xn),本题目要求你求出u对xi在(a1,a2,…,an)处的偏导数∂u∂xi(a1,a2,…,an)。

求算多元函数在一点处对某一自变量的偏导数的方法是:将函数的该自变量视为单一自变量,其余自变量认为是常数,运用一元函数求导的方法求出该偏导数表达式,再代入被求算的点的坐标即可。

例如,要求算u=x1⋅x1⋅x2对x1在(1,2)处的偏导数,可以将x2视为常数,依次应用求导公式。先应用乘法的求导公式:(x1⋅(x1⋅x2))′=x1′(x1⋅x2)+x1(x1⋅x2)′;再应用常数与变量相乘的求导公式,得到x1′⋅x1⋅x2+x1⋅x2⋅x1′;最后应用公式x′=1得到1⋅x1⋅x2+x1⋅x2⋅1。整理得∂u∂x1=2×2⋅x1。再代入(1,2)得到∂u∂x1(1,2)=4。

常见的求导公式有:

  • (是常数)c′=0(c是常数)
  • x′=1
  • (u+v)′=u′+v′
  • (是常数)(cu)′=cu′(c是常数)
  • (u−v)′=u′−v′
  • (uv)′=u′v+uv′

本题目中,你需要求解的函数f仅由常数、自变量和它们的加法、减法、乘法组成。且为程序识读方便,函数表达式已经被整理为逆波兰式(后缀表达式)的形式。例如,x1⋅x1⋅x2的逆波兰式为x1 x1 * x2 *。逆波兰式即为表达式树的后序遍历的结果。若要从逆波兰式还原原始计算算式,可以按照这一方法进行:假设存在一个空栈S,依次读取逆波兰式的每一个元素,若读取到的是变量或常量,则将其压入S中;若读取到的是计算符号,则从S中取出两个元素,进行相应运算,再将结果压入S中。最后,若S中存在唯一的元素,则该表达式合法,其值即为该元素的值。例如对于逆波兰式x1 x1 * x2 *,按上述方法读取,栈S的变化情况依次为(左侧是栈底,右侧是栈顶):

  1. x1;
  2. x1,x1;
  3. (x1⋅x1);
  4. (x1⋅x1),x2;
  5. ((x1⋅x1)⋅x2)。

输入格式

从标准输入读入数据。

输入的第一行是由空格分隔的两个正整数n、m,分别表示要求解函数中所含自变量的个数和要求解的偏导数的个数。

输入的第二行是一个逆波兰式,表示要求解的函数f。其中,每个元素用一个空格分隔,每个元素可能是:

  • 一个自变量xi,用字符x后接一个正整数表示,表示第i个自变量,其中i=1,2,…,n。例如,x1表示第一个自变量x1。
  • 一个整常数,用十进制整数表示,其值在−105到105之间。
  • 一个运算符,用+表示加法,-表示减法,*表示乘法。

输入的第三行到第m+2行,每行有n+1个用空格分隔的整数。其中第一个整数是要求偏导数的自变量的编号i=1,2,…,n,随后的整数是要求算的点的坐标a1,a2,…,an。
输入数据保证,对于所有的i=1,2,…,n,ai都在−105到105之间。

输出格式

输出到标准输出中。

输出m行,每行一个整数,表示对应的偏导数对109+7取模的结果。即若结果为y,输出为k,则保证存在整数t,满足y=k+t⋅(109+7)且0≤k<109+7。

样例 1 输入

2 2
x1 x1 x1 * x2 + *
1 2 3
2 3 4

样例 1 输出

15
3

样例 1 说明

读取逆波兰式,可得被求导的式子是:u=x1⋅(x1⋅x1+x2),即u=x13+x1x2。

对x1求偏导得∂u∂x1=3×12+x2。代入(2,3)得到∂u∂x1(2,3)=15。

对x2求偏导得∂u∂x2=x1。代入(3,4)得到∂u∂x2(3,4)=3。

样例 2 输入

3 5
x2 x2 * x2 * 0 + -100000 -100000 * x2 * –
3 100000 100000 100000
2 0 0 0
2 0 -1 0
2 0 1 0
2 0 100000 0

样例 2 输出

0
70
73
73
999999867

样例 2 说明

读取逆波兰式,可得被求导的式子是:u=x2⋅x2⋅x2+0−(−105)⋅(−105)⋅x2,即u=x23−1010×2。

因为u中实际上不含x1和x3,对这两者求偏导结果均为0。

对x2求偏导得∂u∂x2=3×22−1010。

评测用例规模与约定

测试点nm表达式的性质
1, 2=1≤100仅含有 1 个元素
3, 4=1≤100仅含有一个运算符
5, 6≤10≤100含有不超过 120 个元素,且不含乘法
7, 8≤10≤100含有不超过 120 个元素
9, 10≤100≤100含有不超过 120 个元素

提示

C++ 中可以使用std::getline(std::cin, str)读入字符串直到行尾。

当计算整数n对M的模时,若n为负数,需要注意将结果调整至区间[0,M)内。

真题来源:梯度求解

感兴趣的同学可以如此编码进去进行练习提交

c++满分题解:

#include using namespace std; const int mo = 1e9+7;#define CONST -1#define VAR -2#define OP -3 int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);string s;int n, m;cin >> n >> m;getline(cin, s); // '\n'getline(cin, s);istringstream qwq(s);vector l;vector r;vector info;vector kind;stack id;int node_id = 0;while(getline(qwq, s, ' ')){if (s.size() == 1 && (s[0] == '+' || s[0] == '*' || s[0] == '-')){int rson = id.top();id.pop();int lson = id.top();id.pop();l.push_back(lson);r.push_back(rson);info.push_back(s[0]);kind.push_back(OP); id.push(node_id);++ node_id;}else if (s[0] == 'x'){int x = stoi(s.substr(1));-- x;l.push_back(-1);r.push_back(-1);info.push_back(x);kind.push_back(VAR); id.push(node_id);++ node_id;}else{int x = stoi(s);l.push_back(-1);r.push_back(-1);info.push_back(x);kind.push_back(CONST); id.push(node_id);++ node_id;}}int root = id.top();vector a(n); function(int, int)> solve = [&](int u, int x){if (kind[u] == VAR){return array{a[info[u]], (info[u] == x)};}else if (kind[u] == CONST){return array{info[u], 0};}else{auto lans = solve(l[u], x), rans = solve(r[u], x);int sum = 0, dsum = 0;if (info[u] == '+'){sum = lans[0] + rans[0];dsum = lans[1] + rans[1];if (sum >= mo)sum -= mo;if (dsum >= mo) dsum -= mo;}else if (info[u] == '-'){sum = lans[0] - rans[0];dsum = lans[1] - rans[1];if (sum >= mo)sum -= mo;if (dsum >= mo) dsum -= mo;}else{sum = 1ll * lans[0] * rans[0] % mo;dsum = (1ll * lans[0] * rans[1] % mo + 1ll * lans[1] * rans[0] % mo);if (dsum >= mo) dsum -= mo;}if (sum < 0)sum += mo;if (dsum < 0)dsum += mo;return array{sum, dsum};}};for(int i = 0; i > x;-- x;for(auto &i : a)cin >> i;cout << solve(root, x)[1] << '\n';}return 0;}

运行结果: