NOI 2009 诗人小G

NOI Add comments1,155 views

问题简述

有N个诗句需要被排版为若干行,顺序不能改变。一行内可以有若干个诗句,相邻诗句之间有一个空格。定义行标准长度L,每行的不协调度为|实际长度-L|P,整首诗的不协调度就是每行不协调度之和。任务是安排一种排版方案,使得整首诗的不协调度最小。

问题建模

这是一个最优化问题,抽象成动态规划模型。设第i个诗句的长度为Len[i],前i个诗句的总长度为SumL[i],clip_image002[4]。F[i]为对前i个诗句排版的最小不协调度。

解法1 朴素的动态规划

算法描述

显然每个F[i]可以被分解为F[j]和第j+1…i个句子组成一行的状态,所以状态转移方程为

clip_image004[4]

简化后,可以书写成

clip_image006

在具体实现时,应记录每个状态的决策,以便于输出合法方案。考虑到“最小的不协调度超过1018输出”Too hard to arrange””,为防止64位整型运算溢出,可以先用浮点数类型计算,然后再用整型算出具体值。

复杂度分析

状态数为O(N),每次转移需要以O(N)的时间枚举j,所以时间复杂度为O(N2)。在实际测试中通过了测试点1,2,3,得到30分。

参考程序
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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
/* 
 * Problem: NOI2009 poet
 * Author: Guo Jiabao
 * Time: 2009.9.22 13:30
 * State: Solved
 * Memo: 朴素动态规划
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
 
typedef long long big;
 
const int MAXN=100001,SMAXL=32;
const big INF=~0ULL>>1,LIMIT=1000000000000000000LL;
 
big F[MAXN],sumL[MAXN];
int N,L,P;
int Len[MAXN],deci[MAXN],sel[MAXN];
char sent[MAXN][SMAXL];
 
void init()
{
	scanf("%d%d%d\n",&N,&L,&P);
	for (int i=1;i<=N;++i)
	{
		gets(sent[i]);
		Len[i] = strlen(sent[i]);
		sumL[i] = sumL[i-1] + Len[i];
	}
}
 
big power(big a)
{
	big t=1;
	double dt=1;
	if (a < 0)
		a = -a;
	for (int i=1;i<=P;i++)
	{
		dt *= a;
		if (dt > LIMIT)
			return INF;
		t *= a;
	}
	return t;
}
 
void solve()
{
	int i,j,k;
	big minv,t;
	for (i=1;i<=N;++i)
	{
		minv = INF;
		for (j=0;j<=i-1;++j)
		{
			t = power(sumL[i] - sumL[j] + i-j-1 - L);
			if ( double(t) + double(F[j]) <= LIMIT && t + F[j] < minv)
			{
				minv = t + F[j];
				k = j;
			}
		}
		F[i] = minv;
		deci[i] = k;
	}
}
 
void print()
{
	if (F[N] <= LIMIT)
	{
		cout << F[N] << endl;
		int i,j;
		for (i=N,j=0;i;i=deci[i])
			sel[++j] = i;
		for (i=0;j;j--)
		{
			for (++i;i < sel[j];++i)
				printf("%s ",sent[i]);
			printf("%s\n",sent[i]);
		}
	}
	else
		printf("Too hard to arrange\n");
	printf("--------------------\n");
}
 
int main()
{
	int i,T;
	freopen("poet.in","r",stdin);
	freopen("poet.out","w",stdout);
	scanf("%d",&T);
	for (i=1;i<=T;i++)
	{
		init();
		solve();
		print();
	}
	return 0;
}

解法2 贪心的动态规划

算法描述

观察测试点4,5的N值较大,而L值较小,因此可以限制每行长度,以优化状态转移。

clip_image008

实现时应让j从i-1到0枚举,当j<i-1时一旦发现行长度超过2L,即停止枚举j,因为j继续减少会让行长度继续增加。

算法证明

一个空行的不协调度为LP,若一行内包含多余一个句子,且行长度L’>2L,则行不协调度(L’-L)P>LP。把该行拆分为两行后,设长度分别为L1和L2,L1+L2=L’-1,拆分后的两行不协调度之和为(L1-L)P+(L2-L)P<(L’-L)P,所以拆分为两行后比合在一行好。因此应保证当一行包含多于一个句子时,行长度<=2L。

复杂度分析

状态数为O(N),每次转移需要O(Min{N,L})的时间,所以时间复杂度为O(Min{N2,NL})。在实际测试中通过了前5个测试点,得到50分。

参考程序
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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
/* 
 * Problem: NOI2009 poet
 * Author: Guo Jiabao
 * Time: 2009.9.22 13:51
 * State: Solved
 * Memo: 朴素动态规划 剪枝
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
 
typedef long long big;
 
const int MAXN=100001,SMAXL=32;
const big INF=~0ULL>>1,LIMIT=1000000000000000000LL;
 
big F[MAXN],sumL[MAXN];
int N,L,P;
int Len[MAXN],deci[MAXN],sel[MAXN];
char sent[MAXN][SMAXL];
 
void init()
{
	scanf("%d%d%d\n",&N,&L,&P);
	for (int i=1;i<=N;++i)
	{
		gets(sent[i]);
		Len[i] = strlen(sent[i]);
		sumL[i] = sumL[i-1] + Len[i];
	}
}
 
big power(big a)
{
	big t=1;
	double dt=1;
	if (a < 0)
		a = -a;
	for (int i=1;i<=P;i++)
	{
		dt *= a;
		if (dt > LIMIT)
			return INF;
		t *= a;
	}
	return t;
}
 
void solve()
{
	int i,j,k;
	big minv,t;
	for (i=1;i<=N;++i)
	{
		minv = INF;
		for (j=i-1;j>=0;--j)
		{
			t = sumL[i] - sumL[j] + i-j-1 - L;
			if (j < i-1 && t > L + L)
				break;
			t = power(t);
			if ( double(t) + double(F[j]) <= LIMIT && t + F[j] < minv)
			{
				minv = t + F[j];
				k = j;
			}
		}
		F[i] = minv;
		deci[i] = k;
	}
}
 
void print()
{
	if (F[N] <= LIMIT)
	{
		cout << F[N] << endl;
		int i,j;
		for (i=N,j=0;i;i=deci[i])
			sel[++j] = i;
		for (i=0;j;j--)
		{
			for (++i;i < sel[j];++i)
				printf("%s ",sent[i]);
			printf("%s\n",sent[i]);
		}
	}
	else
		printf("Too hard to arrange\n");
	printf("--------------------\n");
}
 
int main()
{
	int i,T;
	freopen("poet.in","r",stdin);
	freopen("poet.out","w",stdout);
	scanf("%d",&T);
	for (i=1;i<=T;i++)
	{
		init();
		solve();
		print();
	}
	return 0;
}

解法3 凸壳优化动态规划

算法描述

观察发现测试点6,7的N和L都很大,而P值为2。经分析发现可以使用单调队列维护凸壳。

算法分析与证明

当P=2时,观察状态转移方程

clip_image010

设对于F[i]的最优决策为k,那么对于所有的j≠k,均满足

clip_image012

clip_image014clip_image016,则有

clip_image018

clip_image020

clip_image022

因为SumL为单调增函数,所以A,B均为增函数。当B[j]>B[k] ⇒j>k,有

clip_image024

相对的,当j<k时有

clip_image026

如果把(B[i],F[i]+B[i]2)看作是二维平面上的一个点,那么clip_image028恰为斜率公式。因此对于最优决策k,应保证在对应点右边任意一个决策j的对应点,满足直线kj斜率大于2A[i];在对应点左边任意一个决策j的对应点,满足直线kj斜率小于2A[i]。

image

因此所有最优决策在平面上的对应点连线就是一个斜率递增的凸壳。

image

具体实现时,用单调队列维护每个点(B[i],F[i]+B[i]2),每在队尾加入一个新的点,判断斜率是否递增,如果不是则不断删除队尾元素。求F[i]的最优决策只需不断在队首删除点,直到队首两点组成的直线斜率刚好大于2A[i],最优决策就是左端点的对应决策。

复杂度分析

用单调队列每次维护凸壳的时间复杂度为均摊O(1),所以时间复杂度为O(N)。经测试可以通过测试点6,7,配合解法2,一共可以得到70分。

参考程序
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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
/* 
 * Problem: NOI2009 poet
 * Author: Guo Jiabao
 * Time: 2009.9.22 14:30
 * State: Solved
 * Memo: 朴素动态规划 剪枝 凸壳优化
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
 
typedef long long big;
 
const int MAXN=100001,SMAXL=32;
const big INF=~0ULL>>1,LIMIT=1000000000000000000LL;
 
struct MonoQueue
{
	struct point
	{
		big x,y;
		int id;
	}P[MAXN];
 
	int head,tail;
 
	void initialize()
	{
		head = 0;
		tail = -1;
	}
 
	void insert(big x,big y,int id)
	{
		point p={x,y,id};
		for (;head + 1 <= tail;--tail)
		{
			double k1,k2;
			k1 = (p.y - P[tail].y) / double(p.x - P[tail].x);
			k2 = (P[tail].y - P[tail-1].y) / double(P[tail].x - P[tail-1].x);
			if (k1 > k2)
				break;
		}
		P[++tail] = p;
	}
 
	int getmin(big v)
	{
		for (;head + 1 <= tail;++head)
		{
			double k = (P[head+1].y - P[head].y) / double(P[head+1].x - P[head].x);
			if (k > v)
				break;
		}
		return P[head].id;
	}
}MQ;
 
big F[MAXN],sumL[MAXN],A[MAXN],B[MAXN];
int N,L,P;
int Len[MAXN],deci[MAXN],sel[MAXN];
char sent[MAXN][SMAXL];
 
void init()
{
	scanf("%d%d%d\n",&N,&L,&P);
	for (int i=1;i<=N;++i)
	{
		gets(sent[i]);
		Len[i] = strlen(sent[i]);
		sumL[i] = sumL[i-1] + Len[i];
	}
}
 
big power(big a)
{
	big t=1;
	double dt=1;
	if (a < 0)
		a = -a;
	for (int i=1;i<=P;i++)
	{
		dt *= a;
		if (dt > LIMIT)
			return INF;
		t *= a;
	}
	return t;
}
 
void tq()
{
	int i,j;
	big t;
	MQ.initialize();
	MQ.insert(0,0,0);
	for (i=1;i<=N;i++)
	{
		B[i] = sumL[i] + i;
		A[i] = B[i] - 1 - L;
	}
	for (i=1;i<=N;i++)
	{
		j = MQ.getmin(A[i] + A[i]);
		t = power(sumL[i] - sumL[j] + i-j-1 - L);
		if ( double(t) + double(F[j]) <= LIMIT )
			F[i] = F[j] + t;
		else
			F[i] = INF;
		if ( double(B[i]) * double(B[i]) + F[i] <= LIMIT)
			t = F[i] + B[i] * B[i];
		else
			t = INF;
		MQ.insert(B[i],t,i);
		deci[i] = j;
	}
}
 
void simple()
{
	int i,j,k;
	big minv,t;
	k = -1;
	for (i=1;i<=N;++i)
	{
		minv = INF;
		for (j=i-1;j>=0;--j)
		{
			t = sumL[i] - sumL[j] + i-j-1 - L;
			if (t > L + L)
				break;
			t = power(t);
			if ( double(t) + double(F[j]) <= LIMIT && t + F[j] < minv)
			{
				minv = F[j] + t;
				k = j;
			}
		}
		F[i] = minv;
		deci[i] = k;
	}
}
 
void solve()
{
	if (P == 2)
		tq();
	else
		simple();
}
 
void print()
{
	if (F[N] <= LIMIT)
	{
		cout << F[N] << endl;
		int i,j;
		for (i=N,j=0;i;i=deci[i])
			sel[++j] = i;
		for (i=0;j;j--)
		{
			for (++i;i < sel[j];++i)
				printf("%s ",sent[i]);
			printf("%s\n",sent[i]);
		}
	}
	else
		printf("Too hard to arrange\n");
	printf("--------------------\n");
}
 
int main()
{
	int i,T;
	freopen("poet.in","r",stdin);
	freopen("poet.out","w",stdout);
	scanf("%d",&T);
	for (i=1;i<=T;i++)
	{
		init();
		solve();
		print();
	}
	return 0;
}

解法4 决策单调性优化动态规划

算法描述

可以观察到或证明出,该状态转移方程满足决策单调性。因此我们可以使用双端队列维护每个决策区间,对于每个新决策使用二分查找确定位置并更新决策队列。

算法证明

再次观察状态转移方程

clip_image034

clip_image036,状态转移方程可以化为1D/1D标准形式

clip_image038

要证明上述状态转移方程具有决策单调性,k(i)表示F[i]的最优决策,即

clip_image040

当且仅当满足四边形不等式

clip_image042

clip_image044clip_image046clip_image048。其中clip_image050

于是clip_image052。要证明①,只需证明

clip_image054

clip_image056clip_image058,则②等价于

clip_image060

clip_image062

因为clip_image064,且D[i+1]恒为正数,所以S<T。于是要证明③,只需证明下列函数在整数域内(非严格)单调递增

clip_image066

(1)若P为偶数

clip_image068,求导得clip_image070

因为clip_image072,P-1为奇数,所以clip_image074clip_image076恒成立,f(x)在实数域内单调递增。

(2)若P为奇数
(a)当X-C>=0

clip_image068[1],求导得clip_image070[1]

因为clip_image080,P-1为偶数,所以clip_image074[1]clip_image076[1]恒成立,f(x)在实数域内单调递增。

(b)当X<=0

clip_image084,求导得clip_image086。因为P-1为偶数,clip_image076[2]恒成立,f(x)在实数域内单调递增。

(c)当0<X<C

clip_image090,求导得clip_image086[1]。因为P-1为偶数,clip_image076[3]恒成立,f(x)在实数域内单调递增。

综上所述,f(x)在实数域内单调递增,即在正数域内单调递增,因而③②①依次得证。

因此状态转移方程clip_image006[1]具有决策单调性。

复杂度分析

状态数为O(N),每次维护决策队列的时间为O(logN),所以时间复杂度为O(NlogN)。在测试中通过了全部测试点,拿到了100分。

参考程序
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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
/* 
 * Problem: NOI2009 poet
 * Author: Guo Jiabao
 * Time: 2009.9.22 16:30
 * State: Solved
 * Memo: 动态规划 决策单调性
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
 
typedef long long big;
 
const int MAXN=100001,SMAXL=32;
const big LIMIT=1000000000000000000LL;
 
struct interval
{
	int s,t,deci;
}di[MAXN];
 
double F[MAXN];
int N,L,P,Stop;
int Len[MAXN],deci[MAXN],sel[MAXN];
char sent[MAXN][SMAXL];
big G[MAXN],sumL[MAXN];
 
void init()
{
	scanf("%d%d%d\n",&N,&L,&P);
	for (int i=1;i<=N;++i)
	{
		gets(sent[i]);
		Len[i] = strlen(sent[i]);
		sumL[i] = sumL[i-1] + Len[i];
	}
}
 
double dpower(double a)
{
	double t=1;
	if (a < 0)
		a = -a;
	for (int i=1;i<=P;i++)
		t *= a;
	return t;
}
 
double getF(int i,int j)
{
	double t = dpower(sumL[i] - sumL[j] + i-j-1 - L);
	return F[j] + t;
}
 
big power(big a)
{
	big t=1;
	double dt=1;
	if (a < 0)
		a = -a;
	for (int i=1;i<=P;i++)
	{
		dt *= a;
		if (dt > LIMIT)
			return LIMIT+1;
		t *= a;
	}
	return t;
}
 
big getG(int i,int j)
{
	big t = power(sumL[i] - sumL[j] + i-j-1 - L);
	if (F[j] + t <= LIMIT)
		return G[j] + t;
	else
		return LIMIT + 1;
}
 
void update(int i)
{
	while (di[Stop].s > i && getF(di[Stop].s,i) < getF(di[Stop].s,di[Stop].deci) )
	{
		di[Stop-1].t = di[Stop].t;
		Stop --;
	}
	int a=di[Stop].s,b=di[Stop].t,m;
	if (a < i+1)
		a = i+1;
	while (a+1<b)
	{
		m = (a + b) >> 1;
		if ( getF(m,di[Stop].deci) < getF(m,i) )
			a = m;
		else
			b = m-1;
	}
	if ( a < b && getF(b,di[Stop].deci) < getF(b,i) )
		a = b;
	if (a+1 <= di[Stop].t)
	{
		di[Stop + 1].s = a+1;
		di[Stop + 1].t = di[Stop].t;
		di[Stop + 1].deci = i;
		di[Stop].t = a;
		++Stop;
	}
}
 
void solve()
{
	int i,j;
	di[Stop=1].s = 1;
	di[Stop].t = N;
	for (i=j=1;i<=N;i++)
	{
		if (i > di[j].t)
			++j;
		deci[i] = di[j].deci;
		F[i] = getF(i,deci[i]);
		update(i);
	}
	for (i=1;i<=N;i++)
		G[i] = getG(i,deci[i]);
}
 
void print()
{
	if (G[N] <= LIMIT)
	{
		cout << G[N] << endl;
		int i,j;
		for (i=N,j=0;i;i=deci[i])
			sel[++j] = i;
		for (i=0;j;j--)
		{
			for (++i;i < sel[j];++i)
				printf("%s ",sent[i]);
			printf("%s\n",sent[i]);
		}
	}
	else
		printf("Too hard to arrange\n");
	printf("--------------------\n");
}
 
int main()
{
	int i,T;
	freopen("poet.in","r",stdin);
	freopen("poet.out","w",stdout);
	scanf("%d",&T);
	for (i=1;i<=T;i++)
	{
		init();
		solve();
		print();
	}
	return 0;
}

Maybe you like

标签:, , , ,


23 Responses to “NOI 2009 诗人小G”

  1. lccycc Says:
    Internet Explorer 7.0;Windows Vista

    太强悍了!

    [回复]

  2. lccycc Says:
    Internet Explorer 7.0;Windows Vista

    弱问为什么算法三O(n)的复杂度还过不了全部呢?

    [回复]

    BYVoid 回复:
    Firefox 3.5.8Windows 7

    算法三是針對第6,7個測試點的特殊算法,算法二可以過了前5個點

    [回复]

  3. wwy250 Says:
    Firefox 3.5.8Ubuntu

    弱问
    我知道若满足四边形不等式 一定有决策单调性
    但是满足决策单调性一定满足四边形不等式么?
    您文中说的是当切仅当

    [回复]

    BYVoid 回复:
    Firefox 3.6Windows 7

    是,參加楊哲論文

    [回复]

    wwy250 回复:
    Firefox 3.5.8Ubuntu

    我有看杨哲论文 没有发现有关于充分必要的结论或证明

    [回复]

    wwy250 回复:
    Firefox 3.5.8Ubuntu

    您能讲解一下么。。。 我自己怎么也推不出来

    [回复]

    BYVoid 回复:
    Firefox 3.6Windows 7

    2007 杨哲《凸完全单调性的一个加强与应用》 幻燈片第三頁的證明每一步都是充分必要的

    [回复]

    wwy250 回复:
    Firefox 3.5.8Ubuntu

    可是你用的这个性质在第四页。。。

    [回复]

  4. Orz Says:
    Internet Explorer 6.0Windows 2000

    神牛能把这题的数据发给我吗?感激不尽…

    [回复]

    Orz 回复:
    Internet Explorer 6.0Windows 2000

    2721401802qq.com

    [回复]

    BYVoid 回复:
    Firefox 3.5.9Ubuntu

    http://lmgtfy.com/?q=noi2009+%E6%95%B0%E6%8D%AE

    [回复]

    Orz 回复:
    Internet Explorer 6.0Windows 2000

    网上我找过了,就只有day1的另两题的数据,这题是没有的..

    [回复]

    BYVoid 回复:
    Firefox 3.5.9Ubuntu

    好好找找,这题数据50多MB,没办法发

    [回复]

  5. 哈凌大侠 Says:
    Internet Explorer 6.0Windows XP

    在研读大牛结题报告时,

    偶然发现貌似大牛的第四个程序过不了样例

    输出

    1358
    brysj,
    hhrhl. yqqlm, gsycl.
    ——————–

    我刚开始研究决策单调性,看不出程序的纰漏
    请帮助

    [回复]

    哈凌大侠 回复:
    Internet Explorer 6.0Windows XP

    是不是应该吧91、92行改成

    if (a < i)

    a = i;

    我觉得用a表示决策终点挺别扭的

    表示新决策起点挺顺的

    [回复]

  6. AndyBear Says:
    Firefox 3.6.3Ubuntu

    解法三里的这句话”每在队尾加入一个新的点,判断斜率是否递增,如果不是则不断删除队尾元素”,不理解为什么是要删除队尾元素,而不是不加入新点呢?

    [回复]

    BYVoid 回复:
    Google Chrome 5.0.342.9GNU/Linux

    刪除後再加入新點

    [回复]

    AndyBear 回复:
    Google Chrome 5.0.375.38GNU/Linux

    我的意思是说,可不可以不加入新点呢?这样的话不就不会破坏单调性了。。或者说,新点一定是都要加入吗?

    [回复]

    BYVoid 回复:
    Google Chrome 5.0.342.9GNU/Linux

    當然新點都是一定要加入的,你可以想想,即使以後可能被再刪除。

    [回复]

    AndyBear 回复:
    Google Chrome 5.0.375.38GNU/Linux

    恩。。多谢咯~

    [回复]

  7. 哈凌大侠 Says:
    Internet Explorer 6.0Windows XP

    大牛,您不能无视新手啊

    麻烦指点着一下,应该是那样改的吧?

    [回复]

  8. zm110 Says:
    Firefox 3.6.4Windows XP

    能把checker程序发给我吗?

    [回复]

Leave a Reply

38 queries. 0.796 seconds. Designed by NattyWP .
Images by desEXign.