Note: This article is available in Chinese only. 本文暂无英文版本。
View original
http://codeforces.com/problemset/problem/548/B
比赛的时候不懂为什么就没做出来…. 其实很容易想到一个o(q*(n+m))的做法… 就是每次更新，要同时更新当前更新行的最大连续和….O（m）可以完成…然后在O（n）扫一遍，找到所有行中的最大值。 然后需要注意的是，在第一次更改之前就要把每个行的最大值处理出来l.. 然后cf机器真是够快，O(nmq)的1.2S过。。。。
代码实现
1
2
3
4
5
6
7
8 /* ***********************************************
9 Author :111qqz
10 Created Time :2016年02月19日 星期五 17时01分58秒
11 File Name :code/cf/problem/548B.cpp
12 ************************************************ */
13
14 #include <algorithm>
15 #include <cstdio>
16 #include <iostream>
17 #include <cstring>
18 #include <string>
19 #include <cmath>
20 #include <map>
21
22 using namespace std;
23 const int N=5E2+5;
24 int a[N][N];
25 int fans;
26 int n,m,q,x,y,cur,ans[N];
27 int main()
28 {
29 cin>>n>>m>>q;
30 for (int i = 1 ; i <= n;i++ )
31 {
32 for (int j = 1; j <= m ; j++ )
33 scanf("%d",&a[i][j]);
34 cur = 0;
35 for (int j = 1; j <=m ;j++ )
36 if (a[i][j]==1)
37 {
38 cur++;
39 ans[i]=max(cur,ans[i]);
40 }
41 else
42 {
43 cur = 0;
44 }
45 }
46 for ( int i = 1 ; i <= q; i++ )
47 {
48 scanf("%d %d",&x,&y);
49 a[x][y]=a[x][y]^1;
50 // if (i==3) cout<<a[x][y]<<"sadsadasd"<<endl;
51 cur = 0;
52 ans[x]=0;
53 for (int j = 1; j <=m ;j++ )
54 if (a[x][j]==1)
55 {
56 cur++;
57 ans[x]=max(cur,ans[x]);
58 }
59 else
60 {
61 cur = 0;
62 }
63 fans=-1;
64 for (int j = 1;j <= n ; j++ )
65 if (ans[j]>fans)
66 {
67 fans=ans[j];
68 }
69 cout<<fans<<endl;
70 }
71
72
73 return 0;
74 }