解题报告(ABDEG/10)
链接:https://ac.nowcoder.com/acm/contest/3003
A. 做游戏题目链接:https://ac.nowcoder.com/acm/contest/3003/A
分析:签到题
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std ;
typedef long long LL ;
LL a , b , c , x , y , z ;
int main () {
cin >> a >> b >> c >> x >> y >> z ;
cout << ( min ( a , y ) + min ( b , z ) + min ( c , x )) << endl ;
return 0 ;
}
B. 排数字题目链接:https://ac.nowcoder.com/acm/contest/3003/B
分析:贪心,拼“61616161...”就行了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std ;
int n ;
string s ;
int one , six ;
int main () {
cin >> n >> s ;
for ( int i = 0 ; i < n ; i ++ ) {
if ( s [ i ] == '1' ) one ++ ;
else if ( s [ i ] == '6' ) six ++ ;
}
int res = 0 ;
if ( six >= 2 && one >= 1 ) {
res ++ , six -= 2 , one -- ;
while ( six && one ) res ++ , six -- , one -- ;
}
cout << res << endl ;
return 0 ;
}
C. 算概率题目链接:https://ac.nowcoder.com/acm/contest/3003/C
分析:
D. 数三角题目链接:https://ac.nowcoder.com/acm/contest/3003/D
分析:暴力枚举,判钝角三角形,结果还因为精度问题WA了几次。
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
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std ;
typedef pair < int , int > PII ;
const int N = 510 ;
int n ;
PII p [ N ];
double dist ( PII a , PII b ) {
int dx = a . x - b . x , dy = a . y - b . y ;
return sqrt ( 1.0 * dx * dx + 1.0 * dy * dy );
}
bool check ( int x , int y , int z ) {
PII a = p [ x ], b = p [ y ], c = p [ z ];
double ab = dist ( a , b );
double bc = dist ( b , c );
double ac = dist ( a , c );
if (( a . x == b . x && a . x == c . x ) || ( a . y == b . y && a . y == c . y )) return false ;
if (( ab + bc <= ac ) || ( ab + ac <= bc ) || ( bc + ac <= ab )) return false ;
if (( ab * ab - bc * bc - ac * ac > 1e-6 ) || ( bc * bc - ab * ab - ac * ac > 1e-6 ) || ( ac * ac - bc * bc - ab * ab > 1e-6 )) return true ;
return false ;
}
int main () {
cin >> n ;
for ( int i = 1 ; i <= n ; i ++ ) scanf ( "%d%d" , & p [ i ]. x , & p [ i ]. y );
int res = 0 ;
for ( int i = 1 ; i <= n ; i ++ ) {
for ( int j = i + 1 ; j <= n ; j ++ ) {
for ( int k = j + 1 ; k <= n ; k ++ ) {
if ( check ( i , j , k )) res ++ ;
}
}
}
cout << res << endl ;
return 0 ;
}
E. 做计数题目链接:https://ac.nowcoder.com/acm/contest/3003/E
分析:推一下公式可得,$2\sqrt {i \times j}=k-i-j$,即 $i \times j$ 为完全平方数,只要在 $i \times j \le n$ 的限制下枚举即可。需要考虑 $i,j$ 的大小关系。
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 () {
int n ;
cin >> n ;
long long res = 0 ;
for ( int i = 1 ; i <= n / i ; i ++ ) {
for ( int j = 1 ; j < i ; j ++ ) {
if ( i * i % j == 0 ) res ++ ;
}
}
res = res * 2 + ( int ) sqrt ( n );
cout << res << endl ;
return 0 ;
}
F. 拿物品题目链接:https://ac.nowcoder.com/acm/contest/3003/F
分析:
G. 判正误题目链接:https://ac.nowcoder.com/acm/contest/3003/G
分析:碰运气,直接看快速幂取模后等式是否成立,模数用1e9+7就WA,用1e9+9就AC。
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
#include <bits/stdc++.h>
using namespace std ;
typedef long long LL ;
const int mod = 1e9 + 9 ;
int qmi ( int a , int k ) {
int res = 1 % mod ;
while ( k ) {
if ( k & 1 ) res = ( LL ) res * a % mod ;
k >>= 1 ;
a = ( LL ) a * a % mod ;
}
return res ;
}
int main () {
int T ;
cin >> T ;
while ( T -- ) {
int a , b , c , d , e , f , g ;
cin >> a >> b >> c >> d >> e >> f >> g ;
int p1 = qmi ( a , d ), p2 = qmi ( b , e ), p3 = qmi ( c , f );
if ((( p1 + p2 ) % mod + p3 ) % mod == g % mod ) puts ( "Yes" );
else puts ( "No" );
}
return 0 ;
}
H. 求函数题目链接:https://ac.nowcoder.com/acm/contest/3003/H
分析:
总结挺难的一场,枯。
第三场官方说明考点:枚举,贪心,DP,数论,思维,数据结构,哈希