想查看其他题的真题及题解的同学可以前往查看：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 <bits/stdc++.h>
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<int> l;
vector<int> r;
vector<int> info;
vector<int> kind;
stack<int> 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<int> a(n);
function<array<int, 2>(int, int)> solve = [&](int u, int x){
if (kind[u] == VAR){
return array<int, 2>{a[info[u]], (info[u] == x)};
}else if (kind[u] == CONST){
return array<int, 2>{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<int, 2>{sum, dsum};
}
};
for(int i = 0; i < m; ++ i){
int x;
cin >> x;
-- x;
for(auto &i : a)
cin >> i;
cout << solve(root, x)[1] << '\n';
}
return 0;
} 运行结果：
文章出处登录后可见！
