SRM 398(1-250pt)-白红宇

SRM 398(1-250pt)

阅读量：6936 次

发布时间：2019-06-27

本文共 3895 字，大约阅读时间需要 12 分钟。

题意：有两个变量x和y，三种运算符+,*,-，组成等式"变量运算符变量运算符变量运算符变量"，要求每个变量恰好出现两次，且等式的值为val的等式有多少个。注意不计算运算符的优先级，比如2+2*3先计算2+2，最终结果得12。

解法：暴力即可。O(2^4 * 3^3)。终于交到200pt了...

tag:brute-force

1 // BEGIN CUT HERE  2 /*  3  * Author:  plum rain  4  * score :  5  */  6 /*  7   8  */  9 // END CUT HERE 10 #line 11 "CountExpressions.cpp" 11 #include 
      
        12 #include 
       
         13 #include 
        
          14 #include 
         
           15 #include 
          
            16 #include 
           
             17 #include 
            
              18 #include 
             
               19 #include 
              
                20 #include 
               
                 21 #include 
                
                  22 #include 
                 
                   23 #include 
                  
                    24 #include 
                   
                     25 #include 
                    
                      26 #include 
                     
                       27 #include 
                      
                        28 #include 
                       
                         29 #include 
                        
                          30 #include 
                         
                           31 #include 
                           32 #include 
                           
                             33 #include 
                            
                              34 35 using namespace std; 36 37 #define CLR(x) memset(x, 0, sizeof(x)) 38 #define CLR1(x) memset(x, -1, sizeof(x)) 39 #define PB push_back 40 #define SZ(v) ((int)(v).size()) 41 #define ALL(t) t.begin(),t.end() 42 #define zero(x) (((x)>0?(x):-(x))

VI; 48 typedef vector

VS; 49 typedef vector

VD; 50 typedef pair

pii; 51 typedef long long int64; 52 53 const double eps = 1e-8; 54 const double PI = atan(1.0)*4; 55 const int maxint = 2139062143; 56 57 int num(int x) 58 { 59 int ret = 0; 60 while (x){ 61 if (x & 1) ++ ret; 62 x >>= 1; 63 } 64 return ret; 65 } 66 67 int gao(int s, int t, int x, int y) 68 { 69 int num = s & 1 ? x : y, times = 0; 70 s >>= 1; 71 while (times < 3){ 72 int tmp = s & 1 ? x : y; 73 int suan = t % 3; 74 if (suan == 0) num = tmp + num; 75 else if (suan == 1) num = tmp * num; 76 else num = num - tmp; 77 78 s >>= 1; t /= 3; 79 ++ times; 80 } 81 return num; 82 } 83 84 class CountExpressions 85 { 86 public: 87 int calcExpressions(int x, int y, int val){ 88 int cnt = 0; 89 int the = 3 * 3 * 3; 90 for (int i = 0; i < (1<<4); ++ i) if (num(i) == 2) 91 for (int j = 0; j < the; ++ j) 92 if (gao(i, j, x, y) == val) ++ cnt; 93 return cnt; 94 } 95 96 // BEGIN CUT HERE 97 public: 98 void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); if ((Case == -1) || (Case == 5)) test_case_5(); } 99 private:100 template

string print_array(const vector

&V) { ostringstream os; os << "{ "; for (typename vector

::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }101 void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }102 void test_case_0() { int Arg0 = 7; int Arg1 = 8; int Arg2 = 16; int Arg3 = 9; verify_case(0, Arg3, calcExpressions(Arg0, Arg1, Arg2)); }103 void test_case_1() { int Arg0 = 3; int Arg1 = 5; int Arg2 = 7; int Arg3 = 5; verify_case(1, Arg3, calcExpressions(Arg0, Arg1, Arg2)); }104 void test_case_2() { int Arg0 = 99; int Arg1 = 100; int Arg2 = 98010000; int Arg3 = 6; verify_case(2, Arg3, calcExpressions(Arg0, Arg1, Arg2)); }105 void test_case_3() { int Arg0 = -99; int Arg1 = 42; int Arg2 = -1764; int Arg3 = 2; verify_case(3, Arg3, calcExpressions(Arg0, Arg1, Arg2)); }106 void test_case_4() { int Arg0 = 100; int Arg1 = -100; int Arg2 = -100000000; int Arg3 = 0; verify_case(4, Arg3, calcExpressions(Arg0, Arg1, Arg2)); }107 void test_case_5() { int Arg0 = 1; int Arg1 = 2; int Arg2 = 5; int Arg3 = 17; verify_case(5, Arg3, calcExpressions(Arg0, Arg1, Arg2)); }108 109 // END CUT HERE110 111 };112 113 // BEGIN CUT HERE114 int main()115 {116 // freopen( "a.out" , "w" , stdout ); 117 CountExpressions ___test;118 ___test.run_test(-1);119 return 0;120 }121 // END CUT HERE

View Code

转载于:https://www.cnblogs.com/plumrain/p/srm_398.html

你可能感兴趣的文章