【清北学堂国庆刷题班】 Day5

T1 blocks

Description

小明是一个积木爱好者，这一天，小明堆了一堆高度连续递减的积木，假设第i个位置的积木高度为d**idi， 热爱思考的小明在想，如果每天在第i堆的积木上多加i个，即每天第i堆的积木高度加i，最短多少天能够出现两堆积木高度相等呢？

小明试了很久也没有达到出现两堆积木高度相等的那天，于是他想找你帮忙计算一下。

Input

第一行一个数n，n堆积木的原始高度

接下来一行，n个数，第i个数d**idi，表示第i堆积木的高度

Output

一个数，即两堆积木相等至少需要的天数

Sample Input1

1
2
5
37 29 24 17 9

Sample Output1

1
5

Sample Input2

1
2
20
569 546 511 472 443 419 388 363 324 286 258 230 209 187 154 129 100 74 53 28

Sample Output2

1
21

Data

40 %, n ≤ 100，di≤10000d_i\le 10000

70 %, n ≤ 5000，di≤109d_i\le 10^9

100 %, n ≤ 100000，di≤109d_i\le 10^9

思路

这道题目我开始的思路就是：

因为这个高度是递减的，所以我想到了一个解方程的方法，计算每一个和每一个之间的差距，然后计算计算出来方程的最小值，这样就可以出来答案了：

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#define re register
using namespace std;
const double ex=0.00001;
double n;
long double d[100005];
long double ans=999999.0;
int main()
{
//	freopen("data.in","r",stdin);
//	freopen("blocks.out","w",stdout);
	cin>>n;
	for(re int i=1;i<=n;++i)
	scanf("%llf",&d[i]);
	for(re int i=1;i<=n;++i)
	{
		for(re int j=i;j<=n;j++)
		{
			if(abs(d[i]-d[j])/abs(i-j)-ans<=ex)
			ans=abs(d[i]-d[j])/abs(i-j);
		}
	}
	cout<<(int)ans<<endl;
	//fclose(stdin);
//	fclose(stdout); 
	return 0;
}

所以我们怎么样才能拿到满分呢？

我们观察，第n堆积木总是比n-1堆积木小，而且他们每天增加的高度相差1，并且我们可以很简单的推理得到，若果有两堆积木相等，一定是相邻的两个，所以我们计算出来原数列每两个元素的差值绝对值，直接枚举最小值即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
int n;
int d[100005];
int minn=999999;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>d[i];
		if(i!=1)
		minn=min(minn,d[i-1]-d[i]);
	}
	cout<<minn<<endl;
	return 0;
}

T2 sort

Description

小明现在手上有一个长度为n（n 为偶数）的序列，序列的值互不相等，但小明觉得一个无序的序列怎也么不好看，于是他想对这个序列进行排序。

小明是一个懒且随便的人，所以对于这个序列的排序，小明觉得其实差不多就行了， 也就是说，如果前 n2\frac n 2 个元素里的最大值小于等于后 n2\frac n 2个元素里的最小值，那么小明就觉得这是一个"有序"的序列。

对于每次交换，选择两个不同的序号 i 和 j 并交换aia_i与 aja_j，每次操作的代价是|i−j|。 现在小明想知道对于给定序列转换为一个“有序“的序列所需的最小代价。

Input

第一行一个整数n（n为偶数），表示序列的长度

接下来一行n个数，描述小明的序列

Output

一个数，即转化为小明认为的有序需要的最小代价

Sample Input

1
2
10
39 49 8 16 31 12 22 40 53 58

Sample Output

1
10

Data

40 %, n ≤ 10

80 %, n ≤ 100000

100 %, n ≤ 500000，ai≤109a_i\le 10^9

思路

我：模拟，把序列分为两部分，然后分段进行枚举,找出每一段的最大值和最小值，然后模拟交换过程，将他们两个的差的绝对值加入答案中，可以得四十分

40分代码

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#define ll long long
#define re register
using namespace std;
ll n;
ll a[500005];
ll ans;
ll maxn,x,minn,y;
int main(){
	cin>>n;
	for(re int i=1;i<=n;++i){
		cin>>a[i];
	}
	while(1)
	{
		maxn=-999999,minn=999999;
		for(re int i=1;i<=n/2;++i){
			if(a[i]>=maxn)
			maxn=a[i],x=i;
		}
		for(re int i=n/2+1;i<=n;++i){
			if(a[i]<minn)
			minn=a[i],y=i;
		}
		if(maxn<=minn) break;
		ans+=abs(x-y);
		swap(a[x],a[y]);
	}
	cout<<ans<<endl;
	return 0;
}

只有四十分的指数级别大爆搜当然不符合我的形象，尽管我只写出来了这个代码，但是我肯定要努力加油理解题解啊，所以80分的做法可以想一想：

我们可以把一个序列分成两部分，然后再开一个，对这个序列排一个序，对于前一半，只要交换比有序序列中点大的，对于后一半，只要交换比有序序列中点小的即可

现在我们做出来了八十分的做法，所以一百分的做法怎么做呢，襄阳五中的校训是“文明振奋求实创新”，我们要具有创新思维。然而在这里创新思维并没有什么用处，因为100%的解法来源于八十分的解法，只要把int改成long long就好了

代码

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
#include <bits/stdc++.h>
using namespace std;
struct Node {
	int val,id;
}a[1001000];
int n;
bool cmp(Node x,Node y){return x.val < y.val;}
int main()
{
	//freopen("sort.in","r",stdin); freopen("sort.out","w",stdout);
	cin >> n;
	for (int i = 1;i <= n;i++)
		{
			scanf("%d",&a[i].val);//读入
			a[i].id = i;
		}
	sort (a + 1,a + n + 1,cmp);//对于整个序列进行排序
	int mid = n / 2;
	long long ans = 0;
	for (int i = 1;i <= mid;i++)
		if (a[i].id > mid)//如果在原数列中在中点右边，所以所有的都要比左边大，要交换的就是排序过的数列的左半边中存在的原数列的中点右边的数
			ans += a[i].id;
	for (int i = mid + 1;i <= n;i++)//同理
		if (a[i].id <= mid)
			ans -= a[i].id;
	cout<<ans<<endl;
	return 0;
}

T3 string

Description

李华给了小明一堆字符串,所有字符串由’a’到’z’组成，小明还是觉得一堆串太乱了，为了美观，小明决定给所有串分个类。

具体地，小明现在有了n个字符串，想要划分到nk\frac n k个集合中，每个集合共k个字符串，为了使每个集合尽可能整齐，小明定义一个集合的美观度为该集合中所有字符串公共前缀的长度，

即假设集合为"noipac,noipak,noipcspak"，可知他们有公共前缀"noip"，即集合的美观度为4，

现在，小明想知道对于划分后的nk\frac n k个集合，美观度之和最大是多少。

Input

第一行两个正整数n,k,分别表示字符串总数和每个集合的字符串数量

接下来n行，每行一个字符串

Output

一个数，即美观度之和最大是多少

Sample Input

1
2
3
4
5
6
7
6 2
noipac
noipak
noipcspac
cspac
cspak
noipcspak

Sample Output

1
17

Data

40 %, n ≤ 10,k ≤ 5,每个字符串长度 ≤ 100

70 %, n ≤ 10000,K ≤ n,每个字符串长度 ≤ 100

100 %, n ≤ 100000,K ≤ n,每个字符串长度 ≤ 100000,字符串总长度不超过2∗1062*10^6k整除n

思路

20%:

直接暴力枚举每个集合中公共前缀，然后加起来，指数级别大爆搜

60%:

在无序的情况下思考比较困难，由于问题与顺序无关，不妨从考虑从有序的角度思考。
排序后，发现前缀存在一个性质，即i和i + 2的公共前缀长度 = min(i和i + 1的公共前缀，
i+1和i+2的公共前缀),也就意味着，假设现在剩余n串，将n个串排序后看做一个环形，其中包含第1个串的集合，为环形上连续的一块，采用区间动态规划处理。
f[i][j]f[i][j]表示区间剩余[i,j]的最大美观度，O(k)枚举第i串和哪一串合并在一起，并转移。
时间复杂度O(n2)O(n^2)

100%：

由于问题与前缀相关，考虑在trie树上处理，用所有字符串建立一棵trie树，我们通过前序遍历可以得到字符串排序后的结果。在trie树上思考，对于一个子树，从tire深度最深的deep层开始，如果能够凑出K个，肯定凑成一个集合是最优的，否则就会被放置在deep - 1层进行统一考虑，也就意味着，在遍历trie时，记录两个数，一个是已经凑出的集合的美观度之和，一个是剩余未放入集合的字符串个数，统计答案即可

代码

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
#include <bits/stdc++.h>

using namespace std;
struct Node{
	int sum_val,residue;
};
char ch[2001000];
int n,K;
int f[2001000][27],top = 1,val[2001000];
int vis[2001000][27],t_cnt;

void init()    //build a tree
{
	int now = 1,len = strlen(ch + 1);
	for (int i = 1;i <= len;i++)
		{
			int t = ch[i] - 'a' + 1;
			if (vis[now][t] == t_cnt)     now = f[now][t];
			else {
				vis[now][t] = t_cnt;
				now = f[now][t] = ++top;
			}
		}
	val[now]++;
}
Node operator + (Node x,Node y){return (Node){x.sum_val + y.sum_val,x.residue + y.residue};}
Node dfs(int node,int dep)
{
	Node val_node = (Node){0,val[node]};
	for (int i = 1;i <= 26;i++)
		if (vis[node][i] == t_cnt)
			{
				val_node = val_node + dfs(f[node][i],dep + 1);
			}
	val_node.sum_val += dep * (val_node.residue / K);
	val_node.residue = val_node.residue % K;
	return val_node;
}

int main()
{
	//freopen("string.in","r",stdin);     freopen("string.out","w",stdout);
	int T = 0;
	T = 1;
	for (int w = 1;w <= T;w++)
		{
			cin >> n >> K;   top = 1;   t_cnt++;
			memset(val,0,sizeof (val));
			for (int i = 1;i <= n;i++)
				{
					scanf("%s",ch + 1);
					init();
				}
			Node ans = dfs(1,0);
			printf("%d",ans.sum_val);
		}
    return 0;
}

T4 dinner

Description

小明所在的班级要组织一个聚餐，已知班级里一共n名同学，编号为1到n，其中有m对同学关系不好，如果同时在一起就会相互卷起来。

在聚餐时卷起来是大家都不想看到的事情，为此，小明提出了q种方案，第i种方案由[Li,RiL_i,R_i]区间组成，表示本次聚餐由所有区间内的同学共同参加。

然而，其实小明自己也不知道每个方案里面，会不会有一对关系不好的人卷起来，为此他找到了你来帮忙。

Input

第一行；三个正整数n，m，q，分别表示班级同学总数和关系不好的同学对数，以及方案个数。

接下来m行，每行两个数u，v，表示u，v关系不太好，同一个同学可能与多个同学关系不好。

接下来q行，每行首先一个数k，表示区间个数，接下来2 * k个数，描述L1,R1,...Lk,RkL_1,R_1,...L_k,R_k

Output

q行，对于每个方案，回答"GG"表示会有人卷起来，"SAFE"表示没有关系不好的同学同时在场。

Sample Input

1
2
3
4
5
6
7
8
9
10 5 3
3 8
3 2
8 4
8 5
5 8
2 1 3 6 8
1 3 5
2 4 6 9 10

Sample Output

1
2
3
GG
SAFE
SAFE

Data

40 %, n,m,Q≤1000,K≤100n,m,Q ≤ 1000,K ≤ 100

80 %, n,m,Q≤200000,K≤100,∑k≤200000n,m,Q ≤ 200000,K ≤ 100,∑k≤200000

100 %, n,m,Q≤200000,K≤n,∑k≤200000n,m,Q ≤ 200000,K ≤ n,∑k≤200000

思路

可以来一个大搜索，可以得四十分，而我剩下的就不会做了。

80%：

k比较小，考虑设计一个与k相关的算法，离线处理+线段树维护，考虑关系不好的对[i,j],i≤j[i,j],i\le j，从1到n枚举每一个同学，枚举到j时，将与j关系不好的位置i在线段树中的值设为j，如果j为某个方案中某个区间[x,j]的右端点，即我们在线段树中查找该方案中，该区间前的区间最大值，如果存在某个区间最大值大于x，则该方案存在冲突，对于每个方案，假设有kik_i个区间，则需要查询ki2k_i^2次，总复杂度$O(mlog(n) + \sum k^2log(n)) $

100%:

做法一：(这个我还是能看懂的)
考虑通过差分+位运算压位来解决问题。考虑暴力"将方案提出的区间标为"1"，即差分后将两个区间端点左端点加1，右端点+1位置减1，随后，通过前缀和，我们可以得到整个区间的每个位置的表示，发现一个int数值只置为1是非常浪费的，可以考虑位运算压位，long long 60位每一位处理一个方案。
时间复杂度O(Q∗(n+m)/60)O(Q * (n + m) / 60)
做法二：
考虑分块处理。将40分做法和80分做法结合起来，当k≥limk\ge lim时采用40分做法，当k≤limk\le lim时采用80分做法。
时间复杂度$O((n + m) * Q / lim + (n + m)log(n) + Q * lim * log(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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
using namespace std;
#define int64 long long
struct Node{
	int L,R;
};
int n,m,Q,cnt,lim = 60;
int64 bits[200200];
Node a[200200];
bool ans[200200];
void solve()
{
	long long sum = 0;
	for (int i = 1;i <= n;i++)     bits[i] += bits[i - 1];
	for (int i = 1;i <= m;i++)     sum |= (bits[a[i].L] & bits[a[i].R]);
	for (int i = 0;i < lim;i++)
		if (sum & ((int64)1 << i))     ans[cnt + i] = 0;
		else ans[cnt + i] = 1;
	cnt += lim;
}
int main()
{
    //freopen("dinner10.in","r",stdin);    freopen("dinner10.out","w",stdout);
	cin >> n >> m >> Q;
	for (int i = 1;i <= m;i++)   
		scanf("%d %d",&a[i].L,&a[i].R);
	int id,K,L,R;
	for (int i = 0;i < Q;i++)
		{
			id = i % lim;
			if (id == 0)     memset(bits,0,sizeof (bits));
			scanf("%d",&K);
			int L1,R1,L2,R2;
			scanf("%d %d",&L1,&R1);
			for (int j = 1;j <= K - 1;j++)
				{
					scanf("%d %d",&L2,&R2);
					if (L2 == R1) 
						{
							R1 = R2;
							continue ;
						}else {
						bits[L1] += (int64)1 << id;
						bits[R1 + 1] -= (int64)1 << id;
						L1 = L2;   R1 = R2;
					}
				}
				bits[L1] += (int64)1 << id;
				bits[R1 + 1] -= (int64)1 << id;
			if (id == lim - 1)    solve();
		}
	if (Q % lim != 0)     solve();
	for (int i = 0;i < Q;i++)
		if (ans[i] == 0)     printf("GG\n");
		else printf("SAFE\n");
    return 0;
}

总结

知识还是有漏洞，第一题第二题在考场上应该拿满分没有问题，但是却没有拿满分，并且第三题和第四题都应该得到部分分，主要原因在于心态崩了，所以放弃掉了。以后应该对于每一道题目考试之前都看一遍，把握一下大体题目难度，对于自己有把握的题目一定要拿到满分，这样才能真正的拿到省一。