CSP-202309-3-梯度求解

• 作為一個算法小白，本人第一次接觸大模擬的題，本題的算法參考自：【CSP】202309-3 梯度求解

解題思路

1.輸入處理

• getchar();：從標準輸入讀取一個字符。這里它的作用可能是用來“吃掉”（消耗）前一個輸入后留下的換行符。確保getline能正確讀取到下一行文本。

• getline(cin, op);：從標準輸入流cin中讀取一行文本，直到遇到換行符（用戶按下回車鍵），然后將讀取到的文本（不包括換行符）存儲到之前聲明的字符串變量中。

2.逐個處理表達式中的元素

(1)變量$x_i$的表示

struct elem {int index; // 變量索引，即x的下標long long value; // 變量值long long derivative; // 對應變量的導數值
};

• 注意，這里因為最后求的是導函數的值，而無需記錄導數的形式。例如，對于$f(x)=x^2,x=1$，其導函數$f^{\prime }(x)=2x$，這里我們直接記錄$f^{\prime }(1)=2$，即derivative=2。

(2)將數字字符串轉換為長整型

long long str2ll(string a) {int sign = 1; // 判斷是正數還是負數long long ans = 0;if (a[0] == '-')sign = -1;for (int i = 0; i < a.length(); i++) {if (a[i] != '-')ans = 10 * ans + (a[i] - '0');}return ans * sign;
}

(3)使用 stringstream 逐個處理 op 字符串中的元素

• std::stringstream 是一個流類，可以像輸入/輸出流一樣操作字符串。允許把字符串分割成多個部分，根據空白字符（如空格、制表符等）來拆分原始字符串。

• 循環的作用是逐個讀取 op 字符串中的每個以空格分隔的子字符串，并在每次迭代中處理這些子字符串。這種處理方式對于解析和執行基于逆波蘭表示法（RPN）的算術表達式非常有效，因為它允許程序按照操作的順序（從左到右）逐步計算表達式的結果。

stringstream ss(op);
string s;
while (ss >> s) {}

(4)逆波蘭式的處理邏輯

• 題目所給的字符串只涉及：x，x的索引，運算符+-*，常數。
• 整理來看可以分為兩類：變量+運算符，這也就明確了處理的邏輯。

  • 變量$x_i$，存入elem中。

    if (s[0] == 'x') {elem a;a.index = str2ll(s.substr(1, s.length() - 1)); // 得到變量下標a.derivative = xIndex == a.index ? 1 : 0; // 該變量是否要被求偏導（導數是 1，否則為 0）a.value = value[a.index]; // 變量在給定的值數組中的值st.push(a); // 將包含變量信息的結構體 a 壓入棧中，以便后續計算表達式的值和導數（和數字運算一樣）
    }
    

  • 運算符，由于求導運算本質上還是算數運算，并且是給定了變量值，本質上還是我們之前遇到過的算數運算的規則：遇到運算符，移出棧頂的兩個操作數，進行對應的運算，res用于保存運算結果。

    elem op2 = st.top();
    st.pop();
    elem op1 = st.top();
    st.pop();
    elem res;
    

  • 由于求的是導數，這里的+-*不再是普通意義上的+-*，要符合導數運算的規則。

    switch (s[0]) {
    case '+': {res.value = ((op1.value + op2.value) % MOD + MOD) % MOD;res.derivative = ((op1.derivative + op2.derivative) % MOD + MOD) % MOD;break;
    }
    case '-': {res.value = ((op1.value - op2.value) % MOD + MOD) % MOD;res.derivative = ((op1.derivative - op2.derivative) % MOD + MOD) % MOD;break;
    }
    case '*': {res.value = ((op1.value * op2.value) % MOD + MOD) % MOD;res.derivative = ((op1.derivative * op2.value + op1.value * op2.derivative) % MOD + MOD) % MOD;
    }
    }
    st.push(res);
    

  • 常數，類似于非變量的$x_i$。

    else {elem a;a.value = str2ll(s);a.derivative = 0;st.push(a);
    }
    

• 最終，棧頂的結果即為運算結果。

3.完善代碼

#include <iostream>
#include <vector>
#include <stack>
#include <sstream>using namespace std;// 定義一個結構體 elem，用于表示表達式中的元素
struct elem {int index; // 變量索引long long value; // 變量值long long derivative; // 對應變量的導數
};const long long MOD = 1000000007; // 模數// 將字符串轉換為長整型
long long str2ll(string a) {int sign = 1; // 判斷是正數還是負數long long ans = 0;if (a[0] == '-')sign = -1;for (int i = 0; i < a.length(); i++) {if (a[i] != '-')ans = 10 * ans + (a[i] - '0');}return ans * sign;
}int main() {int n, m;cin >> n >> m; // 輸入變量個數和表達式數量string op;getchar();getline(cin, op); // 獲取表達式字符串vector<elem> expr;stack<elem> st;for (int i = 0; i < m; i++) {int xIndex;vector<long long> value(n + 1);cin >> xIndex; // 輸入變量xi,其余均視為常量for (int j = 1; j <= n; j++)cin >> value[j]; // 輸入每個變量的值stringstream ss(op);string s;while (ss >> s) {// 判斷是否是變量if (s[0] == 'x') {elem a;a.index = str2ll(s.substr(1, s.length() - 1)); // 得到變量的索引a.derivative = xIndex == a.index ? 1 : 0; // 變量對目標變量的導數是 1，否則為 0a.value = value[a.index]; // 變量在給定的值數組中的值st.push(a); // 將包含變量信息的結構體 a 壓入棧中，以便后續計算表達式的值和導數}// 檢查當前讀取到的字符串 s 是否只有一個字符且為加號、減號或乘號。如果是這三個運算符之一，就執行相應的運算邏輯else if (s.length() == 1 && (s[0] == '+' || s[0] == '-' || s[0] == '*')) {// 處理運算符的邏輯elem op2 = st.top();st.pop();elem op1 = st.top();st.pop();elem res;switch (s[0]) {case '+': {res.value = ((op1.value + op2.value) % MOD + MOD) % MOD;res.derivative = ((op1.derivative + op2.derivative) % MOD + MOD) % MOD;break;}case '-': {res.value = ((op1.value - op2.value) % MOD + MOD) % MOD;res.derivative = ((op1.derivative - op2.derivative) % MOD + MOD) % MOD;break;}case '*': {res.value = ((op1.value * op2.value) % MOD + MOD) % MOD;res.derivative = ((op1.derivative * op2.value + op1.value * op2.derivative) % MOD + MOD) % MOD;}}st.push(res);}else {elem a;a.value = str2ll(s);a.derivative = 0;st.push(a);}}long long ans = st.top().derivative;cout << ((ans % MOD) + MOD) % MOD << endl; // 輸出結果取模}return 0;
}