CCF-CSP真题《202309-3 梯度求解》题解

题目

string转longlong忘记处理负数卡了半天，服了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<sstream>
typedef long long ll;
using namespace std;
int n,m,temp;
ll a[302];
string f,x,b;
ll mod=1e9+7;

struct node
{
	string con;
	node* lson;
	node* rson;
	int size;
}tree[302];

bool isSymble(string x)
{
	if(tree[temp].con=="+" || tree[temp].con=="-" || tree[temp].con=="*") return true;
	else return false;
}

ll ato(string x)
{
	ll tans = 0;
	bool flag=false;
	for(int i=0;i<x.length();i++)
	{
		if(x[i]=='-')
		{
			flag=true;
			continue;
		}
		tans *= 10;
		tans += ll(char(x[i])-'0');
		tans = tans%mod;
	}
	if(flag) tans=-tans;
//	cout<<flag;
	return tans%mod;
}

ll get(node* p)
{
	string con = p->con;
	if(con=="+") return (get(p->lson) + get(p->rson))%mod;
	if(con=="-") return (get(p->lson) - get(p->rson))%mod;
	if(con=="*") return (get(p->lson) * get(p->rson))%mod;
	if(con.substr(0,1)=="x") return a[ato(con.substr(1))]%mod;
	else return ato(con)%mod;
}

ll solve(node* p)
{
	string con = p->con;
	if(con=="+") return (solve(p->lson) + solve(p->rson))%mod;
	if(con=="-") return (solve(p->lson) - solve(p->rson))%mod;
	if(con=="*") return (((solve(p->lson)*get(p->rson))%mod) + ((solve(p->rson)*get(p->lson))%mod))%mod;
	if(con.substr(1)==b) return 1;
	else return 0;
}

int main()
{
	scanf("%d%d",&n,&m);
	getchar();
	getline(cin, f);
    stringstream ss(f);
	while(ss>>x)
	{
		temp++;
		tree[temp].con = x;
		if(isSymble(tree[temp].con))
		{
			int tmp=temp;
			tmp--;
			tree[temp].rson = &tree[tmp];
			tmp -= tree[tmp].size;
			tree[temp].lson = &tree[tmp];
			tree[temp].size = 1 + tree[temp].lson->size + tree[temp].rson->size; 
		}
		else
		{
			tree[temp].size = 1;
			tree[temp].lson = NULL;
			tree[temp].rson = NULL;
		}
	}
//	for(int i=1;i<=temp;i++)
//	{
//		cout<<i<<"\t"<<tree[i].con<<"\t"<<tree[i].size;
//		if(tree[i].lson!=NULL) cout<<"\t"<<tree[i].lson->con;
//		if(tree[i].rson!=NULL) cout<<"\t"<<tree[i].rson->con;
//		cout<<endl;
//	} 
	for(int i=1;i<=m;i++) 
	{
		cin>>b;
		for(int j=1;j<=n;j++) scanf("%lld", &a[j]);
		ll ans = solve(&tree[temp]);
		ll mans = ans%mod;
		if(mans<0) mans+=mod;
		printf("%lld\n", mans);
	}
}