T20200828

Posted on Edited on In Word count in article: 1.2k Reading time ≈ 4 mins.
大东辰的测试

T1 doubt

贪心，让亦或最小的，就是二进制下最相近的亦或在一起

用\(01\)字典树贪心乱搞

Code

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
#include<bits/stdc++.h>
using namespace std;
int read(){
	int x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-')f=1;ch=getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ? -x : x;
}
const int N = 2e5+100,M = (2e5+100) * 31;
int rt[2],ch[M][2],cnt[M],si;
int A[N],B[N],n;
vector<int> Ans;
void insert(int a,int t,int x){
	if(t < 0) return;
	int i = (x>>t)&1;
	if(!ch[a][i]) ch[a][i] = ++si;
	cnt[ch[a][i]]++;
	insert(ch[a][i],t-1,x);
}
void print(int a,int b,int x,int t,int num){
	if(t < 0) {for(int i = 1;i <= num;i++) Ans.push_back(x);return;}
	if(cnt[ch[a][0]] && cnt[ch[b][0]]){
		int sum = min(cnt[ch[a][0]],cnt[ch[b][0]]);
		sum = min(num,sum);
		print(ch[a][0],ch[b][0],x,t-1,sum);
		cnt[ch[a][0]] -= sum;cnt[ch[b][0]] -= sum;num -= sum;
	}
	if(cnt[ch[a][1]] && cnt[ch[b][1]]){
		int sum = min(cnt[ch[a][1]],cnt[ch[b][1]]);
		sum = min(sum,num);
		print(ch[a][1],ch[b][1],x,t-1,sum);
		cnt[ch[a][1]] -= sum;cnt[ch[b][1]] -= sum;num -= sum;
	}
	if(cnt[ch[a][1]] && cnt[ch[b][0]]){
		int sum = min(cnt[ch[a][1]],cnt[ch[b][0]]);
		sum = min(sum,num);
		print(ch[a][1],ch[b][0],x+(1<<t),t-1,sum);
		cnt[ch[a][1]] -= sum;cnt[ch[b][0]] -= sum;num -= sum;
	}
	if(cnt[ch[a][0]] && cnt[ch[b][1]]){
		int sum = min(cnt[ch[a][0]],cnt[ch[b][1]]);
		sum = min(sum,num);
		print(ch[a][0],ch[b][1],x+(1<<t),t-1,sum);
		cnt[ch[a][0]] -= sum;cnt[ch[b][1]] -= sum;num -= sum;
	}
}
int main()
{
	n = read();rt[0] = ++si;rt[1] = ++si;
	for(int i = 1;i <= n;i++) A[i] = read(),insert(rt[0],30,A[i]);
	for(int i = 1;i <= n;i++) B[i] = read(),insert(rt[1],30,B[i]);
	print(rt[0],rt[1],0,30,n);
	sort(Ans.begin(),Ans.end());
	for(int i = 0;i < Ans.size();i++) printf("%d ",Ans[i]);
}

T2 block

日常鸽一题

状压Dp

Code

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = (int) 1e5 + 5;

const int MOD = (int) 1e9 + 7;

int n, h[MAXN], sorted[MAXN];

int qpow(int a, int x) {
    int res = 1;
    for (; x > 0; x >>= 1) {
        if (x & 1)
            res = 1LL * res * a % MOD;
        a = 1LL * a * a % MOD;
    }
    return res;
}

bool added[MAXN];
int R_L[MAXN], L_R[MAXN];

int dp[MAXN][2][2][2];
int last_h[MAXN];

void merge(int dp_l[2][2][2], int dp_r[2][2][2], int res[2][2][2]) {
    int tmp[2][2][2];
    
    memset(tmp, 0, sizeof tmp);
    
    for (int l = 0; l < 2; ++l)
    for (int r = 0; r < 2; ++r) {
        for (int ll = 0; ll < 2; ++ll)
        for (int rr = 0; rr < 2; ++rr)
        for (int sl = 0; sl < 2; ++sl)
        for (int sr = 0; sr < 2; ++sr) {
            int t = sl | sr | (ll == rr);
            tmp[l][r][t] = (tmp[l][r][t] + 1LL * dp_l[l][ll][sl] * dp_r[rr][r][sr]) % MOD;
        }
    }
    
    memcpy(res, tmp, sizeof tmp);
}

void calc(int L, int h_now) {
    if (last_h[L] == h_now) {
        return;
    }
    
    int tmp[2][2][2];
    int t = (last_h[L] - h_now) & 1;

    for (int l = 0; l < 2; ++l)
    for (int r = 0; r < 2; ++r) {
        tmp[l][r][1] = dp[L][l ^ t][r ^ t][1];
        tmp[l][r][0] = 1LL * (dp[L][l][r][0] + dp[L][l ^ 1][r ^ 1][0]) * qpow(2, last_h[L] - h_now - 1) % MOD;
    }

    memcpy(dp[L], tmp, sizeof tmp);
}

int main() {
#ifndef LOCAL
    freopen("block.in", "r", stdin);
    freopen("block.out", "w", stdout);
#endif
    
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", h + i);
        sorted[i] = i;
    }
    
    std::sort(sorted + 1, sorted + n + 1, [&] (int a, int b) {
        return h[a] > h[b];
    });

    for (int i = 1; i <= n; ++i) {
        int j = sorted[i];

        int tmp[2][2][2];
        int L = j, R = j;

        memset(tmp, 0, sizeof tmp);
        tmp[0][0][0] = tmp[1][1][0] = 1;

        if (R_L[j - 1]) {
            int l = R_L[j - 1], r = j - 1;
            L_R[l] = R_L[r] = 0;
            calc(l, h[j]);
            merge(dp[l], tmp, tmp);
            L = l;
        }

        if (L_R[j + 1]) {
            int l = j + 1, r = L_R[j + 1];
            L_R[l] = R_L[r] = 0;
            calc(l, h[j]);
            merge(tmp, dp[l], tmp);
            R = r;
        }

        added[j] = true;
        memcpy(dp[L], tmp, sizeof tmp);
        L_R[L] = R;
        R_L[R] = L;
        last_h[L] = h[j];
    }

    if (h[sorted[n]] > 1) {
        int t = (h[sorted[n]] - 1) & 1;
        int tmp[2][2][2];

        for (int l = 0; l < 2; ++l)
        for (int r = 0; r < 2; ++r) {
            tmp[l][r][1] = dp[1][l ^ t][r ^ t][1];
            tmp[l][r][0] = 1LL * (dp[1][l][r][0] + dp[1][l ^ 1][r ^ 1][0]) * qpow(2, h[sorted[n]] - 1 - 1) % MOD;
        }
        
        memcpy(dp[1], tmp, sizeof tmp);
    }

    int ans = 0;
    for (int i = 0; i < 2; ++i)
    for (int j = 0; j < 2; ++j)
    for (int k = 0; k < 2; ++k) {
        ans = (ans + dp[1][i][j][k]) % MOD;
    }

    printf("%d\n", ans);

    return 0;
}
//std码风好评

T3 road

考场上只有widsnoy​巨佬想到了正解， %%%

这道就是说，给你\(n\)个点，\(n+1\)条边，让你随意删一条边都能使这个图联通的连边方案数

问题转化：

我们发现，不能有点的度数为\(1\)

所以绝大多数的点的度数为\(2\)

那么就有如下两种情况：

  • 有一个点度数为\(4\)
  • 有两个点度数为\(3\)

那么有这样一个式子：\(Ans = \frac{n!(n-3)}4+\frac{n!(n-4)}8+\frac{n!(n-3)(n-4)}{24}\)

然后分段打表处理阶乘

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7, inv2 = 5e8 + 4, inv3 = 333333336;
ll n, ans = 0;

int main() {
	scanf("%lld", &n);
	ll mi = 1, t = inv2 * inv2 % mod;//4
	for (ll i = 2; i <= n; ++i) mi = mi * i % mod;//n!
	ans += (n - 3) * t % mod;
	t = t * inv2 % mod;
	ans += (n - 4) * t % mod;//8
	ans += (n - 3) * (n - 4) % mod * t % mod * inv3 % mod;
	ans = ans % mod * mi % mod;
	printf("%lld\n", ans);
}