CF#581 题解
A BowWow and the Timetable
如果不是4幂次方直接看位数除以二向上取整，否则再减一
#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
贪心做
#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中的距离，加入这个点然后把当前点设置成这个点
最后一个点必须加入（
#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
", 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就好了。
#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(egin{array}{c}{x+y-1} \ {y}end{array} ight))（相当于是一个插板法）
- 添加一个-1，对于方案不是完全小于等于0的的所有方案都要给答案-1。具体来说，减少了(left(egin{array}{c}{x+y-1} \ {x}end{array} ight)-k[x][y-1])
大概就这样了，有不清楚的看官方题解吧（
#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;
}