TopCoder SAM 631 DIV2_html/css_WEB-ITnose

200: Water question

class TaroGrid {public:	int getNumber(vector <string>);};int TaroGrid::getNumber(vector <string> grid){    int ans=0;    int black=0,white=0;    int N=grid.size();    for(int i=0;i<N;i++)    {        black=0;white=0;        if(grid[0][i]=='B') black++;        else white++;        for(int j=1;j<N;j++)        {            if(grid[j][i]=='W')            {                if(black)                {                    ans=max(ans,black);                    black=0;                    white=1;                }                else if(white)                {                    white++;                }            }            else if(grid[j][i]=='B')            {                if(black)                {                    black++;                }                else if(white)                {                    ans=max(ans,white);                    white=0;                    black=1;                }            }        }        ans=max(ans,max(white,black));    }    return ans;}

500: Try to lean to the left and judge whether each ball of cats can be laid flat

class CatsOnTheLineDiv2 {public:	string getAnswer(vector <int>, vector <int>, int);};struct CAT{    int p,c;}cat[55];bool cmp(CAT x,CAT y){    if(x.p!=y.p)        return x.p<y.p;    else        return x.c<y.c;}string CatsOnTheLineDiv2::getAnswer(vector <int> pos, vector <int> count, int time){    int n=pos.size();    for(int i=0;i<n;i++)    {        cat[i].p=pos[i];        cat[i].c=count[i];    }    sort(cat,cat+n,cmp);    bool flag=true;    int left=-(1<<30),right=-(1<<30);    for(int i=0;i<n;i++)    {        left=max(right+1,cat[i].p-time);        right=left+cat[i].c-1;        if(right-cat[i].p>time)            flag=false;    }    if(flag) return "Possible";    else return "Impossible";}

950: Memoized Search

map<LL,LL> ret;class TaroCoins {public:    LL dfs(LL n)    {        if(ret.count(n)) return ret[n];        LL ans=0;        if(n%2LL) ans=dfs(n/2LL);        else ans=dfs(n/2LL)+dfs(n/2LL-1LL);        ret[n]=ans;        return ans;    }	long long getNumber(long long N)	{	    ret[0]=1;        return dfs(N);	}};