赛时过程

这次树状数组专项练习赛，~~我不会告诉你我做不起板子题。~~

先看T1，一个sb板子，然后完美打挂过了。

T2以为是某长代码蓝题的加强版直接爬，当时想这怕不是紫题。

T3一看就知道毒瘤爬。T4板子又打挂了，40。现在排名垫底，rk10。

慌得1p。看着旁边的某些高中学长比赛时讨论得热火朝天心里很不舒服。强迫自己冷静下来去看T3，没思路看T2，发现自己傻逼了，这题不就是个板子吗。于是切了回到T1。

T1调了一个sb错误过了样例A了。现在剩下T3，由于是IOI赛制，我卡了卡常卡挂了然后老老实实开T3。

想了一会儿发现可以逆序对做，于是代码灰常简单，就是必须getchar读入让我看着很不舒服。然后A了。于是AK，rk2，某高中巨佬xhw先AK了（这场比赛除了我都是高一）。我的程序总用时慢了100ms。

于是………………

我记得xhw巨佬好像不会写fread（（（（，赶紧卡常卡了半天比xhw巨佬少跑了一一半的时间。然后rk1。

没想到这场比赛还能打个翻身仗。不过也许题水也是一个原因吧~~我都能做出来那还能不水吗~~。

赛后题解

T1T2板子，T4也比较板，写个T3题解吧。

题目：

何老板最近在玩一款叫”彩色方块”的小游戏，游戏虽然简单，但何老板仍旧乐此不疲。
游戏中有 $n$ 个彩色方块成一排，方块的颜色用字母表示，给出目标排列，只要把它们排成跟目标一样的排列，就算过关。每次操作只能交换相邻两个方块。
给出一关游戏，何老板想知道，最少操作几次就能过关，请你帮他计算最少所需的操作步数。

输入格式
第一行，一个整数 $n$ 表示方块的数量
第二行，$n$ 个大写字母，表示一开始方块的排列情况。每个字母表示对应方块的颜色。
第三行，$n$ 个大写字母，表示方块的目标排列情况。

输出格式就不说了，样例：

样例输入

1
2
3

3
RGB
GBR

样例输出

有一个比较显然的贪心策略：按照目标排列给原始排列编上号，比如样例原始排列编号312。然后先把编号小的交换的前面去，这样依次交换。然后就是一个逆序对板子。

#include <cstdio>
#include <cstring>
#include <deque>
#define gc (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 131072, stdin), p1 == p2) ? EOF : *p1 ++)

char buf[131072], *p1, *p2;
std::deque<int> block[26];
char str1[1000005], str2[1000005];
int a[1000005], c[1000005], n;
inline void update(const int x) {
for (int i(x); i <= n; i += (i & ~i + 1)) ++ c[i];
}
inline int query(const int x) {
int sum(0);
for (int i(x); i; i -= (i & ~i + 1)) sum += c[i];
return sum;
}

signed main() {
long long ans(0LL);
scanf("%d", &n);
char ch;
while ((ch = gc) == '\n' && ch == '\r' && ch == ' ');
for (int i(1); i <= n; ++ i) str1[i] = gc - 65;
while ((ch = gc) == '\n' && ch == '\r' && ch == ' ');
for (int i(1); i <= n; ++ i) str2[i] = gc - 65;
for (int i(1); i <= n; ++ i) block[str1[i]].push_back(i);
for (int i(1); i <= n; ++ i)
a[block[str2[i]].front()] = i, block[str2[i]].pop_front();
for (int i(1); i <= n; ++ i) ans += (long long)query(n) - query(a[i]), update(a[i]);
printf("%lld", ans);
}

zqs`s blog

1/13树状数组专项练习赛总结

赛时过程

赛后题解