SRM 446(1-250pt, 1-500pt)-白红宇

SRM 446(1-250pt, 1-500pt)

阅读量：6330 次

发布时间：2019-06-22

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

嗯。。。。今天的500确实比较好

DIV1 250

　　模拟。。。略

1 // BEGIN CUT HERE  2 /*  3  * Author:  plum rain  4  * score :  5  */  6 /*  7   8  */  9 // END CUT HERE 10 #line 11 "CubeWalking.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 clr0(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; 49 typedef vector

vs; 50 typedef vector

vd; 51 typedef pair

pii; 52 typedef long long int64; 53 54 const double eps = 1e-8; 55 const double PI = atan(1.0)*4; 56 const int inf = 2139062143 / 2; 57 int temp[4][2] = { { 0, -1}, { 1, 0}, { 0, 1}, {-1, 0}}; 58 59 class CubeWalking 60 { 61 public: 62 string finalPosition(string mov){ 63 int n = sz(mov); 64 int x = 1, y = 1, dic = 0; 65 for (int i = 0; i < n; ++ i){ 66 if (mov[i] == 'L') dic = (dic + 3) % 4; 67 else if (mov[i] == 'R') dic = (dic + 1) % 4; 68 if (mov[i] == 'W') x = (x + temp[dic][0] + 3) % 3, y = (y + temp[dic][1] + 3) % 3; 69 } 70 if (x == 1 && y == 1) return "GREEN"; 71 if (!x && y == 1) return "BLUE"; 72 if (!y && x == 1) return "BLUE"; 73 if (y == 2 && x == 1) return "BLUE"; 74 if (x == 2 && y == 1) return "BLUE"; 75 return "RED"; 76 } 77 78 // BEGIN CUT HERE 79 public: 80 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(); } 81 private: 82 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(); } 83 void verify_case(int Case, const string &Expected, const string &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } } 84 void test_case_0() { string Arg0 = "LLRR"; string Arg1 = "GREEN"; verify_case(0, Arg1, finalPosition(Arg0)); } 85 void test_case_1() { string Arg0 = "WWWWWWWWWWWW"; string Arg1 = "GREEN"; verify_case(1, Arg1, finalPosition(Arg0)); } 86 void test_case_2() { string Arg0 = "WLWRW"; string Arg1 = "RED"; verify_case(2, Arg1, finalPosition(Arg0)); } 87 void test_case_3() { string Arg0 = "WWLLWRWLWLLRWW"; string Arg1 = "BLUE"; verify_case(3, Arg1, finalPosition(Arg0)); } 88 89 // END CUT HERE 90 91 }; 92 93 // BEGIN CUT HERE 94 int main() 95 { 96 // freopen( "a.out" , "w" , stdout ); 97 CubeWalking ___test; 98 ___test.run_test(-1); 99 return 0;100 }101 // END CUT HERE

View Code

DIV1 500

题意：给定一个有n个点的带权图，有一个蚂蚁要从点0到点1，它每秒走stp步，最多能走tim秒，走的时间可以少于tim秒，但一定要是整数秒。问，若蚂蚁得分为它通过的边权之和(通过某边两次则得两次分)，则求最大得分，若不能用整数秒走到1并停下，输出IMPOSSIBLE。

　　　n <= 50, stp <= 100, tim <= 10^9。

解法：首先，如果要求一定要走tim，那就很简单了，用矩阵乘法快速幂可以解决。

　　　至于走的时间可以少于tim，处理方法就是加一条1到1，长度为1s，边权为0的自环。

　　　然后，首先用矩阵乘法快速幂算出用时1s，从i点走到j点得分最高为多少。再赋值A[1][1] = max(A[1][1], 0)(若A[1][1]大于0则不用赋值)，然后再调用矩阵乘法快速幂即可。

tag:graph, matrix, 快速幂, good

1 // BEGIN CUT HERE  2 /*  3  * Author:  plum rain  4  * score :  5  */  6 /*  7   8  */  9 // END CUT HERE 10 #line 11 "AntOnGraph.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 clr0(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; 50 typedef vector

vs; 51 typedef vector

vd; 52 typedef pair

pii; 53 typedef int64 mtx[500][500]; 54 55 const double eps = 1e-8; 56 const double PI = atan(1.0)*4; 57 const int inf = 2139062143 / 2; 58 const int64 temp = 0 - (1LL<<62); 59 60 class AntOnGraph 61 { 62 public: 63 int dit[1000], n; 64 void mtx_eql(mtx &a, mtx b) 65 { 66 for (int i = 0; i < n; ++ i) for (int j = 0; j < n; ++ j) a[i][j] = b[i][j]; 67 } 68 void mtx_mul(mtx &a, mtx b) 69 { 70 mtx ret; 71 for (int i = 0; i < n; ++ i) 72 for (int j = 0; j < n; ++ j){ 73 ret[i][j] = temp; 74 for (int k = 0; k < n; ++ k) 75 if (a[i][k] != temp && b[k][j] != temp) 76 ret[i][j] = max(ret[i][j], a[i][k] + b[k][j]); 77 } 78 79 mtx_eql(a, ret); 80 } 81 void mtx_pow(mtx &an, int64 num) 82 { 83 if (num == 1) return; 84 85 mtx ret; mtx_eql(ret, an); 86 -- num; 87 88 while (num){ 89 if (num & 1) mtx_mul(ret, an); 90 num >>= 1; 91 mtx_mul(an, an); 92 } 93 94 mtx_eql(an, ret); 95 } 96 97 string gao(int64 x) 98 { 99 int len = 0;100 bool u = 0;101 if (x < 0) x = 0 - x, u = 1;102 103 while (x){104 dit[len++] = x % 10;105 x /= 10;106 }107 108 if (!len) return "0";109 string ret; ret.clear();110 if (u) ret.pb ('-');111 for (int i = len-1; i >= 0; -- i) ret.pb (dit[i] + '0');112 return ret;113 }114 string maximumBonus(vector

p0, vector

p1, vector

p2, int stp, int tim){115 n = sz(p1);116 int cnt = 0;117 mtx an;118 for (int i = 0; i < n; ++ i)119 for (int j = 0; j < n; ++ j){120 cnt = 100 * (p0[i][j]-'0') + 10 * (p1[i][j] - '0') + p2[i][j] - '0';121 if (cnt == 0) an[i][j] = temp;122 else an[i][j] = cnt - 500;123 }124 125 mtx_pow(an, (int64)stp);126 if (an[1][1] < 0) an[1][1] = 0;127 128 mtx_pow(an, (int64)tim);129 if (an[0][1] == temp) return "IMPOSSIBLE";130 else return gao(an[0][1]);131 }132 133 // BEGIN CUT HERE134 public:135 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(); }136 private:137 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(); }138 void verify_case(int Case, const string &Expected, const string &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }139 void test_case_0() { string Arr0[] = { "05","50"}; vector

Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arr1[] = { "00","00"}; vector

Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); string Arr2[] = { "01","10"}; vector

Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); int Arg3 = 3; int Arg4 = 2; string Arg5 = "3"; verify_case(0, Arg5, maximumBonus(Arg0, Arg1, Arg2, Arg3, Arg4)); }140 void test_case_1() { string Arr0[] = { "05","50"}; vector

Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arr1[] = { "00","00"}; vector

Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); string Arr2[] = { "01","10"}; vector

Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); int Arg3 = 2; int Arg4 = 3; string Arg5 = "IMPOSSIBLE"; verify_case(1, Arg5, maximumBonus(Arg0, Arg1, Arg2, Arg3, Arg4)); }141 void test_case_2() { string Arr0[] = { "0550","0000","0005","5000"}; vector

Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arr1[] = { "0000","0000","0000","0000"}; vector

Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); string Arr2[] = { "0110","0000","0001","1000"}; vector

Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); int Arg3 = 7; int Arg4 = 9; string Arg5 = "49"; verify_case(2, Arg5, maximumBonus(Arg0, Arg1, Arg2, Arg3, Arg4)); }142 void test_case_3() { string Arr0[] = { "0540","0000","0004","4000"}; vector

Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arr1[] = { "0090","0000","0009","9000"}; vector

Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); string Arr2[] = { "0190","0000","0009","9000"}; vector

Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); int Arg3 = 7; int Arg4 = 9; string Arg5 = "-5"; verify_case(3, Arg5, maximumBonus(Arg0, Arg1, Arg2, Arg3, Arg4)); }143 void test_case_4() { string Arr0[] = { "079269665406","506042219642","720809987956",144 "315099331918","952306192584","406390344278",145 "999241035142","370785209189","728363760165",146 "019367419000","279718007804","610188263490"}; vector

Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arr1[] = { "038604914953","804585763146","350629473403",147 "028096403898","575205051686","427800322647",148 "655168017864","582553303278","980402170192",149 "620737714031","686142310509","092421645460"}; vector

Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); string Arr2[] = { "063231394554","109852259379","740182746422",150 "853015982521","476805512496","898530717993",151 "430534005863","440162807186","132879980431",152 "685312177072","780267345400","959947501200"}; vector

Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); int Arg3 = 37; int Arg4 = 1221; string Arg5 = "20992235"; verify_case(4, Arg5, maximumBonus(Arg0, Arg1, Arg2, Arg3, Arg4)); }153 154 // END CUT HERE155 156 };157 158 // BEGIN CUT HERE159 int main()160 {161 // freopen( "a.out" , "w" , stdout ); 162 AntOnGraph ___test;163 ___test.run_test(-1);164 return 0;165 }166 // END CUT HERE

View Code

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