Burnling's Blog
0%

220529 总结

发表于 更新于

预计：$100+100+40$

自测：$50+40+30$

一个小时写完了前两题，剩的两小时里面用半小时写了个深搜，剩下的时间一直在调T3（

怎么全是极端数据

少开 long long 多 #define int long long

挂大分

T1 小麦亩产一千八

斐波那契数列题

每个格子的小麦数序列为 ${1,x,x+1,2x+1,3x+2,\dots}$

预处理出斐波那契数列前 $30$ 项，计算出 $x$ 的值后计算结果即可

注意到 $1\leq p \leq 10^6$ ，要开 $\text{long long}$

嗯然后我读入 $x$ 的时候没开 $\text{long long}$ 白挂 $50$ 分

T2 休息

考的时候直接上的模拟

因为我写的是扫一遍能把所有的区间都翻转一遍觉得足够了就没去写优化

又因为后六个点全是极端数据所以后六个点一个没过

但显然还是不够

第一次翻转之后，由于翻转后是若干段断开的单调区间，所以再翻转仅能在两个区间的交界处发生

我虽然发现了这一性质，但是我不知道该怎么用（

看了学姐博客，发现可以利用这一性质通过求逆序对来快速求解（毕竟每次翻转只会翻转若干个长度为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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>
using namespace std;

#define FO(name) freopen(name".in","r",stdin);freopen(name".out","w",stdout)

const int maxN = 4e5;

int N;
int books[maxN];

int T[maxN];
long long cnt;

void merge(int l,int r){
	int mid = (l + r) >> 1;
	int p1 = l;
	int p2 = mid+1;
	int p = l;
	while(p1 <= mid && p2 <= r){
		if(books[p1] < books[p2]){
			T[p++] = books[p1++];
		}else{
			T[p++] = books[p2++];
			cnt += mid - p1 + 1;
		}
	}
	while(p1 <= mid) T[p++] = books[p1++];
	while(p2 <= r) T[p++] = books[p2++];
	for(int i = l;i<=r;i++) books[i] = T[i];
}

void mergeSort(int l,int r){
	if(l == r) return;
	int mid = (l + r) >> 1;
	mergeSort(l,mid);
	mergeSort(mid+1,r);
	merge(l,r);
}

int main() {
	FO("rest");
	scanf("%d",&N);
	for(int i = 1; i<=N; i++) {
		scanf("%d",&books[i]);
	}
	books[N+1] = 1e9;

	int st = 1;
	int ed = 1;
	for(int i = 2; i<=N+1; i++) {
		if(books[i] < books[ed]){
			ed = i;
		}else{
			if(st != ed) cnt++;
			int len = (ed - st + 1) >> 1;
			for(int j = 1;j<=len;j++){
				swap(books[st+j-1],books[ed-j+1]);
			}
			ed = st = i;
		}
	}
	mergeSort(1,N);
	printf("%lld\n",cnt);
	return 0;
}

T3 军训

考场上用的 DFS ，但由于 $1 \leq N \leq 20000 $ ，在 $n \gt 10000$ 会由于递归层数太多而爆栈

（不过在 $1 \leq N \leq 10000$ 算法应该是正确的）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//非常朴素的dfs写法，仅能过 40% 的数据
//dfs(学号，女友指数最高的班级的女友指数，这个班级女友值，这个班级欠扁值，所有班级欠扁值总和)
void dfs(int k,int maxny,int sumny,int qbz,int sumqb){
	if(k > N){
		if(sumqb > LIMIT) return;
		ans = min(ans,maxny);
		return;
	}
	if(sumny >= ans) return;
	if(sumqb > LIMIT) return;

	//新开班，第k个学生在新班 
	dfs(k+1,max(maxny,gf[k]),gf[k],qb[k],sumqb+qb[k]);
	
	//插入旧班，第k个学生在旧班
	dfs(k+1,max(maxny,sumny+gf[k]),sumny+gf[k],max(qbz,qb[k]),sumqb-qbz+max(qbz,qb[k])); 
}

后来想把 $20000$ 拆成两半分别递归后再合并结果但是没写明白（