P1054 [NOIP2005 提高组] 等价表达式
如果我们计算表达式的每一项的系数，再逐一比较，难度较大。所以，我们可以将每个柿子带入10个数，算出10个结果。如果10个结果都相等，就认为两个柿子等价。
在计算一个有括号，加减乘幂运算的表达式时，如果直接求解的话，难度仍然较大。但是利用它的优先级来递归求解，可以简单很多。
具体来说，设我们当前要计算的柿子对应字符串的 \([l,r]\) 。我们先在这里边任意地找到一个优先级最低的运算，设这个运算的位置为 \(pos\) 。然后，递归求解 \([l,pos-1]\) 和 \([pos+1,r]\) 的值，再通过该运算将两个柿子合并即可。
\(code:\)
#include<iostream>
#include<cstdio>
#include<string>
#define ll long long
using namespace std;
const ll mod=1e9+7;
string b[10005],a,tmp;ll n,ans[205][55],ans1[55];
ll f(ll x,ll y){
ll sum=x;x=1;
while(y){
if(y&1)
x=x*sum%mod;
sum=sum*sum%mod;
y>>=1;
}
return x;
}
ll work(string a,ll l,ll r,ll x){
ll val=0,minn=1e12,pos,cnt=0,p[55];
for(int i=0;i<=50;++i)
p[i]=1e12;
for(int i=r;i>=l;--i){
if(a[i]==')') val+=100;
if(a[i]=='(') val-=100;
if(a[i]=='^') p[i]=val+3,++cnt;
if(a[i]=='*') p[i]=val+2,++cnt;
if(a[i]=='+') p[i]=val+1,++cnt;
if(a[i]=='-') p[i]=val+1,++cnt;
if(minn>p[i])
minn=p[i],pos=i;
}
if(cnt==0){
for(int i=l;i<=r;++i)
if(a[i]=='a')
return x;
ll num=0;
for(int i=l;i<=r;++i)
if(a[i]>='0'&&a[i]<='9')
num=(num*10%mod+a[i]-'0')%mod;
return num;
}
else{
if(a[pos]=='^')
return f(work(a,l,pos-1,x),work(a,pos+1,r,x));
if(a[pos]=='*')
return work(a,l,pos-1,x)*work(a,pos+1,r,x)%mod;
if(a[pos]=='+')
return (work(a,l,pos-1,x)+work(a,pos+1,r,x))%mod;
if(a[pos]=='-')
return (work(a,l,pos-1,x)+mod-work(a,pos+1,r,x))%mod;
}
return 0;
}
int main(){
getline(cin,a);cin>>n;getline(cin,tmp);
for(int i=1;i<=n;++i)
getline(cin,b[i]);
for(int i=1;i<=10;++i)
ans1[i]=work(a,0,a.size()-1,i);
for(int i=1;i<=n;++i){
for(int j=1;j<=10;++j)
ans[i][j]=work(b[i],0,b[i].size()-1,j);
}
for(int i=1;i<=n;++i){
bool ok=1;
for(int j=1;j<=10;++j)
if(ans1[j]!=ans[i][j])
ok=0;
if(ok)
cout<<(char)('A'-1+i);
}
return 0;
}
P1039 [NOIP2003 提高组] 侦探推理
枚举每一个人并假定他是罪犯，再枚举日期，然后判断是否矛盾即可。
\(code:\)
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<map>
using namespace std;
int n,m,p,s[105],is[105],t[105];string name[25],a[105][105],tmp;
bool ok[105],is_crime[105];
string d[10]={" ","Monday.","Tuesday.","Wednesday.","Thursday.","Friday.","Saturday.","Sunday."};
map <string,int> f;
bool judge(int talk,int x,int y,int z){
//talk:说话者，x:说话者认为他是或不是罪犯，y:假定的罪犯，z:是或不是罪犯
if((z==1&&x==y)||(z==0&&x!=y)){//这次talk说的是实话
if(t[talk]==0)//talk之前已经说过谎，不符题意
return 0;
t[talk]=1;
}
else{//这次talk说谎
if(t[talk]==1)//talk之前说实话，不符题意
return 0;
t[talk]=0;
}
if(z==t[talk]) is_crime[x]=1;//z
return 1;
}
bool judge2(int talk,int x,int y){
//talk:说话者，x:说话者认为的日期，y:假定的日期
if(x!=y){//这次talk说的是实话
if(t[talk]==1) return 0;//talk之前已经说过谎，不符题意
t[talk]=0;
}
else{//这次talk说谎
if(t[talk]==0) return 0;//talk之前说实话，不符题意
t[talk]=1;
}
return 1;
}
bool work(int crime,int date){
bool hav=0;
for(int i=1;i<=p;++i){
if(!ok[i])
continue;
hav=1;
int now=is[i];
//以下为5种情况
if(s[i]==3&&a[i][1]=="I"&&a[i][2]=="am"&&a[i][3]=="guilty."){
if(!judge(now,now,crime,1))
return 0;
}
else if(s[i]==4&&a[i][1]=="I"&&a[i][2]=="am"&&a[i][3]=="not"&&a[i][4]=="guilty."){
if(!judge(now,now,crime,0))
return 0;
}
else if(s[i]==3&&f[a[i][1]]>=1&&f[a[i][1]]<=m&&a[i][2]=="is"&&a[i][3]=="guilty."){
if(!judge(now,f[a[i][1]],crime,1))
return 0;
}
else if(s[i]==4&&f[a[i][1]]>=1&&f[a[i][1]]<=m&&a[i][2]=="is"&&a[i][3]=="not"&&a[i][4]=="guilty."){
if(!judge(now,f[a[i][1]],crime,0))
return 0;
}
else if(s[i]==3&&a[i][1]=="Today"&&a[i][2]=="is"){
int _get=0;
for(int j=1;j<=7;++j)
if(d[j]==a[i][3])
_get=j;
if(!_get)
continue;
if(!judge2(now,_get,date))
return 0;
}
}
if(!hav&&m>1){//所有人的话都不符合格式，且不止一个人，说明罪犯难以确定
cout<<"Cannot Determine\n";
return 1;
}
int sum=0,sum2=0;
for(int i=1;i<=m;++i){
if(t[i]==0) ++sum;
else if(t[i]==1)++sum2;
}
if(sum>n||m-sum2<n)//说谎的人数不符题意
return 0;
int tot=0,point=0;
for(int i=1;i<=m;++i){
int pp=f[name[i]];
if(is_crime[pp])
++tot,point=i;
}
if(tot>1)
cout<<"Cannot Determine\n";
else if(tot==1)
cout<<name[point]<<endl;
else
cout<<name[crime]<<endl;
return 1;
}
int main(){
cin>>m>>n>>p;
f["I"]=f["am"]=f["not"]=f["guilty."]=f["is"]=f["Today"]=114;
for(int i=1;i<=7;++i)
f[d[i]]=114;
for(int i=1;i<=m;++i)
cin>>name[i],f[name[i]]=i;
for(int i=1;i<=p;++i){
if(tmp=="")
cin>>tmp;
int now=f[tmp.substr(0,tmp.size()-1)];
ok[i]=1;is[i]=now;//ok[i]表示第i句话是否符合格式，is[i]表示第i句话的讲话者
while(cin>>tmp){
if(tmp[tmp.size()-1]==':')
break;
if(!f[tmp])
ok[i]=0;
a[i][++s[i]]=tmp;
}
}
for(int i=1;i<=m;++i)
for(int j=1;j<=7;++j){
for(int k=1;k<=m;++k)
t[k]=-1,is_crime[k]=0;//t[k]表示k是否说谎，is_crime[k]表示k是否是罪犯
if(work(i,j))
return 0;
}
cout<<"Impossible\n";
return 0;
}