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;
}

热门相关:我有一座恐怖屋   买妻种田:山野夫君,强势宠!   异世修真邪君   嫡嫁千金   重生之嫡女祸妃