CF#581 (div2)题解

CF#581 题解

A BowWow and the Timetable

如果不是4幂次方直接看位数除以二向上取整,否则再减一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
using namespace std;
#define MAXN 200006
int n , m , A[MAXN];
char ch[MAXN];
int main() {
scanf("%s",ch);
int len = strlen( ch );
int flg = 0;
for( int i = 1 ; i < len ; ++ i ) if( ch[i] != '0' ) { flg = 1; break; }
if( ! flg ) cout << len / 2;
else cout << ( len + 1 ) / 2;
}

B Mislove Has Lost an Array

贪心做

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
using namespace std;
#define MAXN 200006
int n , l , r;
int main() {
cin >> n >> l >> r;
int mn , mx; mn = mx = 0;
for( int i = l - 1 ; i >= 0 ; -- i ) mn += ( 1 << i );
mn += ( n - l );
for( int i = r - 1 ; i >= 0 ; -- i ) mx += ( 1 << i );
mx += ( n - r ) * ( 1 << r - 1 );
cout << mn << ' ' << mx << endl;
}

Anna, Svyatoslav and Maps

直接在给定path上跑,贪心一下,如果当前点到下个点距离不到在path中的距离,加入这个点然后把当前点设置成这个点

最后一个点必须加入(

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#define mem( a ) memset( a , 0x3f , sizeof a )
#define MAXN 1000016
using namespace std;
int ans[MAXN] , pre[MAXN] , G[106][106];
int n , m , dat[MAXN];
char str[3000];
void print(int ps) {
if (!ps) return;
print(pre[ps]);
printf("%d ", dat[ps]);
}
int main() {
mem( ans ); mem( G );
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%s", str + 1);
for (int j = 1; j <= n; ++j)if (str[j] == '1')
G[i][j] = 1;
}
for (int k = 1; k <= n; ++k)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) if (i != j)
G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
ans[1] = 0;
scanf("%d", &m);
for (int i = 1; i <= m; ++i) scanf("%d", &dat[i]);
for (int i = 2; i <= m; ++i)
for (int j = 1; j <= n; ++j)
if ( i - G[j][dat[i]] > 0 && dat[i - G[j][dat[i]]] == j && ans[i - G[j][dat[i]]] + 1 < ans[i] ) {
ans[i] = ans[i - G[j][dat[i]]] + 1;
pre[i] = i - G[j][dat[i]];
}
printf("%d\n", ans[m] + 1);
print(m);
}

D1 & D2 Kirk and a Binary String

首先,最优解一定是把原来的某些1变成0

假设在某种情况下,可以把0变成1

  • 如果它左右有一个位置是0,那么肯定不能变成1,否则答案+1
  • 如果左右都是1,那么也不能变成1,不然总长度+1

定义一个序列是fixed的,满足一下条件:

  • 10是fixed的。

  • p是fixed,那么1p0是fixed的。

  • p、q是fixed,那么pq是fixed

很容易发现,fixed的子段有几个性质,首先1和0的个数一样,每个段中最长不降一定是长度的一半(可以通过全部选0或者选1做到)并且fixed的子段一定不能1变0(任意变最长不降数量一定增加)

那么可以把一个fixed的子段看做一个可变的数,它既可以是0也可以是1,这种子段直接删掉就好了。不断重复删除直到序列中没有剩下的fixed的子段,也就一定形成了0…01…1的形式,这个时候这些1一定都是可以删除的。其实最后形成的序列是非fixed的序列组成的一个不降序列,在这个的基础上把fixed的序列添加进去,并且fixed的序列跟着这个序列取就行了,如果我们把这个序列全部变0,显然fixed的序列就全部选0就好了。

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<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<stack>
using namespace std;
#define MAXN 100006
char ch[MAXN];
int n , book[MAXN];
stack<pair<char,int> > S;
int main() {
scanf("%s",ch);
n = strlen( ch );
for( int i = 0 ; i < n ; ++ i )
if( ch[i] == '0' && !S.empty() && S.top().first == '1' ) S.pop();
else S.push( make_pair( ch[i] , i ) );
while( !S.empty() ) {
if( S.top().first == '1' ) book[S.top().second] = 1;
S.pop();
}
for( int i = 0 ; i < n ; ++ i )
putchar( book[i] ? '0' : ch[i] );
}

Natasha, Sasha and the Prefix Sums

可以假设k[x][y]表示x个1y个-1使得最大前缀和小于等于0的情况总数。考虑dp转移,当x > y的时候,显然k的值是0,否则,我们一定可以在最后放一个-1或者1使得这个序列最大前缀和仍然小于等于0。所以有$k[x][y]=k[x-1][y]+k[x][y-1]$

然后设dp数组,dp[x][y]是x个1y个-1的答案。

对于这个dp我们考虑从前面添加数的两种转移:

  • 添加一个1,显然对于所有方案答案都要增加1,那么增加的总数就是总排列数,也就是一个组合数$\left(\begin{array}{c}{x+y-1} \ {y}\end{array}\right)$(相当于是一个插板法)
  • 添加一个-1,对于方案不是完全小于等于0的的所有方案都要给答案-1。具体来说,减少了$\left(\begin{array}{c}{x+y-1} \ {x}\end{array}\right)-k[x][y-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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<stack>
using namespace std;
#define int long long
#define MAXN 2006
#define P 998244853
int k[MAXN][MAXN] , dp[MAXN][MAXN];
int J[MAXN * 10] , inv[MAXN * 10] , invJ[MAXN * 10];
int n , m;
int C( int x , int y ) {
return J[x] * invJ[y] % P * invJ[x - y] % P;
}
signed main() {
cin >> n >> m;
inv[0] = inv[1] = J[0] = invJ[0] = J[1] = invJ[1] = 1;
for( int i = 2; i < 10 * MAXN ; ++ i ) J[i] = J[i - 1] * i , J[i] %= P , inv[i] = ( P - P/i )*inv[P%i] % P , invJ[i] = inv[i] * invJ[i - 1] % P;
for( int i = 0 ; i <= m ; ++ i ) k[0][i] = 1;
for( int i = 1 ; i <= n ; ++ i )
for( int j = 1 ; j <= m ; ++ j ) if( i <= j )
k[i][j] = k[i - 1][j] + k[i][j - 1] , k[i][j] %= P;
for( int i = 0 ; i <= n ; ++ i ) dp[i][0] = i;
for( int i = 1 ; i <= n ; ++ i ) {
for( int j = 1 ; j <= m ; ++ j )
dp[i][j] = ( ( dp[i - 1][j] + C( i + j - 1 , j ) ) % P + ( dp[i][j - 1] - ( C( i + j - 1 , i ) - k[i][j - 1] + P ) % P + P ) % P ) % P;
}
cout << dp[n][m] << endl;
}

文章作者: yijan
文章链接: https://yijan.co/2019/08/22/old53/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog