2019牛客暑期多校训练营第九场
2019-08-16 / Luo Jinrong   

进度

A B C D E F G H I J
∅ ∅ √ ∅

E. All men are brothers

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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define per(i,a,n) for (int i=a;i<n;i++)
#define rep(i,a,n) for (int i=n-1;i>=a;i--)
 
const int MAXN(40);
const ll INF(0x3f3f3f3f3f);
const double EPS(1e-6);
 
ll n, m;
ll cn4;
ll x, y;
ll sigmaa, sigmaafang;
 
class UnionFind {
public:
    int *parent;   // 标注当前元素的父节点的位置
    int *rank;     // 标注当前元素的层级数
    int size;       // 并查集中的元素个数
    ll *sum;
 
    //将父节点指向自身表示此为根结点，初始化层数1，所有元素独立成集合。
    void init() {
        for (int i = 0; i < size; i++) {
            parent[i] = i;
            rank[i] = 1;
            sum[i] = 1;
        }
    }
 
    UnionFind(int size){
        this->size = size;
        parent = new int[size];
        rank = new int[size];
        sum = new ll[size];
        init();
    }
    inline int find(int target) {
        if(target >= size)//数组越界
            return -1;
        if(target == parent[target])
            return target;
        return find(parent[target]);
    }
    inline void get_together(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if(pRoot == qRoot)//本来就是同一个集合
            return;
        if(rank[pRoot] > rank[qRoot]) { // p 所在的树的高度比 q 所在树的高度高，这时应该让 q 的根节点元素连接到 p 的根节点元素
            parent[qRoot] = pRoot; // 此时树的高度不变
            sum[pRoot]+=sum[qRoot];
        } else if(rank[pRoot] < rank[qRoot]) {
            parent[pRoot] = qRoot; // 此时树的高度不变
            sum[qRoot]+=sum[pRoot];
        } else {
            parent[pRoot] = qRoot; // 此时树的高度 +1
            rank[qRoot] += 1;
            sum[qRoot]+=sum[pRoot];
        }
    }
    inline bool isConnected(int p, int q) {
        return find(p) == find(q);
    }
};
 
inline ll C(ll n) {
    bool flag[5];
    memset(flag, true, sizeof(flag));
    ll tmp = n;
    ll ans = 1;
    ///4
    if (tmp % 4 == 0 && flag[0]) {
        ans *= tmp / 4;
        flag[0] = false;
    } else if ((tmp - 1) % 4 == 0 && flag[1]) {
        ans *= (tmp - 1) / 4;
        flag[1] = false;
    } else if ((tmp - 2) % 4 == 0 && flag[2]) {
        ans *= (tmp - 2) / 4;
        flag[2] = false;
    } else if ((tmp - 3) % 4 == 0 && flag[3]) {
        ans *= (tmp - 3) / 4;
        flag[3] = false;
    }
 
    ///3
    if (tmp % 3 == 0 && flag[0]) {
        ans *= tmp / 3;
        flag[0] = false;
    } else if ((tmp - 1) % 3 == 0 && flag[1]) {
        ans *= (tmp - 1) / 3;
        flag[1] = false;
    } else if ((tmp - 2) % 3 == 0 && flag[2]) {
        ans *= (tmp - 2) / 3;
        flag[2] = false;
    } else if ((tmp - 3) % 3 == 0 && flag[3]) {
        ans *= (tmp - 3) / 3;
        flag[3] = false;
    } else {
        ans /= 3;
    }
 
    ///2
    if (tmp % 2 == 0 && flag[0]) {
        ans *= tmp / 2;
        flag[0] = false;
    } else if ((tmp - 1) % 2 == 0 && flag[1]) {
        ans *= (tmp - 1) / 2;
        flag[1] = false;
    } else if ((tmp - 2) % 2 == 0 && flag[2]) {
        ans *= (tmp - 2) / 2;
        flag[2] = false;
    } else if ((tmp - 3) % 2 == 0 && flag[3]) {
        ans *= (tmp - 3) / 2;
        flag[3] = false;
    } else {
        ans /= 2;
    }
    for (int i = 0; i < 4; ++i) {
        if (flag[i])
            ans *= (tmp - i);
    }
    return ans;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m;
    //求出C(n, 4)
    cn4 = C(n);
    cout << cn4 << '\n';
    //建立初始并查集，所有人不在一个集合
    UnionFind UF(n);    //人在0-n-1
    sigmaafang=sigmaa=n;
    per(i, 0, m) {
        cin >> x >> y;
        x--;y--;
        //判断两者是否在一个集合
        x=UF.find(x);
        y=UF.find(y);
        if(x!=y){
            //减去两个集合人数
            sigmaa-=UF.sum[x]+UF.sum[y];
            sigmaafang-=(UF.sum[x]*UF.sum[x])+(UF.sum[y]*UF.sum[y]);
            //计算答案
            cn4 -= (sigmaa*sigmaa-sigmaafang)/2*UF.sum[x]*UF.sum[y];
            //加上总和
            sigmaa=n;
            sigmaafang+=(UF.sum[x]+UF.sum[y])*(UF.sum[x]+UF.sum[y]);
            UF.get_together(x, y);
        }
        cout << cn4 << '\n';
    }
 
    return 0;
}

B. Quadratic equation

题意

给定两个整数$b$,$c$，求$x$,$y$满足$(x+y) mod p=b$,$(x*y) mod p=c$，其中$p=1000000007$。

做法

由
$$
(x+y)\mod p =b
$$
可得
$$
(x+y)^2\mod p=b^2\mod p
$$
又因为
$$
xy\mod p=c
$$
得
$$
((x+y)^2-4xy)\mod p=(x-y)^2\mod p=b^2-4c\mod p
$$
于是问题转化为求二次剩余

  • 如果$b^2-4c$是模$p$的二次剩余，因为$p\mod 4=3$，则$x-y=(b^2-4c)^{(p+1)/4}$，因为$x-y+b\mod p=2x\mod p$，所以可以通过$(x-y+b)*inv\mod p$得到$x$，其中$inv$为$2$的逆元；$y$就可通过$b-x$得到。
  • 如果$b^2-4c$是模$p$的二次非剩余，则不存在这样的$x$,$y$，输出$-1 -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
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
#define FIN freopen("./B.in","r",stdin)
using namespace std;
typedef long long ll;
const ll maxn(1e5+5),mod(1e9+7);
ll T,b,c,n,x_y,x,y;
ll qpow(ll a,ll b){
	ll ans=1,tmp=a;
	while(b){
		if(b&1){
			ans=ans*tmp%mod;
		}
		tmp=tmp*tmp%mod;
		b>>=1;
	}
	return ans;
}
int main(){
#ifndef ONLINE_JUDGE
	FIN;
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>T;
	for(int t=1;t<=T;t++){
		cin>>b>>c;
		n=((b*b-4*c)%mod+mod)%mod;
		x_y=qpow(n,(mod+1)/4);
		if(x_y*x_y%mod!=n){
			cout<<"-1 -1\n";
			continue;
		}
		x=(x_y+b)*qpow(2,mod-2)%mod;
		y=(b-x+mod)%mod;
		if(x>y){
			swap(x,y);
		}
		cout<<x<<" "<<y<<"\n";
	}
}

D. Knapsack Cryptosystem

题意

给定一个整数数列$a_i$和一个整数$sum$，求数列中哪些数的和恰好为这个整数，以01串形式输出。

做法

因为$1\leq n\leq 36$，如果直接暴力做的话复杂度为$O(2^n)$，显然会T。这个时候我们就可以想到分块暴力做，即折半枚举，我们先枚举前一半的每种情况求和$s1$，用map存下来，map分别存每种情况的和以及对应的01串的十进制形式。然后枚举后一半，每种情况求和$s2$，对于每一个和查找map里面存不存在$s1=sum-s2$，如果存在就直接输出s1对应的01串及s2对应的01串。

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
#include<bits/stdc++.h>
#define FIN freopen("./D.in","r",stdin)
using namespace std;
typedef long long ll;
const ll maxn(1e2+5);
ll T,n,s,a[maxn],l,r;
unordered_map<ll,ll> mp;
int main(){
#ifndef ONLINE_JUDGE
	FIN;
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>s;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	l=n/2,r=n-l;
	for(int i=((1<<l)-1);i>=0;i--){
		ll sum=0;
		for(int j=0;j<l;j++){
			if(i&(1<<j)){
				sum+=a[j+1];
			}
		}
		mp[sum]=i;
	}
	for(int i=((1<<r)-1);i>=0;i--){
		ll sum=0;
		for(int j=0;j<r;j++){
			if(i&(1<<j)){
				sum+=a[j+1+l];
			}
		}
		if(mp.find(s-sum)!=mp.end()){
			ll pos=mp[s-sum];
			for(int j=0;j<l;j++){
				cout<<((pos&(1<<j))?1:0);
			}
			for(int j=0;j<r;j++){
				cout<<((i&(1<<j))?1:0);
			}
		}
	}
}

J. Symmetrical Painting

题意

给定n个宽度在x轴方向且为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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define per(i,a,n) for (int i=a;i<n;i++)
#define rep(i,a,n) for (int i=n-1;i>=a;i--)
 
const int MAXN(3e5+7);
const ll INF(0x3f3f3f3f3f);
const double EPS(1e-6);
 
int N;
ll l[MAXN], r[MAXN], m[MAXN];   //初始值
ll everypos[5*MAXN];            //离散化坐标
int L[5*MAXN], R[5*MAXN], M[5*MAXN];   //下值、上值、中值 在离散化后坐标上的矩阵个数
int cnt;
ll f, a, b;
ll outt;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> N;
    per(i, 1, N+1) {
        cin >> l[i] >> r[i];
        m[i] = l[i]+r[i];
        l[i] *= 2;
        r[i] *= 2;
        everypos[cnt++] = m[i];
        everypos[cnt++] = l[i];
        everypos[cnt++] = r[i];
    }
    sort(everypos, everypos+cnt);
    cnt = unique(everypos, everypos+cnt)-everypos;
    per(i, 1, N+1) {
        L[lower_bound(everypos, everypos+cnt, l[i])-everypos]++;
        R[lower_bound(everypos, everypos+cnt, r[i])-everypos]++;
        M[lower_bound(everypos, everypos+cnt, m[i])-everypos]++;
    }
    outt = f = a = b = 0;
    everypos[cnt] = 0;
    rep(i, 0, cnt) {
        f += (everypos[i+1]-everypos[i])*(a-b);
        outt = max(outt, (ll)f);
        a += (R[i]-M[i]);
        b += (M[i]-L[i]);
    }
    cout << outt << endl;
 
    return 0;
}

return 0;

本文链接：
https://luojinrong.github.io/2019/08/16/2019牛客暑期多校训练营第九场/