Zth's Blog

记录学习路上的点滴

0%

第13届蓝桥杯省赛软件类CA

发表于 更新于 分类于

烂桥杯

试题C：求和

思路

设$sum_i = \sum_i^n a_i$

$O(n)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <cstdio>

int n;
long long a[200005], s;
long long ans;

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++)
		scanf("%lld", &a[i]), s += a[i];
		
	for(int i = 1; i <= n; i ++)
	{
		s -= a[i];
		
		ans += s * a[i];
	}
	
	printf("%lld", ans);
	
	return 0;
}

试题 D: 选数异或

思路

每遇到最近的$i, j, a_{i} \oplus a_j = x$， 我们就记录一个区间$[i, j]$， 记录的区间之间没有完全包含关系， 因为如果有， 那大的区间是没有用的， 查询$[l, r]$的时候就看一下$[l, r]$内有没有我们记录的区间就可以了

$O(mlogn)$

代码

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
#include <iostream>
#include <cstdio>
#include <algorithm>

int n, m, x;
int a[100005];
int pos[1100006];
int l[100005], r[100005], cnt;

int main()
{
	scanf("%d%d%d", &n, &m, &x);
	for(int i = 1; i <= n; i ++)
	{
		scanf("%d", &a[i]);
		
		int tmp = a[i] ^ x;
		
		if(pos[tmp])
		{
			if(pos[tmp] > l[cnt])
			{
				cnt ++;
				
				l[cnt] = pos[tmp];
				
				r[cnt] = i;
			}
		}
		
		pos[a[i]] = i;
	}
	
	for(int i = 1; i <= m; i ++)
	{
		int ql, qr;
		scanf("%d%d", &ql, &qr);
		
		int p = std:: lower_bound(l + 1, l + cnt + 1, ql) - l;
		
		if(l[p] >= ql && r[p] <= qr)
			printf("yes");
		else
			printf("no");
			
		if(i != m) printf("\n");
	}
	
	return 0;
}

试题 E: 爬树的甲壳虫

思路

设$dp_i$为爬到$i$层的期望步数， 当从$i - 1$层爬到$i$层时， 成功爬上的概率为$1 - P_i$， 那么我们期望的爬取次数就是$\frac{1}{1 - P_i}$

再加上个求逆元就好了

$O(n)$

代码

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
#include <iostream>
#include <cstdio>

const long long mod = 998244353;

int n;
long long ans[100005];

long long Qpow(long long a, long long b)
{
	long long res = 1;
	
	for( ; b; b >>= 1, a = a * a % mod)
		if(b & 1)
			res = res * a % mod;
			
	return res;		
}

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++)
	{
		long long x, y;
		scanf("%lld%lld", &x, &y);
		
		long long tmp = Qpow(y - x, mod - 2);
		long long tms = y * tmp % mod;
		
		ans[i] = tms * (ans[i - 1] + 1) % mod;
	}
	
	printf("%lld", ans[n]);
	
	return 0;
}

试题 F: 青蛙过河

思路

这是我赛时自己瞎想的贪心， 大家都用的dp， 我这个应该不对， dp思路还是比较显然的

二分+贪心

检查答案为$res$时， 找到连续$res$的子段最小和， 和$x \times 2$比一下

$O(nlogn)$

代码

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
#include <iostream>
#include <cstdio>
#include <cstring>

int n, x;
int h[100005], s[100005];

bool Check(int a)
{
	if(a == n) return true;
	
	int mn = 1e9 + 1;
	 
	for(int i = a; i < n; i ++) mn = std:: min(mn, s[i] - s[i - a]);
	 
	if(mn >= x)
		return true;
	else
		return false;
}

int Binary_Search(int l, int r)
{
	while(l < r)
	{
		int mid = (l + r) >> 1;
		
		if(Check(mid))
			r = mid;
		else
			l = mid + 1;
	}
	
	return l;
}

int main()
{
	scanf("%d%d", &n, &x);
	for(int i = 1; i < n; i ++)
		scanf("%d", &h[i]), s[i] = s[i - 1] + h[i];
		
	x *= 2;
	
	printf("%d", Binary_Search(1, n));
	
	return 0;
}

试题 G: 最长不下降子序列

思路

$1 \leq A_i \leq 10^6$， 观察到这个就好做了

我们求出$up_i$表示以$i$位置结尾的最长不降子序列， $down_i$表示以$i$位置为开头的最长不降子序列

那我们顺序枚举$i$， 对于每个$up_i$， 找一个最大的$down_j$， 满足$j > i + k, A_j >= A_i$， $i$的答案就是$up_i + down_j + k$

找$down_j$时使用线段树维护(可能T， 树状数组好一点)

$O(nlogn)$

代码

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
#include <iostream>
#include <cstdio>
#include <vector> 
#include <algorithm>

#define root 1, n, 1
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1

int n, k;
int a[100005];
int up[100005], down[100005];
int res1[100005], cnt1, res2[100005], cnt2;
int mx[4000006];
int ans;

struct ST
{
	void Update(int rt)
	{
		mx[rt] = std:: max(mx[rt << 1], mx[rt << 1 | 1]);
	}
	
	void Modify(int l, int r, int rt, int p, int v)
	{
		if(l == r)
		{
			mx[rt] = std:: max(mx[rt], v);
			
			return;
		}
		
		int mid = (l + r) >> 1;
		
		if(p <= mid)
			Modify(lson, p, v);
		else
			Modify(rson, p, v);
			
		Update(rt);	
	}
	
	int Query(int l, int r, int rt, int ql, int qr)
	{
		if(l >= ql && r <= qr) return mx[rt];
		
		int mid = (l + r) >> 1;
		
		if(qr <= mid)
			return Query(lson, ql, qr);
		else if(ql > mid)
			return Query(rson, ql, qr);
		else
			return std:: max(Query(lson, ql, qr), Query(rson, ql, qr));
	}
};

void Up()
{
	for(int i = 1; i <= n; i ++)
	{
		if(! cnt1)
		{
			res1[++ cnt1] = a[i];
			up[i] = i;
			
			continue;
		}
		
		int p = std:: upper_bound(res1 + 1, res1 + cnt1 + 1, a[i]) - res1;
		up[i] = p;
		
		res1[p] = a[i];
		cnt1 = std:: max(p, cnt1);
	}
}

void Down()
{
	std:: reverse(a + 1, a + n + 1);
	for(int i = 1; i <= n; i ++) a[i] = -a[i];
	
	for(int i = 1; i <= n; i ++)
	{
		if(! cnt2)
		{
			res2[++ cnt2] = a[i];
			down[i] = 1;
			
			continue;
		}
		
		int p = std:: upper_bound(res2 + 1, res2 + cnt2 + 1, a[i]) - res2;
		down[i] = p;
		
		res2[p] = a[i];
		cnt2 = std:: max(p, cnt2);
	}
	
	for(int i = 1; i <= n; i ++) a[i] = -a[i];
	
	std:: reverse(a + 1, a + n + 1);
	std:: reverse(down + 1, down + n + 1);
}

void Solve()
{				
	ST st;			
	
	for(int i = n - 1 - k; i >= 1; i --)
	{
		st.Modify(root, a[i + k + 1], down[i + k + 1]);
		
		ans = std:: max(ans, k + up[i] + st.Query(root, a[i], 1e6));
	}
}

int main()
{
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
	
	if(k == n)
	{
		printf("%d", n);
		
		return 0;
	}
	
	Up();
	Down();
	
	Solve();
	
	printf("%d", ans); 
	
	return 0;
}

剩下的题

剩下的就没做了， 等什么时候民间OJ有了补完再上题解

Update1

青蛙那题dp思路显然， 但是是错误的， 因为dp计算的其实是方案数， 不是实际可以跳的次数， 我的贪心是正确的

G题我写的应该是有问题应该是#define root 1 1000000 1， 原来那样会RE

前四个应该是全对了的