Don't let your dreams be dreams.

WELCOME——一只蒟蒻的幻想

| 题解, HAOI, BZOJ

教练，我要刷水题

听说HAOI有洪水，像我这种蒟蒻最喜欢了，于是最近就开始刷HAOI了。。。

BZOJ1044 木棍分割

点这里去虐题

妈的用MarkDown贴题面真TM蛋碎
据说支持内嵌html然后我把html贴上去之前的内容就华丽丽地消失了(:з」∠)
或者说是我这个编辑器的锅吗，我还是选择稳妥的不贴题面了
好,停止吐槽

说起来这道题原来是我给初三讲课里面的题目
原来一直懒得去做，现在趁着刷水一起做了

对于第一问，感觉应该可以算是很经典的问题了，二分长度，然后贪心验证就好了
然后对于第二问，我们可以很容易地想到一个O(NM)复杂的Dp，用f[i][j]表示前j个木棍分成i段的方案数，然后就可以得到 $$f[i][j]=\sum^{k<j}_{k=0} f[i-1][k] (sum[j]-sum[k]<=len)$$ 我们可以显然的发现，这个是会华丽丽地T掉的。但是我们可以发现对与递增的j，k的位置也是递增的，所以我们可以使用队列优化DP。
然后因为空间问题，还要对第一维滚存
不过具体的复杂度我并不会证，可能还是不对的。但是至少还是过去了。。(:з」∠)
今天晚上听见初三爷在纠结滚存怎么滚，感觉我的作业是不是太凶残了

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
#include <cstdio>
#include <cstring>
#include <algorithm>
const int mod = 10007;
const int N = 500010;
using namespace std;
int a[N],f[2][N],sum[N],q[N],tot,n,ans2,m;
int read(){
	int x = 0,f = 1,c = getchar();
	while (c<'0' || c>'9') {if (c=='-') f = -1;c = getchar();}
	while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
	return x*f;
}
int Judge(int x){
	int res = 0,s = 0;
	for (int i=1;i<=n;i++) {s+=a[i];if (s>x) {res++;s = a[i];}if (res>m) return 0;if (a[i]>x) return 0;}
	return 1;
}
int main(){
	n = read();m = read();
	for (int i=1;i<=n;i++) {a[i] = read();sum[i] = sum[i-1]+a[i];}
	int l = 0,r = sum[n],Ans = 0;
	while (l<=r) {
		int mid = (l+r)>>1;
		if (Judge(mid)) {Ans = mid;r = mid-1;}
		else l = mid+1;
	}
	printf("%d ",Ans);
	f[0][0] = 1;
	for (int i=1;i<=m;i++) {
		int pre = i&1,cur = pre^1;
		int l = 1,r = 1;q[1] = 0;tot = f[cur][0];
		for (int j=1;j<=n;j++) {
			while (l<=r && sum[j]-sum[q[l]]>Ans) tot = (tot-f[cur][q[l++]]+mod)%mod;
			f[pre][j] = tot;q[++r] = j;
			tot = (tot+f[cur][j])%mod;
		}
		for (int j=n-1;j;j--) {
			if (sum[n]-sum[j]>Ans) break;
			ans2 = (ans2+f[pre][j])%mod;
		}
		memset(f[cur],0,sizeof(f[cur]));
	}
	printf("%d\n",ans2);
}

BZOJ1043 下落的圆盘

点击这里去虐题

一道计算几何的题目
上次做计算几何是什么时候来着(:з」∠)应该已经是好几个月以前的事情了吧。。
我们观察数据范围可以知道

这是一个很裸很裸的暴力

因为n只有1000所以直接$N^2$，对每一个圆盘暴力枚举每一个在它上方的圆盘，然后求出被遮盖的弧长
2016031_1.png
对于两个相交的圆，我们可以知道他们的半径和圆心之间的距离。然后就可以很轻易的使用反三角函数求出图中的$\angle EAC$。然后再求出直线$AC$的极角，就可以表示出被遮盖的位置。因为这样求出来的弧度可能是负数，所以需要把它转换到$[0,2\pi]$的范围内。然后就简单地统计一下就好了。
复杂度: $O(N^2)$

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
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
const int N = 1010;
using namespace std;
double r[N],x[N],y[N],ans,pi;
int n,top;
struct Line {double l,r;} q[N];
bool cmp(Line a,Line b){return a.l<b.l;}
double dis(int a,int b){return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));}
int Cover(int a,int b) {if (r[a]>=r[b]+dis(a,b)) return 1;return 0;}
void Work(int a,int b){
	double d = dis(a,b);
	double t = (r[a]*r[a]-r[b]*r[b]+d*d)/(2*d);
	double st = atan2((x[a]-x[b]),(y[a]-y[b]));
	double l = acos(t/r[a]);
	q[++top] = (Line){st-l,st+l};
}
double calc(int x){
	for (int i=x+1;i<=n;i++) if (Cover(i,x)) return 0;
	top = 0;double tmp = 0,now = 0;
	for (int i=x+1;i<=n;i++)
		if (!Cover(x,i) && r[i]+r[x]>dis(i,x)) Work(x,i);
	for (int i=1;i<=top;i++) {
		if (q[i].l<0) q[i].l+=2*pi;
		if (q[i].r<0) q[i].r+=2*pi;
		if (q[i].l>q[i].r) {q[++top] = (Line){0,q[i].r};q[i].r = 2*pi;}
	}
	sort(q+1,q+1+top,cmp);
	for (int i=1;i<=top;i++) 
		if (q[i].l>now) {
			tmp+=q[i].l-now;
			now = q[i].r;
		}
		else now = max(now,q[i].r);
	tmp+=2*pi-now;
	return r[x]*tmp;
}
int main(){
	scanf("%d",&n);pi = acos(-1);
	for (int i=1;i<=n;i++) scanf("%lf%lf%lf",&r[i],&x[i],&y[i]);
	for (int i=1;i<=n;i++) ans+=calc(i);
	printf("%.3lf\n",ans);
}

BZOJ1049 数字序列

点击这里去虐题

感觉有点厉害的一道题，诶其实只是我弱(:з」∠)
对于第一问，要求最小化改变的数量，可以转化成最大化不变的数量。然后我们考虑对与这个进行DP，设f[i]表示i位置不变的最大不变数量，然后可以得到一个的DP方程$$f[i] = Max f[j]+1 (a[i]-a[j]>=i-j)$$后面的限制条件是因为要满足递增。
然后我们将a[i]-a[j]>=i-j移项得到a[i]-i>=a[j]-j可以发现原问题就转化为了对a[i]-i数组求最长不下降子序列。直接写一个$O(N\log_2N)$的模板上去就好了

然后对与第二问。。
在满足第一问的前提下的最小改变量，考虑那一些位置可以转移到i，然后就会得到一个DP方程$$g[i] = Min g[j]+w[i][j] (f[j]+1=f[i]) $$其中w[i][j]表示把i到j这一段改成符合条件的最小代价。
然后对此有一个性质，w[i][j]的方案一定会以某一个k分界，使得[j,k]之间的均为b[j],[k+1,i]之间的均为b[i]，证明嘛。。。

我不会！别问我！！

还是直接贴神犇的证明吧
20150315_2.png

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
#include <cstdio>
#include <cstring>
#include <algorithm>
const int N = 40000;
using namespace std;
long long g[N],s1[N],s2[N];
int f[N],Min[N],head[N],a[N],n,cnt,L;
int read(){
	int x = 0,f = 1,c = getchar();
	while (c<'0' || c>'9') {if (c=='-') f = -1;c = getchar();}
	while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
	return x*f;
}
struct data{int x,y,next;} e[N];
void Insert(int x,int y){
	e[++cnt].x = x;e[cnt].y = y;
	e[cnt].next = head[x];head[x] = cnt;
}
int find(int x){
	int l = 1,r = L,res = 0;
	while (l<=r) {
		int mid = (l+r)>>1;
		if (Min[mid]<=x) {res = mid;l = mid+1;}
		else r = mid-1;
	}
	return res;
}
void solve1(){
	memset(Min,127,sizeof(Min)); Min[0] = -1<<30;
	for (int i=1;i<=n;i++) {
		int t = find(a[i]);
		f[i] = t+1; L = max(t+1,L);
		Min[t+1] = min(Min[t+1],a[i]);
	}
}
void solve2() {
	for (int i=n;i>=0;i--) {Insert(f[i],i);g[i] = 1ll<<60;}
	g[0] = 0;a[0] = -1<<30;
	for (int x=1;x<=n;x++)
		for (int i=head[f[x]-1];i;i=e[i].next){
			int p = e[i].y;
			if (p>x) break;
			if (a[p]>a[x]) continue;
			for (int j=p;j<=x;j++) s1[j] = abs(a[p]-a[j]),s2[j] = abs(a[j]-a[x]);
			for (int j=p+1;j<=x;j++) s1[j]+=s1[j-1],s2[j]+=s2[j-1];
			for (int j=p;j<x;j++) g[x] = min(g[x],g[p]+s1[j]+s2[x]-s2[j]-s1[p]);
		}
}
int main(){
	n = read();
	for (int i=1;i<=n;i++) a[i] = read()-i;
	a[++n] = 1<<30;
	solve1();
	solve2();
	printf("%d\n%lld\n",n-f[n],g[n]);
}

有错误请指出$$\mathcal {FIN}$$