Codeforces Round #507 (Div. 2, based on Olympiad of Metropolises)
A. Palindrome Dance
Description:
A group of n dancers rehearses a performance for the closing ceremony. The dancers are arranged in a row, they’ve studied their dancing moves and can’t change positions. For some of them, a white dancing suit is already bought, for some of them — a black one, and for the rest the suit will be bought in the future.
On the day when the suits were to be bought, the director was told that the participants of the olympiad will be happy if the colors of the suits on the scene will form a palindrome. A palindrome is a sequence that is the same when read from left to right and when read from right to left. The director liked the idea, and she wants to buy suits so that the color of the leftmost dancer’s suit is the same as the color of the rightmost dancer’s suit, the 2nd left is the same as 2nd right, and so on.
The director knows how many burls it costs to buy a white suit, and how many burls to buy a black suit. You need to find out whether it is possible to buy suits to form a palindrome, and if it’s possible, what’s the minimal cost of doing so. Remember that dancers can not change positions, and due to bureaucratic reasons it is not allowed to buy new suits for the dancers who already have suits, even if it reduces the overall spending.
Input:
The first line contains three integers n, a, and b ( 1≤n≤20, 1≤a,b≤100) — the number of dancers, the cost of a white suit, and the cost of a black suit.
The next line contains n numbers ci, i-th of which denotes the color of the suit of the i-th dancer. Number 0 denotes the white color, 1 — the black color, and 2 denotes that a suit for this dancer is still to be bought.
Output
If it is not possible to form a palindrome without swapping dancers and buying new suits for those who have one, then output -1. Otherwise, output the minimal price to get the desired visual effect.
Sample Input:
5 100 1
0 1 2 1 2
Sample Output:
101
Sample Input:
3 10 12
1 2 0
Sample Output:
-1
Sample Input:
3 12 1
0 1 0
Sample Output:
0
题目链接
求通过将数列中的2改变为0或1把数列改变为对称数列的最小化费，若对应位置的数字已固定则直接加相应的花费值，否则取两者最小化费即可。
AC代码:
#include <bits/stdc++.h>
using namespace std;
int main(int argc, char *argv[]) {
int N, A, B;
scanf("%d%d%d", &N, &A, &B);
vector<int> Suit(N, 2);
for (int i = 0; i < N; ++i) {
scanf("%d", &Suit[i]);
}
bool Flag = true;
int Cnt = 0, Ans = 0;;
int Mid = N / 2;
for (int i = 0; i < Mid; ++i) {
if (Suit[i] == 2) {
if (Suit[N - i - 1] == 0) {
Ans += A;
}
else if (Suit[N - i - 1] == 1) {
Ans += B;
}
else {
if (Suit[N - i - 1] == 2) {
Cnt += 2;
}
else {
Cnt++;
}
}
}
else if (Suit[N - i - 1] == 2) {
if (Suit[i] == 0) {
Ans += A;
}
else if (Suit[i] == 1) {
Ans += B;
}
else {
if (Suit[i] == 2) {
Cnt += 2;
}
else {
Cnt++;
}
}
}
else if (Suit[i] != Suit[N - i - 1]) {
Flag = false;
}
}
Ans += Cnt * min(A, B);
if ((N & 1) && Suit[(N + 1) / 2 - 1] == 2) {
Ans += min(A, B);
}
Ans = Flag ? Ans : -1;
printf("%d\n", Ans);
return 0;
}
B. Shashlik Cooking
Description:
Long story short, shashlik is Miroslav’s favorite food. Shashlik is prepared on several skewers simultaneously. There are two states for each skewer: initial and turned over.
This time Miroslav laid out n skewers parallel to each other, and enumerated them with consecutive integers from 1 to n in order from left to right. For better cooking, he puts them quite close to each other, so when he turns skewer number i, it leads to turning k closest skewers from each side of the skewer i, that is, skewers number i−k, i−k+1, …, i−1, i+1, …, i+k−1, i+k (if they exist).
For example, let n=6 and k=1. When Miroslav turns skewer number 3, then skewers with numbers 2, 3, and 4 will come up turned over. If after that he turns skewer number 1, then skewers number 1, 3, and 4 will be turned over, while skewer number 2 will be in the initial position (because it is turned again).
As we said before, the art of cooking requires perfect timing, so Miroslav wants to turn over all n skewers with the minimal possible number of actions. For example, for the above example n=6 and k=1, two turnings are sufficient: he can turn over skewers number 2 and 5.
Help Miroslav turn over all n skewers.
Input:
The first line contains two integers n and k ( 1≤n≤1000, 0≤k≤1000) — the number of skewers and the number of skewers from each side that are turned in one step.
Output
The first line should contain integer l — the minimum number of actions needed by Miroslav to turn over all n skewers. After than print l integers from 1 to n denoting the number of the skewer that is to be turned over at the corresponding step.
Sample Input:
7 2
Sample Output:
2
1 6
Sample Input:
5 1
Sample Output:
2
1 4
题目链接
先用 K×2+1的覆盖范围尽可能的覆盖数列中的数，最后剩下的部分判断是否能直接通过最左侧（或最右侧）覆盖点的位置调整覆盖，若不能则去掉一个范围完全覆盖点，在两侧通过覆盖点位置调整进行覆盖。
AC代码:
#include <bits/stdc++.h>
using namespace std;
int main(int argc, char *argv[]) {
int N, K;
scanf("%d%d", &N, &K);
int Scope = K * 2 + 1;
int Cnt = N / Scope;
int Judge = N - Cnt * Scope;
if (Scope >= N) {
if (K >= N) {
printf("%d\n", 1);
printf("%d", 1);
}
else {
printf("%d\n", 1);
printf("%d", K + 1);
}
}
else if (Judge == 0) {
printf("%d\n", Cnt);
for (int i = K + 1, k = 1; k <= Cnt; i += Scope, ++k) {
printf("%d ", i);
}
}
else if (Judge >= K + 1 && Judge < Scope) {
printf("%d\n", Cnt + 1);
printf("%d ", Judge - K);
for (int i = Judge - K + Scope, k = 1; k <= Cnt; i += Scope, ++k) {
printf("%d ", i);
}
}
else if (Judge < K + 1) {
Cnt--;
Judge += Scope;
int A = 0, B = 0;
while (A < K + 1 && Judge > 0) {
A++;
Judge--;
}
while (B < K + 1 && Judge > 0) {
B++;
Judge--;
}
if (Judge > 0) {
while (A < Scope && Judge > 0) {
A++;
Judge--;
}
while (B < Scope && Judge > 0) {
B++;
Judge--;
}
}
printf("%d\n", Cnt + 2);
printf("%d ", A - K);
for (int i = A - K + Scope, k = 1; k <= Cnt; i += Scope, ++k) {
printf("%d ", i);
}
printf("%d ", N - (B - K) + 1);
}
printf("\n");
return 0;
}
投递蚂蚁集团等公司10个岗位 >
