Fork me on GitHub

[AtCoder Beginner Contest 144]题解

我菜爆了😢

9x9

思路

签到题,直接判断一下两个数的大小即可.

代码

1
2
3
4
5
6
7
8
9
10
11
#include <bits/stdc++.h>
using namespace std;
int main ( void ) {
int a , b;
cin >> a >> b;
if ( a >= 1 && a <= 9 && b >= 1 && b <= 9 )
cout << a * b << endl;
else
cout << "-1" << endl;
return 0;
}

81

思路

从$2$枚举到$9$然后判断一下另一半是否小于$10$即可,注意$1$的情况.

代码

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 ( void ) {
int a , b;
cin >> a;
if ( a == 1 ) {
cout << "Yes" << endl;
return 0;
}
for ( int i = 2 ; i <= 9 ; i++ )
if ( a % i == 0 ) {
if ( a / i <= 9 && a / i >= 1 ) {
cout << "Yes" << endl;
return 0;
}
}
cout << "No" << endl;
return 0;
}

Walk on Multiplication Table

思路

我们可以在$\sqrt{n}$的时间内枚举出每个数的因数,然后对于每个因子判断一下是否可以更新答案即可.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
int main ( void ) {
long long a;
cin >> a;
if ( a == 1 ) {
cout << "0" << endl;
return 0;
}
long long ans = 1e16;
for ( int i = 1 ; i <= sqrt ( a ) ; i++ ) {
if ( a % i == 0 )
ans = min ( ans , ( i - 1 ) + ( a / i ) - 1 );
}
cout << ans << endl;
return 0;
}

Water Bottle

思路

根据生活常识,我们发现如果把杯子倾斜,水能洒出来的话,从这个杯子的剖面去看,一共会有两种情况:剖面是个梯形与剖面是个三角形.
而又因为当只有本来杯子内水的体积占用了原来杯子的体积的一半以上时剖面才会是个梯形,所以我们可以分两种情况分别讨论.
我们将剖面画出来,然后发现这个图形的面积$S \times a$即为水的体积$x$,所以我们就可以算出来可变边的长度,再根据反三角函数计算出本来的解是多少.

弧度转角度: 角度=弧度$ \times 180 / Π$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
double a,b,x;
double Rad_to_deg = 45.0 / atan(1.0);
int main ( void ) {
cin>>a>>b>>x;
if ( x >= ( a * a * b ) / 2 ) {
double C = 2.0 * b - ( 2.0 * x / ( a * a ) );
double hu = atan ( a / C );
hu = hu * Rad_to_deg * 1.0;
printf ( "%.10lf\n" , 90.0000000 - hu );
}
else {
double A = ( 2.0 * x ) / ( a * b );
double hu = atan ( A / b );
hu = hu * Rad_to_deg * 1.0;
printf ( "%.10lf\n" , 90.0000000 - hu );
}
return 0;
}

Gluttony

思路

根据我们的直觉,我们把$A$数组从小到大排序,然后把$F$数组从大到小排序,这样的话答案一定是最优的请自行证明.
然后我们考虑怎么统计答案,显然,题目中要求最大值最小,所以我们可以二分这个最大值$mid$,然后对于每一组$A_i$与$F_i$,我们设$cnt_i$为使这组$A_i \times B_i <= mid$时需要的锻炼次数.
然后我们就可以列出$F_i \times ( A_i - cnt_i ) <= mid $ , 即$cnt_i = max ( 0 , A_i - mid / F_i )$.

代码

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
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read () {
int s = 0 , w = 1;
char ch = getchar ();
while ( ch > '9' || ch < '0' ) { if ( ch == '-' ) w = -1; ch = getchar ();}
while ( ch >= '0' && ch <= '9' ) { s = s * 10 + ch - '0'; ch = getchar ();}
return s * w;
}
const int N = 2e5 + 10;
int n , k;
int A[N] , F[N];
inline bool cmp ( int x , int y ) {
return x > y;
}
inline bool check ( int mid ) {
int cnt = 0;
for ( int i = 1 ; i <= n ; i++ )
cnt += max ( 0ll , A[i] - mid / F[i] );
if ( cnt <= k )
return true;
else
return false;
}
signed main ( void ) {
n = read () , k = read ();
for ( int i = 1 ; i <= n ; i++ )
A[i] = read ();
for ( int i = 1 ; i <= n ; i++ )
F[i] = read ();
sort ( A + 1 , A + 1 + n );
sort ( F + 1 , F + 1 + n , cmp );

int l = 0 , r = 1e16;

while ( l <= r ) {
int mid = ( l + r ) >> 1;
if ( check ( mid ) )
r = mid - 1;
else
l = mid + 1;
}
printf ( "%lld\n" , l );
return 0;
}
因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:[AtCoder Beginner Contest 144]题解

文章作者:KRrrrrrrrr

发布时间:2019年10月28日 - 09:10

最后更新:2019年10月28日 - 15:10

原始链接:http://krrrr.xyz/2019/10/28/AtcoderABC144题解/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。