CCF |
您所在的位置：网站首页 › csp真题 › CCF |
|
解题思路
乍一看，本题题意极其通俗易懂，似乎与往年第三题的风格不太相符，其难点正在于无法将我们脑中简单的偏导数运算过程转化成代码，具体表现为几个关键小问题：我该如何存储最终要求导的多项式？在求偏导数时我该如何忽略其他无关变量？常系数应该如何处理，是否应该和其他乘积项统一成同一种形式？如果这些问题可以解决那么本题就可以解决了。 根据我们的数学直觉，最终要求偏导数的多项式一定是 a x 1 q x 2 w . . . x n e + b x 1 r x 2 t . . . x n y + . . . + z x 1 u x 2 i . . . x n o ax_1^qx_2^w...x_n^e+bx_1^rx_2^t...x_n^y+...+zx_1^ux_2^i...x_n^o ax1qx2w...xne+bx1rx2t...xny+...+zx1ux2i...xno，通过观察这个多项式，我们首先要思考的是如何存储多项式中的乘积项 a x 1 q x 2 w . . . x n e ax_1^qx_2^w...x_n^e ax1qx2w...xne，若以下面的方式存储，单独的一个常数也可以视为乘积项的特殊形式 struct item { ll coefficient;//系数或常数 mapmp;//一个下标对应一个指数 例如x2的5次方 那么key值为2，value值为5 item(ll coe,mapmp):coefficient(coe),mp(mp) {}//结构体构造函数 };//乘积项有了上面的基础，多项式可以以下面的方式进行存储，vector中每一项都是一个乘积项，且默认这些乘积项都由加号连接，那么遇到减号该如何处理呢？答案是可以将减号看成一个负号乘到每一个乘积项的系数coefficient中。 struct formula { vectorvec;//规定所有乘积项均用+连接 formula(vectorvec):vec(vec) {} };//多项式到此为止，最关键的数据结构模型已经建立好了，随后的多项式加法，减法，乘法，乃至求偏导，都是非常基础的模拟过程，具体请详见下方完整代码。 题目链接ccf-csp认证-梯度求解 AC代码 #include #include #include #include #include using namespace std; typedef long long ll; ll mod=1e9+7; stackst;//栈S vectorval;//存储求导时的变量值 struct item { ll coefficient;//系数或常数 mapmp;//一个下标对应一个指数 例如x2的5次方 那么key值为2，value值为5 item(ll coe,mapmp):coefficient(coe),mp(mp) {}//结构体构造函数 };//乘积项 struct formula { vectorvec;//规定所有乘积项均用+连接 formula(vectorvec):vec(vec) {} };//多项式 ll convert(string str)//字符串转换成数字 { ll num=0; for(int i=(str[0]=='-')?1:0;i ll coefficient_c=A.coefficient*B.coefficient; mapmp_c; map::iterator it; for(it=A.mp.begin();it!=A.mp.end();it++){ mp_c[it->first]=A.mp[it->first]+B.mp[it->first]; B.mp.erase(it->first); } for(it=B.mp.begin();it!=B.mp.end();it++){ mp_c[it->first]=B.mp[it->first]; } return item(coefficient_c,mp_c); } formula formula_mul(formula A,formula B)//多项式乘法 { vectorvec; for(int i=0;i vec.push_back(item_mul(A.vec[i],B.vec[j])); } } return formula(vec); } formula formula_add(formula A,formula B)//多项式加法 { for(int i=0;i for(int i=0;i ll sum=0,mul; for(int i=0;i//此乘积项含有要求导的变量才拥有计算价值 mul=(now.coefficient*now.mp[goal])%mod; now.mp[goal]--; for(map::iterator it=now.mp.begin();it!=now.mp.end();it++){ for(int k=0;ksecond;k++){ mul=(mul*val[it->first])%mod; } } sum=(sum+mul)%mod; } } return sum; } int main() { int n,m; cin>>n>>m;//求解函数中所含自变量的个数和要求解的偏导数的个数 getchar();//很重要，如果缺少这行代码会导致str为空 string str,temp; getline(cin,str); stringstream sin(str); while(sin>>temp){ if(temp=="+" || temp=="-" || temp=="*"){//运算符 formula A=st.top(); st.pop();//从栈中依次弹出两个formula formula B=st.top(); st.pop(); if(temp=="*"){ st.push(formula_mul(B,A)); }else if(temp=="+"){ st.push(formula_add(B,A)); }else{ st.push(formula_sub(A,B));//A B的顺序很重要 } }else{ mapmp;//下标 指数 vectorvec; if(temp[0]=='x'){//自变量 mp[convert(temp.substr(1,temp.length()-1))]=1; vec.push_back(item(1,mp));//把乘积项包装成多项式 }else{//常数 vec.push_back(item(convert(temp),mp));//把乘积项包装成多项式 } st.push(formula(vec)); } } for(int i=0;i cin>>value; val.push_back(value); } ll ans=function(st.top(),val[0]); cout |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |