10.24 模拟赛

昨天dls毒瘤虐场今天终于来了一场信心赛。。（但估计明天jls要毒瘤了）

A 字符串

考虑建出序列自动机，也就是每一个位置指向它之后第一个 0/1 然后直接dp求最短长度，dp的过程可以记搜实现。求答案就再正着做一遍就好了。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
#define MAXN 4006
int n , m;
int s[MAXN] , t[MAXN];
int nxt[2][MAXN][2];
int dp[MAXN][MAXN];
int ans;
int Just_DOIT( int p1 , int p2 ) {
	if( p1 > n && p2 > m ) return dp[p1][p2] = 0;
	if( dp[p1][p2] != 0x3f3f3f3f ) return dp[p1][p2];
	for( int id = 0 ; id <= 1 ; ++ id )
		dp[p1][p2] = min( dp[p1][p2] , 1 + Just_DOIT( nxt[0][p1][id] , nxt[1][p2][id] ) );
	return dp[p1][p2];
}
void Make_Your_Dream_COMETRUE( int p1 , int p2 , int curlen ) {
	for( int id = 0 ; id <= 1 ; ++ id ) {
		int &t1 = nxt[0][p1][id] , &t2 = nxt[1][p2][id];
		if( curlen + dp[t1][t2] + 1 == ans ) {
			printf("%d",id) , Make_Your_Dream_COMETRUE( t1 , t2 , curlen + 1 );
			break;
		}
	}
}

int main() {
	cin >> n >> m;
	for( int i = 1 ; i <= n ; ++ i ) scanf("%1d",&s[i]);
	for( int i = 1 ; i <= m ; ++ i ) scanf("%1d",&t[i]);
	nxt[0][n][1] = nxt[0][n][0] = n + 1;
	nxt[1][m][1] = nxt[1][m][0] = m + 1;
	nxt[0][n + 1][1] = nxt[0][n + 1][0] = n + 1;
	nxt[1][m + 1][1] = nxt[1][m + 1][0] = m + 1;
	for( int i = n ; i ; -- i ) 
		memcpy( nxt[0][i - 1] , nxt[0][i] , sizeof nxt[0][i] ),
		nxt[0][i - 1][s[i]] = i;
	for( int i = m ; i ; -- i ) 
		memcpy( nxt[1][i - 1] , nxt[1][i] , sizeof nxt[1][i] ),
		nxt[1][i - 1][t[i]] = i;
	memset( dp , 0x3f , sizeof dp );
	ans = Just_DOIT( 0 , 0 );
	Make_Your_Dream_COMETRUE( 0 , 0 , 0 );
}

B 序列

显然有每一个数字出现只会是 $ 2^t-1 $ 次

可以考虑最大选择的数字是 $ M $ 然后由于 $2^tx < M$ 的个数其实是很少的，所以可以直接计算。复杂度是远远跑不到的 $ tlog^2n $

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
int f(int x) {
    int res = 0, base = 1;
    while (x) res += x * (x + 1) / 2 * base, base <<= 1, x >>= 1;
    return res;
}
int calc(int x) {
    int res = 0;
    while (x) res += x, x >>= 1;
    return res;
}
int n;
signed main() {
    int T;cin >> T;
    while (T--) {
        cin >> n;
        int l = 1, r = 2000000000, ans;
        while (l <= r) {
            int m = (l + r) >> 1;
            if ( f(m - 1) < n ) ans = m, l = m + 1;
            else r = m - 1;
        }
        cout << calc(ans - 1) + (n - f(ans - 1)) / ans << endl;
    }
    return 0;
}

C 交换

一个最简单的贪心，如果我们从小到大来放，那么这个数字一定放在了当前的最左边或者最右边，而它经过的数字一定是大于这个数字本身的数，因为小于它的数字已经被移走了，而大的数字与它的相对位置没有变化，也就是原来在它左边现在就还在它左边。所以把一个数字往左边移动的代价就是左边大于这个数字的个数，于是可以贪心地做。

重复元素其实根本不是问题，对于重复的数字，如果这个数字往左边移，就先钦定左边的数字先移动，直接统计左右有多少个比这个数字大的数字就好了。

拿个BIT维护一下就好了。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
#define MAXN 300006
int n;
int A[MAXN] , res;
struct BIT {
	int T[MAXN];
	void add( int x , int c ) {
		while( x < MAXN ) T[x] += c , x += ( x & -x );
	}
	int sum( int x ) {
		int ret = 0;
		while( x > 0 ) ret += T[x] , x -= ( x & -x );
		return ret;
	}
	int get( int x ) {
		return sum( MAXN - 1 ) - sum( x );
	}
} lef , rig;
signed main() {
	cin >> n;
	for( int i = 1 ; i <= n ; ++ i ) 
		scanf("%lld",&A[i]) , rig.add( A[i] , 1 );
	for( int i = 1 ; i <= n ; ++ i ) {
		rig.add( A[i] , -1 );
		res += min( rig.get( A[i] ) , lef.get( A[i] ) );
		lef.add( A[i] , 1 );
	}
	cout << res << endl;
}