SRM 555 DIV 2

255pt:
제목:
01 행렬을 주고 한 줄과 한 열을 바꾸는 것이 그의 총합이 가장 크고 가장 큰 총합을 구하며 매거 행렬을 구하고 억제 또는 O(n^3)를 취하면 된다.

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

#include <stack>

#include <set>

#include <map>

#include <string>



#define CL(a,num) memset((a),(num),sizeof(a))

#define iabs(x)  ((x) > 0 ? (x) : -(x))

#define Min(a,b) (a) > (b)? (b):(a)

#define Max(a,b) (a) > (b)? (a):(b)



#define ll long long

#define inf 0x7f7f7f7f

#define MOD 100000007

#define lc l,m,rt<<1

#define rc m + 1,r,rt<<1|1

#define pi acos(-1.0)

#define test puts("<------------------->")

#define maxn 100007

#define M 100007

#define N 107

using namespace std;

//freopen("din.txt","r",stdin);





class XorBoardDivTwo{

    public:

    int theMax(vector <string> board){

        int a[55][55];

        int i,j;

        int sz = board.size();

        int len = board[0].size();

        int sum = 0;

        for (i = 0; i < sz; ++i){

            for (j = 0; j < len; ++j){

                a[i][j] = board[i][j] - '0';

                sum += a[i][j];

            }

        }

        int ans = -inf;

        int row,col;

        for (i = 0; i < sz; ++i){

            for (j = 0; j < len; ++j){

                int tmp = sum;

                for (col = 0; col < len; ++col){

                    a[i][col] ^= 1;

                    if (a[i][col] == 0) tmp--;

                    else tmp++;

                }

                for (row = 0; row < sz; ++row){

                    a[row][j] ^= 1;

                    if (a[row][j] == 0) tmp--;

                    else tmp++;

                }

                if (ans < tmp) ans = tmp;

                for (col = 0; col < len; ++col) a[i][col] ^= 1;

                for (row = 0; row < sz; ++row) a[row][j] ^= 1;

            }

        }

        return ans;

    }

};

　
500pt;시간은 자신이 아직 약하다는 것을 증명한다. 테스트를 마치고 방금 제출하려고 했는데 시간이 돼서 어이가 없다. 경기 후에 제출했다.속도가 여전히 따라가지 못한다.
제목:
01열을 정하여 몇 개의 자열로 나누면 자열의 첫 번째 수는 0이 될 수 없고 각 자열은 5의 멱을 요구하며 최소 분할의 속도를 구한다.
아이디어:
DP: dp[i]=min(dp[i], dp[j]+1)j는 모든 만족이 i보다 작고 j+1과 i 이 단락의 직렬이 5를 만족시키는 멱이다.
먼저 각 점과 그의 앞쪽 점이 5의 멱을 형성할 수 있는 점을 구하고 기록한 다음에 O(n)가 dp를 한 번 걷는다.

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

#include <stack>

#include <set>

#include <map>

#include <string>



#define CL(a,num) memset((a),(num),sizeof(a))

#define iabs(x)  ((x) > 0 ? (x) : -(x))

#define Min(a,b) (a) > (b)? (b):(a)

#define Max(a,b) (a) > (b)? (a):(b)



#define ll long long

#define inf 0x7f7f7f7f

#define MOD 100000007

#define lc l,m,rt<<1

#define rc m + 1,r,rt<<1|1

#define pi acos(-1.0)

#define test puts("<------------------->")

#define maxn 100007

#define M 100007

#define N 107

using namespace std;

//freopen("din.txt","r",stdin);





class CuttingBitString{

    public:

    int dp[55];

    ll Pow(int a,int b){

        ll sum = 1;

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

            sum *= a;

        }

        return sum;

    }

    //     5  

    bool is5pow(int j,int i,int *a){

        ll s = 0;

        for (int t = j,ct = 0; t >= i; --t,++ct){

            s += (ll)a[t]*Pow(2,ct);

        }

        while (s%5 == 0){

            s /= 5;

        }

        if (s != 1) return false;

        else return true;

    }

    int getmin(string S){

        struct node{

            int pre[55];//              5    

            int len;

        }b[55];

        CL(b,0);



        int i,j;

        int a[55];

        int sz = S.size();



        for (i = 0; i < sz; ++i) a[i + 1] = S[i] - '0';



        //    

        for (i = 1; i <= sz; ++i){

            if (a[i] == 0) continue;

            for (j = i; j <= sz; ++j){

                if (is5pow(j,i,a)){

                    b[j].pre[b[j].len++] = i - 1;

                }

            }

        }



        for (i = 1; i <= sz; ++i) {

            dp[i] = inf;

        }

        dp[0] = 0;

        for (i = 1; i <= sz; ++i){

           // printf("I,B[i]len %d %d
",i,b[i].len);

            for (j = 0; j < b[i].len; ++j){

                int tmp = b[i].pre[j];

                //printf(">>%d
",tmp);

                dp[i] = min(dp[i],dp[tmp] + 1);

            }

        }

        /*for (i = 1; i <= sz; ++i) printf("%d ",dp[i]);

        test;*/

        if (dp[sz] == inf) return -1;

        else return dp[sz];

    }

};