【2024秋#114】锦城ACM周测题解
2024秋#114】锦城ACM周测题解
A.awa1
思路
这里是对答案进行二分，我们预测一个答案的范围，取这个范围的中点，试探是否可行。
如果可行，将这个范围的右边的范围缩小到mid(注意我们所求是最短时间，所以当mid可行的时候我们是将预测的最大的值变小)，如果不可行，说明我们预测的这个范围左边部分都不可行，将l变为mid,将我们的预期时间变大
讲讲判断具体是怎么操作的吧:
ans代表我们预测的天数，遍历每一件衣服，如果在预测的天数里面，衣服没能自己风干.则减去风干的湿度，剩下的我们看使用烘干机需要多少天，如果需要烘干机的天数比我们预测的天数还多,相当于每天使用烘干机还没干
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,a,b;
ll s[500010];
bool check(ll ans)
{
ll sum=0;
for(int i=1;i<=n;i++)
if(s[i]>ans*a)
sum+=ceil((s[i]-ans*a)*1.0/b);
if(sum>ans)
return false;
return true;
}
int main()
{
cin>>n>>a>>b;
for(int i=1;i<=n;i++)
cin>>s[i];
sort(s+1,s+1+n);
ll l=0,r=s[n]+1,res=0;
while(l+1!=r)
{
ll mid=(l+r)>>1;
if(check(mid))
{
r=mid;
res=mid;
}
else
l=mid;
}
cout<<r;
return 0;
}
B.awa2
思路
要构造一个排列，那么我们可以先从大到小输出k到n之间的数，因为这样的一个过程中g(i)的始终为0，且f(i)的和最大。
然后输出m+1到k−1之间的数，这里的顺序无所谓，因为对于f(i)和g(i)都没有影响。
最后从小到大输出1到m之间的数即可。因为这样的可以使得g(i)的和最小，结果就最大。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void ac()
{
ll n,m,k;
cin>>n>>m>>k;
for(int i=n;i>=k;i--)
cout<<i<<" ";
for(int i=m+1;i<k;i++)
cout<<i<<" ";
for(int i=1;i<=m;i++)
cout<<i<<" ";
cout<<endl;
}
int main()
{
int t;
cin>>t;
while(t--)
ac();
return 0;
}
C.awa3
思路
我们只用考虑相邻元素之间的差就可以了，因为假如本个元素比上一个小，那么其实这个元素要减的话，上一个元素已经帮你减掉了。假如本个元素比较大，对答案的贡献就是a[i]-a[i-1]
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,op[100005],a[100005];
ll ans=0;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>op[i];
for(int i=1;i<=n;i++)
{
a[i]=op[i]-op[i-1];
if(a[i]>0)
ans+=a[i];
}
cout<<ans;
return 0;
}
D.awa4
思路
一.首先，1,2,3,4,5都可以一次取到，当n=6时，第一个人先取1-5个，无论怎么取，第二个人全去走就赢了。
二.对于6的倍数，一定不能是质数的K次方，证明：先是除2以外的质数都是奇数，而奇数乘奇数都是奇数，故6的倍数全不是n的K次方；对于2，由于6中存在因数3，故6n也不是2的K次方。
三.对于12第一个人取1-5个第二个人直接取到剩下6个，就变成了情况一，第一个人取不到6个，若去6个以上，则直接败；
四.归纳6n。第一个人无法去6的倍数个，第二个人只要将数压倒6*m(m<n就会慢慢推到情况二，就又是第一个人输。
五。对于非6的倍数，第一个人只要去1-5个，使之变成6的倍数，就变成情况四了。
所以，只有当a为六的倍数时，Roy才能赢。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,x;
int main()
{
cin>>n;
while(n--)
{
cin>>x;
if(x%6==0)
cout<<"Roy wins!"<<endl
else
cout<<"October wins!"<<endl
}
return 0;
}
B.awa5
思路
显然暴搜+剪枝
我们可以反向搜索，也就是先选大的
不难发现这样更容易产生更大的答案
然后乱搞搞就过了
点击查看代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,c,ans;
ll op[1005],a[1005];
void dfs(int pos,long long x)
{
if(x>c)return;
if(op[pos-1]+x<=c)
{
ans=max(ans,op[pos-1]+x);
return;
}
ans=max(ans,x);
for(int i=pos-1;i>=1;i--)
dfs(i,x+a[i]);
return;
}
int main()
{
cin>>n>>c;
for(int i=1;i<=n;i++)
{
cin>>a[i];
op[i]=op[i-1]+a[i];
}
dfs(n+1,0);
cout<<ans<<endl;
return 0;
}