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\) 时,若两个序列都倒序,则猫赢,若第一列有序而第一行倒序,则狐狸赢。
标签:11,typedef,排列,匹配,多校,back,牛客,奇偶性,include From: https://www.cnblogs.com/dkdklcx/p/17625226.html