暑假牛客多校第八场 2023-8-11（H、K）
H. Insert 1, Insert 2, Insert 3, ...
算法：栈
做法：
我们分析题目发现每个区间的左端点一定是 \(1\)，而且每个新加入的数 \(x\) 一定是匹配最靠近它的且未经匹配的 \(x - 1\)。举个例子，在[1,1,2,2,3]中我们加入一个数 \(3\) 时由于从左到右的第二个 \(2\) 是已经和第一个 \(3\) 匹配了，所以新加入的 \(3\) 应该和第一个 \(2\) 匹配，且第二个 \(1\) 和第一个 \(2\) 匹配，第一个 \(1\) 和第二个 \(2\) 匹配。那么新加入的 \(3\) 应该是和从左到右第一个 \(1\) 和第二个 \(2\) 匹配成一组。再举个例子，在区间[1,1,2,2]中，我们新加入一个 \(3\)，那么 \(3\) 应该和最近的且未经匹配的 \(x - 1\) 匹配，那么匹配的数就是第二个 \(2\) 了，若匹配第二个 \(2\)，那么第二个区间[1][1,2,2,3]就不是一个合法区间了。
我们每次加入一个数，找到最靠近它的匹配数，然后定位最靠近它的且和这个数是一组的 \(1\)，如果最靠近它的 \(1\) 左边还有 \(1\)，那么加上这些 \(1\) 区间会不同且区间合法。另外如果找到的这个最靠近它的 \(1\) 右边还有 \(1\) ，那么右边的所有 \(1\)（不超过右边界）都不能成为左区间端点，即右边的所有的匹配的 \(1\) 已经确定了，那么下次完成找匹配 \(x\) 的 \(1\) 还想再加 \(1\) 来增加不同区间就应该以这个新确定的 \(1\) 往左找 \(1\)的数量。如果新加入的数完全找不到可以匹配的 \(x - 1\)，那么这段区间就可以跳过了。
code
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <cmath>
#include <string>
#include <set>
#define x first
#define y second
#define endl '\n'
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
typedef pair<double, double> PDD;
typedef pair<int, string> PIS;
int dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };
const int N = 1000010, M = 200100, INF = 0x3f3f3f3f, mod = 998244353, TIME = 50001;
int n;
LL ans;
vector<int> p[N], s;
void solve()
{
cin >> n;
for (int i = 1, x, y; i <= n; i++)
{
cin >> x; x--;
if (x == 0)p[1].push_back(i), s.push_back(i), ans += s.size();
else if (p[x].empty())s.clear();
else
{
y = p[x].back(), p[x].pop_back(), p[x + 1].push_back(y);
while (s.back() > y)s.pop_back();
ans += s.size();
}
}
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 1;
while (t--)
{
solve();
}
return 0;
}
K. Scheming Furry
算法：对于一个1，2，3，... ，n的排列我们有如下定理。
- 排列的逆序数为奇数时为奇排列，为偶数时为偶排列。
- 排列的奇排列和偶排列数量相同，各为 \(\frac{n!}{2}\) 个。
- 每一次对排列的任意两个数进行变换时，逆序数的奇偶性会变换。
做法：首先我们注意到如果狐狸一开始只用一次就可以使矩阵有序，那么狐狸赢。其次\(n \ge 3\) 并且 \(m \ge 3\) 时两者为了都不让对方赢，总有办法做一些使对方不能成功排序的做法。当 \(n = 2\) 且 \(m \ge 3\) 时，第一列的逆序数的奇偶性和第一行的奇偶性相同时就是猫赢，否则平局。
解释：猫想要赢，一定是在狐狸把它第一列排成有序后猫再做一次使这第一行有序。我们知道排列有序的序列一定是逆序数为 \(0\) 的排列，那么其一定是偶排列。而一开始第一列可以是有序也可以是无序，如果是有序，则为偶排列，那么我们就象征性的设其为偶数就好了，无序的话可能是奇排列也可能是偶排列，但由于只有两个数，那么必定是奇排列了。猫如果是奇排列，那么狐狸也应该是奇排列。这样最后一步时，狐狸是偶排列，猫是奇排列，再下一步就是偶排列，得到排序矩阵。猫是偶排列同理。
当 \(n \ge 3\) 且 \(m = 2\) 时，第一列的逆序数的奇偶性和第一行的奇偶性不相同则狐狸赢，否则平局。当 \(n = 2\) 且 \(m = 2\) 时，若两个序列都倒序，则猫赢，若第一列有序而第一行倒序，则狐狸赢。