AtCoder Regular Contest 125 - ARC125

AtCoder Regular Contest 125

B - Squares

题意

给出一个 $N$，求有多少对 $(x,y)$ 满足如下条件：

• $1\leqslant x, y\leqslant N$。

• $x^2-y$ 是一个平方数。（规定 $0$ 也是平方数）

答案对 $998244353$ 取模。

数据范围：$N\leqslant 10^12$

思路

设 $x^2-y=z^2, (z\in \mathbb Z_{\geqslant 0})$，则 $y=x^2-z^2=(x-z)(x+z)$

令 $p=(x-z), q=(x+z)$，则：

$$\begin{cases} 1\leqslant pq\leqslant N\\ p\geqslant q\\ \frac{p+q}{2}=x\in[1,N] \end{cases}$$

可以发现，$q$ 的取值一共只有 $\sqrt N$ 种。

对于每一个 $q$ 只用 $O(1)$ 求出 $p$ 即可。

不难发现，$p$ 的取值只能为 $q, q+2, q+4, \ldots, \min(\left\lfloor\frac{N}{q}\right\rfloor, 2N-q)$，

令 $M = \min(\left\lfloor\frac{N}{q}\right\rfloor, 2N-q)$，故一共有 $\left\lfloor\frac{M-q}{2}\right\rfloor+1$ 种取值。

总复杂度 $O(\sqrt N)$。

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int P = 998244353;
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, ans = 0;
	cin >> n;
	for (int i = 1; i * i <= n; i++) {
		ans = (ans + 1 + (min(n/i, 2*n-i) - i) / 2) % P;
	}
	cout << ans << '\n';
	return 0;
}

C - LIS to Original Sequence

题意

给出 $N,K$ 和一个长度为 $K$ 的序列 $A=(A_1,A_2,\cdots,A_K)$，求一个 $1\ldots N$ 的排列，使得序列 $A$ 是该排列的一个最长上升子序列（LIS - longest increasing subsequence），并且要求排列的字典序最小。

输入保证 $A$ 是一个严格单增序列。

数据范围：$1\leqslant K\leqslant N\leqslant 2\times 10^5$

思路

考虑如何通过 $A$ 来构造出一个排列 $P$，用 $P_i$ 代表排列 $P$ 中的第 $i$ 个元素：

首先，当 $K=1$ 时，$P_i=(N, N-1, N-2, \cdots, 1)$。

其次，当 $K\geqslant 2$ 时：

1. 如果 $A_1=1$，那么一定有 $P_1=A_1=1$，才能使得 $P$ 的字典序最小，且一定能满足要求。

2. 如果 $A_1\geqslant 2$，那么一定有 $P_1=A_1$，那么此时 $P$ 中的数字1还没有使用过，如果我们令 $P_2=1$ 是不影响LIS的，因为题目只要求是LIS中一个即可，而且这样能使得字典序保持最小，所以有 $P_2=1$。

   • 证明：$P_1=A_1$。反设：若 $P_1 < A_1$，那么最长上升子序列一定会比 $A$ 多出一个元素，不满足题意；若 $P_1 > A_1$，则不满足字典序最小这个条件，综上，$P_1=A_1$。

上面都只考虑了 $A_1$，由于这个操作具有独立性，可以直接将 $A_1$ 删去，考虑后面的元素，每个元素都按照上述方式加入排列 $P$ 中，只不过元素 $1$ 的定义向右移了几位。

可以使用双指针模拟，$i$ 指向 $A$ 中元素，$j$ 指向 $P$ 中当前的 “1”（也就是当前能插入的最小的数字），保证不重复插入即可，如果枚举到了最后一个元素，按照 $K=1$ 的情况处理即可。

总复杂度 $O(N)$。

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int P = 998244353;
const int N = 2e5 + 10;
int vis[N];
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	int n, m;
	scanf("%lld %lld", &n, &m);
	vi ans;
	for (int i = 0, p = 1; i < m; i++) {
		int x;
		scanf("%lld", &x);
		if (i == m-1) {
			for (int j = n; j >= p; j--) {
				if (!vis[j]) {
					ans.pb(j);
				}
			}
			break;
		}
		ans.pb(x);
		if (x != p) {
			vis[x] = 1;
			ans.pb(p);
		}
		while (vis[++p]);
	}
	for (auto i : ans) cout << i << ' ';
	return 0;
}