源代码:ACM/OpenjudgeNow/Codeforces at master · abmcar/ACM (github.com)
更好的阅读体验: Codeforces Round #780 (Div. 3) (全题解) - Abmcar’s 茶水间
(头一次知道全A是绿色的
A. Vasya and Coins 题目大意: 思路:思考如果没有1硬币,则只能支付2的倍数的金额,1无法支付
若有一个1硬币和无限2硬币,则任意金额都可支付
1 = 1 1 = 1 1=1
2 = 2 2 = 2 2=2
3 = 2 + 1 3 = 2 + 1 3=2+1
4 = 2 + 2 4 = 2 + 2 4=2+2
5 = 2 + 2 + 1 5 = 2 + 2 + 1 5=2+2+1
因此,最大金额能支付的金额为a+2*b
最大不能支付的金额为 a + 2 ∗ b + 1 a+2*b+1 a+2∗b+1
代码:void solution()
{
long long a, b;
cin >> a >> b;
if (a == 0)
cout << 1 << endl;
else
cout << a + 2 * b + 1 << endl;
}
B. Vlad and Candies
题目大意:
思路:
该题都难点在于读题
题目中说会优先选择“the most frequent”的蛋糕,这里的意思是取最大的蛋糕
之后,我们再来想一下什么情况下是NO
如果当前最大的蛋糕只有一个,大小为maxn,如果第二大的蛋糕大小为maxn-1,那么这两个蛋糕可以来回吃,但如果更小的话,则必须连续吃2口
因此判断蛋糕中大小为maxn和maxn-1的数量,若大于等于2个,则可以,否则不行
代码:void solution()
{
int n;
cin >> n;
map vis;
int tmp;
int maxn;
maxn = 0;
for (int i = 1; i <= n; i++)
{
cin >> tmp;
maxn = max(maxn, tmp);
vis[tmp]++;
}
if (vis[maxn] + vis[maxn - 1] >= 2 || maxn == 1)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
C. Get an Even String
题目大意:
思路:
我们使用类似dp的方法,用M[it]表示最长的一个以it结尾的非偶数串
用ans表示当前能达到的最大的偶数串
之后遍历字符串,若M[it] > ans,则更新ans为M[it]
否则,更新M[it] = ans + 2
最后得到的ans,即为最长偶数串
代码:void solution()
{
string oriS;
cin >> oriS;
int ans = 0;
map<char, int> M;
for (char it: oriS)
{
if (M[it] > ans)
{
ans = max(ans,M[it]);
M[it] = 0;
}else
{
M[it] = ans+2;
}
}
cout << oriS.size()-ans << endl;
}
D. Maximum Product Strikes Back
题目大意:
思路:
首先我们知道0一定不能取,因此需要按0分割区间
思考一下如果没有0该怎么解决这个问题?
怎么在一个区间内找价值最大的一个子区间,很容易想到一个滑动窗口的问题,但是这个问题并不是简单的加减,因此我们不能随意舍弃任何一个有贡献的数,由此,我们使用双指针,按照类似单调队列的方式不断去最大值
值得注意的是,由于数据过大,我们不能真的去算具体结果,只能存乘2的数量
代码:void solution()
{
int n;
cin >> n;
vector<int> nums(n);
int tmp = 0;
for (int i = 0; i < n; i++)
{
cin >> nums[i];
if (nums[i] == 0)
tmp++;
}
if (tmp == n)
{
cout << n << " 0" << endl;
return;
}
int maxn = 0;
int l = n;
int r = 0;
int nowf = true;
int nowAns = 0;
deque<pair<int, int>> Q;
for (int i = 0; i < n; i++)
{
if (nums[i] == 0)
{
while (!Q.empty())
{
if (Q.front().first < 0)
nowf = !nowf;
if (abs(Q.front().first) == 2)
nowAns--;
if (nowf && nowAns > maxn)
{
maxn = nowAns;
l = Q.front().second+1;
r = n - Q.back().second - 1;
}
Q.pop_front();
}
nowAns = 0;
}
else
{
if (Q.empty())
{
if (nums[i] < 0)
nowf = false;
else
nowf = true;
if (abs(nums[i]) == 2)
nowAns = 1;
else
nowAns = 0;
}
else
{
if (nums[i] < 0)
nowf = !nowf;
if (abs(nums[i]) == 2)
nowAns++;
}
Q.push_back({ nums[i], i });
if (nowf && nowAns > maxn)
{
maxn = nowAns;
l = Q.front().second;
r = n - Q.back().second - 1;
}
}
}
while (!Q.empty())
{
if (Q.front().first < 0)
nowf = !nowf;
if (abs(Q.front().first) == 2)
nowAns--;
if (nowf && nowAns > maxn)
{
maxn = nowAns;
l = Q.front().second+1;
r = n - Q.back().second - 1;
}
Q.pop_front();
}
cout << l << " " << r << endl;
}
E. Matrix and Shifts
题目大意:
思路:
(感觉这个比D题简单
写过八皇后的人应该都知道,不论怎么平移,对应的对角线不会变化
因此枚举n条对角线中1的数量,取最大的一条对角线即可
答案为对角线上0的数量和非对角线上1的数量
代码:void solution()
{
int n;
cin >> n;
vector<string> bd(n+1);
for (int i = 1; i <= n; i++)
{
cin >> bd[i];
bd[i] = "-" + bd[i];
}
int tot1 = 0;
vector<int> nums(n+1);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (bd[i][j] == '1')
{
tot1++;
if (i-j >= 0)
nums[i-j]++;
else
nums[n-(j-i)]++;
}
int maxn = 0;
for (int i = 0; i <= n; i++)
maxn = max(maxn,nums[i]);
// cout << maxn << endl;
cout << n-maxn+(tot1-maxn) << endl;
}
F2. Promising String (hard version)
题目大意:
思路:
F1F2一起写了这里
思考一下那些字符串符合要求
- 字符串中+数量和-数量相等的
- 字符串中-的数量比+的数量大3*k的
如何快速得知前缀当中有多少个符合条件的字符串呢?
可以先求一遍前缀和,之后可以看某个位置之前有多少个数等于当前位置的前缀和,有多少个数,就有多少个子串,但此时,还没有考虑-较多的情况
我们可以直接令前缀和%3,看之前有多少个%3之后和他相等的数,但同时,另一个前缀和相等的位置的前缀和应当小于后一个前缀和,因为我们只要-较多的情况,不要+较多的情况
对于这个问题,我们可以使用树状数组来实现,类似求逆序对
代码:template<typename T>
class Fenwick
{
public:
Fenwick()
{
}
Fenwick(int _n) : n(_n)
{
fenw.resize(n + 1);
}
void resize(int _n)
{
n = _n;
fenw.clear();
fenw.resize(_n + 1);
}
void modifty(int x, T val)
{
while (x <= n)
{
fenw[x] += val;
x |= (x + 1);
}
}
T get(int x)
{
T cnt{};
while (x >= 0)
{
cnt += fenw[x];
x = (x & (x + 1)) - 1;
}
return cnt;
}
private:
vector<T> fenw;
int n;
};
void solution()
{
int n;
string s;
cin >> n >> s;
vector<int> preAns(n + 1);
int minn = 0;
for (int i = 0; i < n; i++)
{
preAns[i + 1] = preAns[i] + (s[i] == '-' ? 1 : -1);
minn = min(preAns[i + 1], minn);
}
minn = minn * -1;
Fenwick<int> fen[3];
for (int i = 0; i < 3; i++)
fen[i].resize(n + minn + 1);
int ans = 0;
for (int i = 0; i <= n; i++)
{
int tmp = abs((preAns[i] + minn) % 3);
ans += fen[tmp].get(preAns[i] + minn);
fen[tmp].modifty(preAns[i] + minn, 1);
}
cout << ans << endl;
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)