注意这里的优化：我们先将所有操作读进内存，从后往前计算出哪些操作是必要的，然后仅仅执行必要的操作就行了至于哪些操作的是必要的呢，我们需要从后往前维护当前哪些变量的值是必要的，首先，程序结束的时候，显然所有变量的值都是必要的。每当遇到一个赋值语句的时候，被覆盖的变量的值之前就是不必要的了。每当遇到一个计算语句的时候，如果修改的变量是必要的，那么显然用来作为运算的变量也就变为必要的了
Accepted354615MS1988K1633 BC++ 代码 #include < iostream > #include < cmath > #include < cstring > using namespace std; int n = 0 ; char s[ 300003 ][ 5 ]; bool useful[ 300003 ]; bool u[ 10 ]; const __int64 base = 1000000000 ; struct integer{ __int64 a[ 600 ]; int length; integer(){ memset(a, 0 , sizeof (a)); a[ 0 ] = 1 ; length = 0 ; } void operator += (integer x) { __int64 t = 0 ; if (x.length > length) length = x.length; length += 5 ; for ( int i = 0 ; i < length;i ++ ) { a[i] += (x.a[i] + t); if (a[i] >= base ) a[i] -= base , t = 1 ; else t = 0 ; } length = 599 ; while (a[length] == 0 && length > 0 ) length -- ; } void operator *= (integer x) { __int64 res[ 600 ],t; memset(res, 0 , sizeof (res)); for ( int i = 0 ;i <= length;i ++ ) { t = 0 ; for ( int j = 0 ; ! (j > x.length && t == 0 );j ++ ) { res[i + j] += (a[i] * x.a[j] + t); t = res[i + j] / base ; res[i + j] %= base ; } } memcpy(a,res, sizeof (res)); length = 599 ; while (a[length] == 0 && length > 0 ) length -- ; } void output() { int i = length; printf( " %I64d " ,a[i]); i -- ; for ( ;i >= 0 ;i -- ) printf( " I64d " ,a[i]); puts( "" ); }}ans[ 10 ]; int main(){ int i; while (gets(s[n])) n ++ ; for (i = 0 ;i < 10 ;i ++ ) u[i] = true ; for (i = n - 1 ;i >= 0 ;i -- ) { useful[i] = u[s[i][ 0 ] - ' A ' ]; if (s[i][ 3 ] == 0 ) u[s[i][ 0 ] - ' A ' ] = false ; else { if (u[s[i][ 0 ] - ' A ' ] == true ) u[s[i][ 3 ] - ' A ' ] = true ; } } for (i = 0 ;i < n;i ++ ) if (useful[i]) { if (s[i][ 3 ] == 0 ) ans[s[i][ 0 ] - ' A ' ] = ans[s[i][ 2 ] - ' A ' ]; else if (s[i][ 1 ] == ' + ' ) ans[s[i][ 0 ] - ' A ' ] += ans[s[i][ 3 ] - ' A ' ]; else if (s[i][ 1 ] == ' * ' ) ans[s[i][ 0 ] - ' A ' ] *= ans[s[i][ 3 ] - ' A ' ]; } for (i = 0 ;i < 10 ;i ++ ) ans[i].output(); return 0 ;}
这一题用JAVA处理大数很easy，但是不会JAVA程序（表示很弱）……
附上大牛编写的JAVA版代码，供ym（仰慕）。
Accepted35461375MS5268K790 BJava import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.math. * ; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader( new InputStreamReader(System.in)); int n = 10 ; BigInteger[] mem = new BigInteger[n]; for ( int i = 0 ;i < n; ++ i){ mem[i] = BigInteger.ONE; } while ( true ){ String s = br.readLine(); if (s == null ) break ; if (s.length() == 3 ){ mem[s.charAt( 0 ) - ' A ' ] = mem[s.charAt( 2 ) - ' A ' ]; } else { int n1 = s.charAt( 0 ) - ' A ' ,n2 = s.charAt( 3 ) - ' A ' ; if (s.charAt( 1 ) == ' * ' ){ mem[n1] = mem[n1].multiply(mem[n2]); } else { mem[n1] = mem[n1].add(mem[n2]); } } } for ( int i = 0 ;i < n; ++ i){ System.out.println(mem[i]); } }}
转载于:https://www.cnblogs.com/DreamUp/archive/2010/08/30/1812399.html
