2023“钉耙编程”中国大学生算法设计超级联赛（3）
1005.Out of Control
题意:
有n个数\(x_1,x_2,...,x_n\)，在其中选k个数依次放入栈中。如果当前放入栈中的数\(x_i\)小于栈顶的数，则向栈中放入与先前的栈顶相同的数而不是\(x_i\)。求对于每个k对应的方案数。
分析：
先排序离散化，然后考虑dp。
状态定义: f[i][j]表示长度为i且最后一个数是j的方案数。
状态转移：
f[i][j] = \(\sum_{t = 1}^jf[i - 1][t]\)
答案：
长度为 i的栈由长度为i - 1的栈转移过来, 且长度为i - 1的栈最后一位要小于等于j。那么对于长度为i的这类问题的答案即\(\sum_{j = i + 1}^nf[i][j]\)，条件就是小于等于j的数量必须要大于等于i
优化：
对于求f[i][j] = \(\sum_{t = 1}^jf[i - 1][t]\)：
f[i][1] = f[i - 1][1]
f[i][2] = f[i - 1][1] + f[i - 1][2] = f[i][1] + f[i - 1][2]
f[i][3] = f[i - 1][1] + f[i - 1][2] + f[i - 1][3] = f[i][2] + f[i - 1][3]
因此:
f[i][j] = f[i][j - 1] + f[i - 1][j]
\(\Rightarrow\) f[j] = f[j - 1] + f[j] \(\Rightarrow\) f[j] += f[j - 1]
因此f[n]即为答案。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3010, mod = 1e9 + 7;
LL f[N];
int a[N];
int main() {
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --) {
int n;
cin >> n;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
}
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; i ++) {
if (a[i] > a[i - 1])
f[i] = f[i - 1] + 1;
else
f[i] = f[i - 1];
}
cout << f[n] << "\n";
for (int i = 2; i <= n; i ++) {
for (int j = i + 1; j <= n; j ++) {
if (a[j] > a[j - 1])
f[j] = (f[j] + f[j - 1]) % mod;
else
f[j] = f[j - 1];
}
cout << f[n] << "\n";
}
}
return 0;
}
1011.8-bit Zoom
题意：
将 n × n 的矩阵放大为原来的 z% 倍，不行则输出 error
分析：
按题意模拟一下即可
代码:
#include <bits/stdc++.h>
using namespace std;
int main() {
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t, n, z;
char g[55][55];
cin >> t;
while (t--) {
cin >> n >> z;
for (int i = 0; i < n; i++) {
cin >> g[i];
}
if ((n * z) % 100 != 0) {
cout << "error" << endl;
}
else if ((1 * z) % 100 == 0) {
int p = z / 100;
for (int i = 0; i < n * z / 100; i++) {
for (int j = 0; j < n * z / 100; j++) {
cout << g[i / p][j / p];
}
cout << endl;
}
}
else if (2 * z % 100 == 0) { // z == 150
bool flag = true;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j += 2) {
if (g[i][j] != g[i][j + 1] || g[j][i] != g[j + 1][i]) {
flag = false;
break;
}
}
if (!flag) break;
}
if (flag) {
for (int i = 0; i < n * z / 100; i++) {
for (int j = 0; j < n * z / 100; j++) {
cout << g[i / 3 * 2][j / 3 * 2];
}
cout << endl;
}
}
else {
cout << "error" << endl;
}
}
else { // z = 125, z = 175;
bool flag = true;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j += 4) {
for (int k = j; k < j + 2; k++) {
if (g[i][k] != g[i][k + 1] || g[k][i] != g[k + 1][i]) {
flag = false;
break;
}
}
if (!flag) break;
}
if (!flag) break;
}
if (flag) {
int p = z * 4 / 100;
for (int i = 0; i < n * z / 100; i++) {
for (int j = 0; j < n * z / 100; j++) {
cout << g[i / p * 4][j / p * 4];
}
cout << endl;
}
}
else {
cout << "error" << endl;
}
}
}
return 0;
}
1012.Noblesse Code
题意：
给定n个模板二元组(\(a_i， b_i\))，有q次询问，每次给你一个二元组（A，B），问能通过若干次操作得到的模板二元组的数量。每次操作可以让(A，B)变成（A+B，B）或者（A，A+B）。
分析：
（A，B）的正向操作有两种，但它的逆向操作有且只有一种。
若A > B，则一定由(A - B, B)得来；
若A < B，则一定由(A, B - A)得来；
若A = B，则一定由(A, B)得来。
把这种关系用二叉树来表示，(A, B)的根节点是(gcd(A, B), gcd(A, B))。若(A, B)能通过一系列操作得到(a, b)则，（A，B）到根节点的路径必然是(a, b)到根节点路径的前缀。一种暴力的做法就是把路径求出来，然后计算能够匹配的数量。但这个路径会很长，考虑如何优化。
对于一个二元组(a, b)，假设a > b，我们观察路径：(a, b)-> (a - b, b)->(a - 2b, b), ... , (a % b, b), (a % b, b - (a % b)), (a % b, b - 2(a % b)), ... , (a % b, b % (a % b))...可以发现我们可以将那些具有相同操作的点归为一类，只考虑起点和拐点，因此我们可以进行路径压缩，一种压缩路径的方式是将拐点映射到一个起点的有序集合（A > B下的映射关系保留横坐标即可）。这样一来，我们就可以预处理n个二元组，对于每次询问，我们只需二分查找（A, B）逆向对应的拐点映射的有序集合即可得到答案。
整理一下：
1.预处理映射：
①映射1：a > b, (a % b, b) \(\rightarrow\) set(x)。set(x)是起点横坐标的有序集合。
②映射2：a < b, (a, b % a) \(\rightarrow\) set(y)。set(y)是起点纵坐标的有序集合。
③映射3：a = b, a \(\rightarrow\) cnt(a)。cnt(a)是起点横坐标a出现的次数。
2.对于每次询问（A, B）：
①若A > B，在映射1中二分查找key = (A % B, B)对应的set(x), 统计x >= A的数量。
②若A < B，在映射2中二分查找key = (A, B % A)对应的set(y), 统计y >= B的数量。
③若A = B，在映射1中二分查找key = (0, B)对应的set(x)，累加答案，在映射2中二分查找key = (A，0)对应的set(y)，累加答案，在映射3中累加key = a对应的cnt(a)。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PLL;
map<PLL, vector<LL>> mp1, mp2;
map<LL, LL> mp3;
int main() {
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --) {
mp1.clear();
mp2.clear();
mp3.clear();
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i ++) {
LL a, b;
cin >> a >> b;
if (a == b) {
mp3[a] ++;
} else {
while (a && b) {
if (a > b) {
mp1[{a % b, b}].push_back(a);
a = a % b;
} else {
mp2[{a, b % a}].push_back(b);
b = b % a;
}
}
}
}
for (auto &x : mp1) {
sort(x.second.begin(), x.second.end());
}
for (auto &x : mp2) {
sort(x.second.begin(), x.second.end());
}
while (m --) {
LL ans = 0;
LL a, b;
cin >> a >> b;
if (a > b) {
auto &v = mp1[{a % b, b}];
ans += v.end() - lower_bound(v.begin(), v.end(), a);
} else if (a < b) {
auto &v = mp2[{a, b % a}];
ans += v.end() - lower_bound(v.begin(), v.end(), b);
} else {
auto &v1 = mp1[{0, b}];
auto &v2 = mp2[{a, 0}];
ans += v1.end() - lower_bound(v1.begin(), v1.end(), a);
ans += v2.end() - lower_bound(v2.begin(), v2.end(), b);
ans += mp3[a];
}
cout << ans << "\n";
}
}
return 0;
}