天使果冻
输入：
5
1 2 5 3 5
4
2
3
4
5输出：
1//前2个数，第二大的是1。
2//前3个数，第二大的是2。
3//前4个数，第二大的是3。
5//前5个数，第二大的是5。错误示范：
超时，由于使用了优先队列，当x很大时，入队出队非常浪费时间。---》通过37%
优化成在内部定义优先队列，不需要出队。---》通过50%
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
int q;
cin >> q;
while (q--) {
int x;
cin >> x;
priority_queue<int> pq;//默认最大堆，加上greater是最小堆
for (int i = 0; i < x; ++i) {
pq.push(a[i]);
}
pq.pop(); // 移除最大的元素
cout << pq.top() << '\n'; // 输出第二大的元素
}
return 0;
}思路：
使用两个数组
max1和max2分别存储前 i 个元素的最大值和次大值。在遍历时动态更新最大值和次大值。
正确代码：
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
// 预处理每个位置的最大值和次大值
vector<int> max1(n), max2(n);
max1[0] = a[0];
max2[0] = -1; // 没有次大值
for (int i = 1; i < n; ++i) {
if (a[i] > max1[i - 1]) {
max2[i] = max1[i - 1];
max1[i] = a[i];
} else if (a[i] == max1[i - 1]) {
max1[i] = a[i];
max2[i] = a[i];
} else {
max1[i] = max1[i - 1];
max2[i] = max(max2[i - 1], a[i]);
}
}
int q;
cin >> q;
while (q--) {
int x;
cin >> x;
cout << max2[x - 1] << '\n';
}
return 0;
}dd爱旋转
输入输出样例：
思路；
旋转 180° 等价于将矩阵上下翻转后再左右翻转。
行镜像操作就是简单的上下翻转。
异或运算：相同为零，不同为一。
代码：
~~~这种思路很好~~~：
该代码中，state有四种状态00、01、10、11。
初始状态=当前状态：异或为零，回到原始状态。
初始状态！=当前状态：异或之后可以保存这两种状态。
01^10=11，00^01=01，00^10=10，11^01=10，11^10=01……经过验证正确！
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<vector<int>> matrix(n, vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cin >> matrix[i][j];
}
}
int q;
cin >> q;
int state = 0; // 0: 原始状态, 1: 旋转180°, 2: 行镜像, 3: 旋转180° + 行镜像
while (q--) {
int x;
cin >> x;
if (x == 1) {
state ^= 1; // 切换旋转180°状态
} else if (x == 2) {
state ^= 2; // 切换行镜像状态
}
}
// 根据最终状态输出矩阵
if (state == 0) {
// 原始状态
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cout << matrix[i][j] << " ";
}
cout << "\n";
}
} else if (state == 1) {
// 旋转180°
for (int i = n - 1; i >= 0; --i) {
for (int j = n - 1; j >= 0; --j) {
cout << matrix[i][j] << " ";
}
cout << "\n";
}
} else if (state == 2) {
// 行镜像
for (int i = n - 1; i >= 0; --i) {
for (int j = 0; j < n; ++j) {
cout << matrix[i][j] << " ";
}
cout << "\n";
}
} else if (state == 3) {
// 旋转180° + 行镜像
for (int i = 0; i < n; ++i) {
for (int j = n - 1; j >= 0; --j) {
cout << matrix[i][j] << " ";
}
cout << "\n";
}
}
return 0;
}小红取数
输入：
5 5
4 8 2 9 1输出：
20//取后四个数即可代码：
dp的思想。
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
const long long INF = LLONG_MIN;
int main() {
int n, k;
cin >> n >> k;
vector<long long> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
// dp[i][j] 表示前 i 个数中，和模 k 等于 j 的最大和
vector<vector<long long>> dp(n + 1, vector<long long>(k, INF));
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < k;j++)
{
// 更新当前数带来的对所有余数的影响：
// dp[i][(j+arr[i-1])%k]更新对余数的影响，选最大值：
// 要么加入arr[i-1]:选择余数为j的状态加上arr[i-1],则对新余数(j+arr[i-1])%k产生影响，更新
// 要么不加入arr[i-1], 选择前一个状态本来余数就是(j+arr[i-1])%k的值
dp[i][(j + a[i - 1]) % k] = max(dp[i - 1][j] + a[i - 1],dp[i - 1][(j + a[i - 1]) % k]);
}
}
if (dp[n][0] <= 0) {
cout << -1 << endl;
} else {
cout << dp[n][0] << endl;
}
return 0;
}