即日起本博客将减少直至停止发布奇怪的题解和奇怪的代码。
毕竟别人的博客都能找到的东西。
即日起本博客将减少直至停止发布奇怪的题解和奇怪的代码。
毕竟别人的博客都能找到的东西。
一个n x m的矩阵中有很多障碍物.
现求一个最大的且不包含障碍物的子矩阵.
把每个格子向上延伸到障碍或者边界的连续的空格看做一条线段, 则对于该格来说, 它对应的一个子矩阵子矩阵即为这条线段左右可移动到的边界.
又知任何一个矩阵均可以由它最下层的某个对应线段长度恰好为矩形高度的格子表示.
故对于每一个格子, 求出其对应矩阵即可(即其对应线段左右移动的最远地点)
可推得:
up[i][j] = up[i-1][j] + 1, 当格子为障碍物或者边界时, up为0
left[i][j] = max(left[i-1][j], lo+1) 其中lo为当前格子所在行左侧最靠近的障碍坐标.
同理有
right[i][j] = min(right[i-1][j], ro-1)
# include <cstdio> # include <algorithm> # define rep(x, n) for (int x = 0; x < n; ++x) using namespace std; const int maxn = 1003; int t; int n, m; int a[maxn][maxn]; int up[maxn][maxn], left[maxn][maxn], right[maxn][maxn]; int main() { scanf("%d", &t); while ( t-- ) { scanf("%d%d", &n, &m); rep(i, n) rep(j, m) { char ch = getchar(); while ( ch != 'R' && ch != 'F' ) ch = getchar(); a[i][j] = ch == 'R' ? 1 : 0; } int ans = 0; rep(i, n) { int lo = -1, ro = m; rep(j, m) if ( a[i][j] ) { up[i][j] = left[i][j] = 0; lo = j; } else { up[i][j] = i == 0 ? 1 : up[i-1][j] + 1; left[i][j] = i == 0 ? lo+1 : max(left[i-1][j], lo+1); } for (int j = m-1; j >= 0; --j ) if ( a[i][j] == 1 ) { right[i][j] = m; ro = j; } else { right[i][j] = i == 0 ? ro-1 : min(right[i-1][j], ro-1); ans = max(ans, (right[i][j] - left[i][j] + 1) * up[i][j]); } } printf("%d\n", ans*3); } return 0; }
2012年8月购买了一套罗技键鼠套装owo…一直觉得使用感觉不错.
今年突然出现鼠标中键下按不灵了…键盘有个地方卡键…于是就去了售后…
罗技的保修政策很给力….包装盒和发票并不是必须的
售后人员检查了一下确实有问题再检查一下鼠标的某pin就说发回厂家送修了
然后一个礼拜的样子通知我去售后点拿…换新了..耶!
此题一看,树状数组里神奇的 n & -n 就派上用场了。
输入你,输出 n-(n&-n)+1 和 n+(n&-n)-1 即可。
当然可以用一个递归来划分区间。同样我也写了一下。。比上面的方法可慢了不少。。
# include <iostream> using namespace std; int t, n; void dfs(long long root, long long min, long long max) { if ( root == n ) { cout << min << " " << max << endl; return; } if ( n < root ) dfs((root+min)>>1, min, root-1); else dfs( ((root+max)>>1)+1, root+1, max ); } int main() { cin >> t; while ( t-- ) { cin >> n; dfs((1<<30), 1, 2147483647); } return 0; }
韩国:夹在美利坚与北方同胞间的修罗场
朝鲜:进击的三胖
美国:问题儿童都来自朝鲜
日本:我的军队很少
菲律宾:美帝的宠物国家
俄罗斯:就算开战只要干预就没问题了吧
中国:邻国的怪同盟
利比亚:迷茫民众与懦弱的我
英国:我家王妃才不可能这么可爱
印度:少女与公交车
多欢乐…..