題意：

給你一個矩形的畫布，此畫布由‘B’和‘.’組成，畫T次每次畫的時候他的左上角的起始點是確定的幾位(1,1),(2,2),(3,3)......(T,T); 在畫的過程中可能會出現相互覆蓋求畫完T次后一共有多少個‘B’

例

{ "..B", "B..", "BB." } 3

Returns: 10

思路：

假設矩形的長度為n次，開始我一直在思考覆蓋完n次后減去多少，在第n次以后每一個減去的都一樣了。不過這樣會出現重復的減去，不對。我們只需要考慮在覆蓋n個后第一個的總共剩下多少個沒有被覆蓋的。以后都是一樣的了。最后我們只需要計算一下最后n-1個的數就可以了。最后計算的復雜度為O(50^3).

class PastingPaintingDivTwo {public:long long countColors(vector <string> clipboard, int T){char tp[55][55];int i,j,ki,kj,k;int sz = clipboard.size();if (sz == 1){LL ans = 0;for (i = 0; i < clipboard[0].size(); ++i)if (clipboard[0][i] == 'B') ans += 1;// printf("11111111111111\n");ans = ans*T;return ans;}else{LL ans = 0;for (i = 0; i < sz; ++i){for (j = 0; j < clipboard[i].size(); ++j){tp[i][j] = clipboard[i][j];}}LL ct;for (k = 1; k < sz; ++k){for (i = k, j = 0; i < sz; ++i,++j){for (ki = k,kj = 0; ki < clipboard[i].size(); ++ki,++kj){if (clipboard[i][ki] == 'B' && clipboard[j][kj] == 'B'){tp[i][ki] = '.';}}}}ct = 0;for (i = 0; i < sz; ++i){for (j = 0; j < clipboard[i].size(); ++j){if (tp[i][j] == 'B') ct++;}}if (T - (sz - 1) > 0)ans = (LL)(T - (sz - 1))*ct;// cout<<ans<<endl;int p; CL(tp,0);int mk = min(sz - 1,T);for (p = 1; p <= mk; ++p){for (i = 0; i < sz; ++i){for (j = 0; j < clipboard[i].size(); ++j){tp[i][j] = clipboard[i][j];//tt[i][j] = clipboard[i][j];}}for (k = 1; k < sz - p; ++k){for (i = k, j = 0; i < sz; ++i,++j){for (ki = k,kj = 0; ki < clipboard[i].size(); ++ki,++kj){if (clipboard[i][ki] == 'B' && clipboard[j][kj] == 'B'){tp[i][ki] = '.';}}}}ct = 0;for (i = 0; i < sz; ++i){for (j = 0; j < clipboard[i].size(); ++j){if (tp[i][j] == 'B') ct++;}}ans += ct;}//printf("222222222222\n");return ans;}} };

　　

轉載于:https://www.cnblogs.com/E-star/archive/2012/12/02/2797954.html

總結

以上是生活随笔為你收集整理的TC SRM 562 div2 B 题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。