T1#

题意#

X 和 Y 各有一个权值 $v_x, v_y$.

现在从最低位开始依次比较。

比如 $v_x=37$，$v_y=28$：

• 首先比较最后一位，$(7,8)$，Y 暂时领先。
• 再加上前一位，$(37,28)$，X 暂时领先。
• 比较结束。

如果我们用 X 代表小 X 暂时领先，Y 代表小 Y 暂时领先，那么可以写下一个字符串 XY。

再比如，$v_x=137$，$v_y=47$。

如果我们再用 Z 表示小 X 与小 Y 的点赞数暂时一样，那么写下的字符串应该为 XYZ。

给定最后的字符串 $s_i$，请构造一种可能的 $(v_x v_y)$。

若不存在构造方案，输出 $-1$.

为了方便输出，用前导零补足位数。

对于 $100\%$ 的数据，$s_i \in \{\texttt{X},\texttt{Y},\texttt{Z}\}$，$1 \le \text{len}(s) \le 10^6$。

XY

37
28

XYZ

137
047

ZZZZZZ

000000
000000

XYZXYZ

-1

题解#

如果 $Z$ 不是连续的后缀，则无解。

否则用 $0/1$ 构造即可。

const int MAXN = 1e6 + 10;
string s;
int a[MAXN], b[MAXN];
int main() {
	cin >> s;
	int n = s.length(), flag = 0;
	for(int i = 0; i < n; i++) {
		if(flag && s[i] != 'Z') {
			cout << -1 << endl;
			return 0;
		}
		if(s[i] == 'X') a[i] = 1, b[i] = 0;
		else if(s[i] == 'Y') a[i] = 0, b[i] = 1;
		else if(s[i] == 'Z') flag = 1;
	}
	for(int i = 0; i < n; i++) cout << a[i]; cout << endl;
	for(int i = 0; i < n; i++) cout << b[i]; cout << endl;
	return 0;
}

T2#

题意#

给定正整数 $n$，请找出一个合法的三元组 $(x, y, z)$，满足：

要求：$x, y, z\in \Z^+$ 且互不相同。

$1\leq n\leq 10^4$.

题解#

那就直接 $z=n$，则有：

考虑裂项公式：

因此：

于是得到：

当 $n=1$ 时，$x=y=n+1$，无解。

否则，按上述方案构造即可。

T3#

题意#

给定一个长度为 $n$ 的数组 $a$。

你需要确定一个范围 $[x,y]$，并将 $a$ 数组分成 $k$ 段，使得对于每一段，在范围 $[x,y]$ 以内的不同元素个数大于在范围 $[x,y]$ 以外的不同元素个数。

此处的 $x, y$ 都是权值，不是下标。

请求出任意一组使得 $(y-x)$ 最小的 $x,y$，并输出划分的方案。

数据范围：

• $t$ 组数据，$1\leqslant t\leqslant 3\times 10^4$。
• $1\leqslant k\leqslant n\leqslant 2\times 10^5$，$\sum n\leqslant 2\times 10^5$。
• $1\leqslant a_i\leqslant n$。

题解#

对于这道题，最根本的问题是最小化的 $(y-x)$，而具体的形式是如何划分整个序列。

我们可以发现，如果同时考虑这两个问题，事情会变得非常复杂，难以下手。

所以我们不妨暂且扔下具体的形式，去考察最根本的问题。

**性质：**划分为 $k$ 段时，在 $[x, y]$ 内的数总体上至少要比在此区间以外的数多 $k$ 个。

**证明：**每个段内至少多一个，一共多至少 $k$ 个。

做法：

先将整个序列从小到大排序，然后用一个大小为 $n-\lfloor\frac{n-k}{2}\rfloor$ 的滑动窗口去检测。

窗口两端的数就是 $[x, y]$，取 $(y-x)$ 的最小值即可确定 $[x, y]$。

推理一下可以发现，让每一段都多一个，可以使滑动窗口尽可能小，这样 $(y-x)$ 也会相应更小，同时这样的一组 $[x, y]$ 一定有可行的划分方案。

最后构造方案时也是每一段多一个就划开即可。

T4#

题意#

https://ac.nowcoder.com/acm/contest/11251/D ↗

小红想让你构造一个长度不超过 $200000$ 的字符串，其中包含 $k$ 个 $\texttt {red}$ 子序列。你能帮帮她吗？

子序列的定义：在原串中必须按顺序，可以不连续。例如，$\texttt {reddd}$ 有3个：$\underline{\texttt{red}}\texttt{dd}$，$\underline{\texttt{re}}\texttt{de}\underline{\texttt{d}}$，$\underline{\texttt{r}}\texttt{ed}\underline{\texttt{ed}}$.

若无法构造，输出 $-1$，多解输出任意。

数据范围：$0\leq k\leq 10^{14}$.

题解#

考虑字符串：

在第一个 $\texttt{re}$ 后面加 $x$ 个 $\texttt{d}$，可稳定增加 $x$ 个子序列；

在第二个 $\texttt{re}$ 后面加 $x$ 个 $\texttt{d}$，可稳定增加 $3x$ 个子序列；

以此类推，

在第 $k$ 个 $\texttt{re}$ 后面加 $x$ 个 $\texttt{d}$，可稳定增加 $\frac{k\cdot (k+1)}{2}x$ 个子序列。

于是把字符串长度缩小到 $n^{\frac{1}{3}}$ 级别，可以证明这样的长度一定小于 $200000$.

#include<bits/stdc++.h>
using namespace std;
int tong[101010];
int main(){
    long long n,i,j,k,p;
    cin>>n;
    if(n==0)return cout<<"d",0;
    for(i=1;i*i*i/6<=n;i++);
    i--;
    for(j=i;j>0;j--){
        tong[j]+=n/(j*(j+1)/2);
        n%=j*(j+1)/2;
    }
    for(j=1;j<=i;j++){
        cout<<"re";
        while(tong[j]--)cout<<"d";
    }
}

T5#

题意#

Task1：试判断能否构造并构造一个长度为 $n$ 的 $1 \dots n$ 的排列，满足其 $n$ 个前缀和在模 $n$ 的意义下互不相同。若存在，请给出一种构造方案。

Task2：试判断能否构造并构造一个长度为 $n$ 的 $1 \dots n$ 的排列，满足其 $n$ 个前缀积在模 $n$ 的意义下互不相同。若存在，请给出一种构造方案。

测试点类型 $1$：$10$ 分，满足 $X = 1$，$1 \leq n \leq 10$。
测试点类型 $2$：$40$ 分，满足 $X = 1$，$1 \leq n \leq {10}^5$。
测试点类型 $3$：$10$ 分，满足 $X = 2$，$1 \leq n \leq 10$。
测试点类型 $4$：$40$ 分，满足 $X = 2$，$1 \leq n \leq {10}^5$。

样例输入 #1#

1 1
8

样例输出 #1#

2 8 7 6 5 4 3 2 1

样例输入 #2#

2 1
11

样例输出 #2#

2 1 2 3 5 10 6 7 4 9 8 11

题解#

设序列为 $a_i$，分别讨论两个子任务。

Task1#

设 $s_i=(\sum\limits_{j=1}^i a_i)\bmod n$，可以有如下发现：

1. $\forall l, r, s_l\equiv s_r\pmod n$ 当且仅当 $s_r-s_{l-1}\equiv 0\pmod n$. 因此不存在区间 $[l, r]$ 的区间和是 $n$ 的倍数。
2. 当 $a_i=n$ 时，$i=1$.
3. 若 $2\nmid n$ 且 $n\neq 1$，无解。

接下来对有解情况进行构造。

发现 $n$ 必定为偶数，要想让 $s$ 构成 $\bmod n$ 意义下的完全剩余系，考虑把所有偶数在模意义下取相反数。

也就是说，使：

注意到，所有偶数的符号为负，再加上 $n$ 变为正数后，仍为偶数，所以 $s$ 仍然满足题意。

则有 $a_i$ 的通项公式：

注意 $a_1=n\neq 0$.

Task2#

设 $s_i=(\prod\limits_{j=1}^i a_i)\bmod n$，可以有如下发现：

1. $\forall l, r, s_l\equiv s_r\pmod n$ 当且仅当 $\frac{s_r}{s_{l-1}}\equiv 0\pmod n$. 因此不存在区间 $[l, r]$ 的区间积是 $n$ 的倍数。
2. 当 $a_i=n$ 时，$i=n$.
3. 当 $a_i=1$ 时，$i=1$.
4. 当 $n$ 为合数时（$4$ 除外），$n\mid (n-1)!$，所以 $s_{n-1}\equiv s_n\pmod n$，无合法方案。

因此序列开头为 $1$，末尾为 $n$，$n$ 为质数，想到 $s_i=i$ 是否可行？

下面在 $s_{i-1}+1\equiv s_i\pmod n$ 的情况下构造：

于是可以从头开始递推完成构造。

T6#

题意#

给你 $n$ 个整点和它们的坐标，现在给它们分成两组并两两连上边。

对于每条边，如果两端的点在：同一组则边为黄色，不同组则为蓝色。

现在让你给出任意一种分组方案，使得所有长度相同的边颜色相同。

保证存在合法方案。

$2\leq n\leq 10^3$，$|x_i|, |y_i|\leq 10^6$.

题解#

将点分为黑色和白色两组。

考虑对格子黑白染色，坐标和为偶数的染为黑色。

一、若两种颜色的点都存在#

黄色边的边长平方一定是奇数，蓝色边的边长平方一定是偶数，满足题目条件。

直接按黑白颜色分组即可。

二、若只存在一种颜色的点#

不妨设只存在黑点，因为只有白点，就可以全部下移一格，转化为黑点。

如果所有点的两维坐标都是偶数，则可以直接 $\div 2$，但我们只保证了 $2\mid (x+y)$.

想要转化到让 $(x+y)$ 既有奇数又有偶数，过程中不改变点之间的位置关系。

注意到 $2\mid (x+y)\Rightarrow 2\mid (x-y)$.

联想到坐标旋转公式：

若旋转 $45\degree$，则有：

旋转和缩放都可以保证点间位置关系不变。我们只想看到整数，于是让：

这样进行若干次，最终一定会使黑白点均存在。

分为了黑白点就可以由之前的方法解决，否则继续递归。

递归的次数为 $\mathcal O(\log A)$ 次，其中 $A$ 为坐标值域大小。