MENU

暑假集训——周赛2

2019-06-27 • 阅读: 21 • 数据结构—树状数组基本数据结构—单调栈阅读设置

线段树/树状数组

是的,没看见周赛有线段树的题😤。

A题(树状数组)

A - Japan POJ - 3067

题意:给出一些线段,寻找交点的个数。

刚开始看到数据只有1000,想暴力找交点,线段(x,y)(x,y),两条线段有交点就是 (x_1 > x_2 && y_1 <y_2 ) 或者 (x_2>x_1 && y_2<y_1) ,暴力寻找然后超时了。由于是交点只与点的关系所决定,我们不妨按照xx从大到小开始遍历,我们可以发现,比如说遍历到了当前的 xx,这个xx对答案的贡献是多少呢? 显然就是前面的已经遍历过的那些线段中yy坐标比当前yy坐标小的线段的数量,这就可以树状数组来求个数。按照遍历的顺序,依次把yy插入树状数组中,然后对于当前遍历的累加贡献即可。注意:要用 longlonglong long

主要代码👇


bool operator<(const P &o)const
{
	if (x == o.x) return y>o.y;
	return x > o.x;
}
sort(a + 1, a + k + 1);
for (int i = 1; i <= k; i++)
{
	ans += ask(a[i].y - 1);
	add(a[i].y);
}

B题(找规律)

B - Paths in a Complete Binary Tree

题意:给定起点,按照给定的字符串在图上走,求终点的节点编号。

这题之前有点印象,和lowbitlowbit有关。假设当前节点为xx

  • xx是奇数,该节点为叶子节点.
  • xx为偶数,左儿子就是 x(lowbit(x)>>1)x-(lowbit(x)>>1),右儿子就是 x+(lowbit(x)>>1)x+(lowbit(x)>>1).
  • xx的父亲节点为 x+lowbit(x)x+lowbit(x) 或者 xlowbit(x)x-lowbit(x).

当时我就卡在如何求父亲节点,因为左右儿子的求法不一样,比赛的时候看图随意口胡了一种判断方法,交上去WA了。第二天补题的时候发现,判断左儿子的方法:直接 v=x+lowbit(x)v=x+lowbit(x),再v=v(lowbit(v)>>1)v=v-(lowbit(v)>>1),判断vv是否和xx一样即可。比赛时没能想到,确实有点气人啊。

C题(dp+树状数组)

C - K-inversions

题意:类似于逆序对,我认为这个叫K序对,因为序列长度要求为K。

想着用树状数组求解,不会。赛后补题的。
dpijdp_{ij}表示满足以ii结尾序列长度为jj的个数,我们最终需要 i=1ndp[i][k]\sum_{i=1}^{n}dp[i][k]

如果ii11nn变化,递推式就是 :

dp[i][j]=dp[k][j1],(k<i,ai<ak)dp[i][j]= \sum dp[k][j-1] ,(k<i,a_i<a_k)

求和的过程可以用树状数组来求解。由于如果从前往后遍历,我们需要求解的是满足比当前a_i大的,我们个将数组反转过来,这样我们就可以变成求解比 aia_i 小的了。其实树状数组也能求解大于某一个数的个数,将树状数组更新和查询的过程中xx变化反过来即可,也就是认为数组的最远的一端是起点。
我们遍历到aia_i时,将dp[i][j1]dp[i][j-1]aia_i这个位置插入树状数组中,这样在后面求和的时候,比aia_i大的数就可以利用这个数,比aia_i小的数不会用到。时间复杂度O(n×k×logn)O(n \times k \times log_n)


#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 2e4 + 10;
const int mod = 1e9;
typedef  long long ll;
#define lowbit(x) (x&(-x))
int c[N][12],n,k,a[N];
int dp[N][12];
void add(int x, int y, int val)
{
	while (x <= n)
	{
		c[x][y] = (c[x][y] + val) % mod;
		x += lowbit(x);
	}
}
int ask(int x, int y)
{
	int res = 0;
	while (x)
	{
		res = (res + c[x][y]) % mod;
		x -= lowbit(x);
	}
	return res;
}
int main()
{
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	for (int i = 1; i <= n; i++){
		dp[i][1] = 1;
	}
	for (int i = 1; i <= n / 2; i++)
		swap(a[i], a[n - i+1]);
	for (int j = 2; j <= k; j++)
	{
		for (int i = j-1; i <= n; i++)//i从1开始也行,i<j-1的部分dp[i][j]都是0,对答案无影响
		{
			dp[i][j] = ask(a[i] - 1,j);//这里也可以只用一个1维树状数组循环利用
			add(a[i], j, dp[i][j - 1]);
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++)
		ans = (ans + dp[i][k]) % mod;
	cout << ans << endl;
	return 0;
}

D题(贪心)

D - Make Palindrome

题意:求最小的次数将字符串变为回文串,在一次操作中,你可以变换任意一个字符。你可以随意移动字符串的位置,不增加次数

回文串的特点是最多有1个字符的出现次数为奇数,其他为均为偶数。
我们可以记录每个字符出现的次数,然后从小到大遍历字符,若当前字符个数为奇数,哪么我们可以再寻找一个个数也为奇数的字符,将其替换为我们这个字典序较小子符,这样我们花费一次就可以消去两个奇数字符。如果找不到,说明他就是中间字符。最后我们按照字典序从小到大输出字符即可。


#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 2e5 + 10;
const int mod = 1e9;
typedef  long long ll;
#define lowbit(x) (x&(-x))
int num[30];
int len, tot;
char s[N];
int main()
{
	scanf("%s", s);
	len = strlen(s);
	for (int i = 0; i < len; i++)
		num[s[i] - 'a']++;
	int pos = -1, f = 0;
	for (int i = 0; i < 26; i++)
	{
		if (num[i] & 1)
		{
			f = 1;
			for (int j = 25; j>i; j--)
			{
				if (num[j] & 1){
					num[i]++;
					num[j]--;
					f = 0;
					break;
				}
			}
			if (f) pos = i;
		}
	}
	for (int i = 0; i < 26; i++)
	{
		if (!num[i]) continue;
		int t = num[i] / 2;
		while (t--)
			s[tot++] = i + 'a';
	}
	if (pos != -1) s[tot++] = pos + 'a';
	for (int i = 25; i >= 0; i--)
	{
		if (!num[i]) continue;
		int t = num[i] / 2;
		while (t--)
			s[tot++] = i + 'a';
	}
	printf("%s\n", s);
	return 0;
}

F题(单调栈/ST表)

F - A Magic Lamp HDU - 3183

题意:从字符串中删除m个字符,使得字典序最小,不改变字符的相对位置。

单调栈:

维护一个从栈顶到栈底递减的字符串,当前字符比栈顶大或相等,直接插入,否则弹出,直到大于栈顶或栈空。删除的个数达到mm就要及时停止,最后输出栈中前nmn-m个字符即可。字符相等为什么直接插入? 因为这个字符保留在栈中是最优的。如果后面有比它小的字符,那这个就可能被删除,如果没有,那就是后面字符比它大,都不会影响答案。

ST表:

不断的从区间中寻找最小的字符,然后暴力查找下标,再更新区间。第一次查找的区间为 [1,m+1][1,m+1],这个区间的选取,每次都要保证最终留有足够的字符来使得我们的最终字符个数为nmn-m。假设当前查找第ii个字符,上次查找的位置下标为idx,那么这次查找的区间就是 [idx+1,m+i][idx+1,m+i] .ST表求解即可

#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e3 + 10;
typedef long long ll;
#define lowbit(x) (x&(-x))
int n,m,k;
char s[N];
char a[N];
int tot;
int main()
{
	while (scanf("%s%d", s, &m) != EOF)
	{
		tot = 0;
		int lose = 0;
		n = strlen(s);
		for (int i = 0; i < n; i++)
		{
			if (lose >= m) { a[++tot] = s[i]; continue; }
			while (tot&&s[i] < a[tot])
			{
				tot--;
				lose++;
				if (lose >= m) break;
			}
			a[++tot] = s[i];
		}
		int up = n - m;
		int i = 1;
		while (a[i] == '0'&&i <= up) i++;
		if (i > up){
			puts("0");
			continue;
		}
		for (; i <= up; i++)
		{
			putchar(a[i]);
		}
		puts("");
	}
	return 0;
}

返回文章列表 文章二维码 打赏
本页链接的二维码
打赏二维码