程序员进阶之算法练习（六十二）AK练习
程序员进阶之算法练习（六十二）AK练习
正文
题目1
题目链接 题目大意： 小明有a个1元硬币，b个2元硬币； 小明想要购买一个商品，并且不想找零； 现在小明想知道自己无法给到最低价格是多少；
比如说1个1元硬币，1个2元硬币，最低价格就是4元； 比如说0个1元硬币，1个2元硬币，最低价格就是1元；（不能找零）
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤1e4) 每个样例一行，整数 𝑎𝑖 and 𝑏𝑖 (0≤𝑎𝑖,𝑏𝑖≤1e8)
输出： 每个样例一行，输出最低价格；
Examples input 5 1 1 4 0 0 2 0 0 2314 2374
output 4 5 1 1 7063
题目解析： 如果有1元硬币，那么必然可以给到a+2*b价格内的所有整数； 如果没有1元硬币，那么1元就无法给到；
class Solution {
static const int N = 201010;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int x, y;
cin >> x >> y;
cout << (x > 0 ? x+1+2*y : 1) << endl;
}
}
}
ac;题目2
题目链接 题目大意： 小明有n种糖果，每种糖果分别有a[i]颗； 现在小明开始吃糖果，并且每次只吃剩下糖果数量最多的那种，如果有多种则可以任意选择一种数量最多的糖果；
小明想知道最终，能不能吃完所有糖果，并且满足没有连续2天吃到一样的糖果；
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤1e4) 每个样例两行，第一行整数 𝑛 (1≤𝑛≤2⋅1e5) 第二行是n个整数𝑎𝑖 (1≤𝑎𝑖≤1e9)
输出： 每个样例一行，如果可以输出YES，如果不行则输出NO；
Examples input 4 aabbcc aaab aaa abba
output 0 2 1 2
题目解析： 因为题目限定了每次只吃数量最多的糖果，那么可以将数组排序，这样方便后续抉择； 我们唯一能选的，就是当出现两种糖果一样多情况，我们要如何吃； 容易知道，假如有两个糖果一样多，只要交替吃就行了； 那么问题就变成，最多和次最多的两个糖果，能不能顺利达到数量一致的情况； 容易知道相差超过1就无法达到，因为需要连续两天吃一样的最多数量的糖果。
class Solution {
static const int N = 201010;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
sort(a, a + n);
bool ans = 0;
if (n == 1) {
ans = a[0] <= 1;
}
else {
ans = (a[n - 1] - a[n - 2]) <= 1;
}
cout << (ans ? "YES" : "NO") << endl;
}
}
}
ac;题目3
题目链接 题目大意： 字符串s可以成为偶字符串，如果字符串满足： 1、字符串的长度为偶数； 2、所有奇数位的字符𝑎[𝑖]，满足𝑎[𝑖]=𝑎[𝑖+1]；
比如说“aa”、“aabb”、“aabbcc”就是偶字符串，但是“aaa”、“aaab”、“abba”就不是偶字符串； 现在想知道，最少移除掉字符串s中多少个字符，可以使得字符串s变成偶字符串；
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤1e4) 每个样例一行，字符串 𝑠 (1≤|𝑠|≤2⋅105),
输出： 每个样例一行，输出最少移除的字符串；
Examples input 4 aabbcc aaab aaa abba
output 0 2 1 2
题目解析：
dp[i] 表示前i个字符，能找到的最长even字符串； 那么对于第i个字符，我们有两个选择： 取第i个字符，那么找到最近一个和第i个字符相近的位置k，我们有dp[i]=max(dp[i], dp[k-1] + 2)； 不取第i个字符，那么有dp[i]=max(dp[i], dp[i - 1])；
class Solution {
static const int N = 201010;
char str[N];
int dp[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
cin >> (str + 1);
int n = strlen(str + 1);
int pos[26] = {0};
for (int i = 1; i <= n; ++i) {
dp[i] = dp[i - 1];
int index = str[i] - 'a';
if (pos[index]) { //
dp[i] = max(dp[i], dp[pos[index] - 1] + 2);
}
pos[index] = i;
}
cout << n - dp[n] << endl;
}
}
}
ac;题目4
题目链接 题目大意： 给出n个整数的数组a，其中数组的元素绝对值满足 abs(a[i]) <= 2； 现在可以移除数组前面x个元素和后面y的个元素，求剩下的元素乘积尽可能的大；
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤1e4) 每个样例两行，第一行是整数𝑛 (1≤𝑛≤2⋅1e5) 接下来是n个整数𝑎1,𝑎2,…,𝑎𝑛 (|𝑎𝑖|≤2)；
输出： 每个样例一行，包括整数x和y，x和y分别表示：移除数组前面x个元素和后面y的个元素； 允许移除所有的元素，这样乘积为1； 如果有多个答案，输出任意一个；
Examples input 5 4 1 2 -1 2 3 1 1 -2 5 2 0 -2 2 -1 3 -2 -1 -1 3 -1 -2 -2
output
0 2 3 0 2 0 0 1 1 0
题目解析： 题目的要求是乘积尽可能大，那么数字0首先被排除，因为0乘以任意数字都0，而移除所有元素的乘积结果都是1； 那么按照0，将数组切分成若干段，题目变成了在某一个子区间[left, right]中，寻找乘积最大的子区间； 假如区间[left, right]没有负数，或者有偶数个负数，那么这个区间所有数字的乘积就是最大的； 假如区间[left, right]有奇数个负数，那么肯定是去掉最左边的负数（假如位置是posLeft），或者去掉最右边的负数（假如位置是posRight）； 这样就可以得到区间[left, right]的最大乘积；
由于乘积会比较大，这里只需要统计2和-2的数量即可，这个结果越大，则乘积越大。
class Solution {
static const int N = 201010;
int a[N];
int ansTotal, ansLeft, ansRight;
int pos[N], k;
void find(int left, int right) {
int total = 0, posLeft = 0, posRight = right;
int cntTotal = 0, cntLeft = 0, cntRight = 0;
for (int i = left; i <= right; ++i) {
if (a[i] < 0) {
++total;
}
if (abs(a[i]) == 2) {
++cntTotal;
}
if (a[i] < 0 && !posLeft) {
posLeft = i;
}
if (a[i] < 0) {
posRight = i;
}
}
for (int i = left; i <= posLeft; ++i) {
if (abs(a[i]) == 2) {
++cntLeft;
}
}
for (int i = posRight; i <= right; ++i) {
if (abs(a[i]) == 2) {
++cntRight;
}
}
if (total % 2 == 0) {
if (cntTotal > ansTotal) {
ansTotal = cntTotal;
ansLeft = left;
ansRight = right;
}
}
else {
if (cntLeft < cntRight) {
cntTotal -= cntLeft;
if (cntTotal > ansTotal) {
ansTotal = cntTotal;
ansLeft = posLeft + 1;
ansRight = right;
}
}
else {
cntTotal -= cntRight;
if (cntTotal > ansTotal) {
ansTotal = cntTotal;
ansLeft = left;
ansRight = posRight - 1;
}
}
}
}
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
k = 0;
pos[k++]= 0;
for (int i = 1; i <= n; ++i) {
if (a[i] == 0) { //
pos[k++] = i;
}
}
pos[k++] = n + 1;
ansTotal = 0;
ansLeft = 1;
ansRight = 0;
for (int i = 1; i < k; ++i) {
int l = pos[i - 1];
int r = pos[i]; // (l, r)
find(l + 1, r - 1);
}
cout << ansLeft - 1 << " " << (n - ansRight) << endl;
}
}
}
ac;题目5
题目链接 题目大意： 给出一个n x n的矩阵，矩阵由数字0和1组成； 现在可以对矩阵进行下列操作： 1、将数组的每一行向上移动； 2、将数组的每一行向下移动； 2、将数组的每一列向左移动； 2、将数组的每一列向右移动； 这个操作是没有代价的，可以进行任意次； 然后还可以对矩阵中任何一个数字进行异或（XOR）操作，这个操作的代价是1；
现在想要把整个矩阵变成单元矩阵，问最小的代价是多少； （单元矩阵是一个对角线为非零元素，其它元素为零的方形矩阵）
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤1e4) 每个样例两行，第一行是整数𝑛 (1≤𝑛≤2000) 接下来是n x n的01矩阵；
输出： 每个样例一行，输出最小的代价。
Examples input 4
3 010 011 100
5 00010 00001 10000 01000 00100
2 10 10
4 1111 1011 1111 1111 output 1 0 2 11
题目解析： 题目的要求是构造单元矩阵的代价最小，那么需要尽可能利用无代价的4个位移操作； 以简单的3阶矩阵来分析，对于矩阵 010 001 010 我们可以拼接4个矩阵，得到 010 010 001 001 010 010 ---------- 010 010 001 001 010 010
以左移一列为例，结果就是图中左上角的2-4列，如下： 0 100 0 010 0 100
按照这个思路，其实就是在4个n x n矩阵拼出来的大矩阵中，找到一个n x n子矩阵，并且斜对角线的1尽可能多； 那么就直接从每一行的第一列开始向右下角遍历，保持长度为n的斜对角线，存在尽可能多的1； 但是直接拼接4个矩阵去模拟，整体实现复杂度比较高；对于第i行第j列的元素a[i][j]，右下角其实就是a[i+1][j+1]，其中： j是从1到n，因为每行的遍历都是从最左开始； i可能会存在大于n的情况，此时可以对n取模，保证数组不越界；
假设对角线上最多的1数量为maxSize，矩阵中所有1的数量是totalSize； 那么答案就是ans=(total - maxSize) + (n - maxSize) 。
class Solution {
static const int N = 3010;
char a[N][N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> (a[i] + 1);
}
int total = 0, maxSize = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
total += ('1' == a[i][j]);
}
// 从a[i][1]开始，向右下角遍历
int tmpSize = 0;
for (int k = 0; k < n; ++k) {
int x = (i - 1 + k) % n + 1;
int y = 1 + k;
// cout << x << " " << y << endl;
if (a[x][y] == '1') {
++tmpSize;
}
}
maxSize = max(maxSize, tmpSize);
}
cout << (total - maxSize) + (n - maxSize) << endl;
}
}
}
ac;题目6
题目链接 题目大意： 给出由+和-组成的字符串，我们称字符串为平衡的字符串，假如+和-的字符是相同的； 现在可以对字符串执行操作，每次将两个相邻的-号合并为+号； 假如若干次操作之后，字符串变成了平衡的字符串，那么这个字符串可以称之为特殊的字符串；
现在给出长度为n的字符串，问字符串中有多少子串是特殊的；
输入： 第一行，整数𝑡 表示t个样例 (1≤𝑡≤500) 每个样例两行，第一行是整数 𝑛 (1≤𝑛≤3000) 第二行是字符串；
输出： 输出满足要求的子串数量；
Examples input 5 3 +-+ 5 -+--- 4 ---- 7 --+---+ 6 +++--- output 2 4 2 7 4
题目解析：
这是easy难度，题目给出来的范围比较小；
那么可以使用最暴力的办法，O(N*N)的复杂度，枚举所有字符串的子串；
再分别计算这个子串是否符合要求；
判断一个字符串是否是特殊的，可以遍历整个字符串中+和-的数量（假如总数是x和y）；
如果x==y，或者x<y并且(y-x)%3==0 && (y-x)%3 < z，则子串满足要求。
统计x或者y是一个比较快的过程，用countx[i][j]表示区间[i, j]内的+数量，那么countx[i][j]可以由countx[i][j-1]来快速计算；y的计算同理；
class Solution {
static const int N = 3010;
char str[N];
int a[N];
int dp[N]; // dp[i] 前i个字符，以i结尾，并且x==y的子串数量
int countx[N][N], county[N][N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
cin >> (str + 1);
// 如果x==y，或者x<y并且`(y-x)%3==0
int ans = 0;
for (int i = 1; i <= n; ++i) {
for (int j = i; j <= n; ++j) {
if (str[j] == '+') {
countx[i][j] = countx[i][j - 1] + 1;
county[i][j] = county[i][j - 1];
}
else {
countx[i][j] = countx[i][j - 1];
county[i][j] = county[i][j - 1] + 1;
}
if (countx[i][j] == county[i][j] || ((countx[i][j] < county[i][j] && (county[i][j] - countx[i][j]) % 3 == 0))) {
++ans;
}
}
}
cout << ans << endl;
}
}
}
ac;题目7
题目链接 题目大意： 给出由+和-组成的字符串，我们称字符串为平衡的字符串，假如+和-的字符是相同的； 现在可以对字符串执行操作，每次将两个相邻的-号合并为+号；假如若干次操作之后，字符串变成了平衡的字符串，那么这个字符串可以称之为特殊的字符串；
现在给出长度为n的字符串，问字符串中有多少子串是特殊的；
输入： 第一行，整数𝑡 表示t个样例 每个样例两行，第一行是整数𝑛 第二行是字符串；
输出： 输出满足要求的子串数量；
Examples input 5 3 +-+ 5 -+--- 4 ---- 7 --+---+ 6 +++--- output 2 4 2 7 4
题目解析： 这是hard难度，题目给出来的范围比较大，O(N*N)的复杂度枚举所有字符串的子串的方式已经不适用； 首先需要对我们已经采用的方法进行简化，countx和county其实可以简化为countx-county的方式，并且由二维简化为一维： 我们用sum[i]表示前i个字符相加的结果，字符+表示-1，字符-表示+1； 那么子串[i, j]可以用sum[j] - sum[i - 1]的方式快速得到结果，(sum[j] - sum[i - 1])%3==0 && sum[j] >= sum[i - 1] 表示有解；
从左到右遍历字符串，对于第j个字符，首先得到sum[j]，然后遍历i∈[1, j-1]判断 (sum[j] - sum[i - 1])%3==0 && sum[j] >= sum[i - 1] 的数量； 这个遍历过程存在较多重复计算，我们只在乎i∈[1, j-1]这个区间中sum[i]的值，而对i的位置并不关心，并且sum[i]的值最多也只有2n+1种可能（取值范围是[-n, n]）； 那么如果我们把sum[i]的结果直接存到[-n, n] 这个区间上，我们就可以直接获取遍历这个区间的值即可。 以n=4为例，sum[i]的结果可能有[-4,-3,-2,-1,0,1,2,3,4]，如果sum[j]=3，那么我们只需要取sum[i]=3/0/-3的值；如果sum[j]=2，那么我们只需要取sum[i]=-1/-4的值； 由于我们只在乎%3的结果，我们可以用cnt[0,1,2]来表示sum[i]%3的值和，这样从数组中取值就不需要遍历，可以很快取到某个余数的值；
但是这里还有一个条件是sum[j] >= sum[i - 1]，sum[j]=0的时候，sum[i]=3这种情况是不允许的，所以cnt的值是需要维护的，维护方式就是： 当我们sum[j]变小的时候，cnt作为累加和，要退掉之前累加的值； 比如说sum[j]=2的时候，cnt累加了[-4, 2]的区间；sum[j+1]=1的时候，cnt累加了[-4, 1]的区间；也就是cnt需要退掉sum[j]=2的值；
由于sum[i]的取值范围是[-n, n] 我们可以将sum[i]+n，这样取值范围变成[0, 2n]，好处是可以用数组来表示，并且不影响我们对结果的结算，因为 (sum[j] - sum[i - 1])等于 (sum[j] + n）-（sum[i-1] + n），sum[j] >= sum[i-1] 等于 sum[j] + n >= sum[i-1] + n；
class Solution {
static const int N = 200010;
char str[N];
int sum[N * 2];
int cnt[3];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
cin >> (str + 1);
lld ans = 0;
int preCount = n;
memset(cnt, 0, sizeof(cnt));
memset(sum, 0, sizeof(sum));
sum[preCount] = 1;
cnt[preCount % 3] = 1;
for (int i = 1; i <= n; ++i) {
int curCount = preCount + (str[i] == '-' ? 1 : -1);
int index = curCount % 3;
if (curCount < preCount) {
cnt[preCount % 3] -= sum[preCount];
}
else {
cnt[curCount % 3] += sum[curCount];
}
ans += cnt[index % 3];
cnt[curCount % 3]++;
sum[curCount]++;
preCount = curCount;
}
cout << ans << endl;
}
}
}
ac;总结
趁着假日闲暇时光以及工作间隙，把1660CF的7个题目都AC了。 有一丝成就感，毕竟已经是退役接近十年的选手；也有一丝挫败感，在毕业多年之后，水平已经变成只能在DIV3达成AK成就。 在最应该学习的时候，没有努力学习，那么未来即使有机会也很难超越自己。当年不擅长做的数论题，现在依旧不会做。 这让我逐渐明白一个道理：面对困难和挑战，人在当下的选择，往往会影响后续一辈子。 不是说生活一定要迎难而上，一定要吃得苦中苦方为人上人，而是思考和确定自己的目标、选择、动力，然后再努力前行。
腾讯云开发者
