1、魔术师的烦恼
我叫小王，一个倒霉的魔术师，昨天我精心准备的多副扑党牌被我家猫翻的乱七八糟，更悲剧的是，居然还丢了几张。你能帮我整理一下吗？整理的方法如下：每次都从乱序扑克牌堆中尽可能找到完全相同的一副扑克牌并排好序，直到所有扑克均排好序。当然，魔术师的扑克牌里面还含了很多赢得魔术师的秘密，相同扑克顺序千万不能乱了。注意：不需要考虑一整副牌全部都丢了的情况，这么倒霉的情况不会发生在我身上...
额，应该吧
备注：一副完整的扑克牌包含\(52\)张牌，不包含大小王，为简化处理，将扑克牌进行编码，扑克牌ID范围是\([1,52]\)。
输入
第一行为扑克牌个数，范围是\([1,1000]\)
第二行为扑克牌ID列表，依次用空格隔开。
输出
第一行输出整理出多少副扑克牌（标记为\(M\)）
第二行到第\(M+1\)行：每一行都保存在乱序扑克牌堆中的扑克牌信息，扑克牌信息包含扑克牌位置和扑克牌ID，依次用空格隔开。
样例
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
| 输入：
3
3 3 4
输出：
2
1 3 3 4
2 3
提示：
可以看到，这个牌堆里面有两个3，由于不存在整副牌全部丢失的情况，所以魔术师精心准备了两副牌（如果是三副牌的话就意味着有一副牌全部被丢失了，不符合题目描述的情境）。第一行：2
将乱序牌堆（输入）的位置标注后如下：
1 2 3
3 3 4
根据题目要求，需要先尽可能组成一副牌，选取不重复的两张牌，即位置1的扑克牌3和位置3的扑克牌4。这里不能选择位置2的扑克牌3的原因在于，相同的扑克牌整理好后先后顺序不能乱。因此，第二行输出：13 3 4。
现在乱序牌堆里面只剩下位置2的扑克牌3了。将它拿出来后进行排序，所以第三行输出：2 3。
输入：
7
7 5 3 4 4 3 4
输出：
3
3 3 4 4 2 5 1 7
6 3 5 4
7 4
提示：
乱序牌堆如下：
1 2 3 4 5 6 7
7 5 3 4 4 3 4
乱序牌堆中最多包含3个4，所以有3副扑克牌。第一行：3
将每张扑克牌位置和ID编码，显示格式：[位置，ID]。
第一次从乱序牌堆中抽取扑克牌时，根据规则选取[1,7],[2,5],[3,3],[4,4]，将扑克牌排非序后为[3,3],[4,4],[2,5],[1,7]。第二行：3 3 4 4 2 5 1 7
剩余乱序牌堆如下：
5 6 7
4 3 4
选取扑克牌[5,4],[6,3],排序后为：[6,3],[5,4]。第三行：6 3 5 4
乱序牌堆只剩下[7,4]。第四行：7 4
|
解答
这是一道题意比较晦涩难懂的模拟题。我们可以使用数组存储每个ID编码出现的所有位置。由于需要取出的是一幅尽量完整的牌，因此需要在每个ID数组中取出一个最小的下标来组成一幅牌（如果存在的话），并且将这些牌保存起来，存到一个新的数组中，直到最后输出即可。
这里使用的一个技巧是，如果一个ID数组为空，那么就跳过它，不再进行遍历（使用一个数组del和一个map共同实现）。
代码
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
| # include <bits/stdc++.h>
using namespace std;
const int N=1004;
map<int,vector<int>>mp;
int a[N];
int main(){
int n,x;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=n;i>=1;i--)
mp[a[i]].push_back(i);
vector<vector<int>>ans;
while(!mp.empty()){
vector<int>del,row;
for(auto &[k,v]:mp){
int x=v.back();
v.pop_back();
row.push_back(x);
row.push_back(k);
if(v.size()==0) del.push_back(k);
}
for(int k:del) mp.erase(k);
ans.emplace_back(row);
}
printf("%d\n",ans.size());
for(auto &v:ans){
for(int i=0;i<v.size();i++){
printf("%d%c",v[i], " \n"[i+1==v.size()]);
}
}
}
|
2、计算最长路径长度
给定一组节点\(N\)及节点间的依赖关系\(E\)，其中\(N[i](0\le i< n)\)表示第\(i\)个节点，\(E[i][j]\)表示第\(i\)个节点依赖于第\(j\)个节点，依赖长度为\(E[i][j]\)。计算图中所有节点间的最长路径长度。
输入
\(n\)：节点个数，节点编号依次从\(0\)到\(n-1\)。
\(m\)：依赖关系数量，接下来输入\(m\)条依赖元组。
\(i,j,l\)：第\(j\)个节点依赖第\(i\)个节点，依赖长度为\(l\)。满足\((j<i)\)。
- 给定的图为有向无环图
- \(1 \le n \leq 100\)
- \(0 \leq m \leq 10000\)
- \(0 < l \leq 100\)
输出
MaxL：给定图的最长路径长度。
样例
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
| 输入：
3
2
0 1 3
0 2 4
输出：
4
提示：
给定图中存在3个节点，2条依赖，即第1个节点依赖第0个节点，依赖长度为3; 第2个节点依赖第0个节点，依赖长度为4。所以图中存在2条路径，即0到1和0到2。0到1的路径长度为3，0到2的路径长度为4，所以0到2是该图的关键路径，因此该图中关键路径长度为4。
输入：
3
3
0 1 3
0 2 4
1 2 2
输出：
5
提示：
最长关键路径为0->1->2，长度为5。
输入：
6
7
0 1 3
0 2 4
0 3 4
1 4 3
2 4 3
3 5 4
4 5 2
输出：
9
提示：
最长关键路径为0->2->4->5，长度为9。
|
解答
这是经典的拓扑排序和动态规划相结合的题目，用于求有向无环图中的最长路径。
令\(d_u\)表示以\(u\)为终点的最长路径长度，那么不难写出\(d\)的状态转移方程为：
\[d_v=\max_{(u,v)\in
E}\{d_u+l(u,v)\}\]
其中\(l\)表示题目中提到的边权。
因此，最终输出\(\displaystyle{\max_{u=0}^{n-1}\{d_u\}}\)即可，在计算\(d\)的过程中使用拓扑排序完成。
代码
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
| # include <bits/stdc++.h>
# define pi pair<int,int>
# define X first
# define Y second
using namespace std;
const int N=104;
vector<pi>g[N];
int deg[N],dis[N];
int n,m;
int main(){
int x,y,w;
scanf("%d %d",&n,&m);
for(int i=0;i<m;i++){
scanf("%d %d %d",&x,&y,&w);
g[x].push_back(pi(y,w));
++deg[y];
}
queue<int>q;
for(int i=0;i<n;i++){
if(deg[i]==0){
q.push(i);
}
}
while(!q.empty()){
int u=q.front();q.pop();
for(auto [v,w]:g[u]){
dis[v]=max(dis[v],dis[u]+w);
if(--deg[v]==0) q.push(v);
}
}
printf("%d\n",*max_element(dis,dis+n));
}
|
3、虚拟机资源分配
云转发多租户体系中，租户们订购了不同带宽的转发资源。现在需要为这些租户分配虚拟机资源以承载其转发业务。已知单台虚拟机的最大转发带宽为\(m\)（保证单个租户的带宽不会超过单台虚拟机的转发能力），且虚拟机数量可以按需增加。要求虚拟机转发带宽利用率最大化，即优先在现有虚拟机上分配尽可能多的租户带宽，当无法再分配时，才考虑新增虚拟机。请计算最少需要分配多少台虚拟机以承载所有租户的转发带宽，并按从大到小的顺序列出每台虚拟机所承载的租户转发带宽大小。
输入
第1行为\(m\)，表示虚拟机的最大转发带宽，范围为\([64,1024]\)。
第2行为\(n\)，表示租户的数量，范围为\([1,16]\)。
第3行为这批租户所购买的带宽容量大小，数据间用空格隔开。单个租户带宽容量大小范围为\([1,64]\)。
输出
第1行为分配的虚拟机数量。
第2行按从大到小顺序，列出每台虚拟机所承载的租户转发带宽大小，数据间用空格隔开。
样例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| 输入：
64
3
31 25 4
输出：
1
64
提示：
所有租户的带宽加起来未超过单台虚拟机的转发能力，只需分配一台虚拟机。
输入：
64
5
30 30 3 14 7
输出：
2
63 21
提示：
第一台虚拟机最多能承担的租户带宽为63，剩下的租户带宽需另起一台虚拟机来承担。
|
解答
需要注意的是，这里优先令分配的虚拟机数量最少，然后再尽量让部分的虚拟机分配的带宽尽可能多。
首先解决第一个问题：最少需要分配多少台虚拟机，才能承接地起这些用户的带宽。这里我们使用状态压缩动态规划来进行求解：我们使用一个\(n\)位二进制数\(s\)表示这\(n\)个用户的一个子集。令\(v(s)\)表示这个子集中所有的用户租用的带宽之和。这意味着如果\(v(s)>m\)，那么子集\(s\)不可能单独地作为一个子集，分配在同一台虚拟机中。
令\(f(s)\)表示至少需要多少台虚拟机，才能够将子集\(s\)这些租户完成分配。那么可以写出如下状态转移方程：
\[f(s)=
\left \{\begin{aligned}
&0 & & \text{if}\quad s=0 \\
&\min_{k\& s=k,v(s)\le m}\{f(s\oplus k)+1\} & &
\text{if}\quad s>0 \\
\end{aligned}\right.\]
其中\(\&,\oplus\)分别表示这些二进制数的与运算和异或运算。这意味着，在状态\(s\oplus
k\)中，我们添加一个虚拟机来承受子集\(k\)中所有用户的带宽，由此从状态\(s\oplus k\)转移到\(s\)。
在实现中，如何枚举\(s\)的所有子集\(k\)？这可以使用一个for循环简单地解决：for(int k = s; k; k = (k - 1) & s)，其原理在于遇到一个最低位的\(1\)后，减\(1\)操作会将这个\(1\)置\(0\)，并将所有低位的\(0\)置成\(1\)。
因此最终答案为\(f(2^n-1)\)。
接下来解决第二个问题：如何让部分的虚拟机分配的带宽尽可能多。
这个问题的解决方法非常简单：在进行转移的时候，判断从当前决策转移到\(s\)和从旧决策转移到\(s\)的整个虚拟机方案取出来，并对这两个方案对应数组进行逆序排序，如果当前方案对应数组的字典序比较大，那么取当前转移方式。
代码
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
| # include <bits/stdc++.h>
using namespace std;
const int N=16;
int s[1<<N],f[1<<N],pre[1<<N];
int a[N],n,mx;
vector<int>gen_st(int st){
vector<int>ans;
for(int i=st;i;i=pre[i])
ans.push_back(s[i]-s[pre[i]]);
return ans;
}
int main(){
scanf("%d %d",&mx,&n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
memset(f,0x3f,sizeof(f));
f[0]=0;
for(int st=1;st<(1<<n);st++){
for(int i=0;i<n;i++){
if(st>>i&1){
s[st]+=a[i];
}
}
for(int k=st;k;k=(k-1)&st){
if(s[k]>mx) continue;
if(f[st^k]+1<f[st]){
f[st]=f[st^k]+1;
pre[st]=st^k;
}
else if(f[st^k]+1==f[st]){
vector<int>old=gen_st(st);
vector<int>now=gen_st(st^k);
now.push_back(k);
sort(old.begin(),old.end(),greater<int>());
sort(now.begin(),now.end(),greater<int>());
if(now>old) pre[st]=st^k;
}
}
}
vector<int>ans=gen_st((1<<n)-1);
sort(ans.begin(),ans.end(),greater<int>());
printf("%d\n",ans.size());
for(int i=0;i<ans.size();i++)
printf("%d%c",ans[i]," \n"[i+1==ans.size()]);
}
|