学步园

很长时间没有在tc上做比赛，还是老老实实从D2区开始吧！

我们这个房间很有意思，最后分数排名前三的家伙在最简单的250分上都卡了一小会——其中就包括我。也许是因为久疏战阵，缺乏对模拟题的手感吧。

第二题求乘积的层次，实际上就是求质因数的个数。我居然先打了一张四百万的质数表……

这题到最后只有两个人过。进入challenge环节之后，当排名前列的几位在代码间寻寻觅觅，苦心竭力欲求一Ch而不得的时候，一个灰颜色的、只靠250p拿了160分的选手在谈笑风生间连续干掉了四个人，让我们看得目瞪口呆……

第三题太长了！我敲到一半才发现，五分钟之后就要被迫关掉代码了。【其实是你土鳖啦】

确实是方法土鳖了。

当需要四个方向旋转求解时，只需要把原图旋转四个方向，然后按一个方向写判断函数即可。

#define REP(i,n) for(int i=0;i<(int)(n);++i)<br /> #define SIZE(t) ((int)((t).size()))<br /> #define LL long long<br /> #define MP make_pair</p> <p>class RotatingTriangles<br /> {<br /> char m[51][51];<br /> int N, M;</p> <p> void rot ()<br /> {<br /> char t[51][51];<br /> memset ( t, ' ', sizeof ( t ) );<br /> int i, j;<br /> for ( i = 0; i < N; i ++ )<br /> for ( j = 0; j < M; j ++ )<br /> t[j][N - i - 1] = m[i][j];<br /> swap ( N, M );<br /> memcpy ( m, t, sizeof ( m ) );<br /> }</p> <p> int getOne ( int i, int j )<br /> {<br /> int ret = 0;<br /> int len;<br /> for ( len = 1; ; len ++ )<br /> {<br /> int bi = i, bj = j - len + 1, ti = i - len + 1, tj = j;<br /> if ( bj < 0 || ti < 0 )<br /> return ret;<br /> if ( bi != N - 1 && m[bi + 1][bj] == '#' )<br /> return ret;<br /> if ( tj != M - 1 && m[ti][tj + 1] == '#' )<br /> return ret;<br /> int k, sum = 0;<br /> for ( k = 0; k < len; k ++ )<br /> {<br /> if ( m[bi][bj] == '.' )<br /> return ret;<br /> if ( m[bi][bj] == '/' )<br /> sum ++;<br /> bi --, bj ++;<br /> }<br /> if ( sum == len )<br /> ret ++;<br /> }<br /> return ret;<br /> }</p> <p> int getTwo ( int i, int j )<br /> {<br /> int ret = 0;<br /> int len;<br /> for ( len = 1; ; len ++ )<br /> {<br /> int li = i, lj = j - len + 1, ri = i, rj = j + len, bi = i - len + 1;<br /> if ( lj < 0 || rj >= M || bi < 0 )<br /> return ret;<br /> if ( i != N - 1 && ( m[i + 1][lj] == '#' || m[i + 1][rj] == '#' ) )<br /> return ret;<br /> int k, sum = 0;<br /> for ( k = 0; k < len; k ++ )<br /> {<br /> if ( m[li][lj] == '.' || m[ri][rj] == '.' )<br /> return ret;<br /> if ( m[li][lj] == '/' && m[ri][rj] == '/' )<br /> sum ++;<br /> li --, ri --, lj ++, rj --;<br /> }<br /> if ( sum == len )<br /> ret ++;<br /> }<br /> return ret;<br /> }<br /> public:<br /> int count(vector <string> grid)<br /> {<br /> int i, j;<br /> N = grid.size (), M = grid[0].size ();<br /> memset ( m, ' ', sizeof ( m ) );<br /> for ( i = 0; i < N; i ++ )<br /> for ( j = 0; j < M; j ++ )<br /> m[i][j] = grid[i][j];<br /> int k;<br /> int sum = 0;<br /> for ( k = 0; k < 4; k ++ )<br /> {<br /> rot ();<br /> for ( i = 0; i < N; i ++ )<br /> {<br /> for ( j = 0; j < M; j ++ )<br /> {<br /> sum += getOne ( i, j );<br /> sum += getTwo ( i, j );<br /> }<br /> }<br /> }<br /> return sum;<br /> }<br /> }

明天再做D1的题。

============从代码中挣扎着爬出来的分割线============

OK，250p和500p都顺利【？】过掉。虽然时间用的有点长，几乎是ACRush同学的十倍，不过我相信在有生之年应该可以把这个数字减到两到三倍。总之还是需要多加练习。

250p  UnfoldingTriangles

模拟题。贪心，不断展开fold、减去剩余的unfoldlimit就可以了。码的第一次还求了个最长能够得到的三角形边长，结果FST。其实在循环里判断一下就可以了。

500p  FourBlocks

DP位操作。

这个题目不错，比赛中过的人也比较多。我觉得我写的比ACRush清楚【喂，别臭美】，但他的代码比我少一些。而且用十分钟写完代码，对于我来说实在是不可能的任务。嗯，我起码用了两个钟头了吧……

和zoj1100相类似。我用一个钟头看懂了一年半前自己写的代码，果断跨领域移植，终于取得了重大突破。

首先将原图转90度摆放，从上到下分层。每一层最多10个数，即1<<10 = 1024种状态。在从第n层推导第n+1层的时候，可以预先作出状态转移。

一共有三种转移模式：当2*2方块中无1，上层和下层同时填充2个；上层填一个，下层填一个；上层填一个，下层不填。因为转移之后上层必须为满，所以后两种情况上层也必须填充。

 #define REP(i,n) for(int i=0;i<(int)(n);++i)<br /> #define SIZE(t) ((int)((t).size()))<br /> #define LL long long<br /> #define MP make_pair</p> <p>typedef pair < pair < int, int >, int > pii;</p> <p>int W, H;<br /> int dp[30][1 << 10];<br /> set < pii > s;<br /> vector < string > v;</p> <p>int length ( int n )<br /> {<br /> return n ? length ( n >> 1 ) + ( n & 1 ) : 0;<br /> }</p> <p>void dfs ( int h, int pos, int from, int to, int cost )<br /> {<br /> if ( pos > W )<br /> return;<br /> if ( pos == W )<br /> {<br /> pii key = MP ( MP ( from, to ), cost );<br /> s.insert ( key );<br /> return;<br /> }<br /> if ( pos != W - 1 && v[pos][h] != '1' && v[pos + 1][h] != '1'<br /> && v[pos][h - 1] != '1' && v[pos + 1][h - 1] != '1' )<br /> dfs ( h, pos + 2, ( from << 2 ), ( to << 2 ) + 3, cost + 16 );<br /> if ( v[pos][h] != '1' )<br /> dfs ( h, pos + 1, ( from << 1 ) + 1, ( to << 1 ), cost );<br /> dfs ( h, pos + 1, ( from << 1 ) + 1, ( to << 1 ) + 1, cost + 1 );<br /> }</p> <p>class FourBlocks<br /> {<br /> public:<br /> int maxScore(vector <string> grid)<br /> {<br /> v = grid;<br /> memset ( dp, 0, sizeof ( dp ) );<br /> W = grid.size (), H = grid[0].size ();</p> <p> int i, j;<br /> for ( i = 0; i < ( 1 << W ); i ++ )<br /> dp[0][i] = length ( i );</p> <p> for ( i = 1; i < H; i ++ )<br /> {<br /> s.clear ();<br /> dfs ( i, 0, 0, 0, 0 );<br /> //print ();<br /> set < pii > :: iterator it;<br /> for ( it = s.begin (); it != s.end (); it ++ )<br /> {<br /> int f = it->first.first, t = it->first.second, c = it->second;<br /> dp[i][t] = max ( dp[i - 1][f] + c, dp[i][t] );<br /> }<br /> }<br /> return dp[H - 1][( 1 << W ) - 1];<br /> }<br /> }