SRM144 - SRM 148(少144-DIV1-LV3，147-DIV2-LV3)

时间：2023-02-08 16:25:00

SRM 144

DIV 1 500pt

tag:组合

题意：彩票中奖。给定n, m，从1-n中选择m个数组成数列a1, a2, a3...am。对于数列{am}分别满足以下条件的概率：

　　　(1)数列所有元素不相同且非严格递增；

　　　(2)数列元素可以相同，可以递减；

　　　(3)数列元素不相同，可以递减；

　　　(4)数列元素可以相同，且非严格递增。

解法：所有四种情况均可以用排列组合公式直接解决，要用大数。最难的是最后一种情况，我也是最后一种情况公式写错了。

　　　并且，最后一种情况公式的推导过程也可以看一看官方题解，是一种以前从来没用过的思考方法。

 #include <cstdlib>

 #include <cctype>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 #include <algorithm>

 #include <vector>

 #include <string>

 #include <iostream>

 #include <sstream>

 #include <map>

 #include <set>

 #include <queue>

 #include <stack>

 #include <fstream>

 #include <numeric>

 #include <iomanip>

 #include <bitset>

 #include <list>

 #include <stdexcept>

 #include <functional>

 #include <utility>

 #include <ctime>

 using namespace std;

 #define CLR(x) memset(x, 0, sizeof(x))

 #define PB push_back

 #define SZ(v) ((int)(v).size())

 #define rep(i, n) for(long long i = 0; i < (n); i ++)

 #define repf(i, a, b) for(long long i = (a); i <= (b); i ++)

 #define repd(i, a, b) for(long long i = (a); i >= (b); i --)

 #define flin freopen( "a.in" , "r" , stdin )

 #define flout freopen( "a.out" , "w" , stdout )

 #define out(x) cout<<#x<<':'<<(x)<<endl

 #define tst(a) cout<<#a<<endl

 #define CINBEQUICKER std::ios::sync_with_stdio(false)

 #define flag fla

 typedef vector<int> VI;

 typedef vector<string> VS;

 typedef vector<double> VD;

 typedef unsigned long long int64;

 const double eps = 1e-;

 const double PI = atan(1.0)*;

 const int maxint = ;

 inline int MyMod( int a , int b ) { return (a%b+b)%b;}

 class Node{

     public:

         string name;

         int64 num;

 }node[];

 bool cmp( Node x , Node y )

 {

     if( x.num < y.num )

         return true;

     else if( x.num == y.num && x.name < y.name )

         return true;

     return false;

 }

 int64 MyPow( int64 p , int64 n )

 {

     int64 sq = ;

     while( n >  ){

         if( n %  )

             sq =  sq * p;

         n /= ;

         p = p * p;

     }

     return sq;

 }

 int64 C( int64 x , int64 y )

 {

     int64 ans = ;

     for( int64 i = y , j =  ; i > y-x ; i-- , j ++ )

         ans = (ans*i) / j;

     return ans;

 }

 int64 A( int64 x , int64 y )

 {

     int64 ans = C(x,y);

     repd( i , x ,  )

         ans *= i;

     return ans;

 }

 int64 Ask_Num( int a , int b , bool c , bool d )

 {

     int64 ret;

     if( c && d )

         ret = C(b,a);

     if( c && !d ){

         //ret = MyPow(a,b) - C(b,a);                /*Think : Why Wrong by this way?*/

                 /*很好的组合问题，以下代码公式为C(b,a+b-1)Think why*/

         ret = ;

         for( int64 i =  ; i < b ; i ++ )

             ret *= ( a + b - i -  );

         for( int64 i =  ; i < b ; i ++ )

             ret /= ( i +  );

                 /* end */

     }

     if( !c && d )

         ret = A(b,a);

     if( !c && !d )

         ret = MyPow(a,b);

     return ret;

 }

 class Lottery

 {

     public:

         vector <string> sortByOdds(vector <string> rules){

             int n = SZ( rules );

             rep( i , n ){

                 node[i].name.clear();

                 string s = rules[i];

                 int len = SZ(s);

                 int flag;

                 rep( j , len ){

                     if( s[j] == ':' ){

                         flag = j;

                         break;

                     }

                     node[i].name.PB(s[j]);

                 }

                 flag += ;

                 int a = ( s[flag] - '' ) *  + s[flag+] - '';

                 flag += ;

                 if( s[flag] != ' ' )

                     a = a *  + s[flag++] - '';

                 flag ++;

                 int b;

                 b = s[flag] - '';

                 flag += ;

                 bool c = ( s[flag] == 'T' );

                    flag += ;

                 bool d = ( s[flag] == 'T' );

                 node[i].num = Ask_Num( a , b , c , d );

             }

             sort( node , node+n , cmp );

             VS anss;

             anss.clear();

             rep( i , n )

                 anss.PB( node[i].name );

             return (anss);

         }

         //by plum rain

 };

DIV 1 1100pt

tag:没做，似乎图论

SRM 145

DIV 2 1100pt, DIV 1 600pt

tag: 模拟

 // BEGIN CUT HERE

 /*

 */

 // END CUT HERE

 #line 7 "VendingMachine.cpp"

 #include <cstdlib>

 #include <cctype>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 #include <algorithm>

 #include <vector>

 #include <string>

 #include <iostream>

 #include <sstream>

 #include <map>

 #include <set>

 #include <queue>

 #include <stack>

 #include <fstream>

 #include <numeric>

 #include <iomanip>

 #include <bitset>

 #include <list>

 #include <stdexcept>

 #include <functional>

 #include <utility>

 #include <ctime>

 using namespace std;

 #define CLR(x) memset(x, 0, sizeof(x))

 #define PB push_back

 #define SZ(v) ((int)(v).size())

 #define rep(i, n) for(long long i = 0; i < (n); i ++)

 #define repf(i, a, b) for(long long i = (a); i <= (b); i ++)

 #define repd(i, a, b) for(long long i = (a); i >= (b); i --)

 #define flin freopen( "a.in" , "r" , stdin )

 #define flout freopen( "a.out" , "w" , stdout )

 #define out(x) cout<<#x<<':'<<(x)<<endl

 #define tst(a) cout<<#a<<endl

 #define CINBEQUICKER std::ios::sync_with_stdio(false)

 typedef vector<int> VI;

 typedef vector<string> VS;

 typedef vector<double> VD;

 typedef long long int64;

 const double eps = 1e-;

 const double PI = atan(1.0)*;

 const int maxint = ;

 inline int MyMod( int a , int b ) { return (a%b+b)%b;}

 inline void swa(int &a, int &b) {int t = a;a = b;b = t;}

 struct PUR{

     int c, s;

     int time;

 }bn[];

 int an[][];

 int cn[];

 int snum, cnum, pnum;

 int rot(int a, int b)

 {

     if (a > b)

         swa(a, b);

     return min (b-a, cnum-b+a);

 }

 int find_max()

 {

     int tmp = , ret = ;

     rep (i, cnum)

         if (tmp < cn[i]){

             tmp = cn[i];

             ret = i;

         }

     return ret;

 }

 int solve()

 {

     int ret = ;

     CLR(cn);

     rep (i, cnum)

         rep (j, snum)

             cn[i] += an[j][i];

     int flag = find_max();

     ret += rot (, flag);

     rep (i, pnum){

         int s = bn[i].s, c = bn[i].c, tim = bn[i].time;

         if (an[s][c] == )

             return -;

         cn[c] -= an[s][c];

         an[s][c] = ;

         ret += rot (c, flag);

         flag = c;

         if (i < pnum- && bn[i+].time - tim >= ){

             int pos = flag;

             flag = find_max();

             ret += rot (flag, pos);

         }

     }

     int pos = flag;

     flag = find_max();

     ret += rot (pos, flag);

     return ret;

 }

 class VendingMachine

 {

     public:

         int motorUse(vector <string> prices, vector <string> purchases){

                              /*data initial*/

             CLR(an);

             snum = SZ(prices);

                 int a = , pos = ;

             rep (i, snum){

                 string s = prices[i];

                 int size = SZ(s);

                 rep (j, size){

                     if (s[j] == ' '){

                         an[i][pos++] = a;

                         a = ;

                         continue;

                     }

                     a = a *  + s[j] - '';

                 }

                 an[i][pos++] = a;

                 cnum = pos;

                 a = ;

                 pos = ;

             }

             cout << endl;

             pnum = SZ(purchases);

             rep (i, pnum){

                 int a = ;

                 string s = purchases[i];

                 int j = ;

                 while (s[j] != ','){

                     a = a *  + s[j] - '';

                     j ++;

                 }

                 bn[i].s = a;

                 a = ; j ++;

                 while (s[j] != ':'){

                     a = a *  + s[j] - '';

                     j ++;

                 }

                 bn[i].c = a;

                 a = ; j ++;

                 while (j < SZ(s)){

                     a = a *  + s[j] - '';

                     j ++;

                 }

                 bn[i].time = a;

             }

                     /*end initial*/

             return (solve());

         }

         //by plum rain

 };

DIV 1 1000pt

tag:dp

题意：爬山，从高度为0处爬高度为h的山，当前高度为k时，经过一步可以爬到k-1, k, k+1处。给定数字h, n, 数组{an}，求满足以下条件的爬山方法种数：

　　　(1)爬山过程中，必须到达过至少一次高度h处

　　　(2)从高度0处开始爬山，并且最终回到高度0处，中途不能到高度0处

　　　(3)总共走了n步

　　　(4)如果将每一步到达的高度依次计入一个数组，比如从0爬到1再回到0计为数组{0, 1, 0},则{an}是它的一个子集。

解法：dp，比较普通，没什么好说的。感觉作为一道div1 lv3的题，并不难，只是情况比较复杂，我开了4维数组，写了两遍代码。

　　　还是代码功底太弱了.....

 #include <cstdlib>

 #include <cctype>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 #include <algorithm>

 #include <vector>

 #include <string>

 #include <iostream>

 #include <sstream>

 #include <map>

 #include <set>

 #include <queue>

 #include <stack>

 #include <fstream>

 #include <numeric>

 #include <iomanip>

 #include <bitset>

 #include <list>

 #include <stdexcept>

 #include <functional>

 #include <utility>

 #include <ctime>

 using namespace std;

 #define CLR(x) memset(x, 0, sizeof(x))

 #define PB push_back

 #define SZ(v) ((int)(v).size())

 #define rep(i, n) for(int i = 0; i < (n); i ++)

 #define repf(i, a, b) for(int i = (a); i <= (b); i ++)

 #define repd(i, a, b) for(int i = (a); i >= (b); i --)

 #define flin freopen( "a.in" , "r" , stdin )

 #define flout freopen( "a.out" , "w" , stdout )

 #define out(x) cout<<#x<<':'<<(x)<<endl

 #define tst(a) cout<<#a<<endl

 #define CINBEQUICKER std::ios::sync_with_stdio(false)

 typedef vector<int> VI;

 typedef vector<string> VS;

 typedef vector<double> VD;

 typedef long long int64;

 const double eps = 1e-;

 const double PI = atan(1.0)*;

 const int maxint = ;

 inline int MyMod( int a , int b ) { return (a%b+b)%b;}

 int d, m, n;

 int64 dp[][][][];

 void DP(VI landmarks)

 {

     rep (i, d+){

         rep (k, n+)

             rep (l, )

             dp[i][][k][l] = ;

     }

     dp[][][][] = ;

     repf (i, , d){

         if (i == d){

             dp[i][][n][] = dp[i-][][n][];

             break;

         }

         repf (j, , m){

             repf (k, , n){

                 if (j < m){

                     rep (l, ){

                         dp[i][j][k][l] = dp[i-][j][k][l] + dp[i-][j-][k][l] + dp[i-][j+][k][l];

                         if (k && j == landmarks[k-])

                             dp[i][j][k][l] = dp[i-][j][k-][l] + dp[i-][j-][k-][l] + dp[i-][j+][k-][l];

                     }

                 }

                 else{

                     dp[i][j][k][] = ;

                     dp[i][j][k][] = dp[i-][j][k][] + dp[i-][j-][k][] + dp[i-][j][k][] + dp[i-][j-][k][];

                     if (k && j == landmarks[k-])

                         dp[i][j][k][] = dp[i-][j][k-][] + dp[i-][j-][k-][] + dp[i-][j][k-][] + dp[i-][j-][k-][];

                 }

             }

         }

     }

     tst(aaa);

     rep (i, d+){

         out (i);

         rep (j, m+){

             rep (k, n+)

                 cout << dp[i][j][k][] << " " << dp[i][j][k][] << "  ";

             cout << endl;

         }

         cout << endl << endl;

     }

 }

 class HillHike

 {

     public:

         long long numPaths(int distance, int maxHeight, vector <int> landmarks){

             d = distance; m = maxHeight; n = SZ(landmarks);

             DP(landmarks);

             return (dp[d][][n][]);

         }

     //by plum rain

 };

　　

SRM 146

DIV 1 300pt, DIV 2 500pt

tag:计数问题，math

 #include <cstdlib>

 #include <cctype>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 #include <algorithm>

 #include <vector>

 #include <iostream>

 #include <sstream>

 #include <set>

 #include <queue>

 #include <fstream>

 #include <numeric>

 #include <iomanip>

 #include <bitset>

 #include <list>

 #include <stdexcept>

 #include <functional>

 #include <string>

 #include <utility>

 #include <map>

 #include <ctime>

 #include <stack>

 using namespace std;

 #define CLR(x) memset(x, 0, sizeof(x))

 #define PB push_back

 #define SZ(v) ((int)(v).size())

 #define rep(i, n) for(int i = 0; i < (n); i ++)

 #define repf(i, a, b) for(int i = (a); i <= (b); i ++)

 #define repd(i, a, b) for(int i = (a); i >= (b); i --)

 #define flin freopen( "a.in" , "r" , stdin )

 #define flout freopen( "a.out" , "w" , stdout )

 #define out(x) cout<<#x<<":"<<(x)<<endl

 #define tst(a) cout<<#a<<endl

 #define CINBEQUICKER std::ios::sync_with_stdio(false)

 typedef vector<int> VI;

 typedef vector<string> VS;

 typedef vector<double> VD;

 typedef long long int64;

 const double eps = 1e-;

 const double PI = atan(1.0)*;

 const int maxint = ;

 inline int MyMod( int a , int b ) { return (a%b+b)%b;}

 int64 ask_sqa(int64 n, int64 m)

 {

     int64 ret = ;

     int a = ;

     while (a <= m){

         ret += (n-a+) * (m-a+);

         a ++;

     }

     return ret;

 }

 class RectangularGrid

 {

     public:

         long long countRectangles(int width, int height){

             int64 n = width, m = height;

             if (n < m)

                 swap (n, m);

             int64 tot = ((n * (n + )) / ) * m * (m + ) / ;

             int64 sqa = ask_sqa(n, m);

             return (tot - sqa);

         }

 };

DIV 1 600 pt

tag:dfs

 #include <cstdlib>

 #include <cctype>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 #include <algorithm>

 #include <vector>

 #include <iostream>

 #include <sstream>

 #include <set>

 #include <queue>

 #include <fstream>

 #include <numeric>

 #include <iomanip>

 #include <bitset>

 #include <list>

 #include <stdexcept>

 #include <functional>

 #include <string>

 #include <utility>

 #include <map>

 #include <ctime>

 #include <stack>

 using namespace std;

 #define CLR(x) memset(x, true, sizeof(x))

 #define PB push_back

 #define SZ(v) ((int)(v).size())

 #define rep(i, n) for(int i = 0; i < (n); i ++)

 #define repf(i, a, b) for(int i = (a); i <= (b); i ++)

 #define repd(i, a, b) for(int i = (a); i >= (b); i --)

 #define flin freopen( "a.in" , "r" , stdin )

 #define flout freopen( "a.out" , "w" , stdout )

 #define out(x) cout<<#x<<":"<<(x)<<endl

 #define tst(a) cout<<#a<<endl

 #define CINBEQUICKER std::ios::sync_with_stdio(false)

 typedef vector<int> VI;

 typedef vector<string> VS;

 typedef vector<double> VD;

 typedef long long int64;

 const double eps = 1e-;

 const double PI = atan(1.0)*;

 const int maxint = ;

 const int maxx = ;

 const int le = ;

 const int ri = ;

 inline int MyMod( int a , int b ) { return (a%b+b)%b;}

 struct po{

     bool hash[ri+];

 };

 int n;

 bool ans[ri+];

 VS gg, rr;

 bool can_apr(int num)

 {

     rep (i, ){

         if (!((num%) < ) || !(num%))

             return false;

         num /= ;

     }

     return true;

 }

 bool match (int num, int pos)

 {

     if (!can_apr(num))

         return false;

     int b = , w = ;

     string g = gg[pos], r = rr[pos];

     int a[];

     a[] = num % ; num = (num - a[]) / ;

     a[] = num % ; num = (num - a[]) / ;

     a[] = num % ; num = (num - a[]) / ;

     a[] = num % ;

     rep (i, ){

         if (a[i]+'' == g[i]){

             b ++;

             a[i] = -;

             g[i] = ;

         }

     }

     rep (i, ){

         rep (j, )

             if (a[j]+'' == g[i]){

                 w ++;

                 a[j] = -;

                 g[i] = ;

                 break;

             }

     }

     if (b+'' != r[] || w+'' != r[])

         return false;

     return true;

 }

 void DFS(int pos, bool x, po p)

 {

     if (pos == n){

         if (x)

             repf (i, le, ri)

                 ans[i] = (ans[i] || p.hash[i]);

         return;

     }

     po tmp = p;

     repf (i, le, ri){

         if (i ==  && pos ==  && x){

             out (tmp.hash[]);

             out (match (i, pos));

         }

         if (tmp.hash[i] && !match (i, pos))

             tmp.hash[i] = false;

     }

     if (!pos)

         out (tmp.hash[]);

     if (pos ==  && !x)

         out (tmp.hash[]);

     if (pos ==  && x)

         out (tmp.hash[]);

     DFS(pos+, x, tmp);

     if (!x){

         tmp = p;

         bool xxx[ri+];

         CLR (xxx);

         repf (i, le, ri){

             if (xxx[i] && !match (i, pos))

                 xxx[i] = false;

         }

         repf (i, le, ri)

             tmp.hash[i] = (tmp.hash[i] && !xxx[i]);

         DFS (pos+, , tmp);

     }

 }

 class Masterbrain

 {

     public:

         int possibleSecrets(vector <string> guesses, vector <string> results){

             n = SZ (guesses);

             gg.clear(); rr.clear();

             gg = guesses; rr = results;

             po p;

             CLR (p.hash);

             memset (ans, , sizeof(ans));

             DFS (, , p);

             int ret = ;

             repf (i, le, ri){

                 if (can_apr(i) && ans[i]){

                     ret ++;

                     cout << i << endl;

                 }

             }

             return (ret);

         }

 };

DIV 2 1000pt

tag:记忆划搜索

 #include <cstdlib>

 #include <cctype>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 #include <algorithm>

 #include <vector>

 #include <iostream>

 #include <sstream>

 #include <set>

 #include <queue>

 #include <fstream>

 #include <numeric>

 #include <iomanip>

 #include <bitset>

 #include <list>

 #include <stdexcept>

 #include <functional>

 #include <string>

 #include <utility>

 #include <map>

 #include <ctime>

 #include <stack>

 using namespace std;

 #define CLR(x) memset(x, 0, sizeof(x))

 #define PB push_back

 #define SZ(v) ((int)(v).size())

 #define rep(i, n) for(int i = 0; i < (n); i ++)

 #define repf(i, a, b) for(int i = (a); i <= (b); i ++)

 #define repd(i, a, b) for(int i = (a); i >= (b); i --)

 #define flin freopen( "a.in" , "r" , stdin )

 #define flout freopen( "a.out" , "w" , stdout )

 #define out(x) cout<<#x<<":"<<(x)<<endl

 #define tst(a) cout<<#a<<endl

 #define CINBEQUICKER std::ios::sync_with_stdio(false)

 typedef vector<int> VI;

 typedef vector<string> VS;

 typedef vector<double> VD;

 typedef long long int64;

 const double eps = 1e-;

 const double PI = atan(1.0)*;

 const int maxint = ;

 const int N = ;

 inline int MyMod( int a , int b ) { return (a%b+b)%b;}

 int an[<<N];

 int n;

 VI t;

 int Search (int now, int left)

 {

     if (left == ){

         an[now] = ;

         return an[now];

     }

     if (an[now])

         return an[now];

     int tmp = maxint;

     rep (i, n){

         rep (j, n){

             if (i == j)

                 continue;

             if ((now>>i) &  && (now>>j) & ){

                 if (left == ){

                     tmp = max (t[i], t[j]);

                     break;

                 }

                 now -= ((<<i) + (<<j));

                 rep (k, n){

                     if (!((now>>k) & )){

                         now += (<<k);

                         tmp = min (tmp, Search(now, left-) + max (t[i], t[j]) + t[k]);

                         now -= (<<k);

                     }

                 }

                 now += ((<<i) + (<<j));

             }

         }

     }

     an[now] = tmp;

     return an[now];

 }

 class BridgeCrossing

 {

     public:

         int minTime(vector <int> times){

             n = SZ (times);

             if (n == )

                 return times[];

             if (n == )

                 return max (times[], times[]);

             t.clear();

             rep (i, n)

                 t.PB(times[i]);

             sort (t.begin(), t.end());

             int ma = ( << n) - ;

             CLR(an);

             Search (ma, n);

             return (Search(ma, n));

         }

 };

DIV 1 800pt

tag: 模拟

Ps:800pt 的 lv3....

 #include <cstdlib>

 #include <cctype>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 #include <algorithm>

 #include <vector>

 #include <iostream>

 #include <sstream>

 #include <set>

 #include <queue>

 #include <fstream>

 #include <numeric>

 #include <iomanip>

 #include <bitset>

 #include <list>

 #include <stdexcept>

 #include <functional>

 #include <string>

 #include <utility>

 #include <map>

 #include <ctime>

 #include <stack>

 using namespace std;

 #define CLR(x) memset(x, 0, sizeof(x))

 #define PB push_back

 #define SZ(v) ((int)(v).size())

 #define rep(i, n) for(int i = 0; i < (n); i ++)

 #define repf(i, a, b) for(int i = (a); i <= (b); i ++)

 #define repd(i, a, b) for(int i = (a); i >= (b); i --)

 #define flin freopen( "a.in" , "r" , stdin )

 #define flout freopen( "a.out" , "w" , stdout )

 #define out(x) cout<<#x<<":"<<(x)<<endl

 #define tst(a) cout<<#a<<endl

 #define CINBEQUICKER std::ios::sync_with_stdio(false)

 typedef vector<int> VI;

 typedef vector<string> VS;

 typedef vector<double> VD;

 typedef long long int64;

 const double eps = 1e-;

 const double PI = atan(1.0)*;

 const int maxint = ;

 inline int MyMod( int a , int b ) { return (a%b+b)%b;}

 char a[];

 string s[];

 bool stp[];

 int tim = maxint;

 bool match(int i, char x)

 {

     if (i ==  && x == 'N')

         return true;

     if (i ==  && x == 'E')

         return true;

     if (i ==  && x == 'S')

         return true;

     if (i ==  && x == 'W')

         return true;

     return false;

 }

 bool ok()

 {

     for (int i = ; i < ; i ++){

         if (a[i])

             return false;

         if (!(SZ(s[i]) ==  && s[i][] == '-'))

             return false;

     }

     return true;

 }

 void lesss(int x)

 {

     int len = SZ (s[x]);

     for (int i = ; i < len; i ++){

         if (s[x][i] == '-'){

             s[x].erase(i, );

             break;

         }

     }

     if (!SZ(s[x]))

         s[x].PB ('-');

 }

 void car_in()

 {

     for (int i = ; i < ; i ++){

         if (stp[i]) lesss(i);

         else{

             if (s[i][] == '-') lesss(i);

             else{

                 a[i] = s[i][];

                 s[i].erase(s[i].begin());

                 if (!SZ (s[i]))

                     s[i].PB('-');

             }

         }

     }

 }

 void car_go()

 {

     for (int i = ; i < ; i ++)

         if (match(i, a[i])) a[i] = ;

     char x = a[];

     for (int i = ; i < ; i ++)

         a[i] = a[i+];

     a[] = x;

 }

 bool stop(int x)

 {

     if (s[][] !='-' && s[][] != '-' && s[][] != '-' && s[][] != '-'){

         if (x)  return true;

         if (!a[]) return false;

         return true;

     }

     if (s[(x+)%][] == '-' && !a[(x+)%])

         return false;

     return true;

 }

 string clr(string x)

 {

     int len = SZ(x);

     int flag = -;

     for (int i = ; i < len; i ++){

         if (x[i] == '-') continue;

         flag = i;

     }

     x.erase (flag+, len-flag-);

     if (!SZ(x)) x.PB('-');

     return x;

 }

 class Roundabout

 {

     public:

         int clearUpTime(string north, string east, string south, string west){

             tim = maxint;

             CLR(a);

             CLR(stp);

             s[].clear(); s[].clear(); s[].clear(); s[].clear();

             s[] = clr(north);

             s[] = clr(east);

             s[] = clr(south);

             s[] = clr(west);

             for (int i = ; i < ; i ++ )

                 if (stop (i)) stp[i] = ;

             tim = ;

             if (ok())

                 return tim;

             while (){

                 tim ++;

                 car_go();

                 car_in();

                 for (int i = ; i < ; i ++){

                     if (stop(i)) stp[i] = ;

                     else stp[i] = ;

                 }

                 if (ok())

                     break;

             }

             return (tim);

         }

 };

SRM 147

DIV 2 1000pt

tag:没做，看不懂题，让Jne帮忙看也没看懂

DIV 1 500pt

tag:模拟

Ps:代码写的太复杂了- -，up面和down面数目相同，front面和back面相同，left面和right面相同，则样代码就可以简化很多了- -。这就是没有仔细手算样例的后果- -

 #include <cstdlib>

 #include <cctype>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 #include <algorithm>

 #include <vector>

 #include <iostream>

 #include <sstream>

 #include <set>

 #include <queue>

 #include <fstream>

 #include <numeric>

 #include <iomanip>

 #include <bitset>

 #include <list>

 #include <stdexcept>

 #include <functional>

 #include <string>

 #include <utility>

 #include <map>

 #include <ctime>

 #include <stack>

 using namespace std;

 #define CLR(x) memset(x, 0, sizeof(x))

 #define PB push_back

 #define SZ(v) ((int)(v).size())

 #define out(x) cout<<#x<<":"<<(x)<<endl

 #define tst(a) cout<<#a<<endl

 #define CINBEQUICKER std::ios::sync_with_stdio(false)

 typedef vector<int> VI;

 typedef vector<string> VS;

 typedef vector<double> VD;

 typedef long long int64;

 const double eps = 1e-;

 const double PI = atan(1.0)*;

 const int maxint = ;

 inline int MyMod( int a , int b ) { return (a%b+b)%b;}

 struct fra{

     int64 a, b;

     // a / b

     void clr(){

         a = ; b = ;

     }

 };

 vector<fra> ans;

 int r;

 string ask(int64 x)

 {

     if (!x)

         return "";

     string s;

     s.clear();

     while (x > ){

         s.PB((x%) + '');

         x /= ;

     }

     int size = SZ(s);

     string ret;

     ret.clear();

     for (int i = size-; i >= ; i --)

         ret.PB(s[i]);

     return ret;

 }

 string tostring()

 {

     string ret;

     ret.clear();

     ret += ask (ans[].a);

     if (ans[].b == )

         return ret;

     ret += '/';

     ret += ask (ans[].b);

     return ret;

 }

 int64 gcd(int64 a, int64 b){

     if (!b) return a;

     return gcd (b, a%b);

 }

 fra Add(fra x, fra y){

     y.b *= ;

     if (x.b > y.b){

         fra t = x;

         x = y;

         y = t;

     }

     while (x.b < y.b){

         int64 g = gcd (x.b, y.b);

         int64 mx = y.b / g, my = x.b / g;

         x.a *= mx; x.b *= mx;

         y.a *= my; y.b *= my;

     }

     fra ret;

     ret.a = x.a + y.a;

     ret.b = x.b;

     while (!(ret.a % )){

         ret.a /= ;

         ret.b /= ;

         if (ret.b == )

             break;

     }

     return ret;

 }

 VI match(int x){

     VI ret;

     ret.clear();

     if (x ==  || x == ){

         for (int i = ; i < ; i ++)

            ret.PB(i);

     }

     if (x ==  || x == ){

         ret.PB(); ret.PB();

         ret.PB(); ret.PB();

     }

     if (x ==  || x == ){

         for (int i = ; i < ; i ++)

             ret.PB(i);

     }

     return ret;

 }

 void change()

 {

     vector<fra> tmp;

     tmp.clear();

     for (int i = ; i < ; i ++){

         VI x = match(i);

         fra cnt;

         cnt.clr();

         for (int j = ; j < ; j ++)

             cnt = Add (cnt, ans[x[j]]);

         tmp.PB(cnt);

     }

     ans.clear();

     ans = tmp;

 }

 class Dragons

 {

     public:

         string snaug(vector <int> initialFood, int rounds){

             VI xx = initialFood;

             if (xx[] == xx[] && xx[] == xx[] && xx[] == xx[] && xx[] == xx[] && xx[] == xx[])

                 return ask(xx[]);

             r = rounds;

             int64 size = SZ(xx);

             fra x;

             x.clr();

             ans.clear();

             for (int64 i = ; i < size; i ++){

                 x.a = xx[i];

                 ans.PB(x);

             }

             int T = ;

             while (T < r){

                 T ++;

                 change ();

             }

             string s = tostring();

             return (s);

         }

     //by plum rain

 };

DIV 1 1000pt

tag:dp, good

题意：给定两个数字n(n <= 10)，num(num <= 10^17)，和vector<int> a[n]，要求用n种颜色画出num面旗。

　　　每面旗有x条竖条纹组成，条纹数不同的旗子一定不相同，条纹数相同但是对应条纹颜色不同的旗子也为不同的旗。

　　　给条纹上色有一个条件，将n种颜色标为1~n，则如果a[i]中有数字k，则颜色i不能颜色k相邻(此时保证a[k]中一定有i)。

　　　将所染旗帜中条纹数最多的旗帜的条纹数记为ans，求ans的最小值。

　　　例如，n = 3,num = 10, a = {{0}, {1, 2}, {1, 2}}，则染一条条纹的旗帜共有3种，染两条条纹的旗帜共有4种，染三条条纹的6种，3 + 4 + 6 = 13 >= 10，所以答案为3。

解法：首先肯定要用dp，而且dp部分很简单。难点在于，num可以达到10^17，意味着首先dp要注意空间复杂度优化，其次如果不特殊处理，肯定会超时。

　　　考虑到，如果有任意一种颜色可以和两种颜色相邻，那么旗帜的条纹每增加一条所增加的染色种数是呈指数级增长的，ans也就很小，不会超时。

　　　也就是说，只需要特判对每种颜色，能和它相邻的颜色都不超过1种的情况。

 #include <cstdlib>

 #include <cctype>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 #include <algorithm>

 #include <vector>

 #include <iostream>

 #include <sstream>

 #include <set>

 #include <queue>

 #include <fstream>

 #include <numeric>

 #include <iomanip>

 #include <bitset>

 #include <list>

 #include <stdexcept>

 #include <functional>

 #include <string>

 #include <utility>

 #include <map>

 #include <ctime>

 #include <stack>

 using namespace std;

 #define CLR(x) memset(x, 0, sizeof(x))

 #define PB push_back

 #define SZ(v) ((int)(v).size())

 #define out(x) cout<<#x<<":"<<(x)<<endl

 #define tst(a) cout<<#a<<endl

 #define CINBEQUICKER std::ios::sync_with_stdio(false)

 typedef vector<int> VI;

 typedef vector<string> VS;

 typedef vector<double> VD;

 typedef long long int64;

 const double eps = 1e-;

 const double PI = atan(1.0)*;

 const int maxint = ;

 inline int MyMod( int a , int b ) { return (a%b+b)%b;}

 bool fbd[][];

 int n;

 int64 dp[][];

 int64 tot;

 void init(string s)

 {

     tot = ;

     int pos = ;

     int size = SZ (s);

     while (pos < size){

         tot = tot *  + s[pos++] - '';

     }

 }

 int64 DP()

 {

     int64 ret;

     int64 sum;

     if (tot <= n)

         return ;

     int spe = true;

     int64 add = ;

     for (int i = ; i < n; i ++){

         bool cnt = false;

         for (int j = ; j < n; j ++){

             if (fbd[i][j]) continue;

             if (!cnt){

                 cnt = true;

                 add ++;

                 continue;

             }

             spe = false;

             break;

         }

     }

     if (spe){

        ret = ;

         sum = n;

        int64 tim = (tot - sum) / add;

        if (n + tim * add >= tot)

            return (tim + );

        else return (tim + );

     }

     int  pos = ;

     for (int i = ; i < n; i ++)

         dp[][i] = ;

     ret = ;

     sum = n;

     while (sum < tot){

         for (int i = ; i < n; i ++){

             dp[(pos+)%][i] = ;

             for (int j = ; j < n; j ++){

                 if (fbd[i][j]) continue;

                 dp[(pos+)%][i] += dp[pos][j];

             }

             sum += dp[(pos+)%][i];

         }

         pos = (pos+) % ;

         ret ++;

     }

     return ret;

 }

 class Flags

 {

     public:

         long long numStripes(string numFlags, vector <string> forbidden){

             CLR(fbd);

             init(numFlags);

             n = SZ (forbidden);

             for (int i = ; i < n; i ++){

                 string s = forbidden[i];

                 int size = SZ (s);

                 for (int j = ; j < size; j ++){

                     if (s[j] == ' ') continue;

                     fbd[i][s[j]-''] = true;

                 }

             }

             int64 ans = DP();

             return (ans);

         }

         //by plum rain

 };

SRM 148

DIV 1 1100pt

tag:recursion, good

题意：猜数字游戏，给定一个数字x，几个人分别猜测不同的数字，谁猜测数字与x之差最小谁赢，若有两人或多人与x之差相同且最小，则平手，平手不算赢！现在，题目给定数字n，m，数组{an}。

　　　n表示猜数字范围为1~n，在你猜数字前已经有size(an)个人猜过数字，他们猜测的值记录在{an}中，在你猜之后，还将有m个人猜测。

　　　不论你猜测哪个数字，在你之后猜测的人都采取最优策略（即使他自己赢的概率最大，如果猜两个数概率一样，猜小的），求猜多少能使你赢的概率最大。若有多个答案，输出最小的一个。

　　　比如，n = 1000, {an} = {50}, m = 1。则答案为51, 因为当你猜51, 剩下的一个人为了使自己猜赢的概率最大，应该猜49或52，由于要猜小的，所以猜49，则你赢的概率为50，最优情况。

　　　n <= 10^6，0 <= size(an) <= 10, 0 <= m <= 6, n ^ m <= 10^6。

解法：考虑递归。题目中的约束条件n ^ m <= 10^6可以起到提示的作用，但是如果直接暴力，时间复杂度为O（n^(m+1))，可能超时。考虑优化最后一个人猜测的情况。

　　　在最后一个人猜测时情况为-----X--X--X-----X-----（---表示可猜测的点，X表示已猜测的点）

　　　则，最后一个人可能猜测的点只有几个----OXO-XO-XO----XO----(最后一个人可能猜测的点为O)，比较他们即可。

　　　这样就用递归 + 枚举解决了问题。胆识程序很难写。因为对第m个人，他猜测的数字要影响第m+1个人，而m+1猜测的情况又会影响m。

　　　我是参考了SnapDragon的代码。

 #line 7 "NumberGuessing.cpp"

 #include <cstdlib>

 #include <cctype>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 #include <algorithm>

 #include <vector>

 #include <iostream>

 #include <sstream>

 #include <set>

 #include <queue>

 #include <fstream>

 #include <numeric>

 #include <iomanip>

 #include <bitset>

 #include <list>

 #include <stdexcept>

 #include <functional>

 #include <string>

 #include <utility>

 #include <map>

 #include <ctime>

 #include <stack>

 using namespace std;

 #define CLR(x) memset(x, 0, sizeof(x))

 #define PB push_back

 #define SZ(v) ((int)(v).size())

 #define out(x) cout<<#x<<":"<<(x)<<endl

 #define tst(a) cout<<#a<<endl

 #define CINBEQUICKER std::ios::sync_with_stdio(false)

 typedef vector<int> VI;

 typedef vector<string> VS;

 typedef vector<double> VD;

 typedef long long int64;

 const double eps = 1e-;

 const double PI = atan(1.0)*;

 const int maxint = ;

 const int N = ;

 inline int MyMod( int a , int b ) { return (a%b+b)%b;}

 int n;

 int num[], pnum;

 int tot;

 void xequal(int an[], bool x)

 {

     if (x){

         for (int i = ; i < tot; ++ i)

             an[i] = num[i];

         return ;

     }

     for (int i = ; i < tot; ++ i)

         num[i] = an[i];

 }

 int cal (int x, bool xxx)

 {

     int t[], tnum = tot;

     xequal (t, );

     if (xxx) tnum --;

     sort (t, t+tnum);

     if (tnum == -) return n;

     if (x < t[])

         return x + ((t[] - x - ) >> );

     if (x == t[])

         return x + ((t[] - x - ) >> );

     int flag = ;                                                   //添加flag是为了不用特判x 与 t[i]会重合的情况

     for (int i = ; i < tnum; ++ i){

         if (x == t[i]) flag = ;

         if (x < t[i])

             return  + ((t[i] - x - ) >> ) + ((x - t[i--flag] - ) >> );

     }

     return n - x +  + ((x - t[tnum--flag]) >> );

 }

 int findpos()

 {

    int t[], tnum = tot - ;

    xequal (t, );

    sort (t, t+tnum);

    int ret, pret = ;

    if (tnum == ) return ;

    if (t[] > )

        ret = t[] - , pret = cal (t[]-, );

    for (int i = ; i < tnum; ++ i){

        if (t[i] >= n) continue;

        if (i < tnum- && t[i] +  == t[i+])

            continue;

        int tmp = cal (t[i]+, );

        if (tmp > pret)

            ret = t[i] + , pret = tmp;

    }

    return ret;

 }

 int DFS(int pos, int c)

 {

     pnum = pos + tot - c - ;

     if (pos == c){

         int tmp = findpos();

         num[pnum] = tmp;

         return tmp;

     }

     int ntmp[], ret, pret = ;

     xequal(ntmp, );

     for (int i = ; i <= n; ++ i){

         bool xxx = true;

         for (int j = ; j < pnum; ++ j)

             if (num[j] == i){

                 xxx = false;

                 break;

             }

         if (!xxx) continue;

         pnum = pos + tot - c - ;

         num[pnum] = i;

         DFS(pos+, c);

         pnum = pos + tot - c - ;

         int ptmp = cal (i, );

         if (ptmp > pret)

             pret = ptmp, ret = i, xequal (ntmp, );

     }

     xequal (ntmp, );

     return ret;

 }

 class NumberGuessing

 {

     public:

         int bestGuess(int A, vector <int> B, int c){

             int size =  SZ (B);

             n = A, tot = size + c + ;

             CLR (num), pnum = -;

             for (int i = ; i < size; ++ i)

                 num[++pnum] = B[i];

             return DFS(, c);

         }

         //by plum rain

 };

小结：受了别人的推荐，尝试做了一点topcoder的题，现在看了，这些题确实是很有价值的。

　　　并且，这几天对自己做题时存在的两个问题感觉特别明显。

　　　一是代码功底太差了。div2 lv3, div1 lv2，div1 lv3这三道题的代码都不小，每次我写完以后都要调试很久才能和自己的想的算法吻合。而且，上面有不少题的代码都是重写过的，因为之前写的错误太多，修改太麻烦，而且容易引出新的错误。

　　　二是自己写前总是没有或者很难对自己要写的代码有一个比较准确的估计。比如有时把问题想简单了，有时又忽略了个别限制条件，写到一半或者写完了调试的时候才发现，然后又去改。这个时候更改，不仅浪费时间，而且很容易造成新的错误。

　　　刷题！

相关文章