CodeForces 1200D White Lines
- Time limit
1500 ms
Memory limit
262144 kB
解题思路
1200D - White Lines
Let's consider a single row that contains at least one black cell. If the first appearance of a black
cell is at the l"
role="presentation" style="position: relative;">
l
l
-th column and the last appearance of a
black cell is at the r"
role="presentation" style="position: relative;">
r
r
-th column, we can determine whether it
becomes a white line when a certain cell (i,j)"
role="presentation" style="position: relative;">
(i,j)
(
i
,
j
)
is clicked in O(1)"
role="presentation" style="position: relative;">
O(1)
O
(
1
)
, after some preprocessing. It becomes
a white line if and only if a cell (i,j)"
role="presentation" style="position: relative;">
(i,j)
(
i
,
j
)
is clicked where the row is at [i,i+k−1]"
role="presentation" style="position: relative;">
[i,i+k−1]
[
i
,
i
+
k
−
1
]
and j≤l≤r≤j+k−1"
role="presentation" style="position: relative;">
j≤l≤r≤j+k−1
j
≤
l
≤
r
≤
j
+
k
−
1
. We just need to
compute l"
role="presentation" style="position: relative;">
l
l
and r"
role="presentation" style="position: relative;">
r
r
in advance.
Now let's consider all n"
role="presentation" style="position: relative;">
n
n
rows (not columns). First, count all
rows that are already white lines before clicking. Then we count the number of white rows when the
cell (1,1)"
role="presentation" style="position: relative;">
(1,1)
(
1
,
1
)
is clicked, by applying the above
method to all rows from 1"
role="presentation" style="position: relative;">
1
1
to k"
role="presentation" style="position: relative;">
k
k
. Ignore the already-white rows that we
counted before. So far we obtained the number of white rows when the cell (1,1)"
role="presentation" style="position: relative;">
(1,1)
(
1
,
1
)
is clicked. From now, we slide the window. Add the k+1"
role="presentation" style="position: relative;">
k+1
k
+
1
-st row and remove the 1"
role="presentation" style="position: relative;">
1
1
-st row by applying the same method to
them, and we obtain the number of white rows when the cell (2,1)"
role="presentation" style="position: relative;">
(2,1)
(
2
,
1
)
is clicked. We can repeat this until
we calculate all n−k+1"
role="presentation" style="position: relative;">
n−k+1
n
−
k
+
1
cases for clicking the cells at the
1"
role="presentation" style="position: relative;">
1
1
-st column. Then we repeat the whole
process for all n−k+1"
role="presentation" style="position: relative;">
n−k+1
n
−
k
+
1
columns.
The same process can be done for counting white columns, too. Now we know the number of white rows
and white columns when each cell is clicked, so we can find the maximum value among their sums.
Time complexity: O(n2)"
role="presentation" style="position: relative;">
O(n2)
O
(
n
2
)
可以说是十分暴力了，cf上打的标签有brute force。一个优化就是把橡皮覆盖的区域一格一格地移动，这样就可以\(O(1)\)更新边界了，（突然想到滑动窗口，虽然和这题关系不大）。还有个标签是尺取法，好像也没毛病，滑动区域，更新边界，这确实可以算简化的尺取或者双指针吧……
另外，由于滑动区域的时候，左右滑只能快速更新空白列数，不能快速更新空白行数，上下滑同理，所以行和列分开处理，各自来一遍
感想
本来这题没有必要写博客的，但太兴奋了，真的。写完代码，改好CE以后，样例一遍过，半信半疑交上去，居然就AC了！
回想暑假集训这一个月，蠢得跟啥使得，集训题的做题记录，同样是一片绿，别人的就一个AC时间，我的除了AC时间，下方全都有“-1”“-2”“-3”(失败的提交次数)……每个小错都要浪费我至少两个小时……好几次花半天时间，找到了诸如continue写成return、数组下标或者变量写错之类的错，太憋屈了…………
源代码
#include<cstdio>
#include<algorithm>
int n,k;
const int MAXN=2e3+4;
int u[MAXN],d[MAXN],l[MAXN],r[MAXN];
int ansrow[MAXN][MAXN],anscol[MAXN][MAXN],wrow,wcol;
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
char s[2010];
scanf("%s",s+1);
for(int j=1;j<=n;j++)
{
if(s[j]=='B')
{
r[i]=j;
if(!l[i]) l[i]=j;
d[j]=i;
if(!u[j]) u[j]=i;
}
}
}
for(int i=1;i<=n;i++)
{
if(u[i]==0) wcol++;
if(l[i]==0) wrow++;
}
//先是列
for(int i=1;i+k-1<=n;i++)//对于每一行
{
for(int ii=1;ii<=k;ii++)//统计每行开头区域的答案
if(d[ii]&&d[ii]<=i+k-1&&u[ii]>=i) anscol[i][1]++;
for(int j=2;j+k-1<=n;j++)//将统计区域向右滑动
{
anscol[i][j]=anscol[i][j-1];
if(d[j-1]&&d[j-1]<=i+k-1&&u[j-1]>=i) anscol[i][j]--;
if(d[j+k-1]&&d[j+k-1]<=i+k-1&&u[j+k-1]>=i) anscol[i][j]++;
}
}
//然后行也来一遍
for(int i=1;i+k-1<=n;i++)
{
for(int ii=1;ii<=k;ii++)//统计每列开头区域的答案
if(r[ii]&&r[ii]<=i+k-1&&l[ii]>=i) ansrow[1][i]++;
for(int j=2;j+k-1<=n;j++)//将统计区域向下滑动
{
ansrow[j][i]=ansrow[j-1][i];
if(r[j-1]&&r[j-1]<=i+k-1&&l[j-1]>=i) ansrow[j][i]--;
if(r[j+k-1]&&r[j+k-1]<=i+k-1&&l[j+k-1]>=i) ansrow[j][i]++;
}
}
int ans=-1;
for(int i=1;i+k-1<=n;i++)
{
for(int j=1;j+k-1<=n;j++)
ans=std::max(ans,anscol[i][j]+ansrow[i][j]);
}
printf("%d\n",ans+wcol+wrow);
return 0;
}
最新文章
- apt-get 与 yum 的区别
- Android Fragment的使用
- Careercup - Google面试题 - 5085331422445568
- Go推出的主要目的之一就是G内部大东西太多了，系统级开发巨型项目非常痛苦，Go定位取代C++，Go以简单取胜（KISS）
- bzoj 1014 [JSOI2008]火星人prefix（splay+hash）
- 数据访问层DAL(数据库访问抽象类DataProvider)
- 回某位朋友问题备受phpcgi.exe煎熬现在cpu跑满（解决方案）
- Js自动截取字符串长度，添加省略号“……”
- javascript学习笔记(2)
- 团队作业4——第一次项目冲刺（Alpha版本） 1
- （转） Linux中profile、bashrc、bash_profile之间的区别和联系
- 基于Redis的INCR实现一个限流器
- PostgreSQL操作-psql基本命令
- [leetcode 8] String to Integer
- Log4j 基本配置示例
- Linux账号和密码文件 /etc/passwd和/etc/shadow
- 【每日更新】【SQL实用大杂烩】
- linux下安装JDK，及配置环境变量
- 图片与路径（Path）的应用
- iis7+的虚拟目录：未能加载程序集“**”。请确保在访问该页之前已经编译了此程序集