题意：给定一个序列 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:
/*
* Author: Yzcstc
* Created Time: 2014/11/8 19:03:57
* File Name: klo.cpp
*/
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<stack>
#include<ctime>
#define repf(i, a, b) for (int i = (a); i <= (b); ++i)
#define M0(x) memset(x, 0, sizeof(x))
#define Inf 0x7fffffff
using namespace std;
const int maxn = ;
typedef long long ll;
int n, k;
int a[];
#define L ch[x][0]
#define R ch[x][1]
#define KT ch[ch[root][0]][1]
struct SplayTree{
int sz[maxn], pre[maxn], ch[maxn][], v[maxn];
ll sum[maxn];
int m, root;
void push_up(const int& x){
sz[x] = sz[L] + sz[R] + ;
sum[x] = sum[L] + sum[R] + v[x];
}
void init(){
M0(sz), M0(pre), M0(ch), M0(ch), M0(v);
}
void push_down(const int& x){
}
void rotate(int &x, const int f){
int y = pre[x], z = pre[y];
push_down(y), push_down(x);
ch[y][!f] = ch[x][f];
pre[ch[x][f]] = y;
pre[x] = pre[y];
if (z) ch[z][ch[z][] == y] = x;
ch[x][f] = y;
pre[y] = x;
push_up(y);
}
void splay(int &x, const int g){
push_down(x);
while (pre[x] != g){
int y = pre[x], z = pre[y];
if (z == g) rotate(x, ch[y][] == x);
else {
int f = (ch[z][] == y);
ch[y][!f] ? rotate(y, f) : rotate(x, !f);
rotate(x, f);
}
}
push_up(x);
if (!g) root = x;
}
void rto(int k,const int g, int& y){
int x = root;
while (sz[L] + != k){
push_down(x);
if (sz[L] >= k) x = L;
else {
k -= sz[L] + ;
x = R;
}
}
y = x;
splay(x, g);
}
int search(int x, int val){
int y = -;
while (x){
y = x;
if (val <= v[x]) y = x, x = L;
else y = x, x = R;
}
return y;
}
void insert(int x, int val){
int y = search(root, val);
ch[y][val > v[y]] = x;
pre[x] = y;
while (y) push_up(y), y = pre[y];
splay(x, );
}
int findpre(int x){
x = L;
while (R) x = R;
return x;
}
void split(int x){
splay(x, );
int lt = findpre(x);
if (lt){
splay(lt, x);
root = lt, pre[root] = ;
ch[root][] = R;
if (R) pre[R] = root;
} else root = R, pre[R] = ;
push_up(root);
L = R = ;
}
ll query(const int& n, int &vv){
int k = (n+) / , x;
if (!(n & )) ++k;
rto(k, , x);
ll res = (ll)v[x] * (k-) - sum[ch[root][]] + sum[ch[root][]] - (ll)v[x] * (n-k);
vv = v[x];
return res;
}
} S; void init(){
for (int i = ; i <= n; ++i)
scanf("%d", &a[i]);
} void solve(){
if (k == ){
puts("");
for (int i = ; i <= n; ++i)
printf("%d\n", a[i]);
return;
}
S.root = , S.sz[] = , S.sum[] = S.v[] = a[];
for (int i = ; i <= n; ++i)
S.sz[i] = , S.v[i] = S.sum[i] = a[i];
for (int i = ; i <= k; ++i)
S.insert(i, a[i]);
int ans_pos = , ans_val = , val;
ll ans = S.query(k, ans_val), tmp;
for (int i = k + ; i <= n; ++i){
S.split(i-k);
S.insert(i, a[i]);
tmp = S.query(k, val);
if (tmp < ans)
ans = tmp, ans_val = val, ans_pos = i - k + ;
}
cout << ans << endl;
for (int i = ans_pos; i <= ans_pos+k-; ++i) a[i] = ans_val;
for (int i = ; i <= n; ++i) printf("%d\n", a[i]);
} int main(){
// freopen("a.in", "r", stdin);
// freopen("a.out", "w", stdout);
while (scanf("%d%d", &n, &k) != EOF){
init();
solve();
}
return ;
}
题意：有 n(n<=1000)个串，每个串的程度都<=100，有 m 次操作，每次操作都是将第 p1个串的第 w1 个字母和第 p2 个串的第 w2 个字母交换，问对于每一个串 i，在这些操作执行的过程中，它最多几个串相同过。
思路：由于每个串只有100，我们可以用n*m的时间进行hash。。
那么剩下来就是直接维护hash值为某一个数的集合了。。。平衡树可维护。。
code：
/*
* Author: Yzcstc
* Created Time: 2014/11/8 13:53:39
* File Name: poc.cpp
*/
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<stack>
#include<ctime>
#define M0(x) memset(x, 0, sizeof(x))
#define Inf 0x7fffffff
using namespace std;
#define M 10003
const int maxn = ;
/*** splay-tree***/
#define L ch[x][0]
#define R ch[x][1]
int sz[maxn], pre[maxn], rt[maxn], ms[maxn], ch[maxn][], lz[maxn]; void Splay_init(){
M0(sz), M0(pre), M0(rt), M0(ms), M0(ch), M0(lz);
} void pushdown(const int &x){
if (lz[x]){
if (L) lz[L] = max(lz[L], lz[x]), ms[L] = max(ms[L], lz[x]);
if (R) lz[R] = max(lz[R], lz[x]), ms[R] = max(ms[R], lz[x]);
lz[x] = ;
}
} void pushup(int x){} void rotate(int &x, const int f){
int y = pre[x], z = pre[y];
pushdown(y), pushdown(x);
ch[y][!f] = ch[x][f];
pre[ch[x][f]] = y;
pre[x] = pre[y];
if (z) ch[z][ch[z][] == y] = x;
ch[x][f] = y;
pre[y] = x;
pushup(y);
} void splay(int &x, const int g, int &root){
pushdown(x);
while (pre[x] != g){
int y = pre[x], z = pre[y];
if (z == g) rotate(x, ch[y][] == x);
else {
int f = (ch[z][] == y);
ch[y][!f] ? rotate(y, f) : rotate(x, !f);
rotate(x, f);
}
}
pushup(x);
if (!g) root = x;
} void update(int &root, int s){
lz[root] = max(lz[root], s);
ms[root] = max(ms[root], s);
} int right(int x){
while (R) x = R;
return x;
} void insert(int& root, int x, int size){
int p = right(root);
splay(p, , root);
ch[p][] = x, pre[x] = p;
update(root, size);
} void split(int& root, int x){
splay(x, , root);
int lt = ch[x][];
lt = right(lt);
if (lt){
splay(lt, x, root), root = lt;
if (R) pre[R] = root;
pre[root] = , ch[root][] = R;
} else
root = R, pre[R] = ;
L = R = ;
} /*** splay-end***/
map<int, int> mp;
char s[][];
int hs[], n, m, q, pw[]; inline int Hash(const char s[]){
int res = ;
for (int i = ; i < m; ++i)
res = res * M + s[i];
return res;
} void init(){
pw[m-] = ;
for (int i = m-; i >= ; --i)
pw[i] = pw[i+] * M;
for (int i = ; i <= n; ++i){
scanf("%s", s[i]);
hs[i] = Hash(s[i]);
}
} int f[maxn];
void solve(){
Splay_init();
mp.clear();
int tot = , u, v;
for (int i = ; i <= n; ++i){
u = hs[i], v = mp[u];
if (v)
insert(rt[v], i, ++sz[v]);
else {
v = mp[u] = ++tot;
sz[v] = ; rt[v] = i;
update(rt[v], );
}
}
int a, x1, b, x2;
int h1, h2;
while (q--){
scanf("%d%d%d%d", &a, &x1, &b, &x2);
x1--, x2--;
if (a == b){
h1 = hs[a] + pw[x1] * (s[b][x2] - s[a][x1]) + pw[x2] * (s[a][x1] - s[b][x2]);
u = mp[hs[a]], split(rt[u], a);
if (--sz[u] == ) mp[hs[a]] = rt[u] = ;
v = mp[h1];
if (v)
insert(rt[v], a, ++sz[v]);
else {
v = mp[h1] = ++tot;
sz[v] = ; rt[v] = a;
update(rt[v], );
}
hs[a] = h1;
swap(s[a][x1], s[b][x2]);
continue;
}
h1 = hs[a] + pw[x1] * (s[b][x2] - s[a][x1]);
h2 = hs[b] + pw[x2] * (s[a][x1] - s[b][x2]);
u = mp[hs[a]], split(rt[u], a);
if (--sz[u] == ) mp[hs[a]] = rt[u] = ;
u = mp[hs[b]], split(rt[u], b);
if (--sz[u] == ) mp[hs[b]]= rt[u] = ;
v = mp[h1];
if (v)
insert(rt[v], a, ++sz[v]);
else {
v = mp[h1] = ++tot;
sz[v] = ; rt[v] = a;
update(rt[v], );
}
v = mp[h2];
if (v)
insert(rt[v], b, ++sz[v]);
else {
v = mp[h2] = ++tot;
sz[v] = ; rt[v] = b;
update(rt[v], );
}
hs[a] = h1, hs[b] = h2;
swap(s[a][x1], s[b][x2]);
}
for (int i = ; i <= n; ++i){
u = mp[hs[i]];
splay(i, , rt[u]);
f[i] = ms[i];
}
for (int i = ; i <= n; ++i)
printf("%d\n", f[i]);
} int main(){
// freopen("a.in", "r", stdin);
// freopen("a.out", "w", stdout);
while (scanf("%d%d%d", &n, &m, &q) != EOF){
init();
solve();
}
fclose(stdin); fclose(stdout);
return ;
}