想查看其他题的真题及题解的同学可以前往查看: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。 常见的求导公式有:
本题目中,你需要求解的函数f仅由常数、自变量和它们的加法、减法、乘法组成。且为程序识读方便,函数表达式已经被整理为逆波兰式(后缀表达式)的形式。例如,x1⋅x1⋅x2的逆波兰式为
输入格式从标准输入读入数据。 输入的第一行是由空格分隔的两个正整数n、m,分别表示要求解函数中所含自变量的个数和要求解的偏导数的个数。 输入的第二行是一个逆波兰式,表示要求解的函数f。其中,每个元素用一个空格分隔,每个元素可能是:
输入的第三行到第m+2行,每行有n+1个用空格分隔的整数。其中第一个整数是要求偏导数的自变量的编号i=1,2,…,n,随后的整数是要求算的点的坐标a1,a2,…,an。 输出格式输出到标准输出中。 输出m行,每行一个整数,表示对应的偏导数对109+7取模的结果。即若结果为y,输出为k,则保证存在整数t,满足y=k+t⋅(109+7)且0≤k<109+7。 样例 1 输入
样例 1 输出
样例 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 输入
样例 2 输出
样例 2 说明读取逆波兰式,可得被求导的式子是:u=x2⋅x2⋅x2+0−(−105)⋅(−105)⋅x2,即u=x23−1010×2。 因为u中实际上不含x1和x3,对这两者求偏导结果均为0。 对x2求偏导得∂u∂x2=3×22−1010。 评测用例规模与约定
提示C++ 中可以使用 当计算整数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;}
运行结果: