首页 > 代码库 > VIJOS国庆节模拟赛之繁星春水
VIJOS国庆节模拟赛之繁星春水
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 }
VIJOS国庆节模拟赛之繁星春水
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。