CCF-CSP真题《202309-3 梯度求解》思路+python，c++满分题解

女爷i 2024-02-19 08:31 28阅读 0赞

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

<table> 
 <tbody> 
  <tr> 
   <td>试题编号：</td> 
   <td>202309-3</td> 
  </tr> 
  <tr> 
   <td>试题名称：</td> 
   <td>梯度求解</td> 
  </tr> 
  <tr> 
   <td>时间限制：</td> 
   <td>1.0s</td> 
  </tr> 
  <tr> 
   <td>内存限制：</td> 
   <td>512.0MB</td> 
  </tr> 
  <tr> 
   <td>问题描述：</td> 
   <td> <h3>背景</h3> <p>西西艾弗岛运营公司近期在大力推广智能化市政管理系统。这套系统是由西西艾弗岛信息中心研发的。它的主要目的是，通过详细评估岛上各处的市政设施的状况，来指导市政设施的维护和更新。这套系统的核心是一套智能化的传感器网络，它能够自动地对岛上的市政设施进行评估。对市政设施的维护是需要一定成本的，而年久失修的市政设施也可能给岛上的居民造成损失。为了能够平衡成本和收益，信息中心研发了一款数学模型，描述这些变量和损益之间的复杂数学关系。要想得到最优化的成本，就要依靠梯度下降算法来求解。</p> <p>梯度下降算法中，求解函数在一点处对某一自变量的偏导数是十分重要的。小 C 负责实现这个功能，但是具体的技术实现，他还是一头雾水，希望你来帮助他完成这个任务。</p> <h3>问题描述</h3> <p>设被求算的函数&nbsp;u=f(x1,x2,…,xn)，本题目要求你求出&nbsp;u&nbsp;对&nbsp;xi&nbsp;在&nbsp;(a1,a2,…,an)&nbsp;处的偏导数&nbsp;∂u∂xi(a1,a2,…,an)。</p> <p>求算多元函数在一点处对某一自变量的偏导数的方法是：将函数的该自变量视为单一自变量，其余自变量认为是常数，运用一元函数求导的方法求出该偏导数表达式，再代入被求算的点的坐标即可。</p> <p>例如，要求算&nbsp;u=x1⋅x1⋅x2&nbsp;对&nbsp;x1&nbsp;在&nbsp;(1,2)&nbsp;处的偏导数，可以将&nbsp;x2&nbsp;视为常数，依次应用求导公式。先应用乘法的求导公式：(x1⋅(x1⋅x2))′=x1′(x1⋅x2)+x1(x1⋅x2)′；再应用常数与变量相乘的求导公式，得到&nbsp;x1′⋅x1⋅x2+x1⋅x2⋅x1′；最后应用公式&nbsp;x′=1&nbsp;得到&nbsp;1⋅x1⋅x2+x1⋅x2⋅1。整理得&nbsp;∂u∂x1=2x2⋅x1。再代入&nbsp;(1,2)&nbsp;得到&nbsp;∂u∂x1(1,2)=4。</p> <p>常见的求导公式有：</p> 
    <ul> 
     <li>（是常数）c′=0&nbsp;（c是常数）</li> 
     <li>x′=1</li> 
     <li>(u+v)′=u′+v′</li> 
     <li>（是常数）(cu)′=cu′&nbsp;（c是常数）</li> 
     <li>(u−v)′=u′−v′</li> 
     <li>(uv)′=u′v+uv′</li> 
    </ul><p>本题目中，你需要求解的函数&nbsp;f&nbsp;仅由常数、自变量和它们的加法、减法、乘法组成。且为程序识读方便，函数表达式已经被整理为逆波兰式（后缀表达式）的形式。例如，x1⋅x1⋅x2&nbsp;的逆波兰式为&nbsp;<code>x1 x1 * x2 *</code>。逆波兰式即为表达式树的后序遍历的结果。若要从逆波兰式还原原始计算算式，可以按照这一方法进行：假设存在一个空栈&nbsp;S，依次读取逆波兰式的每一个元素，若读取到的是变量或常量，则将其压入&nbsp;S&nbsp;中；若读取到的是计算符号，则从&nbsp;S&nbsp;中取出两个元素，进行相应运算，再将结果压入&nbsp;S&nbsp;中。最后，若&nbsp;S&nbsp;中存在唯一的元素，则该表达式合法，其值即为该元素的值。例如对于逆波兰式&nbsp;<code>x1 x1 * x2 *</code>，按上述方法读取，栈&nbsp;S&nbsp;的变化情况依次为（左侧是栈底，右侧是栈顶）：</p> 
    <ol> 
     <li>x1；</li> 
     <li>x1，x1；</li> 
     <li>(x1⋅x1)；</li> 
     <li>(x1⋅x1)，x2；</li> 
     <li>((x1⋅x1)⋅x2)。</li> 
    </ol><h3>输入格式</h3> <p>从标准输入读入数据。</p> <p>输入的第一行是由空格分隔的两个正整数&nbsp;n、m，分别表示要求解函数中所含自变量的个数和要求解的偏导数的个数。</p> <p>输入的第二行是一个逆波兰式，表示要求解的函数&nbsp;f。其中，每个元素用一个空格分隔，每个元素可能是：</p> 
    <ul> 
     <li>一个自变量&nbsp;xi，用字符&nbsp;<code>x</code>&nbsp;后接一个正整数表示，表示第&nbsp;i&nbsp;个自变量，其中&nbsp;i=1,2,…,n。例如，<code>x1</code>&nbsp;表示第一个自变量&nbsp;x1。</li> 
     <li>一个整常数，用十进制整数表示，其值在&nbsp;−105&nbsp;到&nbsp;105&nbsp;之间。</li> 
     <li>一个运算符，用&nbsp;<code>+</code>&nbsp;表示加法，<code>-</code>&nbsp;表示减法，<code>*</code>&nbsp;表示乘法。</li> 
    </ul><p>输入的第三行到第&nbsp;m+2&nbsp;行，每行有&nbsp;n+1&nbsp;个用空格分隔的整数。其中第一个整数是要求偏导数的自变量的编号&nbsp;i=1,2,…,n，随后的整数是要求算的点的坐标&nbsp;a1,a2,…,an。<br> 输入数据保证，对于所有的&nbsp;i=1,2,…,n，ai&nbsp;都在&nbsp;−105&nbsp;到&nbsp;105&nbsp;之间。</p> <h3>输出格式</h3> <p>输出到标准输出中。</p> <p>输出&nbsp;m&nbsp;行，每行一个整数，表示对应的偏导数对&nbsp;109+7&nbsp;取模的结果。即若结果为&nbsp;y，输出为&nbsp;k，则保证存在整数&nbsp;t，满足&nbsp;y=k+t⋅(109+7)&nbsp;且&nbsp;0≤k&lt;109+7。</p> <h3>样例 1 输入</h3> 
    <blockquote> 
     <p>2 2<br> x1 x1 x1 * x2 + *<br> 1 2 3<br> 2 3 4</p> 
    </blockquote> <h3>样例 1 输出</h3> 
    <blockquote> 
     <p>15<br> 3</p> 
    </blockquote> <h3>样例 1 说明</h3> <p>读取逆波兰式，可得被求导的式子是：u=x1⋅(x1⋅x1+x2)，即&nbsp;u=x13+x1x2。</p> <p>对&nbsp;x1&nbsp;求偏导得&nbsp;∂u∂x1=3x12+x2。代入&nbsp;(2,3)&nbsp;得到&nbsp;∂u∂x1(2,3)=15。</p> <p>对&nbsp;x2&nbsp;求偏导得&nbsp;∂u∂x2=x1。代入&nbsp;(3,4)&nbsp;得到&nbsp;∂u∂x2(3,4)=3。</p> <h3>样例 2 输入</h3> 
    <blockquote> 
     <p>3 5<br> x2 x2 * x2 * 0 + -100000 -100000 * x2 * -<br> 3 100000 100000 100000<br> 2 0 0 0<br> 2 0 -1 0<br> 2 0 1 0<br> 2 0 100000 0</p> 
    </blockquote> <h3>样例 2 输出</h3> 
    <blockquote> 
     <p>0<br> 70<br> 73<br> 73<br> 999999867</p> 
    </blockquote> <h3>样例 2 说明</h3> <p>读取逆波兰式，可得被求导的式子是：u=x2⋅x2⋅x2+0−(−105)⋅(−105)⋅x2，即&nbsp;u=x23−1010x2。</p> <p>因为&nbsp;u&nbsp;中实际上不含&nbsp;x1&nbsp;和&nbsp;x3，对这两者求偏导结果均为&nbsp;0。</p> <p>对&nbsp;x2&nbsp;求偏导得&nbsp;∂u∂x2=3x22−1010。</p> <h3>评测用例规模与约定</h3> 
    <table> 
     <thead> 
      <tr> 
       <th>测试点</th> 
       <th>n</th> 
       <th>m</th> 
       <th>表达式的性质</th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td>1, 2</td> 
       <td>=1</td> 
       <td>≤100</td> 
       <td>仅含有 1 个元素</td> 
      </tr> 
      <tr> 
       <td>3, 4</td> 
       <td>=1</td> 
       <td>≤100</td> 
       <td>仅含有一个运算符</td> 
      </tr> 
      <tr> 
       <td>5, 6</td> 
       <td>≤10</td> 
       <td>≤100</td> 
       <td>含有不超过 120 个元素，且不含乘法</td> 
      </tr> 
      <tr> 
       <td>7, 8</td> 
       <td>≤10</td> 
       <td>≤100</td> 
       <td>含有不超过 120 个元素</td> 
      </tr> 
      <tr> 
       <td>9, 10</td> 
       <td>≤100</td> 
       <td>≤100</td> 
       <td>含有不超过 120 个元素</td> 
      </tr> 
     </tbody> 
    </table><h3>提示</h3> <p>C++ 中可以使用&nbsp;<code>std::getline(std::cin, str)</code>&nbsp;读入字符串直到行尾。</p> <p>当计算整数&nbsp;n&nbsp;对&nbsp;M&nbsp;的模时，若&nbsp;n&nbsp;为负数，需要注意将结果调整至区间&nbsp;[0,M)&nbsp;内。</p> </td> 
  </tr> 
 </tbody> 
</table>

**真题来源：**[梯度求解][Link 1]

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

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

**运行结果：**![7573bcea41204c5996460c375cc08933.png][]

[CCF-CSP]: https://blog.csdn.net/weixin_53919192/article/details/124893395?spm=1001.2014.3001.5502
[Link 1]: http://118.190.20.162/view.page?gpid=T173
[7573bcea41204c5996460c375cc08933.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/b570fcd215ec43f1895c745136a94d53.png