[POI2008]KLO && POC

题意:给定一个序列 s1, s2,...sn,以及一个k,求一个连续的k个数,把s[i]...s[i+k-1]变成一个数s‘,使得sigma(|s[j]-s‘|)(i<=j<=i+k-1)最小

思路:最近无聊切起poi。。顿感智商不够。。

这道题很容易想到把这些数变成中位数最优。。那么就可以用平衡树维护了。。

当然,直接用set维护也就够了。。不过为了练练代码。。我还是写了下splay。。

code:

  1 /*
  2  * Author:  Yzcstc
  3  * Created Time:  2014/11/8 19:03:57
  4  * File Name: klo.cpp
  5  */
  6 #include<cstdio>
  7 #include<iostream>
  8 #include<cstring>
  9 #include<cstdlib>
 10 #include<cmath>
 11 #include<algorithm>
 12 #include<string>
 13 #include<map>
 14 #include<set>
 15 #include<vector>
 16 #include<queue>
 17 #include<stack>
 18 #include<ctime>
 19 #define repf(i, a, b) for (int i = (a); i <= (b); ++i)
 20 #define M0(x)  memset(x, 0, sizeof(x))
 21 #define Inf  0x7fffffff
 22 using namespace std;
 23 const int maxn = 120000;
 24 typedef long long ll;
 25 int n, k;
 26 int a[101010];
 27 #define L ch[x][0]
 28 #define R ch[x][1]
 29 #define KT ch[ch[root][0]][1]
 30 struct SplayTree{
 31       int sz[maxn], pre[maxn], ch[maxn][2], v[maxn];
 32       ll sum[maxn];
 33       int m, root;
 34       void push_up(const int& x){
 35            sz[x] = sz[L] + sz[R] + 1;
 36            sum[x] = sum[L] + sum[R] + v[x];
 37       }
 38       void init(){
 39            M0(sz), M0(pre), M0(ch), M0(ch), M0(v);
 40       }
 41       void push_down(const int& x){
 42       }
 43       void rotate(int &x, const int f){
 44             int y = pre[x], z = pre[y];
 45             push_down(y), push_down(x);
 46             ch[y][!f] = ch[x][f];
 47             pre[ch[x][f]] = y;
 48             pre[x] = pre[y];
 49             if (z) ch[z][ch[z][1] == y] = x;
 50             ch[x][f] = y;
 51             pre[y] = x;
 52             push_up(y);
 53       }
 54       void splay(int &x, const int g){
 55             push_down(x);
 56             while (pre[x] != g){
 57                 int y = pre[x], z = pre[y];
 58                 if (z == g) rotate(x, ch[y][0] == x);
 59                 else {
 60                      int f = (ch[z][0] == y);
 61                      ch[y][!f] ? rotate(y, f) : rotate(x, !f);
 62                      rotate(x, f);
 63                 }
 64             }
 65             push_up(x);
 66             if (!g) root = x;
 67       }
 68       void rto(int k,const int g, int& y){
 69             int x = root;
 70             while (sz[L] + 1 != k){
 71                   push_down(x);
 72                   if (sz[L] >= k) x = L;
 73                   else {
 74                        k -= sz[L] + 1;
 75                        x = R;
 76                   }
 77             }
 78             y = x;
 79             splay(x, g);
 80       }
 81       int search(int x, int val){
 82             int y = -1;
 83             while (x){
 84                  y = x;
 85                  if (val <= v[x]) y = x, x = L;
 86                  else y = x, x = R;
 87             }
 88             return y;
 89       }
 90       void insert(int x, int val){
 91            int y = search(root, val);
 92            ch[y][val > v[y]] = x;
 93            pre[x] = y;
 94            while (y) push_up(y), y = pre[y];
 95            splay(x, 0);
 96       }
 97       int findpre(int x){
 98            x = L;
 99            while (R) x = R;
100            return x;
101       }
102       void split(int x){
103            splay(x, 0);
104            int lt = findpre(x);
105            if (lt){
106                   splay(lt, x);
107                   root = lt, pre[root] = 0;
108                   ch[root][1] = R;
109                   if (R) pre[R] = root;
110            } else root = R, pre[R] = 0;
111            push_up(root);
112            L = R = 0;
113       }
114       ll query(const int& n, int &vv){
115             int k = (n+1) / 2, x;
116             if (!(n & 1)) ++k;
117             rto(k, 0, x);
118             ll res = (ll)v[x] * (k-1) - sum[ch[root][0]] + sum[ch[root][1]] - (ll)v[x] * (n-k);
119             vv = v[x];
120             return res;
121       }
122 } S;
123
124 void init(){
125      for (int i = 1; i <= n; ++i)
126             scanf("%d", &a[i]);
127 }
128
129 void solve(){
130      if (k == 1){
131            puts("0");
132            for (int i = 1; i <= n; ++i)
133                printf("%d\n", a[i]);
134            return;
135      }
136      S.root = 1, S.sz[1] = 1, S.sum[1] = S.v[1] = a[1];
137      for (int i = 2; i <= n; ++i)
138            S.sz[i] = 1, S.v[i] = S.sum[i] = a[i];
139      for (int i = 2; i <= k; ++i)
140            S.insert(i, a[i]);
141      int ans_pos = 1, ans_val = 0, val;
142      ll ans = S.query(k, ans_val), tmp;
143      for (int i = k + 1; i <= n; ++i){
144             S.split(i-k);
145             S.insert(i, a[i]);
146             tmp = S.query(k, val);
147             if (tmp < ans)
148                  ans = tmp, ans_val = val, ans_pos = i - k + 1;
149      }
150      cout << ans << endl;
151      for (int i = ans_pos; i <= ans_pos+k-1; ++i) a[i] = ans_val;
152      for (int i = 1; i <= n; ++i) printf("%d\n", a[i]);
153 }
154
155 int main(){
156 //    freopen("a.in", "r", stdin);
157 //    freopen("a.out", "w", stdout);
158     while (scanf("%d%d", &n, &k) != EOF){
159           init();
160           solve();
161     }
162     return 0;
163 }

题意:有 n(n<=1000)个串,每个串的程度都<=100,有 m 次操作,每次操作都是将第 p1个串的第 w1 个字母和第 p2 个串的第 w2 个字母交换,问对于每一个串 i,在这些操作执行的过程中,它最多几个串相同过。

思路:由于每个串只有100,我们可以用n*m的时间进行hash。。

那么剩下来就是直接维护hash值为某一个数的集合了。。。平衡树可维护。。

code:

  1 /*
  2  * Author:  Yzcstc
  3  * Created Time:  2014/11/8 13:53:39
  4  * File Name: poc.cpp
  5  */
  6 #include<cstdio>
  7 #include<iostream>
  8 #include<cstring>
  9 #include<cstdlib>
 10 #include<cmath>
 11 #include<algorithm>
 12 #include<string>
 13 #include<map>
 14 #include<set>
 15 #include<vector>
 16 #include<queue>
 17 #include<stack>
 18 #include<ctime>
 19 #define M0(x)  memset(x, 0, sizeof(x))
 20 #define Inf  0x7fffffff
 21 using namespace std;
 22 #define M 10003
 23 const int maxn = 201000;
 24 /*** splay-tree***/
 25 #define L ch[x][0]
 26 #define R ch[x][1]
 27 int sz[maxn], pre[maxn], rt[maxn], ms[maxn], ch[maxn][2], lz[maxn];
 28
 29 void Splay_init(){
 30      M0(sz), M0(pre), M0(rt), M0(ms),  M0(ch), M0(lz);
 31 }
 32
 33 void pushdown(const int &x){
 34      if (lz[x]){
 35           if (L) lz[L] = max(lz[L], lz[x]), ms[L] = max(ms[L], lz[x]);
 36           if (R) lz[R] = max(lz[R], lz[x]), ms[R] = max(ms[R], lz[x]);
 37           lz[x] = 0;
 38      }
 39 }
 40
 41 void pushup(int x){}
 42
 43 void rotate(int &x, const int f){
 44      int y = pre[x], z = pre[y];
 45      pushdown(y), pushdown(x);
 46      ch[y][!f] = ch[x][f];
 47      pre[ch[x][f]] = y;
 48      pre[x] =  pre[y];
 49      if (z) ch[z][ch[z][1] == y] = x;
 50      ch[x][f] = y;
 51      pre[y] = x;
 52      pushup(y);
 53 }
 54
 55 void splay(int &x, const int g, int &root){
 56      pushdown(x);
 57      while (pre[x] != g){
 58           int y = pre[x],  z = pre[y];
 59           if (z == g) rotate(x, ch[y][0] == x);
 60           else {
 61                int f = (ch[z][0] == y);
 62                ch[y][!f] ? rotate(y, f) : rotate(x, !f);
 63                rotate(x, f);
 64           }
 65      }
 66      pushup(x);
 67      if (!g) root = x;
 68 }
 69
 70 void update(int &root, int s){
 71      lz[root] = max(lz[root], s);
 72      ms[root] = max(ms[root], s);
 73 }
 74
 75 int right(int x){
 76      while (R) x = R;
 77      return x;
 78 }
 79
 80 void insert(int& root, int x, int size){
 81      int p = right(root);
 82      splay(p, 0, root);
 83      ch[p][1] = x, pre[x] = p;
 84      update(root, size);
 85 }
 86
 87 void split(int& root, int x){
 88      splay(x, 0, root);
 89      int lt = ch[x][0];
 90      lt = right(lt);
 91      if (lt){
 92           splay(lt, x, root), root = lt;
 93           if (R) pre[R] = root;
 94           pre[root] = 0, ch[root][1] = R;
 95      } else
 96           root = R, pre[R] = 0;
 97      L = R = 0;
 98 }
 99
100 /*** splay-end***/
101 map<int, int> mp;
102 char s[1100][110];
103 int hs[1010], n, m, q, pw[1010];
104
105 inline int Hash(const char s[]){
106     int res = 0;
107     for (int i = 0; i < m; ++i)
108          res = res * M + s[i];
109     return res;
110 }
111
112 void init(){
113      pw[m-1] = 1;
114      for (int i = m-2; i >= 0; --i)
115            pw[i] = pw[i+1] * M;
116      for (int i = 1; i <= n; ++i){
117           scanf("%s", s[i]);
118           hs[i] = Hash(s[i]);
119      }
120 }
121
122 int f[maxn];
123 void solve(){
124      Splay_init();
125      mp.clear();
126      int tot = 0, u, v;
127      for (int i = 1; i <= n; ++i){
128            u = hs[i], v = mp[u];
129            if (v)
130                   insert(rt[v], i, ++sz[v]);
131            else {
132                   v = mp[u] = ++tot;
133                   sz[v] = 1; rt[v] = i;
134                   update(rt[v], 1);
135            }
136      }
137      int a, x1, b, x2;
138      int h1, h2;
139      while (q--){
140            scanf("%d%d%d%d", &a, &x1, &b, &x2);
141            x1--, x2--;
142            if (a == b){
143                    h1 = hs[a] + pw[x1] * (s[b][x2] - s[a][x1]) + pw[x2] * (s[a][x1] - s[b][x2]);
144                    u = mp[hs[a]], split(rt[u], a);
145                    if (--sz[u] == 0) mp[hs[a]] = rt[u] = 0;
146                    v = mp[h1];
147                    if (v)
148                           insert(rt[v], a,  ++sz[v]);
149                    else {
150                           v = mp[h1] = ++tot;
151                           sz[v] = 1; rt[v] = a;
152                           update(rt[v], 1);
153                    }
154                    hs[a] = h1;
155                    swap(s[a][x1], s[b][x2]);
156                    continue;
157            }
158            h1 = hs[a] + pw[x1] * (s[b][x2] - s[a][x1]);
159            h2 = hs[b] + pw[x2] * (s[a][x1] - s[b][x2]);
160            u = mp[hs[a]], split(rt[u], a);
161            if (--sz[u] == 0) mp[hs[a]] = rt[u] = 0;
162            u = mp[hs[b]], split(rt[u], b);
163            if (--sz[u] == 0) mp[hs[b]]= rt[u] = 0;
164            v = mp[h1];
165            if (v)
166                   insert(rt[v], a, ++sz[v]);
167            else {
168                   v = mp[h1] = ++tot;
169                   sz[v] = 1; rt[v] = a;
170                   update(rt[v], 1);
171            }
172            v = mp[h2];
173            if (v)
174                   insert(rt[v], b, ++sz[v]);
175            else {
176                   v = mp[h2] = ++tot;
177                   sz[v] = 1; rt[v] = b;
178                   update(rt[v], 1);
179            }
180            hs[a] = h1, hs[b] = h2;
181            swap(s[a][x1], s[b][x2]);
182      }
183      for (int i = 1; i <= n; ++i){
184           u = mp[hs[i]];
185           splay(i, 0, rt[u]);
186           f[i] = ms[i];
187      }
188      for (int i = 1; i <= n; ++i)
189             printf("%d\n", f[i]);
190 }
191
192 int main(){
193 //    freopen("a.in", "r", stdin);
194 //    freopen("a.out", "w", stdout);
195     while (scanf("%d%d%d", &n, &m, &q) != EOF){
196           init();
197           solve();
198     }
199     fclose(stdin); fclose(stdout);
200     return 0;
201 }

时间: 11-06

[POI2008]KLO && POC的相关文章

【BZOJ1125】【POI2008】Poc 原名:Train hash+离散化+平衡树(splay)

链接: #include <stdio.h> int main() { puts("转载请注明出处[vmurder]谢谢"); puts("网址:blog.csdn.net/vmurder/article/details/45739895"); } 题解: 首先我们发现对于每个串,我们把它hash一下,然后建一棵平衡树来支持"插入"."删除"."下传标记"这三种操作就可以记录并更新一个点的答案了

bzoj1112[POI2008]砖块Klo*

bzoj1112[POI2008]砖块Klo 题意: N柱砖,希望有连续K柱的高度是一样的. 你可以选择以下两个动作 1:丢掉某柱砖的一块砖.给某柱加上一块砖,现在希望用最小次数的动作完成任务.N≤100000 题解: 设一个区间长度为k,其中位数为a,比a小的元素个数为b,和为c:比a大的元素个数为d,和为e.则题目要求维护一个长度为k的滑动窗口,能求出它的b*a-c+e-d*a.故用一个维护sum,size两个值的treap来维护.然而似乎我想复杂了?比所有人代码都大1k!注意要开long

BZOJ 1112: [POI2008]砖块Klo

1112: [POI2008]砖块Klo Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 1736  Solved: 606[Submit][Status][Discuss] Description N柱砖,希望有连续K柱的高度是一样的. 你可以选择以下两个动作 1:从某柱砖的顶端拿一块砖出来,丢掉不要了. 2:从仓库中拿出一块砖,放到另一柱.仓库无限大. 现在希望用最小次数的动作完成任务. Input 第一行给出N,K. (1 ≤ k ≤ n ≤

BZOJ 1112 [POI2008]砖块Klo(可持久化线段树)

[题目链接] http://www.lydsy.com/JudgeOnline/problem.php?id=1112 [题目大意] 给出一个数列,对于一个操作,你可以对一个数+1,或者一个数-1, 问若使得数列中出现长度为m的连续相同的数,最少需要的操作数. [题解] 我们发现对于固定区间求最小操作,等价于求区间中数距离中位数差值和最小, 我们发现区间中位数可以利用主席树求区间kth来实现, 同时在主席树上维护权值线段树的区间真值和,那么对于每个区间中的数, 就能分别维护比中位数小的部分的和以

[BZOJ1112] [POI2008] 砖块Klo (treap)

Description N柱砖,希望有连续K柱的高度是一样的. 你可以选择以下两个动作 1:从某柱砖的顶端拿一块砖出来,丢掉不要了. 2:从仓库中拿出一块砖,放到另一柱.仓库无限大. 现在希望用最小次数的动作完成任务. Input 第一行给出N,K. (1 ≤ k ≤ n ≤ 100000), 下面N行,每行代表这柱砖的高度.0 ≤ hi ≤ 1000000 Output 最小的动作次数 Sample Input 5 3 3 9 2 3 1 Sample Output 2 HINT 原题还要求输

[BZOJ 1112] [POI2008] 砖块Klo 【区间K大】

题目链接:BZOJ - 1112 题目分析 枚举每一个长度为k的连续区间,求出这个区间的最优答案,更新全局答案. 可以发现,这个区间的所有柱子最终都变成这k个数的中位数时最优,那么我们就需要查询这个区间的中位数了. 找到中位数之后,我们还应该求出这个区间内小于中位数的数的和,大于中位数的数的和,从而求出操作步数. 这些需要求的值可以用线段树或平衡树来写,我写的是线段树,但是实际上这是一道POI的题目,在MAIN上的空间限制只有35MB,线段树应该是不行的. 因为平衡树只需要 O(n) 空间,所以

python爬虫--自动获取seebug的poc

简单的写了一个爬取www.seebug.org上poc的小玩意儿~ 首先我们进行一定的抓包分析 我们遇到的第一个问题就是seebug需要登录才能进行下载,这个很好处理,只需要抓取返回值200的页面,将我们的headers信息复制下来就行了 (这里我就不放上我的headers信息了,不过headers里需要修改和注意的内容会在下文讲清楚) headers = { 'Host':******, 'Connection':'close', 'Accept':******, 'User-Agent':*

BZOJ1124: [POI2008]枪战Maf

1124: [POI2008]枪战Maf Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 501  Solved: 200[Submit][Status][Discuss] Description 有n个人,每个人手里有一把手枪.一开始所有人都选定一个人瞄准(有可能瞄准自己).然后他们按某个顺序开枪,且任意时刻只有一个人开枪.因此,对于不同的开枪顺序,最后死的人也不同. Input 输入n人数<1000000 每个人的aim Output 你要求最

1131: [POI2008]Sta

1131: [POI2008]Sta Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 783  Solved: 235[Submit][Status] Description 给出一个N个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大 Input 给出一个数字N,代表有N个点.N<=1000000 下面N-1条边. Output 输出你所找到的点,如果具有多个解,请输出编号最小的那个. Sample Input 8 1 4 5 6