1 P1881 閃爍的繁星

分治，維護幾個結果即可。

#include <cstdio> #include <iostream> using namespace std;const int maxn = 200007; int a[maxn<<2][3]; int b[maxn];#define LL 1 #define RR 2void build(int l, int r, int i) {a[i][0] = a[i][1] = a[i][2] = 1;if (l == r) return;else {int m = l+r >> 1;build(l, m, i<<1), build(m + 1, r, i<<1 | 1);}}void modify(int p, int l, int r, int i) {if (l == r) return;else {int m = l+r >> 1;if (p <= m) modify(p, l, m, i<<1);else modify(p, m+1, r, i<<1 | 1);if (b[m] != b[m+1]) {//printf("[%d, %d][%d, %d]\n", l, m, m+1, r);if (a[i<<1][LL] >= m-l+1)a[i][LL] = m-l+1 + a[i<<1 | 1][LL];else a[i][LL] = a[i<<1][LL];if (a[i<<1 | 1][RR] >= r-m)a[i][RR] = r-m + a[i<<1][RR];else a[i][RR] = a[i<<1 | 1][RR];a[i][0] = max(a[i<<1][RR] + a[i<<1 | 1][LL], max(a[i<<1][0], a[i<<1][1]));//printf("%d 0]%d 1]%d 2]%d\n", i, a[i][0], a[i][1], a[i][2]);} else {a[i][0] = max(a[i<<1][0], a[i<<1 | 1][0]);a[i][LL] = a[i<<1][LL];a[i][RR] = a[i<<1 | 1][RR];}}}int main(void) {int N, Q;scanf("%d%d", &N, &Q);build(1, N, 1);for(int i=0; i<Q; ++i) {int c;scanf("%d", &c); b[c] ^= 1;modify(c, 1, N, 1);printf("%d\n", a[1][0]);}return 0; }

?

2 P1882 石階上的磚

可以想到是貪心策略，既然要求兩邊依次相差1，我們索性就先減掉然后再貪心。比賽時2b的最后拍了求平均數的解答，結果測試數據沒一個對的= =。

改成求中位數就AC了，正確性也是不難證明的。。。（太2b了）

1 #include <cstdio> 2 #include <algorithm> 3 #include <vector> 4 using namespace std; 5 6 typedef long long LL; 7 LL castle[2][300002]; 8 vector<LL> sorted; 9 10 #define abs(x) ((x)<0?-(x):(x)) 11 12 int main(void) 13 { 14 int N; 15 scanf("%d", &N); 16 for(int i=0;i<N; ++i) scanf("%I64d", &castle[0][i]); 17 for(int i=0;i<N; ++i) scanf("%I64d", &castle[1][i]); 18 19 int mid = N>>1; 20 sorted.push_back(castle[0][mid]), sorted.push_back(castle[1][mid]); 21 for(int i=1; i+i+1<=N; ++i){ 22 castle[0][mid - i] -= i, castle[1][mid - i] -= i; 23 castle[0][mid + i] -= i, castle[1][mid + i] -= i; 24 25 sorted.push_back(castle[0][mid - i]), sorted.push_back(castle[0][mid + i]); 26 sorted.push_back(castle[1][mid - i]), sorted.push_back(castle[1][mid + i]); 27 } 28 sort(sorted.begin(), sorted.end()); 29 // 求中位數 30 int median = sorted.size() >> 1; 31 LL ans = 0; 32 for(int i=0; i<N; ++i) { 33 ans += abs(castle[0][i] - sorted[median]); 34 ans += abs(castle[1][i] - sorted[median]); 35 } 36 printf("%I64d\n", ans); 37 return 0; 38 }

?

轉載于:https://www.cnblogs.com/e0e1e/p/4008078.html

總結

以上是生活随笔為你收集整理的VIJOS国庆节模拟赛之繁星春水的全部內容，希望文章能夠幫你解決所遇到的問題。

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