解题报告（ABDEGH/10）
链接：https://ac.nowcoder.com/acm/contest/3002
题目链接：https://ac.nowcoder.com/acm/contest/3002/A
分析：$S=1=\frac{1}{2}\times2\times1$。分形状看一下，每种形状的种数，注意不要算重复了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std ;
typedef long long LL ;
const int mod = 1e9 + 7 ;
int main () {
LL n , m ;
cin >> n >> m ;
LL sum = ( n - 1 ) * ( m - 2 ) % mod * ( m - 2 ) % mod + ( n - 2 ) * ( m - 1 ) % mod * n % mod ;
sum += ( n - 1 ) * ( m - 2 ) % mod * n % mod + ( n - 2 ) * ( m - 1 ) % mod * ( m - 2 ) % mod ;
cout << sum * 2 % mod << endl ;
return 0 ;
}
题目链接：https://ac.nowcoder.com/acm/contest/3002/B
分析：签到题
1
2
3
4
5
6
7
8
9
10
11
#include <bits/stdc++.h>
using namespace std ;
int n , x , a , b ;
int main () {
cin >> n >> x >> a >> b ;
printf ( "%.2f \n " , n * ( x * 1.0 / 100 * a + ( 100 - x ) * 1.0 / 100 * b ));
return 0 ;
}
题目链接：https://ac.nowcoder.com/acm/contest/3002/C
分析：分别将umi和靶子连线与坐标轴的交点存下来，注意不要统计同一象限内的靶子。然后分 $x,y$ 轴，用木板覆盖住 $n-k$ 个交点即可。
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
#include <bits/stdc++.h>
using namespace std ;
double sx , sy ;
int n , k ;
vector < double > vx , vy ;
int main () {
cin >> sx >> sy >> n >> k ;
for ( int i = 0 ; i < n ; i ++ ) {
double a , b ; cin >> a >> b ;
if ( sy * b < 0 ) vx . push_back (( a * sy - b * sx ) / ( sy - b ));
if ( sx * a < 0 ) vy . push_back (( b * sx - a * sy ) / ( sx - a ));
}
sort ( vx . begin (), vx . end ());
sort ( vy . begin (), vy . end ());
// 需要挡住 n - k 个
double ans = 1e18 ;
int len = n - k ;
for ( int l = 0 ; l + len - 1 < vx . size (); l ++ ) {
int r = l + len - 1 ;
ans = min ( ans , vx [ r ] - vx [ l ]);
}
for ( int l = 0 ; l + len - 1 < vy . size (); l ++ ) {
int r = l + len - 1 ;
ans = min ( ans , vy [ r ] - vy [ l ]);
}
if ( ans == 1e18 ) puts ( "-1" );
else printf ( "%f \n " , ans );
return 0 ;
}
题目链接：https://ac.nowcoder.com/acm/contest/3002/D
分析：签到题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std ;
int n ;
unordered_set < int > uset ;
int main () {
cin >> n ;
for ( int i = 0 ; i < n ; i ++ ) {
int x ; cin >> x ;
uset . insert ( x );
}
for ( int i = 1 ; i <= n ; i ++ ) {
if ( ! uset . count ( i )) {
printf ( "%d \n " , i );
break ;
}
}
return 0 ;
}
题目链接：https://ac.nowcoder.com/acm/contest/3002/E
分析：按要求模拟即可，一度怀疑是不是只需要这么做就行了，$AC$ 了就放心了。话说这里不能一个递归写到底啊，MLE 了，用循环来写才行。算因子个数的时候用到了一个定理。
若质因数分解：
$$
N=p_1^{\alpha_1}p_2^{\alpha_2}…p_k^{\alpha_k}
$$
则 $N$ 约数之和：
$$
(\alpha_1+1)(\alpha_2+1)…(\alpha_k+1)
$$
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
#include <bits/stdc++.h>
using namespace std ;
typedef long long LL ;
int res ;
LL f ( LL n ) {
if ( n == 3 ) return 2 ;
unordered_map < int , int > primes ;
for ( LL i = 2 ; i <= n / i ; i ++ ) {
while ( n % i == 0 ) {
n /= i ;
primes [ i ] ++ ;
}
}
if ( n > 1 ) primes [ n ] ++ ;
LL sum = 1 ;
for ( auto item : primes ) sum = sum * ( item . second + 1 );
return sum ;
}
int main () {
LL n ;
cin >> n ;
while ( n != 2 ) {
n = f ( n );
res ++ ;
};
cout << res << endl ;
return 0 ;
}
题目链接：https://ac.nowcoder.com/acm/contest/3002/F
分析：这题好可惜，比赛时没开long long，赛后一看过了 88.89% 的数据，顿悟。
路径取法有 $2$ 种：
做法：对于第 $1$ 种取法，只要统计与每个黑色结点直接相连的白色点个数，求和；对于第 $2$ 种取法，需要统计每个黑色结点直接相连的子树中，以白色结点为根的白色连通块大小，都存到vector<int> temp中，然后任两个连通块之间都可组合。体现在代码 49 ~ 50 行。
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
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>
using namespace std ;
const int N = 100010 , M = 2 * N ;
int n ;
int h [ N ], e [ M ], ne [ M ], idx ;
char str [ N ];
int tag [ N ]; // 0表示白
void add ( int a , int b ) {
e [ idx ] = b , ne [ idx ] = h [ a ], h [ a ] = idx ++ ;
}
// 返回以u为根的子树中，白色点的个数
int dfs ( int u , int fa ) {
int sum = 1 ;
for ( int i = h [ u ]; ~ i ; i = ne [ i ]) {
int j = e [ i ];
if ( j == fa || tag [ j ]) continue ;
int s = dfs ( j , u );
sum += s ;
}
return sum ;
}
int main () {
cin >> n ;
memset ( h , - 1 , sizeof h );
scanf ( "%s" , str + 1 );
for ( int i = 1 ; str [ i ]; i ++ ) tag [ i ] = str [ i ] == 'W' ? 0 : 1 ;
for ( int i = 0 ; i < n - 1 ; i ++ ) {
int a , b ;
scanf ( "%d%d" , & a , & b );
add ( a , b ), add ( b , a );
}
// 从所有黑色点开始搜，白色的子树
long long res = 0 ;
for ( int i = 1 ; i <= n ; i ++ ) {
if ( tag [ i ]) { // 黑色
vector < int > temp ;
for ( int j = h [ i ]; ~ j ; j = ne [ j ]) {
int k = e [ j ];
if ( ! tag [ k ]) { // 搜白色连通块
temp . push_back ( dfs ( k , i ));
}
}
for ( int j = 0 ; j < temp . size (); j ++ ) res += temp [ j ];
for ( int j = 0 ; j < temp . size (); j ++ ) {
for ( int k = j + 1 ; k < temp . size (); k ++ ) {
res += 1ll * temp [ j ] * temp [ k ];
}
}
}
}
cout << res << endl ;
return 0 ;
}
题目链接：https://ac.nowcoder.com/acm/contest/3002/G
分析：二分答案区间 $[k,n]$，$check$ 一下 $mid$ 是否有解即可。统计字母出现次数时可以进行优化，对于长度为 $mid$ 的一段子串来说，首先从 $0$ 枚举左端点 $l$，检验 $[0, mid-1]$ 是否有解，如果无解，那么左端点右移一位，这时候我们发现，整个串右移只会影响 $2$ 个字母，也就是上一轮的左端点，和这一轮的右端点，因此只需要cnt[str[l - 1] - 'a']--; cnt[str[r] - 'a']++; 即可。
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
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std ;
const int N = 200010 ;
int n , k ;
char str [ N ];
int cnt [ 26 ];
// 如果长度为mid有解就返回true
bool check ( int mid ) {
int len = strlen ( str );
for ( int l = 0 ; l + mid - 1 < len ; l ++ ) {
int r = l + mid - 1 ;
if ( l == 0 ) {
for ( int j = l ; j <= r ; j ++ ) {
cnt [ str [ j ] - 'a' ] ++ ;
if ( cnt [ str [ j ] - 'a' ] >= k ) return true ;
}
} else {
cnt [ str [ l - 1 ] - 'a' ] -- ; // 去掉开头
cnt [ str [ r ] - 'a' ] ++ ; // 加上结尾
if ( cnt [ str [ r ] - 'a' ] >= k ) return true ;
}
}
return false ;
}
int main () {
cin >> n >> k ;
scanf ( "%s" , str );
bool has_ans = false ;
for ( int i = 0 ; str [ i ]; i ++ ) {
cnt [ str [ i ] - 'a' ] ++ ;
if ( cnt [ str [ i ] - 'a' ] >= k ) has_ans = true ;
}
if ( ! has_ans ) {
puts ( "-1" );
return 0 ;
}
int l = k , r = n ;
while ( l < r ) {
int mid = l + r >> 1 ;
memset ( cnt , 0 , sizeof cnt );
if ( check ( mid )) r = mid ;
else l = mid + 1 ;
}
cout << l << endl ;
return 0 ;
}
题目链接：https://ac.nowcoder.com/acm/contest/3002/H
分析：这题和上题不是一样的嘛 = =，$26$ 个字母变成只有 $0,1$，还是二分答案区间 $[k,n]$，改改上题代码就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
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std ;
const int N = 200010 ;
int n , k ;
char str [ N ];
int cnt [ 2 ];
// 如果长度为mid有解就返回true
bool check ( int mid ) {
int len = strlen ( str );
for ( int l = 0 ; l + mid - 1 < len ; l ++ ) {
int r = l + mid - 1 ;
if ( l == 0 ) {
for ( int j = l ; j <= r ; j ++ ) cnt [ str [ j ] - '0' ] ++ ;
if ( cnt [ 0 ] <= k || cnt [ 1 ] <= k ) return true ;
} else {
cnt [ str [ l - 1 ] - '0' ] -- ; // 去掉开头
cnt [ str [ r ] - '0' ] ++ ; // 加上结尾
if ( cnt [ 0 ] <= k || cnt [ 1 ] <= k ) return true ;
}
}
return false ;
}
int main () {
cin >> n >> k ;
scanf ( "%s" , str );
for ( int i = 0 ; str [ i ]; i ++ ) cnt [ str [ i ] - '0' ] ++ ;
int l = k , r = n ;
while ( l < r ) {
int mid = l + r + 1 >> 1 ;
memset ( cnt , 0 , sizeof cnt );
if ( check ( mid )) l = mid ;
else r = mid - 1 ;
}
cout << l << endl ;
return 0 ;
}
题目链接：https://ac.nowcoder.com/acm/contest/3002/I
分析：这DP我居然没做！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std ;
typedef long long LL ;
const int N = 300010 ;
LL n , a , b , c ;
LL f [ N ];
string str ;
int main () {
cin >> n >> a >> b >> c >> str ;
str = " " + str ;
for ( int i = 1 ; i <= n ; i ++ ) {
f [ i ] = f [ i - 1 ];
if ( i >= 4 && str . substr ( i - 3 , 4 ) == "nico" ) f [ i ] = max ( f [ i ], f [ i - 4 ] + a );
if ( i >= 6 && str . substr ( i - 5 , 6 ) == "niconi" ) f [ i ] = max ( f [ i ], f [ i - 6 ] + b );
if ( i >= 10 && str . substr ( i - 9 , 10 ) == "niconiconi" ) f [ i ] = max ( f [ i ], f [ i - 10 ] + c );
}
cout << f [ n ] << endl ;
return 0 ;
}
题目链接：https://ac.nowcoder.com/acm/contest/3002/I
分析：当时 F 题 WA 了一次之后就直接来做 J 了，因为 J 提交次数相当多，但是通过率极低（没注意），推了一下，总结出一个公式：
$$
f(n)=x^{fi_{n-2}} \cdot y^{fi_{n-1}} \cdot a^{(fi_n-1)\cdot b} \text{ % mod}
$$
其中 $fi(i)$ 表示斐波那契数列第 $i$ 项。看了数据范围，于是我直接套上矩阵快速幂求斐波那契的板子，然后中间各种模，从此走上一条疯狂调试的不归路。赛后再测，发现通过 80% 了，所以应该是优化不够啊 = =，果然这不是我能做的题啊。有空补题。
感觉有提升余地，DP 还是硬伤，二分最近遇到比较多比较敏感，矩阵快速幂还是昨晚临时学的，虽然今天就是复制粘贴板子。两道字符串标程都不是二分，但都被我二分过了emm。不过感觉自己比半年前刚开始学算法，有点进步啊。
第一场官方说明考点：字符串，贪心，矩阵快速幂，概率论，计算几何，并查集，数论。
