正文
标题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颗；
如今小明开始吃糖果，而且每次只吃剩下糖果数量最多的那种，假如有多种则可以恣意选择一种数量最多的糖果；
小明想知道终极，能不能吃完全部糖果，而且满足没有一连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; } 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个字符，能找到的最长even字符串；
那么对于第i个字符，我们有两个选择：
取第i个字符，那么找到迩来一个和第i个字符相近的位置k，我们有dp=max(dp, dp[k-1] + 2)；
不取第i个字符，那么有dp=max(dp, 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 = dp[i - 1]; int index = str - 'a'; if (pos[index]) { // dp = max(dp, dp[pos[index] - 1] + 2); } pos[index] = i; } cout << n - dp[n] << endl; } }}ac;标题4
标题链接
标题大意：
给出n个整数的数组a，其中数组的元素绝对值满足 abs(a) <= 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 < 0) { ++total; } if (abs(a) == 2) { ++cntTotal; } if (a < 0 && !posLeft) { posLeft = i; } if (a < 0) { posRight = i; } } for (int i = left; i <= posLeft; ++i) { if (abs(a) == 2) { ++cntLeft; } } for (int i = posRight; i <= right; ++i) { if (abs(a) == 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); } k = 0; pos[k++]= 0; for (int i = 1; i <= n; ++i) { if (a == 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; // (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[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 + 1); } int total = 0, maxSize = 0; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { total += ('1' == a[j]); } // 从a[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[j]表现区间[i, j]内的+数量，那么countx[j]可以由countx[j-1]来快速盘算；y的盘算同理；
class Solution { static const int N = 3010; char str[N]; int a[N]; int dp[N]; // dp 前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[j] = countx[j - 1] + 1; county[j] = county[j - 1]; } else { countx[j] = countx[j - 1]; county[j] = county[j - 1] + 1; } if (countx[j] == county[j] || ((countx[j] < county[j] && (county[j] - countx[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个字符相加的效果，字符+表现-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的位置并不关心，而且sum的值最多也只有2n+1种大概（取值范围是[-n, n]）；
那么假如我们把sum的效果直接存到[-n, n] 这个区间上，我们就可以直接获取遍历这个区间的值即可。
以n=4为例，sum的效果大概有[-4,-3,-2,-1,0,1,2,3,4]，假如sum[j]=3，那么我们只必要取sum=3/0/-3的值；假如sum[j]=2，那么我们只必要取sum=-1/-4的值；
由于我们只在乎%3的效果，我们可以用cnt[0,1,2]来表现sum%3的值和，如许从数组中取值就不必要遍历，可以很快取到某个余数的值；
但是这里另有一个条件是sum[j] >= sum[i - 1]，sum[j]=0的时间，sum=3这种情况是不允许的，所以cnt的值是必要维护的，维护方式就是：
当我们sum[j]变小的时间，cnt作为累加和，要退掉之前累加的值；
比如说sum[j]=2的时间，cnt累加了[-4, 2]的区间；sum[j+1]=1的时间，cnt累加了[-4, 1]的区间；也就是cnt必要退掉sum[j]=2的值；
由于sum的取值范围是[-n, n] 我们可以将sum+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 == '-' ? 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成绩。
在最应该学习的时间，没有积极学习，那么未来纵然偶尔机也很难超越本身。当年不善于做的数论题，如今仍然不会做。
这让我渐渐明确一个原理：面对困难和挑衅，人在当下的选择，每每会影响后续一辈子。
不是说生存肯定要迎难而上，肯定要吃得苦中苦方为人上人，而是思索和确定本身的目标、选择、动力，然后再积极前行。 |
