Codeforces Round #869 (Div. 2) (题解)
CodeForces1818A
原题链接
思路:每次投票与1不一样的直接扔出去
#include <bits/stdc++.h>
using i64 = long long;
using PII = std::pair<i64,i64>;
#define int i64
#define yes std::cout << "YES\n";
#define no std::cout << "NO\n";
void solve() {
int n, k;
std::cin >> n >> k;
std::vector a(n + 1,std::vector<char>(k + 1));
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= k; j ++) {
std::cin >> a[i][j];
}
}
std::vector<bool> st(n + 1);
int ans = 0;
for (int i = 1; i <= k; i ++) {
for (int j = 2; j <= n; j ++) {
if (!st[j]) {
if (a[j][i] != a[1][i]) {
ans ++;
st[j] = true;
}
}
}
}
std::cout << n - ans << "\n";
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
std::cin >> T;
while (T -- ) {
solve();
}
return 0;
}
CodeForces1818B
原题链接
题意:求al ~ ar的和不被r - l + 1整除的排列
思路:打表找规律
打表代码
#include <bits/stdc++.h>
using i64 = long long;
using PII = std::pair<i64,i64>;
#define int i64
#define yes std::cout << "YES\n";
#define no std::cout << "NO\n";
void solve() {
int n;
std::cin >> n;
for (int i = 1; i <= n; i ++) {
int m = i;
std::vector<int> a(m + 1);
std::iota(a.begin(), a.end(),0);
std::cout << "n=" << m << " ";
bool ok = true;
do {
ok = false;
std::vector<int> s(m + 1);
for (int j = 1; j <= m; j ++) {
s[j] = s[j - 1] + a[j];
}
for (int l = 1; l <= m - 1; l ++) {
if (ok) break;
for (int r = l + 1; r <= m; r ++) {
if ((s[r] - s[l - 1]) % (r - l + 1) == 0) {
ok = true;
break;
}
}
}
if (ok) {
continue;
}
for (int j = 1; j <= m; j ++) {
std::cout << a[j] << " \n"[j == m];
}
break;
} while (next_permutation(a.begin() + 1, a.end()));
if (ok) std::cout << -1 << "\n";
}
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
// std::cin >> T;
while (T -- ) {
solve();
}
return 0;
}
C++代码
#include <bits/stdc++.h>
using i64 = long long;
using PII = std::pair<i64,i64>;
#define int i64
#define yes std::cout << "YES\n";
#define no std::cout << "NO\n";
void solve() {
int n;
std::cin >> n;
if (n == 1) {
std::cout << "1\n";
} else if (n == 2) {
std::cout << "1 2\n";
} else {
if (n & 1) {
std::cout << "-1\n";
} else {
for (int i = 1; i <= n; i ++) {
if (i & 1) {
std::cout << i + 1 << " \n"[i == n];
} else {
std::cout << i - 1 << " \n"[i == n];
}
}
}
}
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
std::cin >> T;
while (T -- ) {
solve();
}
return 0;
}
CodeForces1818C
原题链接
题意: 在L~R范围内找到几乎递增的序列的最大个数
思路: 前缀和乱搞
值得注意的是,前缀和记录的是L-R中需删除元素的个数,而不是L~R中几乎递增的序列的最大个数.原因是后者的正确性无法保证。会出现wa3的情况. 特例:
5 1
1 1 1 1 1
3 5
正确输出为
2
错误输出为
0
此外,如果区间长度<= 2。则答案一定为区间长度
#include <bits/stdc++.h>
using i64 = long long;
using PII = std::pair<i64,i64>;
#define int i64
#define yes std::cout << "YES\n";
#define no std::cout << "NO\n";
void solve() {
int n, q;
std::cin >> n >> q;
std::vector<int> a(n + 10);
for (int i = 1; i <= n; i ++) {
std::cin >> a[i];
}
std::vector<int> st(n + 10);
st[1] = 1,st[2] = 2;
for (int i = 2; i <= n - 1; i ++) {
if (a[i - 1] >= a[i] and a[i] >= a[i + 1]) {
st[i] = st[i - 1] + 1;
} else {
st[i] = st[i - 1];
}
}
while (q -- ) {
int l, r;
std::cin >> l >> r;
if (r - l + 1 <= 2) {
std::cout << r - l + 1 << "\n";
} else {
std::cout << r - l + 1 - (st[r - 1] - st[l]) << "\n";
}
}
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
// std::cin >> T;
while (T -- ) {
solve();
}
return 0;
}
请问c题为什么要把st[1]和st[2]分别初始化成1和2呢?
我没初始化也ac了。
这里初不初始化都没有影响,我这是之前错误的代码忘删了😄,正常应该是st[1]=st[2]=0;执行for循环时,st[2]会重新计算,所以原有的值会被覆盖,而st[1]只有在l = r = 1的情况才会被用到,其他时候不会用到其值(st[1]不管值是多少都不会影响前缀和,这就相当于对这个区间即使加上了某个数,最后也能算出原来的前缀和)。而l=r=1在输出的时候被特判掉了(区间长度<=2,直接输出区间长度),所以他们不会影响到答案