Codeforces Round 984 (Div. 3)——题解
A Quintomania
思路：暴力
B Startup
题意: 给你n个货架 和m种品牌的饮料
每个货架上只能放一种牌子，问最大利润是多少
思路:贪心 建立一个vector p(m)
以品牌号为数组下标，将相同的牌子累加，最后sort降序排序，加上前n个即可
注意点: 货架数和饮料种类数找最小值 当最后的相加次数 例如 1000 1 1 10000 的情况
AC 代码
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
long long n, k,b,c;
cin >> n >> k;
n=min(n, k);
vector<int>p(k);
for (int i = 0; i < k; i++)
{
cin >> b >> c;
b--;
p[b] += c;
}
sort(p.rbegin(),p.rend()); //排好倒着输出 从而降序排序
long long ans = 0;
for (int i = 0; i < n; i++)
{
ans += p[i];
}
cout << ans << endl;
}
return 0;
}
C Anya and 1100
题意: 指定一个数组位置q,将它换成u，然后查看数组中是否存在1100字符串，
如果有就输出YES,否则输出NO
数据量很大 2⋅1E5 最初想法是暴力遍历所有数据，找1100，果不其然超时了
学习其他人的思路后，最后才发现还是想法太简单。
1.不需要每次都遍历所有数据，只需要查看q-3到q+3这段范围的改变前后的1100增减情况
加上cnt的总和只要大于0即可
优点：极大减少了查询次数，而cnt我们也只用每次接受字符串时预处理一次即可
2.确定查询的左右范围
for(int i=max(0,q-3);i<=min(q,len-4),i++)
max(0,q-3) 确定左边的开始位置
min(q,len-4) 确定右边的结束位置
完美的解决了边界问题
3.优化
if(s[q]!=u)
{
执行计算;
}
如果输入的u等于了s[q]那结果不会被影响，就没有计算的必要
AC 代码
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
string s;
int n, cnt = 0;
int len=0;
cin >> s;
cin >> n;
len = s.length();
for (int i = 0; i < len - 3; i++)
{
cnt += s.substr(i, 4) == "1100"; //预处理1100的个数
}
while (n--)
{
int q;
char u;
cin >> q >> u;
q--;
if (s[q] != u)
{
for (int i = max(0, q - 3); i <= min(q, (len - 4)); i++)
{
cnt -= s.substr(i, 4) == "1100";
}
s[q] = u;
for (int i = max(0, q - 3); i <= min(q, (len - 4)); i++)
{
cnt += s.substr(i, 4) == "1100";
}
}
if (cnt)
{
cout << "YES" << endl;
}
else
{
cout << "NO" << endl;
}
}
}
return 0;
}
