记录个比赛2014-02-22

本文从WordPress迁移而来, 查看全部WordPress迁移文章

D.hdu 3874 Necklace

树状数组/线段树的题目,以前做过,很好的思想

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;
#define N 50010
#define MAX 200010
#define MAXVAL 1000010
#define LL long long
#define CL(xx,yy) memset((xx),(yy),sizeof((xx)))

LL c[N];
int n,a[N],pre[MAXVAL];
struct query{
int l,r,id;
LL val;
}q[MAX];
vector<int>save[N];

int lowbit(int x){
return x & (-x);
}

void updata(int val,int pos){
while(pos <= n){
c[pos] += val;
pos += lowbit(pos);
}
}

LL sum(int pos){
LL ans = 0LL;
while(pos){
ans += c[pos];
pos -= lowbit(pos);
}
return ans;
}

void solve(){
for(int i = 1; i <= n; i++){
updata(a[i],i);
if(pre[a[i]] != -1)
updata(-a[i],pre[a[i]]);
pre[a[i]] = i;
for(int k = 0; k < save[i].size(); k++){
int id = save[i][k];
int l = q[id].l , r = i;
LL suml = sum(l-1);
LL sumr = sum(r);
q[id].val = sumr - suml;
}
}
}

int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
CL(c,0);
CL(pre,-1);
for(int i = 1; i <= n; i++)
save[i].clear();
for(int i = 1; i <= n; i++)
scanf("%d",&a[i]);
int Q;
scanf("%d",&Q);
for(int i = 0; i < Q; i++){
q[i].id = i;
q[i].val = -1;
scanf("%d%d",&q[i].l,&q[i].r);
save[q[i].r].push_back(i);
}
solve();
for(int i = 0 ; i < Q; i++)
printf("%I64d\n",q[i].val);
}
return 0;
}

E. hdu 2833 WuKong

题意:给一个带权无向图,给出一对起点终点AB,另一对起点终点CD,AB的最短路,CD最短路,两条最短路的公共顶点最多是多少
一个性质的证明

设P1为AB的最短路径,P2为CD的最短路径,假设P1和P2有两段或更多的公共的段

第一公共段为x—-y,第二公段为p—-q

A,C先走到x,从x走到y,然后两者分头了

A从i路走到p,C从j路走到p路

两者再从p走到q

从开始,又分头走到了各自的终点B,D

  1. i路和j路的长度一定不同,如果长度相同,A,C都可以选i路,这样公共顶点更多(包含了i路上的所有顶点)
  2. i路和j路长度不同,A,C都应该走较短的那条,这样,走出的最短路更短,前面已经假设,A,C走的都是最短路,所以与假设矛盾

结论:P1和P2最多只会有一段连续的公共段

设d[u][v]是u到v的最短路值

因为点只有300,做一个O(n*n)的暴力枚举,枚举i,j是P1和P2的唯一公共段

  1. 首选i—–j段不能违反最短路,即
    1. d[A][i]+d[i][j]+d[j][B] = d[A][B]
    2. d[C][i]+d[i][j]+d[j][D] = d[C][D]
      必须同时成立
  2. 已经假设了i—j是P1和P2的唯一公共段,那么,应该计算出,i到j的最短路中,最多经过多少点

这个问题用dp解决

设一个重点点,i到j的最短路经过k,那么i到k经过最多点+k到j经过最多点 = i到j经过最多点

可以看到,求经过最多点和求最短路的dp思想是一模一样的,所以写一个Floyd,把他们两者都搞定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define N 310
#define INF 0x3f3f3f3f
#define CL(xx,yy) memset((xx),(yy),sizeof((xx)))

int n,m,d[N][N],dp[N][N];
int A,B,C,D;

void Floyd(){
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++){
if(k == i || k == j || i == j) continue;
if(d[i][k] + d[k][j] <= d[i][j]){ // <=
if(d[i][k] + d[k][j] == d[i][j])
dp[i][j] = max(dp[i][j] , dp[i][k] + dp[k][j] - 1);
else
dp[i][j] = dp[i][k] + dp[k][j] - 1;
d[i][j] = d[i][k] + d[k][j];
}
}
}

int solve(){
int ans = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++){
if(d[A][B] != d[A][i]+d[i][j]+d[j][B]) continue;
if(d[C][D] != d[C][i]+d[i][j]+d[j][D]) continue;
ans = max(ans,dp[i][j]);
}
return ans;
}

void test(){
for(int i = 1; i <= n; i++)
for(int j = i+1; j <= n; j++){
printf("[%d , %d] [%d , %d] [%d , %d]\n",
i,j,d[i][j],d[j][i],dp[i][j],dp[j][i]);
}
}

int main(){
while(scanf("%d%d",&n,&m)!=EOF){
if(n == 0 && m == 0) break;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++){
if(i == j) { d[i][i] = 0; dp[i][i] = 1; }
else { d[i][j] = INF; dp[i][j] = 2; }
}
while(m--){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
d[u][v] = min(d[u][v],w);
d[v][u] = min(d[v][u],w);
}
scanf("%d%d%d%d",&A,&B,&C,&D);
Floyd();
//test();
int ans = solve();
printf("%d\n",ans);
}
return 0;
}