列表

详情

NC19903. [BJOI2014]路径

描述

  
在一个N个节点的无向图（没有自环、重边）上，每个点都有一个符号， 可能是数字，也可能是加号、减号、乘号、除号、小括号。你要在这个图上数 一数，有多少种走恰好K个节点的方法，使得路过的符号串起来能够得到一 个算数表达式。路径的起点和终点可以任意选择。 所谓算数表达式，就是由运算符连接起来的一系列数字。括号可以插入在 表达式中以表明运算顺序。 
注意，你要处理各种情况，比如数字不能有多余的前导0，减号只有前面 没有运算符或数字的时候才可以当成负号，括号可以任意添加（但不能有空括 号），0可以做除数（我们只考虑文法而不考虑语意），加号不能当正号。 例如，下面的是合法的表达式： -0/0 ((0)+(((2*3+4)+(-5)+7))+(-(2*3)*6)) 而下面的不是合法的表达式： 001+0 1+2(2) 3+-3 --1 +1 ()

输入描述

第一行三个整数N,M,K，表示点的数量，边的数量和走的节点数。
第二行一个字符串，表示每个点的符号。
接下来M行，每行两个数，表示一条边连的两个点的编号。
1 ≤ N ≤20，0 ≤ M ≤ N×(N-1)/2，0 ≤ K ≤ 30

输出描述

输出一行一个整数，表示走的方法数。这个数可能比较大，你只需要输出它模1000000007的余数即可。

示例1

输入: 

6 10 3
)(1*+0
1 2
1 3
1 4
2 3
3 4
2 5
3 5
3 6
4 6
5 6

输出: 

10

说明:

一共有10条路径，构成的表达式依次是101, (1), 1+1, 1+0, 1*1, 1*0, 0+0, 0+1, 0*0, 0*1

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 6ms, 内存消耗: 748K, 提交时间: 2019-03-16 14:53:03 

#include<iostream>
#include<cstring>
#include<cstdio>
#define P 1000000007
using namespace std;
int f[25][35][35][2],map[50][50],n,m,x,y,ans,num;
char ch[30];
bool cal(int x){return ch[x]=='+'||ch[x]=='-'||ch[x]=='*'||ch[x]=='/';}
bool isnum(int x){return ch[x]>='0'&&ch[x]<='9';}
int dp(int x,int k,int c,int t){
  if (k==num) return ((c==0)&&(!cal(x)));
  int now=f[x][k][c][t];
  if (now>=0) return now;
  now=0;
  for (int i=1;i<=n;i++)
    if (map[x][i]){
      if (isnum(i)){
        if (isnum(x)){
          if (!t) (now+=dp(i,k+1,c,0))%=P;	
        }
        else if (cal(x)||ch[x]=='(') (now+=dp(i,k+1,c,ch[i]=='0'))%=P;   
      }
	  else if (ch[i]=='('||ch[i]==')'){
	     if (ch[i]=='('&&(ch[x]=='('||cal(x))) (now+=dp(i,k+1,c+1,0))%=P;
	     else if (ch[i]==')'&&c&&(isnum(x)||ch[x]==')')) (now+=dp(i,k+1,c-1,0))%=P; 
	  }   
	  else{
	    if (isnum(x)) (now+=dp(i,k+1,c,0))%=P;
	    if (ch[x]==')'||(ch[x]=='('&&ch[i]=='-')) (now+=dp(i,k+1,c,0))%=P;
	  }
    }
  f[x][k][c][t]=now;
  return now;
}
int main(){
  scanf("%d%d%d",&n,&m,&num);
  scanf("%s",ch+1);
  for (int i=1;i<=m;i++){
    scanf("%d%d",&x,&y);
    map[x][y]=map[y][x]=1;
  }	
  memset(f,-1,sizeof(f));
  for (int i=1;i<=n;i++){
    if (ch[i]=='(') (ans+=dp(i,1,1,0))%=P;
    if (ch[i]=='-') (ans+=dp(i,1,0,0))%=P;
    if (ch[i]>='0'&&ch[i]<='9')(ans+=dp(i,1,0,ch[i]=='0'))%=P;
  }
  cout<<ans<<endl; 
}

上一题

© 2024 nowcoder.com