清北学堂寒假提高储备营Day3题解

发表于 | 更新于 | 评论数： | 阅读次数：

半年OI一场空，CE文件见祖宗。

A

分析

题面不在描述。

我们手推几组小数据可以得出，

$$f(1)=1$$
$$f(2)=7$$
$$f(3)=13$$
。。。。。。

因为直角三角形一定是要拼成正方形的，所以我们可以近似的看成有4种砖。

1、$1 \times 1$的方砖。
2、$2 \times 2$的方砖，没有对角线。
3、$2 \times 2$的方砖，有一条从左上到右下的对角线。
4、$2 \times 2$的方砖，有一条从右上到左下的对角线。

我们考虑在一个矩阵上的划分：
kQ7jL6.png

显然，我们最后一列只能选择全部使用$1 \times 1$的方砖。

所以，当我们在最后一列选择全部使用$1 \times 1$的方砖时，有$f[n-1]$种情况。

当我们可以选择最后两列时，就有6种情况了。

所以，当我们在最后两列选择时，有$f[n-2] \times 6$种情况。

那么我们就可以得到递推式：

$$f_i = f_{i-1}+f_{i-2} \times 6$$.

直接$O(n)$过一遍就行了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* Headers */
#include<cstdio>
#include<cstdlib>
#include<cstring>
/* definitions */
const int mod=1e9+7;
int n,f[100];
int main(int argc,char *argv[]){
	scanf("%d",&n);
	f[0]=1;f[1]=1;
	for(int i=2;i<=n;i++)f[i]=(f[i-1]+6ll *f[i-2])%mod;
	printf("%d\n",f[n]);
	return 0;
}

B

题面同样不再描述。

我们首先考虑一个最暴力的算法。

首先把读入的数据排序，然后用三重循环判断是否能构成三角形，最后输出面积和。

附一下核心代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
inline void work(){
    std::sort(num+1,num+n+1);
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			for(int k=j+1;k<=n;k++){
				if(test(i,j,k)){
					cnt++;
					sum=(sum+sec(i,j,k));
				}
			}
		}
	}
}

时间复杂度显然为$O(n^3)$，可以得到$ 50pts $的好成绩。

然后我们考虑一下优化：显然答案满足二分性质。

首先依旧对于输入数据排序。

然后我们枚举两重循环，接着二分查找能够构成三角形的最大数（临界值）。

查找时统计答案，并且计算面积。

时间复杂度$O(n^2 \log n)$，可以得到$70pts$的好成绩。

由于二分查找比较简单，这里就不附代码了（雾

继续优化：

这里就要用到单调队列的思想了。

我们在枚举前两个值的时候（设它们分别为$a,b$），可以发现，对于每一组$a,b$，都有其对应的临界值$c$（也就是能够构成三角形的最大数）。

那我们就可以暴力移动临界值$c$，完成确定临界值时间复杂度$O(1)$的算法。

把排好序的输入数据想成一个数轴。

也就是说，在枚举过程中，对于当前的$a,b$，有其对应的临界值，当枚举到$a,b+1$时，相对应的$c$也向右移动。

那么我们就可以暴力移动模拟这个过程，用$O(1)$的时间复杂度解决。

求面积的时候就要用到前缀和的思想了。

我们把求面积公式（海伦公式）拆开，得到一个多项式，然后就直接用前缀和解决其可。

代码（由于Herself32本人太菜了，这里直接附上zhx大爷的std,经过魔改）

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
/* Headers */
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
/* definitions */
const int maxn = 5010;
const int mod = 1000000007; 
int n,z[maxn],sum2[maxn],sum4[maxn];
/* functions */
int calc(int l,int r,int a,int b){
	int ans=0;
	ans = 2ll *a*a*b*b*(r-l)%mod;
	ans = (ans + 2ll * (a*a+b*b) * (sum2[r]-sum2[l]+mo)) %mod;
	ans = (ans - 1ll *a*a*a*a*(r-l) - 1ll*b*b*b*b*(r-l) - sum4[r]+sum4[l])%mod;
	ans = (ans+mo)%mod;
	return ans;
}
int main(int argc,char *argv[]){
	scanf("%d",&n);
	for(int a=1;a<=n;a++)scanf("%d",&z[a]);
	std::sort(z+1,z+n+1);
	for (int a=1;a<=n;a++){
		sum4[a] = (1ll*z[a]*z[a]*z[a]*z[a]+sum4[a-1])%mod;
		sum2[a] = (1ll*z[a]*z[a]+sum2[a-1])%mod;
	}
	int cnt=0,ans=0;
	for (int a=1;a<=n-2;a++){
		int p=a+2;
		for (int b=a+1;b<=n-1;b++){
			while (p<=n && z[p]<z[a]+z[b])p++;
			p--;
			cnt+=p-b;
			ans+=calc(b,p,z[a],z[b]);
			if (ans>=mod) ans-=mod;
		}
	}
	printf("%d %d\n",cnt,ans);
	return 0;
}

C

分析

直接暴力模拟即可。

我们开一个数组直接模拟球位，然后直接把题目中的左右调换，这样更便于操作。

然后观察题意，我们发现，如果激发一个球之后，它将从数组第一个位置消失（弹出），而如果生成球，就要从后面加入数组。

这不就是一个队列嘛！

但是我们这里并不需要循环队列，直接用head指针操作即可。

再提醒大家几个小小细节：

当球位不够时不能直接添加，而是要激发队首的几个球。
被动和技能不一样，触发被动并不会使球消失。
在生成球的时候，如果球位不够，则激发队首球1次

好了，那么70+行代码也就写出来了。

这里还是直接附上zhx神仙的std（Herself32没来得及重写，TA菜爆了）

代码

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
/* Headers */
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>

/* definitions */
const int maxn = 500010;
const int mo = 1000000007;
int n,s;
int damage,block;
int energe[maxn];
char q[maxn],str[10];
int front=1,tail=1,size=3;

/* functions */
void activate(int p,int x){
	if (q[p] == 'e') damage = (damage + 1ll*max(8+s,0)*x)%mo;
	else if (q[p] == 'i') block = (block + 1ll*max(5+s,0)*x)%mo;
	else if (q[p] == 'd') damage = (damage + 1ll*energe[p]*x)%mo;
	else front--;
	front++;
}

void use(int p,int x){
	if (q[p] == 'e') damage = (damage + 1ll*max(3+s,0)*x)%mo;
	else if (q[p] == 'i') block = (block + 1ll*max(2+s,0)*x)%mo;
	else if (q[p] == 'd') energe[p] = (energe[p] + 1ll*max(s+6,0)*x)%mo;
	else ;
}

int main(int argc,char *argv[]){
	scanf("%d",&n);
	q[1]='e';
	for (int a=1;a<=n;a++){
		int opt;
		scanf("%d",&opt);
		if (opt==1){
			scanf("%s",str+1);
			int l=strlen(str+1);
			for (int b=1;b<=l;b++){
				q[++tail] = str[b];
				if (str[b] == 'd') energe[tail]=6;
			}
			while (tail-front+1>size)activate(front,1);
		}
		if (opt==2){
			int x;
			scanf("%d",&x);
			activate(front,x);
		}
		if (opt==3){
			int i,x;
			scanf("%d%d",&i,&x);
			use(front+i-1,x);
		}
		if (opt==4){
			int x;
			scanf("%d",&x);
			s+=x;
		}
		if (opt==5){
			int x;
			scanf("%d",&x);
			size+=x;
		}
	}
	printf("%d %d\n",damage,block);
	return 0;
}

后记

最后附一下重新评测的题目地址：

A题：HPOJ1030
B题：HPOJ1031
C题：HPOJ1032

祝大家AK愉快！

THE END