10.28 模拟赛

A 排列

写了一种不知道为啥正确的贪心方法。。

巨难写的正解貌似没啥意义就丢在这里了。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
using namespace std;
#define MAXN 5006
int n;
int A[MAXN], B[MAXN], res[MAXN];
multiset<int> S;
int main() <%
    scanf("%d", &n);
    for( int i = 1 ; i <= n ; ++ i )
        scanf("%d",& A[i]);
    for( int i = 1 ; i <= n ; ++ i )
        scanf("%d",& B[i]);
    for (int i = 1; i <= n; i++)
        S.insert(B[i]);
    for (int i = n; i; i--) {
        auto it = S.upper_bound(A[i]);
        it = ( it == S.end() ? S.begin() : it );
        res[i] = *it;
        S.erase(it);
    }
    for (int i = 1; i <= n; i++) {
        int pos = -1;
        for (int j = i + 1; j <= n; j++) {
            if (res[i] >= res[j]) continue;
            bool fuck = 0 , f1 = A[i] < res[i] ,  f2 = A[j] < res[j];
            fuck = ( ( !f1 ) and ( f2 && A[i] < res[j] ) ) or ( ( f1 ) and ( f2 && A[j] < res[i] ) ) or ( f1 and !f2 ) or ( !f1 and !f2 );
            if ( fuck && (pos == -1 || res[pos] < res[j]) ) pos = j;
        }
        if (pos != -1) swap(res[i], res[pos]);
    }
    for( int i = 1 ; i <= n ; ++ i ) printf("%d ", res[i]);
%>

B 分组

首先按照s排序，这样极值一定是某一组选择的最靠后的减去最靠前的。

然后考虑 $ dp[i][j][s] $ 表示前 $ i $ 个同学，到现在没有确定最大值的组 有 $ j $ 组，且目前一共的权值为 $ s $

那么这个就很容易转移了，分三种情况转移：

第 $ i $ 个同学加入了前面的某一组，并且并不作为最大值。
第 $ i $ 个同学加入了前面的某一组，并且作为最大值（也就是结束了某一组）
第 $ i $ 个同学新成了一组

但是由于我们权值是极差，是先减后加，这样转移并不能直接砍掉 $ s \geq k $ 的情况。

可以考虑先给原数组差分，然后每一组就是一段差分的和，并且这个差分显然是正的，就可以砍掉 $ s \geq k $ 的情况了。

实现有些细节，需要想一想。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define int long long
#define P 1000000007
#define MAXN 506
#define MAXK 1006
int n , k;
int s[MAXN] , dir[MAXN];
long long dp[2][MAXN][MAXK];
signed main() {
    cin >> n >> k;
    for( int i = 1 ; i <= n ; ++ i ) scanf("%lld",&s[i]);
    sort( s + 1 , s + 1 + n );
    for( int i = 1 ; i <= n ; ++ i ) dir[i] = s[i] - s[i - 1];
    dp[0][0][0] = 1;
    int cur = 0 , bac = 1;
    for( int i = 1 ; i <= n ; ++ i ) {
        cur ^= 1 , bac ^= 1;
        for( int j = 0 ; j <= i ; ++ j ) {
            for( int ss = 0 ; ss <= k ; ++ ss ) {
                int& x = dp[cur][j][ss];
                x = 0;
                if( ss >= j * dir[i] ) x += 1ll * ( j + 1 ) * dp[bac][j][ss - j * dir[i]] , x %= P;
                if( ss >= ( j - 1 ) * dir[i] && j ) x += dp[bac][j - 1][ss - ( j - 1 ) * dir[i]] , x %= P;
                if( ss >= ( j + 1 ) * dir[i] ) x += 1ll * ( j + 1 ) * dp[bac][j + 1][ss - ( j + 1 ) * dir[i]] , x %= P;
            }
        }
    }
    int res = 0;
    for( int i = 0 ; i <= k ; ++ i )
        res += dp[cur][0][i] , res %= P;
    cout << res << endl;
}

C 异或

最开始想的是xor差分，实际上一开始就相对了，

考虑对于一个点，定义它的点权是它连出去的所有边的边权的xor和

可以证明使得整个树变成0的充要条件就是所有点点权变为0，这个感觉和NOIP 2018 D1T1 很类似，证明也在题解有。

所以每次改变的链就变成了单点修改，考虑链中间的某个点一定有两个与他相连的边被xor，就xor没了。

然后可以贪心得做，最后每个边权要么剩下一个要么不剩下了，状压dp即可。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
#define MAXN 100006

int n;
int head[MAXN] , to[MAXN << 1] , nex[MAXN << 1] , wto[MAXN << 1] , ecn;
void ade( int u , int v , int w ) {
    to[++ecn] = v , wto[ecn] = w , nex[ecn] = head[u] , head[u] = ecn;
}
int S[MAXN];
void dfs( int u , int fa , int wfa ) {
    S[u] = wfa;
    for( int i = head[u] ; i ; i = nex[i] ) {
        int v = to[i];
        if( v == fa ) continue;
        S[u] ^= wto[i];
        dfs( v , u , wto[i] );
    }
}
int num[16];
int dp[1 << 16];
int Just_DOIT( int st ) {
    if( dp[st] != 0x3f3f3f3f ) return dp[st];
    if( !st ) return 0;
    for( int i = 1 ; i < 16 ; ++ i ) if( st & ( 1 << i ) ) {
        int curst = ( st ^ ( 1 << i ) );
        dp[st] = min( dp[st] , Just_DOIT( curst ) + 1 );
        for( int j = 1 ; j < 16 ; ++ j ) if( j != i && ( st & ( 1 << j ) ) ) {
            int cures = Just_DOIT( curst ^ ( 1 << j ) ^ ( 1 << ( j ^ i ) ) ) + ( ( st & ( 1 << ( j ^ i ) ) ) ? 2 : 1 );
            dp[st] = min( dp[st] , cures );
        }
    }
    return dp[st];
}
int main() {
//  freopen("xor3.in","r",stdin);
    cin >> n;
    for( int i = 1 , u , v , w ; i < n ; ++ i ) {
        scanf("%d%d%d",&u,&v,&w);
        ade( u , v , w ) , ade( v , u , w );
    }
    dfs( 1 , 1 , 0 );
    for( int i = 2 ; i <= n ; ++ i ) ++ num[S[i]];
    int res = 0;
    memset( dp , 0x3f , sizeof dp );
    for( int i = 1 ; i < 16 ; ++ i )
        res += num[i] / 2 , num[i] %= 2;
    int sta = 0;
    for( int i = 1 ; i < 16 ; ++ i ) if( num[i] )
        sta |= ( 1 << i );
    cout << res + Just_DOIT( sta ) << endl;
}