2023年9月11日
前面几天去建模，虽然感觉根本过不了。。。。。哎，我们继续回归受制了系列。最近也会总结知识。今天是第二次AK周赛。
ACWING5148 字符串匹配
题目理解，本题是个贪心。题目一点是B串可以随意调整顺序，那就非常EZ了。
- 我们只需要进行对
A串B串做一个字符出现次数的统计 - 先去匹配是否有完全相同的，然后打标记，证明已经被算过了
- 然后再匹配大小写即可
代码实现
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 200, M = 2e5;
int a[N];
int b[N];
string n, m;
bool st[M];
int main()
{
cin >> n >> m;
for(int i = 0 ; i < m.size(); i++)
{
int p = int(m[i]);
b[p]++;
}
int resa = 0, resb = 0;
for(int i = 0 ; i < n.size(); i++)
{
int p = int(n[i]);
if(b[p])
{
resa++;
b[p]--;
st[i] = true;
}
}
for(int i = 0; i < n.size(); i++)
{
if(!st[i])
{
int p = int(n[i]);
if(p < 97 && b[p + 32])
resb++, b[p + 32]--;
else if(p >= 97 && b[p - 32])
resb++, b[p - 32]--;
}
}
cout << resa << " " << resb;
return 0;
}
ACWING5147 数量
题目理解
该题是DFS，我们枚举各种长度的4和7串的组合即可。
代码实现
#include<iostream>
#include<cstring>
using namespace std;
const int N = 10;
int n, u = 1;
int st[N];
int res;
void dfs(int p)
{
if(p == u)
{
int sum = 0;
for(int i = 0; i < p; i++)
sum = sum * 10 + st[i];
if(sum <= n)
res++;
return;
}
st[p] = 4;
dfs(p+1);
st[p] = 7;
dfs(p+1);
}
int main()
{
cin >> n;
int t = n;
while(t)
{
memset(st, 0, sizeof st);
dfs(0);
t /= 10;
u += 1;
}
cout << res;
return 0;
}
最大GCD
题目理解
简单数论？？？应该不算吧，就理解题目，就是n / 2。因为1 ~ n中两数，且不相同的最大公约数就是n / 2。
- 因为最大值是
n，如果n是偶数，那么n的越大公约数就是n / 2。 - 如果
n是奇数，那么就是(n - 1) / 2，int自带下取整，所以就是n / 2。
代码实现
#include<iostream>
using namespace std;
int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; i++)
{
int a;
cin >> a;
cout << a / 2 << endl;
}
return 0;
}
ACWING5201 午餐音乐会
题目理解
对于我来说，这个题非常棒！是我完全没有做过的类型题。该题目需要完成一个目的就是让移动的消耗最少。
这个题的知识点是三分，因为我之前接触的二分，么办法解决，因为我没法确定是往左移损耗最小还是往右移动损耗最小。
我们经过分析题目可以得到如下图示结果：
- 我们可以看出，只有在这个长度为
D的区间，损耗是0，往两边都会增加。是一个下凸函数。 - 下凸函数有个性质，就是多个下凸函数求和，仍为下凸函数。
- 然后我们就可得到总的损耗变化趋势，如下图。
- 得到这个趋势，我们取三等分点。我们首先规定，左边的三等分点一定是大于等于右边的三等分点。那么就会有以下两种情况。
很明显根据图示，橘色部分一定不会是答案，那么就可以把我的左边界，赋值为左三等分点！！ - 右三等分点的情况相同。可以将右三等分点右边的部分去掉！那么最后就可以找到答案啦！！
这个题非常不错！学到了新东西！
代码实现
#include<iostream>
#include<cmath>
using namespace std;
const long long N = 2e5 + 10;
long long p[N], w[N], D[N];
int n;
int l = 0, r = 1e9;
long long check(long long u)
{
long long sum = 0;
for(long long i = 1; i <= n; i++)
{
if(abs(p[i] - u) > D[i])
{
if(u >= p[i])
sum += w[i] * (u - p[i] - D[i]);
else
sum += w[i] * (p[i] - u - D[i]);
}
}
return sum;
}
int main()
{
cin >> n;
for(long long i = 1; i <= n; i++)
cin >> p[i] >> w[i] >> D[i];
while (l <= r)
{
int midl = l + (r - l) / 3;
int midr = r - (r - l) / 3;
if (check(midl) <= check(midr)) r = midr - 1;
else l = midl + 1;
}
cout << min(check(l), check(r));
return 0;
}