题目链接
https://atcoder.jp/contests/abc125
A – Biscuit Generator
大意
饼干生产线每隔 \(A\) 秒生产 \(B\) 个饼干，求截至 \(C+0.5\) 秒能生产多少饼干。
题解
#include <cstdio>
int main()
{
int a,b,t;
scanf("%d%d%d",&a,&b,&t);
printf("%d\n",t/a*b);
return 0;
}
B – Resale
大意
每颗宝石有一个价值 \(v_i\) 和一个费用 \(c_i\)，最大化总价值和总费用之差。
题解
选价值大于费用的就好。
#include <cstdio>
int v[25],c[25];
int main()
{
int n,ans=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&v[i]);
for(int i=1;i<=n;i++)
scanf("%d",&c[i]);
for(int i=1;i<=n;i++)
if(v[i]>c[i])ans+=v[i]-c[i];
printf("%d\n",ans);
return 0;
}
C – GCD on Blackboard
大意
有若干个数字，你可以修改其中一个数字，最大化这些数字的 GCD。
题解
本题等价于删除一个数字，最大化 GCD 值。
为什么？在序列中添加一个数不可能让 GCD 变大，因此想让 GCD 变大的唯一措施就是删除一个数字。在本题中的措施就是可以将一个数改成序列中已经出现的数字来从实际上删除一个数字。
如何高效地解决这个问题呢？采用类似分治的思想，将问题分为两个子问题。
删除位置为 \(k\) 的一个数字后，序列会分为 \(1 \ldots k-1\) 和 \(k+1 \ldots n\) 两段。因此我们可以采用前缀和的思想预处理出前缀段和后缀段的 GCD，枚举删除某个数字的时候，直接合并前缀段和后缀段这两个子问题的解，就可以解决问题。
#include <cstdio>
#include <algorithm>
using namespace std;
int a[100005],pre[100005],post[100005];
int gcd(int a,int b)
{
return b==0?a:gcd(b,a%b);
}
int main()
{
int n,ans=1;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
pre[1]=a[1],post[n]=a[n];
for(int i=1;i<=n;i++)
pre[i]=gcd(pre[i-1],a[i]);
for(int i=n-1;i;i--)
post[i]=gcd(post[i+1],a[i]);
for(int i=1;i<=n;i++)
ans=max(ans,gcd(pre[i-1],post[i+1]));
printf("%d\n",ans);
return 0;
}
D – Flipping Signs
大意
对一个数列可以执行无数次如下操作，选择一个数 \(i\)，使得 \(a_i,a_{i+1}\) 同时取相反数，最大化序列所有数字之和。
题解
结论题。
如果非正数的个数是偶数个，则可以将所有数都变为非负数。
如果非正数的个数是奇数个，则必有一个数无法变为非负数，此时只需将绝对值最小的数设置为负数即可。
解释是很显然的：每次操作并不会改变非正数个数的奇偶性（要改变的两个数字符号相同时，数量变化的值只是 \(2\)，不会影响奇偶性；要改变的两个数字符号不同时，数量不会变化，当然也不会影响奇偶性），因此假如非正数的个数是偶数，一定存在一种方法让所有数字变成非负整数，否则就一定有一个数字无法变为非负整数。
在后一种情况下，显然我们让绝对值最小的数字设置为负数即可。
#include <iostream>
#include <algorithm>
using namespace std;
long long a[100005],ans,n,cnt;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]<=0)cnt++;
a[i]=abs(a[i]);
}
sort(a+1,a+n+1);
for(int i=2;i<=n;i++)
ans+=a[i];
if(cnt%2)ans-=a[1];
else ans+=a[1];
cout<<ans<<endl;
return 0;
}