说在前面:这道题初看有一些思路,但是细看又发现了一些问题,我看了网上的一篇博客,他的思路启发了我,但是那个博客代码居然还有编译错误,所以我带着启发独自完成了这道题。
- PS:这道题要非常注意一点的就是:防止溢出,这也是我写代码3小时,debug3小时的原因。
果然是菜就要多练(不是)
- 代码就是如下部分,注释比较清晰,应该大多能理解,过几天写一个思路复盘和易错总结。
- 然后简述一下思路吧,思路本质上就是python + 逆波兰数, 是的你没听错,是python。
- 首先我们先假设一个最简单的逆波兰
1 1 *
, 很明显是 1 * 1
;
- 如果换成
x1 x1 *
, 就变成了x1 * x1
。
- 这二者的区别的本质就是1是C++中的一种标准类型–int类型,而x1不是,所以我们要自己定义一个可以实现带未知数的* + -的数据类型(数据结构),明白这个代码就能写了。
- 然后为什么说这是python呢?因为python就是用C++/C写的,比如python给一个变量赋值为一个整数1,其实除了这个整数数值1,在python中还存放了很多相关的变量来共同描述这一个整数1,我觉得这也是为什么python不需要申明变量类型的原因。
- 然后要提一点的就是,最开始我思路卡壳,过几天再写一个复盘,说说为啥会卡壳吧~~
/*
by benny
2024.3.15
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <stack>
#include <cmath>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
struct group {
unordered_map<int, int> num;//xi 的 n次方
ll c;//常数
group(unordered_map<int, int> num1, ll c1) {
this->num.insert(num1.begin(), num1.end());
this->c = c1;
}
group operator *(group a){
unordered_map<int, int> tmp;
tmp.insert(this->num.begin(), this->num.end());
for(auto k : a.num)//注意要:合并同类型
{
if (tmp.find(k.first) == tmp.end()){
//没找到
tmp[k.first] = k.second;
}
else{
tmp[k.first] += k.second;
}
}
ll tmpc = this->c * a.c;
tmpc %= MOD;
group tgroup(tmp,tmpc);
//cout << this->c << ", " << a.c << "=" << tmpc << endl;
return tgroup;
}
};
struct unit {
vector<group> nn;
//相连默认用+
unit operator =(unit a){
for(int i = 0; i < a.nn.size(); i++){
this->nn.push_back(a.nn[i]);
}
}
unit operator *(unit a){
unit unit3;
//
// cout << "第一个";
// this->show();
// cout << "第二个";
// a.show();
for(int i = 0; i < this->nn.size(); i++){
for(int j = 0; j < a.nn.size(); j++){
group res = this->nn[i]*a.nn[j];
//cout << "检查" <<this->nn[i].c << "*" << a.nn[j].c <<" = " <<res.c << endl;
//cout << "res = " << res.c << "," << res.num[1] << endl;
//cout << "乘后内部次数" << res.num[1] << endl;
unit3.nn.push_back(res);
//cout << "乘后内部次数2:"<< unit3.nn.back().num[1] << endl;
}
}
return unit3;
}
unit operator +(unit a){
unit unit3;
for(int i = 0; i < this->nn.size(); i++)
unit3.nn.push_back(this->nn[i]);
for(int j = 0; j < a.nn.size(); j++)
unit3.nn.push_back(a.nn[j]);
return unit3;
}
unit operator -(unit a){
unit unit3;
for(int i = 0; i < this->nn.size(); i++)
unit3.nn.push_back(this->nn[i]);
for(int j = 0; j < a.nn.size(); j++){
a.nn[j].c = -a.nn[j].c;
unit3.nn.push_back(a.nn[j]);
}
return unit3;
}
void show(){
for(int i = 0; i < this->nn.size(); i++){
auto& munit = this->nn[i];
ll mc = munit.c;
cout << mc;
for(auto& k : munit.num){
cout << "X" <<k.first << "^" <<k.second;
}
if(i != this->nn.size() - 1)
cout << "+";
}
cout << endl;
}
};
//字符串转换为数字(int)
int to_num(string s) {
int ans = 0;
for(int i = 0; i < s.length(); i++) {
ans = ans*10 + (s[i]-'0');
}
return ans;
}
int n, m;
//n:自变量个数, m求解个数
stack <unit> st; //相当于通过结构体的方式,将逆波兰式展开!!!
//非常牛逼,就相当于python的一个整型和c的整型不是一个东西.
//python将int封装在一个结构体中,除了int数据存储还有其他东西。
int main() {
cin >> n >> m;
getchar();//读取回车
string bolan;
getline(cin, bolan);
int index = 0;
while(index < bolan.length()) {
if(bolan[index] == ' ') { // 如果是空格
index++;
continue;
}
else if(bolan[index] == 'x') {
//如果是变量,用定义的基本元存储
string tmp = "";
do{
tmp += bolan[++index];
}while(index+1 < bolan.length() && bolan[index+1] != ' ');//注意+1判断末尾
index++;
int under_flag = to_num(tmp);
//创建一个基本元
unordered_map<int, int> tmp_map;
tmp_map.insert({under_flag, 1});
group tgroup(tmp_map, 1);//存1次,系数为1;
unit tunit;
tunit.nn.push_back(tgroup);
st.push(tunit);
}
else if(bolan[index] >= '0' && bolan[index] <= '9'){
//遇到常数了ll
ll tmp = 0;
do{
tmp = tmp*10 + bolan[index++] - '0';//注意 - ‘0’
}while(index < bolan.length() && bolan[index] != ' ');
unordered_map<int,int> tmp_map;
group tgroup(tmp_map, tmp);//无变量,且系数为tmp;
unit tunit;
tunit.nn.push_back(tgroup);
//入栈
st.push(tunit);
}
//注意看示例,有负整数!!
else if(bolan[index] == '-' && index + 1 < bolan.length() && bolan[index+1] >= '0' && bolan[index+1] <= '9'){
index++;
//遇到常数了
ll tmp = 0;
do{
tmp = tmp*10 + bolan[index++] - '0';//注意 - ‘0’
}while(index < bolan.length() && bolan[index] != ' ');
tmp = -tmp;
unordered_map<int,int> tmp_map;
group tgroup(tmp_map, tmp);//无变量,且系数为tmp;
unit tunit;
tunit.nn.push_back(tgroup);
//入栈
st.push(tunit);
}
else {
//+ - *
//无论如何先出栈
unit t1 = st.top();
st.pop();
unit t2 = st.top();
st.pop();
if(bolan[index] == '+'){
unit mid_ans = t1 + t2;
st.push(mid_ans);
}
else if(bolan[index] == '-'){
unit mid_ans = t2 - t1;//注意顺序
st.push(mid_ans);
}
else{//*
unit mid_ans = t1 * t2;
//cout << "*后结果";
//mid_ans.show();
st.push(mid_ans);
}
index++;
}
}
//test: 输出波兰式
auto a = st.top();// 最终结果
// a.show();
for(int i = 0; i < m; i++){
int x;
scanf("%d", &x);
int *data = new int[n+10];
for(int j = 1; j <= n; j++){
scanf("%d", &data[j]);
}
ll total_ans = 0;
for(int k = 0; k < a.nn.size(); k++){
if(a.nn[k].num.find(x) == a.nn[k].num.end()){
//没找到
//cout << "meizhaodao:"<< x << "\n" ;
continue;
}
else{
int cc = a.nn[k].num[x];//记得看清是k还是i
a.nn[k].num[x]--;
ll mid_ans = 1;
for(auto &iter : a.nn[k].num){
mid_ans *= pow(data[iter.first], iter.second);
mid_ans %= MOD;
}
mid_ans *= cc * a.nn[k].c;
total_ans += mid_ans;
total_ans %= MOD;//记得取模;
//还原
a.nn[k].num[x]++;
}
}
delete []data;
while(total_ans < 0){
total_ans += MOD;
}
cout << total_ans % MOD << endl;
}
return 0;
}
以上均为个人理解,不喜勿喷,欢迎指错,欢迎讨论~~
时间不早了晚安~玛卡巴卡!