Sarail wanna sleep all day
0%

发表于

题目链接：https://ac.nowcoder.com/acm/contest/7830/J

题目大意：

有n种花，第$i $种花有$a_i$朵。现在要用m朵花组成一束花，要求每束花的中每朵花的种类各不相同，求最多组成几束花。

题目分析：

假设m=2，这就变成了一个配对问题。我们设$m=max\{a_i\},tot=sum\{a_i\}$,当$m\leq\frac {tot}{2}$,则一定是能够恰好两两配对的（花朵总数为奇数会有一个剩余），答案为$\frac{tot}{2}$。反之，数量最多的那种花一定能和其他所有花配对，此时我们只要考虑剩下的花就可以了，答案为$tot -m$。

那么对于m大于2的情况怎么办呢？很简单，只要某一束花大于等于$\frac{tot}{m}$，这种花就一定能和其他所有花配对，我们把这种花的数量从tot里删掉，再把m减1就可以了，最后的答案是$\frac{tot}m$,注意这里的tot是删完之后剩下的花的总数。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
typedef long long ll;
int a[N], n, m;

int main() {
    int T; cin >> T;
    while (T--) {
        cin >> n >> m;
        ll tot = 0;
        for (int i = 1; i <= n; ++i) {
            scanf("%d", a + i);
            tot += a[i];
        }

        for (int i = 1; i <= n; ++i) if (a[i] >= tot / m) {
            tot -= a[i];
            m--;
        }
        cout << tot / m << endl;
    }
}

发表于

链接：https://ac.nowcoder.com/acm/contest/5675/J

题目大意：

给两颗有根树，每个节点有一个标签，每次操作可以任意修改一个标签，问使这两棵树完全相同需要的最少的操作次数。

题目分析：

容易发现这个问题等价于找个对应关系，使得相同的标号尽量多，剩下的标号需要修改。可以用树形dp，转移的时候使用二分图最大权匹配。

具体来说，先对每一个子树进行树哈希（用于判断是否同构），然后进行树形dp。dp时，若发现树1的子树a和树2中的子树b同构，则考虑将他们匹配并求出他们匹配时最多有多少对节点的标签会相同。最大的标签数如何求呢？就是前述的二分图最大权匹配：枚举子树a和子树b的儿子节点，若发现以这两个节点为根的树同构（哈希值相同），则连一条边，边权为递归调用dp方法计算出的这两棵子树配对的最多相同标签的节点数；枚举完所有情况后，再做一遍km算法求出最大权匹配，若子树a与子树b的标签相同，答案为最大权+1，否则为最大权。显然，叶子节点就是天然的递归边界。

另外，虽然题目的数据规模为500，但是在树形结构下二分图中实际有边相连的点的个数会很少，就算是$O(n^4)$的km算法也会跑的非常快（就算是菊花图）。树哈希的方法也有很多种，且一般不容易被卡，随便瞎搞应该也都是可以的。

AC代码

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
163
164
#include <bits/stdc++.h>
using namespace std;
const int N = 500 + 50,base = 23333,inf = 1e17;
typedef unsigned long long ull;
typedef long long ll;

int t1[N],t2[N];

struct node {
    int u,sz;
    ull h; // 以当前节点为根的子树的哈希值，用于判断是否同构。自然溢出取模
    vector<int> son;

    bool operator == (const node& rhs) const {
        return (h == rhs.h) && (sz == rhs.sz);
    }
}t[N << 1];

struct edge {
	int from,to,dist;
	edge(int u,int v,int d) : from(u),to(v),dist(d) {}
};

ll Left[N],Lx[N],Ly[N],w[N][N];
bool S[N],T[N];

bool match(int i,int n) {
	S[i] = true;
	for(int j = 1; j <= n; ++j) if (Lx[i] + Ly[j] == w[i][j] && !T[j]) {
		T[j] = true;
		if (!Left[j] || match(Left[j],n)) {
			Left[j] = i;
			return true;
		}
	} 
	return false;
}

void update(int n) {
	ll a = 1e18;
	for(int i = 1; i <= n; ++i) if(S[i])
		for(int j = 1; j <= n; ++j) if(!T[j])
			a = min(a, Lx[i] + Ly[j] - w[i][j]);
	
	for(int i = 1; i <= n; ++i) {
		if (S[i]) Lx[i] -= a;
		if (T[i]) Ly[i] += a;
	}
}

void km(int n) {
	for(int i = 1; i <= n; ++i) {
		Left[i] = 0;
		Lx[i] = Ly[i] = 0;
		for(int j = 1; j <= n; ++j) 
			Lx[i] = max(Lx[i], w[i][j]);
	}
	
	for(int i = 1; i <= n; ++i) {
		for( ; ;) {
			for(int j = 1; j <= n; ++j) S[j] = T[j] = 0;
			if (match(i, n)) break; else update(n);
		}
	}
}

// 返回的结果为最优匹配中编号相同节点的个数最大值
int buildMap(int rt1, int rt2) {
	vector<edge> stk;
	int t1, t2, nn = 0, res = 0;
    // 由于建树方式能保证一棵树的儿子节点在t数组中的下标总是连续的
    // 因此在这里我们将每一个儿子节点的与第0个儿子的下标的差值加一
    // 作为其在二分图中的编号，以此来减少km算法的时间开销
	if (t[rt1].son.size() > 0) 
		t1 = t[rt1].son[0], t2 = t[rt2].son[0], nn = t[rt1].son.size();
	for (auto son1 : t[rt1].son)
		for (auto son2 : t[rt2].son) 
			if(t[son1] == t[son2]) 
				stk.push_back(edge(son1 - t1 + 1, son2 - t2 + 1, buildMap(son1,son2)));
		
    // 待儿子节点计算完后，才开始计算当前节点否则图中会有多余的边
	for (auto e : stk) w[e.from][e.to] = e.dist;
	km(nn);	
	for(int i = 1; i <= nn; ++i) res += w[Left[i]][i];
    // 还原
	for (auto e : stk) w[e.from][e.to] = -inf;
	
    // 这里注意要判断当前节点是否相同
	return res + (t[rt1].u == t[rt2].u ? 1 : 0);
}

bool isprime[N * N];
int prime[N];
int n,tot,ans;

void get_prime(int MAX) {
    int x = 0;
    memset(isprime, true, sizeof(isprime));
    for (int i = 2; i < MAX; i++) {
        if (x > N - 10) break;
        if (isprime[i]) prime[x++] = i;
        for (int j = 0; j < x; j++) {
            if (i * prime[j] >= MAX) break;
            isprime[i * prime[j]] = 0;
            if (i % prime[j] == 0) break;
        }
    }
}

void dfs(int u) {
    t[u].sz = 1; t[u].h = 0;
    sort(t[u].son.begin(),t[u].son.end());

    for(auto v : t[u].son) {
        dfs(v);
        t[u].sz += t[v].sz;
    }

    for (auto v : t[u].son) t[u].h += t[v].h * prime[t[v].sz];
    t[u].h++;
}

int build(int* p) {
    int rt = ++tot;
    for (int i = 1; i <= n ; ++i)
        if (p[i] == 0){
            t[rt].u = i;
        }

    queue<int> Q;
    Q.push(rt);
    while (!Q.empty()) {
        int u = Q.front(); Q.pop();

        for (int i = 1; i <= n; ++i)
            if (p[i] == t[u].u) {
                t[u].son.push_back(++tot);
                t[tot].u = i;
                Q.push(tot);
            }
    }
    dfs(rt);
    return rt;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

	get_prime(N * N - 100);
	cin >> n;
	for(int i = 0; i <= n; ++i) 
		for(int j = 0; j <= n; ++j)
			w[i][j] = -inf;
			
    for(int i = 1; i <= n; ++i) cin >> t1[i];
    for(int i = 1; i <= n; ++i) cin >> t2[i];

    int rt1 = build(t1), rt2 = build(t2);

    ans = 0;
    ans = max(ans,n - buildMap(rt1,rt2));
    cout << ans << endl;
}