codeforces|codeforces 1102D White Lines codeforces1102DWhiteLines

【codeforces|codeforces 1102D White Lines】题目链接：http://codeforces.com/contest/1200/problem/D
这题比赛时没想出来，赛后补题时想出来了，还是自己太菜了。。。
思路：这题按照暴力去做的话，时间肯定tle，所以我们得去优化。这题需要利用滑动窗口，利用滑动窗口，我们可以把时间降到O(N2),首先预处理每行每列的B的最大位置最小位置，然后接下来就可以去模拟了，我们想，题目给了一个边长为k的正方形可以覆盖，那么这一列(或一行）B的最大，最小位置是不是在边长为k的正方形内。这样就可以利用滑动窗口去搞了，我们用队列( 先进先出 )去模拟边长为k的窗口，就可以得到答案。注意我们先算出，原来就存在的白线有多少，模拟得时候不计这个答案。

1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 using namespace std; 16 long long GCD(long long a, long long b) { return b == 0 ? a : GCD(b, a%b); } 17 const long long inf = 0x7f7f7f7f; 18 const long long mod = 1e9 + 7; 19 double pi = acos(-1.0); 20 char str[2100][2100]; 21 int a[2100][2100]; 22 vectorr[2100], c[2100]; //r统计每行产生得贡献是多少，c统计每列产生得贡献是多少 23 queueval; //模拟滑动窗口 24 int n, k; 25 int R[2100], C[2100]; //预处理白线所在的位置 26 void fact(int i, int minc[], int maxc[], int num) 27 { 28int sum = 0; 29for (int j = 1; j <= n; j++) 30{ 31if (val.size() < k)//小于k时直接放入队列里 32{ 33val.push(j); 34if (minc[j] >= i && minc[j] < i + k && maxc[j] >= i && maxc[j] < i + k)//判断B是不是在正方形内 35{ 36if (num == 0 && C[j] != 1) 37sum++; 38else if (num == 1 && R[j] != 1)//扣出白线所在的位置 39sum++; 40 41} 42if (val.size() == k)//计算产生的贡献 43{ 44if (num == 0) 45c[i].push_back(sum); 46else 47r[j].push_back(sum); 48} 49} 50else 51{ 52int index = val.front(); 53val.pop(); 54val.push(j); 55if (minc[index] >= i && minc[index] < i + k && maxc[index] >= i && maxc[index] < i + k)//需要减去之前第一个入队所产生的产生贡献 56{ 57if (num == 0 && C[index] != 1) 58sum--; 59else if (num == 1 && R[index] != 1) 60sum--; 61} 62if (minc[j] >= i && minc[j] < i + k && maxc[j] >= i && maxc[j] < i + k) 63{ 64if (num == 0 && C[j] != 1) 65sum++; 66else if (num == 1 && R[j] != 1) 67sum++; 68} 69if (num == 0) 70c[i].push_back(sum); 71else 72r[j].push_back(sum); 73} 74} 75while (!val.empty()) 76val.pop(); 77 } 78 int main() 79 { 80ios::sync_with_stdio(false); 81cin.tie(0); cout.tie(0); 82int minr[2100], minc[2100], maxr[2100], maxc[2100]; 83cin >> n >> k; 84for (int i = 1; i <= n; i++) 85{ 86cin >> str[i]; 87for (int j = 0; j < n; j++) 88a[i][j + 1] = (str[i][j] == 'W' ? 0 : 1); 89} 90for (int i = 1; i <= n; i++)//预处理每行每列B的最大最小位置 91{ 92int minn = n, maxn = 0; 93for (int j = 1; j <= n; j++) 94if (a[i][j]) 95{ 96minn = min(minn, j); 97maxn = max(maxn, j); 98} 99minr[i] = minn, maxr[i] = maxn; 100minn = n, maxn = 0; 101for (int j = 1; j <= n; j++) 102if (a[j][i]) 103{ 104minn = min(minn, j); 105maxn = max(maxn, j); 106} 107minc[i] = minn, maxc[i] = maxn; 108} 109int ans = 0; 110for (int i = 1; i <= n; i++)//算出原来就存在的白线数目 111{ 112bool flag = false; 113for (int j = 1; j <= n; j++) 114if (a[i][j]) 115flag = true; 116if (!flag) 117ans++, R[i] = 1; 118flag = false; 119for (int j = 1; j <= n; j++) 120if (a[j][i]) 121flag = true; 122if (!flag) 123ans++, C[i] = 1; 124} 125for (int i = 1; i <= n - k + 1; i++) 126{ 127fact(i, minc, maxc, 0); //算出每行产生的贡献 128fact(i, minr, maxr, 1); //算出每列产生的贡献 129} 130int maxn = 0; ; 131for (int i = 1; i <= n - k + 1; i++) 132for (int j = 0; j < n - k + 1; j++) 133maxn = max(maxn, r[i + k - 1][j] + c[i][j]); //每行每列的贡献加上得到的是正方形所产生的贡献 134cout << ans + maxn << endl; 135 }

转载于:https://www.cnblogs.com/feiyue-1779930274/p/11346142.html