线段树/树状数组
是的，没看见周赛有线段树的题😤。
A题(树状数组)
题意：给出一些线段，寻找交点的个数。
刚开始看到数据只有1000，想暴力找交点，线段,两条线段有交点就是 (x_1 > x_2 && y_1 <y_2 ) 或者 (x_2>x_1 && y_2<y_1) ,暴力寻找然后超时了。由于是交点只与点的关系所决定，我们不妨按照从大到小开始遍历，我们可以发现，比如说遍历到了当前的 ,这个对答案的贡献是多少呢？ 显然就是前面的已经遍历过的那些线段中坐标比当前坐标小的线段的数量，这就可以树状数组来求个数。按照遍历的顺序，依次把插入树状数组中，然后对于当前遍历的累加贡献即可。注意：要用
主要代码👇
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题(找规律)
题意：给定起点，按照给定的字符串在图上走，求终点的节点编号。
这题之前有点印象，和有关。假设当前节点为。
- 是奇数，该节点为叶子节点.
- 为偶数，左儿子就是 ,右儿子就是 .
- 的父亲节点为 或者 .
当时我就卡在如何求父亲节点，因为左右儿子的求法不一样，比赛的时候看图随意口胡了一种判断方法，交上去WA了。第二天补题的时候发现，判断左儿子的方法：直接 ，再，判断是否和一样即可。比赛时没能想到，确实有点气人啊。
C题(dp+树状数组)
题意：类似于逆序对，我认为这个叫K序对,因为序列长度要求为K。
想着用树状数组求解，不会。赛后补题的。
表示满足以结尾序列长度为的个数，我们最终需要
如果从到变化，递推式就是 :
求和的过程可以用树状数组来求解。由于如果从前往后遍历，我们需要求解的是满足比当前a_i大的，我们个将数组反转过来，这样我们就可以变成求解比 小的了。其实树状数组也能求解大于某一个数的个数，将树状数组更新和查询的过程中变化反过来即可，也就是认为数组的最远的一端是起点。
我们遍历到时，将从这个位置插入树状数组中，这样在后面求和的时候，比大的数就可以利用这个数，比小的数不会用到。时间复杂度
#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题(贪心)
题意：求最小的次数将字符串变为回文串，在一次操作中，你可以变换任意一个字符。你可以随意移动字符串的位置，不增加次数
回文串的特点是最多有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表)
题意：从字符串中删除m个字符，使得字典序最小，不改变字符的相对位置。
单调栈：
维护一个从栈顶到栈底递减的字符串，当前字符比栈顶大或相等，直接插入，否则弹出，直到大于栈顶或栈空。删除的个数达到就要及时停止，最后输出栈中前个字符即可。字符相等为什么直接插入？ 因为这个字符保留在栈中是最优的。如果后面有比它小的字符，那这个就可能被删除，如果没有，那就是后面字符比它大，都不会影响答案。
ST表：
不断的从区间中寻找最小的字符，然后暴力查找下标，再更新区间。第一次查找的区间为 ,这个区间的选取，每次都要保证最终留有足够的字符来使得我们的最终字符个数为。假设当前查找第个字符，上次查找的位置下标为idx,那么这次查找的区间就是 .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;
}
评论