逆序数
题目描述
运行代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll n,k;
cin>>n>>k;
ll sum=(n*(n-1))/2;
cout<<sum-k<<endl;
return 0;
}代码思路
-
组合数的计算：在数学中，从
n个不同元素中选取m个元素的组合数记为C(n,m)，计算公式为C(n,m)=n!/(m!(n - m)!)。当m = 2时，即C(n,2)=n*(n - 1)/2，这是因为n!中分子部分是n*(n - 1)*(n - 2)!，而2! = 2*1，约分后得到n*(n - 1)/2。 -
整体逻辑：首先根据输入的
n计算出n个不同元素中选两个元素的组合数sum。然后减去给定的k值，得到最终的结果并输出。这个结果可能代表在某种特定情境下，除去特定的k种情况后，剩余的组合数量。
构造mex
题目描述
运行代码
#include <iostream>
using namespace std;
#define ll long long
const int mod = 998244353;
void solve() {
ll n, m, k;
cin >> n >> m >> k;
if (k == 0) {
if (n < m) {
cout << "NO\n";
} else {
cout << "YES\n";
for (int i = 1; i < m; i++) {
cout << "1 ";
}
cout << n - m + 1 << "\n";
}
} else if (k == 1) {
if (n == 1 || m == 1) {
cout << "NO\n";
} else {
cout << "YES\n";
cout << n << " ";
for (int i = 1; i < m; i++) {
cout << "0 ";
}
cout << "\n";
}
} else {
ll nd = (k) * (k - 1) / 2;
if (nd > n || k > m) {
cout << "NO\n";
} else {
ll lst = n - nd;
if (k == m) {
if (lst == 0) {
cout << "YES\n";
for (int i = 0; i < k; i++) {
cout << i << " ";
}
cout << "\n";
} else {
cout << "NO\n";
}
} else if (lst == k) {
if (m >= k + 2) {
cout << "YES\n";
cout << 1 << " " << lst - 1 << " ";
for (int i = 0; i < k; i++) {
cout << i << " ";
}
ll ss = m - k - 2;
for (int i = 0; i < ss; i++) {
cout << "0 ";
}
cout << "\n";
} else {
cout << "NO\n";
}
} else if (m >= k + 1) {
cout << "YES\n";
cout << lst << " ";
for (int i = 0; i < k; i++) {
cout << i << " ";
}
ll ss = m - k - 1;
for (int i = 0; i < ss; i++) {
cout << "0 ";
}
cout << "\n";
} else {
cout << "NO\n";
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int tn;
cin >> tn;
while (tn--) {
solve();
}
return 0;
}代码思路
- 定义了一些常量和变量，包括
mod用于取模运算，n、m、k用于存储输入的数值，nd用于计算特定的数值，lst用于存储计算后的结果。 solve函数是核心函数，用于解决问题。- 当
k == 0时，如果n < m，则输出"NO"；否则，输出"YES"，并输出m - 1个1和一个n - m + 1。 - 当
k == 1时，如果n == 1或m == 1，则输出"NO"；否则，输出"YES"，并输出一个n和m - 1个0。 - 当
k > 1时，计算nd = (k) * (k - 1) / 2，如果nd > n或k > m，则输出"NO"；否则，计算lst = n - nd。- 如果
k == m且lst == 0，则输出"YES"并输出0到k - 1的序列。 - 如果
lst == k且m >= k + 2，则输出"YES"并按照特定格式输出序列。 - 如果
m >= k + 1，则输出"YES"并按照另一种特定格式输出序列。 - 否则，输出
"NO"。
- 如果
- 当
- 在
main函数中，通过ios::sync_with_stdio(false)和cin.tie(0)进行输入输出流的优化。然后读取测试用例的数量tn，并在循环中调用solve函数进行处理。
小红的X型矩阵
题目描述
运行代码
#include <iostream>
#include <vector>
#include <algorithm>
#define int long long
#define endl '\n'
const int N = 1010;
const int MOD = 1e9 + 7;
void solve() {
int n;
std::cin >> n;
std::vector<std::vector<int>> num(n, std::vector<int>(n));
std::vector<int> h(n, 0);
std::vector<int> l(n, 0);
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
std::cin >> num[i][j];
if (num[i][j]) {
cnt++;
h[(i + j) % n]++;
l[(i - j + n) % n]++;
}
}
}
int mint = 1e9;
if (n % 2 == 1) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int temp = h[(i + j) % n] + l[(i - j + n) % n];
if (num[i][j]) temp--;
int k = (2 * n - 1 - temp) + (cnt - temp);
mint = std::min(mint, k);
}
}
} else {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int temp = h[(i + j) % n] + l[(i - j + n + 1) % n];
int k = (2 * n - temp) + (cnt - temp);
mint = std::min(mint, k);
}
}
}
std::cout << mint << endl;
}
signed main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int t = 1;
while (t--) solve();
return 0;
}代码思路
一、整体思路
-
定义问题规模和常量：
N表示矩阵的最大尺寸，这里设置为 1010。MOD是一个常量，可能用于某些计算中的取模操作，设置为 1e9 + 7。 -
定义
solve函数来解决问题：- 读入整数
n，表示矩阵的边长。 - 创建一个二维向量
num来存储输入的矩阵，同时创建两个长度为n的向量h和l，分别用于统计特定方向上的元素数量。 - 通过双重循环遍历输入矩阵，对于每个位置
(i, j)：读入矩阵元素num[i][j]。如果该元素为非零值，则增加计数变量cnt，并更新h和l向量中对应位置的值。具体来说，通过(i + j) % n和(i - j + n) % n的计算结果来确定在h和l向量中的位置，并将对应位置的值加一。 - 初始化变量
mint为一个较大的值（1e9）。 - 如果
n是奇数：通过三重循环遍历矩阵的每个位置(i, j)。计算变量temp，它是对应位置在h和l向量中的值之和，如果当前位置的矩阵元素为非零值，则减一。计算变量k，根据特定的公式(2 * n - 1 - temp) + (cnt - temp)。更新mint为mint和k的较小值。 - 如果
n是偶数：与奇数情况类似，通过三重循环遍历矩阵的每个位置(i, j)。计算变量temp，这里的计算方式略有不同，使用(i - j + n + 1) % n来更新l向量中的位置。计算变量k，公式为(2 * n - temp) + (cnt - temp)。更新mint为mint和k的较小值。 - 最后输出
mint，即最小的操作次数。
- 读入整数
-
在
main函数中：设置输入输出流的同步，并初始化随机数生成器。读入整数t，表示测试用例的数量，这里固定为 1。调用solve函数来解决问题。
二、原理说明
-
h和l向量的作用：h向量用于统计矩阵中沿着特定对角线方向（通过(i + j) % n确定）上的非零元素数量。l向量用于统计矩阵中沿着另一个对角线方向（通过(i - j + n) % n或(i - j + n + 1) % n确定，取决于n的奇偶性）上的非零元素数量。 -
计算最小操作次数的原理：
- 对于奇数
n和偶数n，分别采用不同的计算公式来计算最小操作次数。 - 计算公式中的各个部分分别代表不同的含义：
2 * n - 1 - temp或2 * n - temp可能表示在某种情况下需要进行的操作次数，与矩阵的大小和当前状态有关。cnt - temp可能表示另一部分操作次数，与非零元素的总数和当前状态下特定方向上的非零元素数量有关。 - 通过遍历矩阵的所有位置，计算每个位置对应的操作次数，并取最小值作为最终的结果。
- 对于奇数