Codeforces Round 540 (Div. 3)(补题)

A. Water Buying(贪心)

胡乱分析

实际上没有什么难的,如果你用一种方案那么就要用到底,因为这只有两种情况方案一合适或者方案二合适,然后分n的奇偶性来输出即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)
{
long long n,a,b;
cin>>n>>a>>b;
if(n&1)
cout<<min(n*a,(n/2)*b+a)<<"\n";
else
cout<<min((n/2)*b,n*a)<<"\n";
}
}

今天早上我又用刚学的js来了一波,js弱数据类型语言第一次接触对他的判别有点不熟悉导致出现了一个小bug最终也调好了

代码

1
2
3
4
5
6
7
8
9
var n=parseInt(readline());
for(var i=0;i<n;i++)
{
var s=readline().split(' ');
if(s[0]%2==0)
print(Math.min(s[0]*s[1],(s[0]/2)*s[2]));
else
print(Math.min(s[0]*s[1],Math.floor(s[0]/2)*s[2]+parseInt(s[1])));
}

B. Tanya and Candies(思维)

胡乱分析

上来寻思了一阵最终得到了和出题人一样的思路奇数偶数项去掉的话奇数偶数会倒置所以根据这个特性来判断即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;
long long num[666666];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
long long sum1=0,sum2=0,sum11=0,sum22=0,ans=0,now1=0,now2=0;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>num[i];
if(i&1)
sum1+=num[i];
else
sum2+=num[i];
}
sum11=sum1;sum22=sum2;
for(int i=1;i<=n;i++)
{
if(i&1)
sum1-=num[i];
else
sum2-=num[i];
if(now1+sum2==now2+sum1)
ans++;
if(i&1)
now1+=num[i];
else
now2+=num[i];
}
cout<<ans;
}

C. Palindromic Matrix(数学&&模拟)

这个题目前还有争议主要就是出的有点复杂并且难度有点高,我现在也没有搞懂

D1. Coffee and Coursework (Easy version)(贪心)

胡乱分析

当时有点贪心的太容易了导致了wa,我最初想的是要都喝了然后如果不行留下当前天数的喝的数然后再继续循环喝完的操作但是实际上只留下一杯是远远的不够贪心的这里用一种非常简单的方法即可枚举出来留下合适的杯数

1
2
3
for(int i=1;i<=n;i++)
for(int j=0;j<n;j++)
sum+=max(0,num[j]-j/i);

看着是非常的奇怪但是实际上这种方法能够保证计算出最优的答案,因为j如果不是i的倍数那么会一直累加到之前的天数上并且发生了自己应当的变化
真的太美妙了!!!

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m;
cin>>n>>m;
vector<int> num(n+10);
for(int i=1;i<=n;i++)
cin>>num[i];
sort(num.rbegin(),num.rend());
for(int i=1;i<=n;i++)
{
int sum=0;
for(int j=0;j<n;j++)
sum+=max(0,num[j]-j/i);
if(sum>=m)
return cout<<i,0;
}
cout<<-1;
}

D2. Coffee and Coursework (Hard Version)(贪心&&二分)

胡乱分析

跟第D1不一样的地方就是限制了O(n2)的算法,那么对于这种能够靠条件判断出范围的问题我们可以用二分搜索来减少时间复杂度
这里也是又对二分有了一些理解并且也准备以后按照MikeMirzayanov的写法进行书写

1
2
3
4
5
6
7
8
9
10
while(r-l>precision) //这里的precision是一个精度可以如果是整数那么就是1,小数的话保留小数位数向上一位即可
{
int mid=(l+r)>>1; //如果是小数的话改成double
if(check(mid))
//转换边界
else
//转换边界

//这里的转换边界看是要求一个范围内的最小值还是最大值,最小值的话就是缩小右边界否则就是缩小左边界
}

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;
vector<int> num(666666);
int n,m;
int check(int x)
{
long long sum=0;
for(int i=0;i<n;i++)
sum+=max(0,num[i]-i/x);
return sum>=m;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>num[i];
sort(num.rbegin(),num.rend());
int l=1,r=n;
while(r-l>1)
{
int mid=(r+l)>>1;
if(check(mid))
r=mid;
else
l=mid;
}
if(check(l))
cout<<l;
else if(check(r))
cout<<r;
else
cout<<-1;
}
就算是一分钱,也是对作者极大的支持
------ 本文结束 ------

版权声明

Baccano by baccano is licensed under a Creative Commons BY-NC-ND 4.0 International License.
baccano创作并维护的Baccano博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证
本文首发于baccano 博客( http://baccano.fun ),版权所有,侵权必究。

小游戏

---小游戏:要不要来选择一下自己可能的老婆?---

简易发声器

---简易的七键钢琴插件---

可以使用鼠标点击琴键也可以使用主键盘1-7或者小键盘的1-7来操作

那么现在开始吧

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
0%