1 今天干的俄罗斯的一场多校，被虐哭啊，就做出两题。
2
3
4
5
6
7
| Gym 100496D | Data Mining |
8 题目讲得是给你一串数字，然后给你ｉ，ｐ，表示从第ｉ开始，对这串数离散话，并且离散化后的字典序要最小，然后输出原来下标为ｉ＋ｐ的离散化后的值
9 是多少。
10 假设ｉ＋ｐ这个位置上的数为ａ。
11 如果在(i,i+p)这个范围内没有ａ，并且这个区间内没有重复的数，那么答案就是ｐ
12 那么按照这个思路走，其实我们只要知道距离i位置最近的ａ的下标为ｒ，那么其实我们只要知道（ｉ，ｒ）这个区间中有多少个不同的数ｎ，那么答案就是
13 ｎ＋１。
14 因为数据比较大，所已对于每次的询问的复杂度必须做到O(1) , O(log(n)) 或 O(sqrt(n)).
15 就这道题而言用线段数O(logn)是可以的，进爷用默队算法O(sqrt(n))也做到了，我也想到了一种O(logn)的算法，蛋奶和，写不出来：
16 首先我们用ＲＭＱ预处理出每段区间的最大值，然后在询问的过程中我们便能用O(1)知道要求的区间的最大值R了，然后呢，用线段数去求R在这段区间按里是
17 第ｋ大，然后ｋ就是答案。（大家都觉得蛮有道理，但都懒得敲。。。）
18
19
20
| Gym 100496H | House of Representatives |
22 题目告诉你ｎ个城市的人口ｐ[n]，他们是构成了一棵树，在告诉你ｎ－１条的路ｗ[n],从一个城市ｖ到ｕ所需要的代价为ｐ[v]*(u到ｖ的距离）.
23 然后我们要在ｎ个城市里选出一个当首都，使其他所有城市到他的代价和最小。
24 欣爷一看就说是树形ｄｐ,然后就ａ掉了。
25 我们可以以编号为１的城市为根开始搜索，用ｏ（ｎ）的复杂度，得到一棵树，用ｄ[u]来保存ｕ这个节点的所有子节点到它的代价和,sum[u]来保存每棵子数
26 中总人口量。
27 这样一遍下来，其实我们就知道了以１号城市为首都的待价ｄ[1],我们设ｄｐ[n]为ｎ号城市当首都的代价，显然ｄｐ[1] = d[1] ;
28 然后如果你思路足够清晰的话可以得到这样一个递推式，设ｕ为ｖ的母亲，n个城市的总人数为all ,
29 那么ｄｐ[v] = d[v] +(all - sum[v])*(u到ｖ的长度）+ dp[u] - d[v] - sum[v]*(u到v的长度） ；
#include<stdio.h>
#include<vector>
#include<set>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll ;
const int M = + ;
int n , city[M] ;
vector<pair<int , int> > g[M] ;
ll d[M] , dp[M];
bool vis[M] ;
ll sum[M] ;
ll all ;
ll minn , id ; void tree (int u) {
for (int i = ; i < g[u].size () ; i ++) {
int v = g[u][i].first ;
if (vis[v]) continue ;
vis[v] = ;
dp[v] = (all - sum[v] ) * g[u][i].second + dp[u] - sum[v] * g[u][i].second ;
if (dp[v] < minn) {
minn = dp[v] ;
id = v ;
}
tree (v) ;
}
} void dfs (int u) {
for (int i = ; i < g[u].size () ; i ++) {
int v = g[u][i].first ;
if (vis[v] ) continue ;
vis[v] = ;
dfs (v) ;
d[u] += sum[v] * g[u][i].second + d[v] ;
sum[u] += sum[v] ;
}
} int main () {
freopen ("house.in" , "r" , stdin) ;
freopen ("house.out" , "w" , stdout) ;
scanf ("%d" , &n ) ;
for (int i = ; i < n ; i ++) {
scanf ("%d" , &city[i + ] ) ;
sum[i + ] = city[i + ] ;
all += sum[i + ] ;
}
for (int i = ; i < n - ; i ++) {
int u , v , w ;
scanf ("%d%d%d" , &u , &v , &w) ;
g[u].push_back (make_pair (v , w) ) ;
g[v].push_back (make_pair (u , w) ) ;
}
//printf ("g[0].size = %d\n" , g[0].size () ) ;
vis[] = ;
dfs ( ) ;
dp[] = d[] ;
minn = d[] ;
//for (int i = 1 ; i <= n ; i ++) printf ("d[%d] = %d , sum[%d] = %d\n" , i , d[i] , i , sum[i] ) ;
//printf ("d[0] = %d\n" , d[0] ) ;
memset (vis , , sizeof(vis)) ;
vis[] = ;
id = ;
tree ( ) ;
printf ("%I64d %I64d\n" , id , minn ) ;
return ;
}
30