SRM 513 div2

兩個号終于都藍了……接下來坐等回綠= =|||

250pt：

水題，不解釋，三重循環判斷即可

vector <string> ans;
string ret;

class TrainingCamp
{
        public:
        vector<string> determineSolvers(vector<string> attendance, vector<string> problemTopics)
        {
            int i,j,n,m,d,k;
            n=attendance.size();
            m=problemTopics.size();
            d=attendance[0].size();
            for (i=0;i<n;i++)
            {
                ret="";
                for (j=0;j<m;j++)
                {
                    for (k=0;k<d;k++)
                    {
                        if (attendance[i][k]=='-' && problemTopics[j][k]=='X') break;
                    }
                    if (k<d) ret+='-';
                    else ret+='X';
                }
                ans.push_back(ret);
            }
            return ans;
        }
};
           

500pt

沒有分析複雜度，考慮隻有50個小球，是以分别求出闆在相鄰兩個小球之間有多少種取法，最後将答案一乘即可，這個不太好數，是以寫完分數不高，後來看到坐标範圍不大，應該可以直接枚舉每個位置，這樣就好寫多了

bool cmp(int x,int y)
{
    return x<y;
}

#define MOD 1000000009

class YetAnotherIncredibleMachine
{
        public:
        long long countWays(vector<int> platformMount,vector<int> platformLength,vector<int> balls)
        {
            long long i,ans,j,n,l,ret,m;
            n=platformLength.size();
            m=balls.size();
            ans=1;
            sort(balls.begin(),balls.end(),cmp);
            for (i=0;i<n;i++)
            {
                ret=0;
                l=platformMount[i]-platformLength[i];
                for (j=0;j<m;j++)
                {
                    if (balls[j]<l) ;
                    else if (balls[j]==l) l++;
                    else
                    {
                        int r=min(balls[j]-1,platformLength[i]+platformMount[i]);
                        if (r-l-platformLength[i]+1>0) ret=(ret+r-l-platformLength[i]+1)%MOD;
                     //   printf("%d..%d..%d..%d~\n",l,r,ret,r-l-platformLength[i]+1);
                        l=balls[j]+1;
                    }
                }
                if (platformMount[i]-l+1>0) ret=(ret+platformMount[i]-l+1)%MOD;
             //   printf("%d..\n",ret);
                ans=(ret*ans)%MOD;
            }
            return ans;
        }
};
           

1000pt

第二題寫挫了，沒時間開第三題了，不然第三題還是很簡單的，4*4的範圍，瞎搞都沒事……直接記憶化搜尋吧。

int Change(int x1,int y1,int x2,int y2,vector<string> board)
{
    int ans=0,i;
    if (x2-x1==1)
    {
        for (i=y1;i<y2;i++)
        {
            ans=ans*10+board[x1][i]-'0';
        }
        return ans;
    }
    if (y2-y1==1)
    {
        for (i=x1;i<x2;i++)
        {
            ans=ans*10+board[i][y1]-'0';
        }
        return ans;
    }
}

int dp[5][5][5][5];

int DFS(int x1,int y1,int x2,int y2,vector<string> board)
{
    int i;
    if (dp[x1][y1][x2][y2]!=-1) return dp[x1][y1][x2][y2];
    if (x2-x1==1)
    {
        dp[x1][y1][x2][y2]=Change(x1,y1,x2,y2,board);
    }
    else if (y2-y1==1)
    {
        dp[x1][y1][x2][y2]=Change(x1,y1,x2,y2,board);
    }
    else
    {
        for (i=x1+1;i<x2;i++)
        {
            dp[x1][y1][x2][y2]=max(dp[x1][y1][x2][y2],DFS(x1,y1,i,y2,board)+DFS(i,y1,x2,y2,board));
        }
        for (i=y1+1;i<y2;i++)
        {
            dp[x1][y1][x2][y2]=max(dp[x1][y1][x2][y2],DFS(x1,y1,x2,i,board)+DFS(x1,i,x2,y2,board));
        }
    }
    return dp[x1][y1][x2][y2];
}

class CutTheNumbers
{
        public:
        int maximumSum(vector<string> board)
        {
            int i,j,n,m;
            n=board.size();
            m=board[0].size();
            memset(dp,-1,sizeof(dp));
            return DFS(0,0,n,m,board);
        }
};