Codeforces Round 867 (Div. 3)
A:ABCD (E差一点点,最后把那种特殊情况想出来然后没写上去就结束了)
A. TubeTube Feed
题意：给两个数组分别是时间和价值，要价值最大但是只能选一个
思路：最开始以为是01背包，结果只选一个，一个一个枚举就行
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, t;
cin >> n >> t;
vector<int> a(n + 1);
vector<int> b(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) cin >> b[i];
int maxx = 0, ans = -1;
for (int i = 1; i <= n; i++) {
int x = a[i], y = b[i];
int tt = i - 1 + x;
if (tt <= t) {
if (y > maxx) {
ans = i;
maxx = y;
}
}
}
cout << ans << '\n';
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
B. Karina and Array
题意：两个数乘积最大
思路：分为两种情况负数×负数，正数×正数
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int x1 = 0, x2 = 0, y1 = 0, y2 = 0;//x表示正数y表示负数
int n;
cin >> n;
if (n == 2) {
int a, b;
cin >> a >> b;
cout << a * b << "\n";
return;
}
for (int i = 0; i < n; i++) {
int a;
cin >> a;
if (a > 0 && a > x1 && a <= x2) {
x1 = a;
} else if (a > 0 && a > x2) {
x1 = x2;
x2 = a;
} else if (a < 0 && a < y1 && a >= y2) {
y1 = a;
} else if (a < 0 && a < y2) {
y1 = y2;
y2 = a;
}
}
cout << max(x1 * x2, y1 * y2) << "\n";
}
signed main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
C. Bun Lover
题意：就是求棕色图案的长度
思路：慢慢找规律面向样例编程
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n;
cin >> n;
cout << n * (n + 1) + n + 2 << "\n";
}
signed main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
D. Super-Permutation
题意：给一个n，b[i]=(a[1]+...+a[i]) mod n,b如果也是一个排列那么a就是超级排列，输出a
思路：当n是奇数的时候，最后一个数求和应该是
$$
b[i]=(n+1)*n/2; b[i]mod n=0
$$
所以此时b是不可能为一个排列的
$$
确定n的位置因为 x mod n=(x+n) mod n 所以n必须处在第一位
$$
并且x和n-x不能连续排列，那么就1，n-2...这样排列
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAX = 2e5 + 10;
bool st[MAX];
void solve() {
int n;
cin >> n;
if (n == 1) {
cout << "1\n";
return;
}
if (n % 2) {
cout << "-1\n";
return;
}
for (int i = 1; i <= n; i++) {
if (i % 2) {
cout << n - i + 1 << " ";
} else {
cout << i - 1 << " ";
}
}
}
signed main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
E. Making Anti-Palindromes
题意：反排列：a[i]!=a[n-i-1]
操作：交换两个数；目标：整个数组都是反排列
思路：有两种情况直接不行1.他是奇数的话中间那个数始终与自身相等
2.若整个排列中有超过一半的数都是相同的也不行
剩下的就可以变成反排列，操作次数：应该为总次数的一般
注意：相同的是不能互相变化的（最后就是被这里卡了一下）
#include <bits/stdc++.h>
using namespace std;
#define int long long
int x[26], y[26];
const int MAX = 2e5 + 10;
char a[MAX];
void solve() {
int n;
memset(x, 0, sizeof(x));
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
x[a[i] - 'a']++;
}
if (n % 2) {
cout << "-1\n";
return;
}
int ma = *max_element(x, x + 26);
if (ma > n / 2) {
cout << "-1\n";
return;
}
int sum = 0;
memset(y, 0, sizeof(y));
for (int i = 0; i < n / 2; i++) {
if (a[i] == a[n - i - 1]) {
y[a[i] - 'a']++;
sum++;
}
}
int mx = *max_element(y, y + 26);
if (mx <= sum / 2) {
cout << (sum + 1) / 2 << '\n';
} else {
cout << mx << '\n';
}
}
signed main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
F. Gardening Friends
后面在补大概思路就是bfs+树形dp
板子(bfs):
queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);
while (q.size())
{
int t = q.front();
q.pop();
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j])
{
st[j] = true; // 表示点j已经被遍历过
q.push(j);
}
}
}