Daily Practice 8th：Codeforces Round #750 (Div. 2)

VP*8；

rating：800--900--1200--1600--2000

A. Luntik and Concerts

给出一分钟的歌曲a首，两分钟的歌曲b首，三分钟的歌曲c首，怎样把这些歌分配到两场音乐会，使得两场音乐会的时间差最小，求这个最小的时间差。

思路：把所有时间求和之后除以二，这个时间一定可以用这些歌凑起来，我们可以先选三分钟的，然后再选2分钟的，再选一分钟的，选完之后把歌的总数减去，用剩下的歌的时间总和和前面操作凑的那一半作差。

AC Code：

#include <bits/stdc++.h>
#pragma GCC optimize(2)template <typename T>
inline void read(T &x) {x = 0;int f = 1;char ch = getchar();while (!isdigit(ch)) {if (ch == '-')f = -1;ch = getchar();}while (isdigit(ch)) {x = x * 10 + ch - '0', ch = getchar();}x *= f;
}template <typename T>
void write(T x) {if (x < 0)putchar('-'), x = -x;if (x > 9)write(x / 10);putchar(x % 10 + '0');
}#define INF 0x3f3f3f3f
typedef long long ll;
const double PI = acos(-1);
const double eps = 1e-6;
const int mod = 1e9 + 7;
const int N = 1e6 + 5;
int t;
ll a, b, c;int main() {
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);std::ios::sync_with_stdio(false);std::cin.tie(0);std::cin >> t;while (t--) {ll sum = 0;std::cin >> a >> b >> c;sum = a * 1 + b * 2 + c * 3;ll cnt = (sum + 1) / 2, ans = cnt;if (cnt >= c * 3) {cnt -= c * 3;c = 0;} else if (cnt < c * 3) {ll aa = cnt / 3;cnt %= 3;c -= aa;}
//		std::cout << cnt << '\n';
//		std::cout << a << ' ' << b << ' ' << c << '\n';if (cnt >= b * 2) {cnt -= b * 2;b = 0;} else if (cnt < 2 * b) {ll bb = cnt / 2;cnt %= 2;b -= bb;}
//		std::cout << cnt << '\n';
//		std::cout << a << ' ' << b << ' ' << c << '\n';if (cnt >= a) {cnt -= a;a = 0;} else if (cnt < a) {ll cc = cnt;cnt %= 1;a -= cc;}
//		std::cout << a << ' ' << b << ' ' << c << '\n';std::cout << abs(ans - a - b * 2 - c * 3) << '\n';}return 0;
}

B. Luntik and Subsequences

给出一个数列，有多少种选择子序列的方法，使得子序列的和等于全部元素和-1。

思路：若序列里没有1，则不可能存在满足条件的子序列；有1，每次选择子序列都要少选一个1，再考虑0的个数，因为0在满足条件的子序列中是可选可不选，计算0的个数tot，计算1的个数cnt，答案就是cnt*2^tot。

AC Code：

#include <bits/stdc++.h>
#pragma GCC optimize(2)template <typename T>
inline void read(T &x) {x = 0;int f = 1;char ch = getchar();while (!isdigit(ch)) {if (ch == '-')f = -1;ch = getchar();}while (isdigit(ch)) {x = x * 10 + ch - '0', ch = getchar();}x *= f;
}template <typename T>
void write(T x) {if (x < 0)putchar('-'), x = -x;if (x > 9)write(x / 10);putchar(x % 10 + '0');
}#define INF 0x3f3f3f3f
typedef long long ll;
const double PI = acos(-1);
const double eps = 1e-6;
const int mod = 1e9 + 7;
const int N = 65;
ll t, n, a[N];ll pmod(ll a,ll b){ll res=1;while(b){if(b&1) res=res*a;b>>=1;a=a*a;}return res;
}int main() {
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);std::ios::sync_with_stdio(false);std::cin.tie(0);std::cin >> t;while (t--) {std::cin >> n;ll cnt = 0, tot = 0;for (int i = 1; i <= n; i++) {std::cin >> a[i];if (a[i] == 1)cnt++;if (a[i] == 0)tot++;}if (cnt == 0) {std::cout << 0 << '\n';continue;}std::cout << cnt*pmod(2,tot) << '\n';}return 0;
}

C. Grandma Capa Knits a Scarf

给出一个字符串，问是否可以通过去掉某个字母的一部分使得字符串成为回文列。

思路：删除的字符只能是26个字母中其中一个，所以遍历26个字母，找到删除的最少的就可以；定义双指针，每换一个字母，就将双指针放置于字符串两侧，若所指字母相同，则分别++、--，若不同，则比较与当前字母的关系，对于某些无法将字符串处理成回文串的字母，可以直接break。

AC Code：

#include <bits/stdc++.h>
#pragma GCC optimize(2)template <typename T>
inline void read(T &x) {x = 0;int f = 1;char ch = getchar();while (!isdigit(ch)) {if (ch == '-')f = -1;ch = getchar();}while (isdigit(ch)) {x = x * 10 + ch - '0', ch = getchar();}x *= f;
}template <typename T>
void write(T x) {if (x < 0)putchar('-'), x = -x;if (x > 9)write(x / 10);putchar(x % 10 + '0');
}#define INF 0x3f3f3f3f
typedef long long ll;
const double PI = acos(-1);
const double eps = 1e-6;
const int mod = 1e9 + 7;
const int N = 65;
int t, n;
std::string s;int main() {
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);std::ios::sync_with_stdio(false);std::cin.tie(0);std::cin >> t;while (t--) {std::cin >> n >> s;int ans = n + 1;for (int c = 0; c < 26; c++) {int l = 0, r = n - 1, cnt = 0;while (l <= r) {if (s[l] == s[r]) {l++, r--;} else if (s[l] == (char)('a' + c)) {cnt++, l++;} else if (s[r] == (char)('a' + c)) {cnt++, r--;} else {cnt = n + 1;break;}}ans = std::min(ans, cnt);}if (ans == n + 1)ans = -1;std::cout << ans << '\n';}return 0;
}

os：双指针还是不行www

D. Vupsen, Pupsen and 0

给出一个不含0的数组a，构造一个数组b，使得两个数组对应项的乘积之和为0，且数组b中不含0。

思路：偶数则两两分组，使这两个数乘积和为0；若是奇数，剩下三个数字，选择相加不为0的两个数看成1个，和另一个进行偶数一样的操作即可。

AC Code：

#include <bits/stdc++.h>
#pragma GCC optimize(2)template <typename T>
inline void read(T &x) {x = 0;int f = 1;char ch = getchar();while (!isdigit(ch)) {if (ch == '-')f = -1;ch = getchar();}while (isdigit(ch)) {x = x * 10 + ch - '0', ch = getchar();}x *= f;
}template <typename T>
void write(T x) {if (x < 0)putchar('-'), x = -x;if (x > 9)write(x / 10);putchar(x % 10 + '0');
}#define INF 0x3f3f3f3f
typedef long long ll;
const double PI = acos(-1);
const double eps = 1e-6;
const int mod = 1e9 + 7;
const int N = 1e5 + 5;
int t, n, a[N], b[N];int main() {
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);std::ios::sync_with_stdio(false);std::cin.tie(0);std::cin >> t;while (t--) {std::cin >> n ;for (int i = 1; i <= n; i++) {std::cin >> a[i];}if (n % 2 == 0) {for (int i = 1; i <= n ; i += 2) {if (a[i] > 0 && a[i + 1] > 0) {b[i] = a[i + 1];b[i + 1] =  - a[i];} else if (a[i] > 0) {b[i] = abs(a[i + 1]);b[i + 1] = a[i];} else if (a[i + 1] > 0) {b[i] = a[i + 1];b[i + 1] = abs(a[i]);} else {b[i] = a[i + 1];b[i + 1] = abs(a[i]);}}} else {for (int i = 1; i <= n - 4; i += 2) {if (a[i] > 0 && a[i + 1] > 0) {b[i] = a[i + 1];b[i + 1] = 0 - a[i];} else if (a[i] > 0) {b[i] = abs(a[i + 1]);b[i + 1] = a[i];} else if (a[i + 1] > 0) {b[i] = a[i + 1];b[i + 1] = abs(a[i]);} else {b[i] = a[i + 1];b[i + 1] = abs(a[i]);}}if (a[n - 2] + a[n - 1] != 0) {b[n] = a[n - 2] + a[n - 1];b[n - 1] = b[n - 2] = -a[n];} else if (a[n - 1] + a[n] != 0) {b[n - 2] = a[n - 1] + a[n];b[n] = b[n - 1] = -a[n - 2];} else if (a[n - 2] + a[n] != 0) {b[n - 1] = a[n - 2] + a[n];b[n] = b[n - 2] = -a[n - 1];}}for (int i = 1; i <= n; i++) {std::cout << b[i] << " \n"[i == n];}}return 0;
}

os：感觉似乎并不难想，，，但是不看题解还是没有思路。。。

E. Pchelyonok and Segments

给出一个数组a，选择一个k，从头开始选取子串，第一个子串长为k，依次递减，直到第k个长度为1，并满足选取的子串和依次递减，求最大的k。

思路：DP，不过是倒序来处理，前缀和预处理数组，计算长度为k时的最优解，要满足条件dif[i+j-1]-dif[i-1]<f[i+1][j]，从f[i+1][j]向f[i][j]转移。

AC Code：

#include <bits/stdc++.h>
#pragma GCC optimize(2)template <typename T>
inline void read(T &x) {x = 0;int f = 1;char ch = getchar();while (!isdigit(ch)) {if (ch == '-')f = -1;ch = getchar();}while (isdigit(ch)) {x = x * 10 + ch - '0', ch = getchar();}x *= f;
}template <typename T>
void write(T x) {if (x < 0)putchar('-'), x = -x;if (x > 9)write(x / 10);putchar(x % 10 + '0');
}#define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
const double PI = acos(-1);
const double eps = 1e-6;
const int mod = 1e9 + 7;
const int N = 1e5 + 5;
int t, n;
ll a[N], dif[N], f[N][500];int main() {
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);std::ios::sync_with_stdio(false);std::cin.tie(0);std::cin >> t;while (t--) {std::cin >> n ;memset(dif, 0, sizeof(dif));for (int i = 1; i <= n; i++) {std::cin >> a[i];dif[i] = dif[i - 1] + a[i];}int k = 0;while (k * (k + 1) / 2 <= n)++k;for (int j = 0; j <= k; j++) {f[n + 1][j] = -INF;}f[n + 1][0] = INF;for (int i = n; i >= 1; i--) {for (int j = 0; j < k; j++) {f[i][j] = f[i + 1][j];if (j && i + j - 1 <= n && dif[i + j - 1] - dif[i - 1] < f[i + j][j - 1])f[i][j] = std::max(f[i][j], dif[i + j - 1] - dif[i - 1]);}}int ans = 0;for (int j = 0; j < k; j++) {if (f[1][j] > 0)ans = j;}std::cout << ans << '\n';}return 0;
}

有些题的处理方法看上去很简单，但是为什么赛时就想不到嘞

若有错误请指教，谢谢！

orzorz