练习地址
点此前往练习
小团的配送团队
小团是美团外卖的区域配送负责人，众所周知，外卖小哥一般都会同时配送若干单，小团在接单时希望把同一个小区的单子放在一起，然后由一名骑手统一配送。但是由于订单是叠在一起的，所以，他归类订单时只能知道新订单和已有的某个订单的小区是相同的，他觉得这样太麻烦了，所以希望你帮他写一个程序解决这个问题。
即给出若干个形如a b的关系，表示a号订单和b号订单是同一个小区的 ，请你把同一个小区的订单按照编号顺序排序，并分行输出，优先输出最小的订单编号较小的小区订单集合。订单的编号是1到n。(可能存在同时出现a b和b a这样的关系,也有可能出现a a这样的关系)
输入描述:
输入第一行是两个正整数n，m，表示接受的订单数量和已知的关系数量。(1<=n，m<=10000)接下来有m行，每行两个正整数a和b，表示a号订单和b号订单属于同一个小区(1<=a,b<=n);
输出描述:
输出第一行包含一个整数x，表示这些订单共来自x个不同的小区。接下来的输出包含x行，每行表示输出若干个订单编号，表示这些订单属于同一个小区，按照订单编号升序输出。优先输出最小的订单编号较小的小区。
输入例子1:
5 5
1 2
2 2
3 1
4 2
5 4
输出例子1:
1
1 2 3 4 5
思路：
根据题意，考虑使用并查集。
注意输出需要输出集合的个数，对所有的订单遍历，查找属于同一个集合中的元素，放入vector容器中。
代码：
#include<bits/stdc++.h>
#define N 10010
using namespace std;
int pa[N];
vector<int> g[N];
//并查集的初始化
void init(int n)
{
for(int i = 0;i<=n;i++)
{
pa[i]=i;
}
}
//并查集的查找:在x所在的集合中查找集合编号
int find(int x)
{
if(x!=pa[x])
pa[x]=x=find(pa[x]);
return pa[x];
}
//并查集的合并：将x和y所在的集合合并
void merge(int x,int y)
{
x = find(x);
y = find(y);
if(x!=y)
{
if(x<y)
pa[y]=x;
else
pa[x]=y;
}
}
int main()
{
int n,m,a,b;
cin>>n>>m;
init(n);
for(int i=0;i<m;i++)
{
cin>>a>>b;
merge(a,b);
}
int count = 0;
for(int i = 1;i<=n;i++)
{
if(pa[i]==i)
count++;
int pi=find(i);
g[pi].push_back(i);
}
cout<<count<<endl;
for(int i=1;i<=n;i++)
{
if(pa[i]==i)
{
for(auto x:g[i])
cout<<x<<" ";
cout<<endl;
}
}
return 0;
}
不一样的逆序数
小团最近对逆序数（将一个数字逐位逆序，例如1234的逆序数为4321，1100的逆序数为11）特别感兴趣，但是又觉得普通的逆序数问题有点太乏味了。
于是他想出了一个新的定义：如果一个数的4倍恰好是它的逆序数，那么称这两个数是新定义下的逆序对。
接下来给定一正整数n，问：不超过n的正整数中有多少对新定义下的逆序对？
输入描述:
单组输入。输入一个正整数n，n<1e7。
输出描述:
第一行输出在不超过n的前提下有多少对逆序数，接下来每一行输出一对逆序数，以空格分隔。如果有多组逆序数，按照第一个数升序输出。如果没有一对逆序数则直接输出0即可。
输入例子1:
10000
输出例子1:
1
2178 8712
思路：
使用穷举法遍历查找满足要求的逆序数。
输出通过pair定义一个数据对，当找到满足要求的逆序数对后，将它们存放在vector容器中，计数+1。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> Reverse;
//获取逆序数
int get(int num)
{
int reverse=0;
while(num)
{
reverse = reverse*10+num%10;
num/=10;
}
return reverse;
}
int main()
{
int n;
cin>>n;
vector<Reverse> nums;
int count=0;
for(int i=1;i<=n;i++)
{
int reverse = get(i);
if(reverse<=n&&reverse==i*4)
{
nums.push_back({i,reverse});
count++;
}
}
cout<<count<<endl;
for(auto x :nums)
cout<<x.first<<" "<<x.second<<endl;
return 0;
}
小团的旅行路线
小团是一个旅游爱好者，快要过春节了，他想统计一下，在过去的一年中他进行过几次旅行，于是他打开了美团app的订单记录，记录显示了他的购买车票的记录。记录是按时间顺序给出的，已知一次旅行的线路一定是一个闭环，即起点和终点是同一个地点。因此当每找到一段闭合的行程，即认为完成了一次旅行。数据保证不会出现不在闭环路径中的数据。
请你在小团的购票记录中统计出他全年共进行了多少次旅行？
输入描述:
输入第一行包含一个正整数n，表示小团的购票记录数量。(1<=n<=10000)接下来有n行，每行是两个长度不超过10的仅由小写字母组成的字符串S_a S_b，表示购买了一张从S_a到S_b的车票。
输出描述:
输出仅包含一个整数，表示小团的旅行次数。
输入例子1:
6
beijing nanjing
nanjing guangzhou
guangzhou shanghai
shanghai beijing
fuzhou beijing
beijing fuzhou
输出例子1:
2
思路：
利用题设：起点和终点是同一个地点。当满足该条件时，计数+1。
代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
string a,b,start="";
int count=0;
for(int i=1;i<=n;i++)
{
cin>>a>>b;
if(start=="")
{
start=a;
}
if(b==start)
{
count++;
start="";
}
}
cout<<count<<endl;
return 0;
}
小团的车辆调度
小团是美团汽车租赁公司的调度师，某个时刻A和B两地都向该公司提交了租车的订单，分别需要a和b辆汽车。此时，公司的所有车辆都在外运营，通过北斗定位，可以得到所有车辆的位置，小团分别计算了每辆车前往A地和B地完成订单的利润。作为一名精明的调度师，当然是想让公司的利润最大化了。
请你帮他分别选择a辆车完成A地的任务，选择b辆车完成B地的任务。使得公司获利最大,每辆车最多只能完成一地的任务。
输入描述:
输入第一行包含三个整数n，a，b，分别表示公司的车辆数量和A，B两地订单所需数量,保证a+b<=n。(1<=n<=2000)接下来有n行，每行两个正整数x，y，分别表示该车完成A地任务的利润和B地任务的利润。
输出描述:
输出仅包含一个正整数，表示公司最大获得的利润和。
输入例子1:
5 2 2
4 2
3 3
5 4
5 3
1 5
输出例子1:
18
思路：
根据题意，可以抽象成0/1背包问题，考虑使用滚动数组优化的动态规划法。
设dp[i][j][k]表示第i辆车，则可以得到如下转移式：
d
p
[
i
]
[
j
]
[
k
]
=
m
a
x
{
d
p
[
i
−
1
]
[
j
−
1
]
[
k
]
+
A
[
i
]
,
d
p
[
i
−
1
]
[
j
]
[
k
−
1
]
+
B
[
i
]
,
d
p
[
i
−
1
]
[
j
]
[
k
]
}
dp[i][j][k]=max\{dp[i-1][j-1][k]+A[i],dp[i-1][j][k-1]+B[i],dp[i-1][j][k]\}
dp[i][j][k]=max{dp[i−1][j−1][k]+A[i],dp[i−1][j][k−1]+B[i],dp[i−1][j][k]}
同时考虑合法状态，对于每一个合法状态dp[i][j][k]，必定会有i≥j+k。所以在转移前需要考虑是否能够转移。
下述代码只过了4/10组用例，AC代码详见评论区。
代码：
#include<bits/stdc++.h>
#define N 1010
using namespace std;
int dp[2][N][N];
int A[N],B[N];
int main()
{
int n,a,b;
cin>>n>>a>>b;
for(int i=1;i<=n;i++)
{
cin>>A[i]>>B[i];
}
for(int i=1;i<=n;i++)
{
dp[i%2][1][0]=A[i];
dp[i%2][0][1]=B[i];
for(int j=1;j<=n;j++)
{
for(int k=1;k+j<=i;k++)
{
dp[i%2][j][k]=max(dp[(i-1)%2][j-1][k]+A[i],dp[(i-1)%2][j][k-1]+B[i]);
if(i-1>=j+k)
dp[i%2][j][k]=max(dp[i%2][j][k],dp[(i-1)%2][j][k]);
}
}
}
cout<<dp[n%2][a][b];
return 0;
}
总结
第一题：
- 并查集模板：
#define N 10010
int pa[N];
//并查集的初始化
void init(int n)
{
for(int i = 0;i<=n;i++)
{
pa[i]=i;
}
}
//并查集的查找:在x所在的集合中查找集合编号
int find(int x)
{
if(x!=pa[x])
pa[x]=x=find(pa[x]);
return pa[x];
}
//并查集的合并：将x和y所在的集合合并
void merge(int x,int y)
{
x = find(x);
y = find(y);
if(x!=y)
{
if(x<y)
pa[y]=x;
else
pa[x]=y;
}
}
-
for(auto i : v)遍历容器元素：C++11的新特性。
-
v是一个可遍历的容器或流，比如vector类型，i就用来在遍历过程中获得容器里的每一个元素。
- 等价于
for(some_iterator it = v.begin(); it != v.end(); ++it)且some_type i = *it。
- 另外还可以是
for(auto**&** i : v),for(auto**&&** i: v)，区别在于i是值还是引用。
第二题：
- 获取一个数的逆序数：
//获取逆序数
int get(int num)
{
int reverse=0;
while(num)
{
reverse = reverse*10+num%10;
num/=10;
}
return reverse;
}
-
输出是数据对时，可通过pair定义一个数据对，再使用vec.push_back(Pair)将其存放入vector容器中。
-
pair：将2个数据组合成一组数据。
- 头文件
#include <utility>
- 创建空的pair对象：
pair<T1, T2> p;
- 以v1和v2的值创建pair对象：
make_pair(v1, v2);
- pair对象的比较运算：
p1 op p2;op是比较运算符>或＜，遵循字典次序。
- pair对象的相等：
p1 == p2;p1和p2的first和second依次相等。
- 返回pair对象中第一个公有数据成员：
p.first;
- 返回pair对象中第二个公有数据成员：
p.second;
- 在某些清况函数会以pair对象作为返回值时，可以直接通过
std::tie进行接收。
-
C++ vector中使用pair：
-
声明vector：vector< pair<T1,T2> > vec;注意：vector<> 与里面的pair<T1,T2>得有间隔，否则会报错，编译器会识别成>>运算符的重载。
-
向vector中插入pair数据：vec.push_back(make_pair<T1,T2>(a,b));
-
定义迭代器：
vector<pair<int,int> > ::iterator iter;
for(iter=vec.begin();iter!=vec.end();iter++);
-
数据读取：
第一个数据：(*iter).first
第二个数据：(*iter).second
第三题：
暂无
第四题：
-
动态规划(DP)解决0/1背包问题：
- 背包容量不足以装入物品i，则装入前i个物品得到的最大价值和装入前i-1个物品得到的最大价值是相同的；
- 背包容量可以装入物品i，如果把第i个物品装入背包，则背包中物品的价值等于把前i-1个物品装入容量为j-wi的背包中的价值加上第i个物品的价值vi；如果第i个物品没有装入背包，则背包中物品的价值等于把前i-1个物品装入容量为j的背包中所取得的价值。取二者中的较大者作为把前i个物品装入容量为j的背包中的最优解。
- 递推式：
V
(
i
,
j
)
=
{
V
(
i
−
1
,
j
)
j
<
w
i
m
a
x
{
V
(
i
−
1
,
j
)
,
V
(
i
−
1
,
j
−
w
i
)
+
v
i
}
j
≥
w
i
V(i,j)=\left\{ \begin{array}{lr} V(i-1,j)&j<w_i\\ max\{V(i-1,j),V(i-1,j-w_i)+v_i\}&j≥w_i \end{array} \right.
V(i,j)={V(i−1,j)max{V(i−1,j),V(i−1,j−wi)+vi}j<wij≥wi
-
滚动数组优化动态规划的空间
二维数组例子：
int i, j, d[100][100];
for(i = 1; i < 100; i++)
for(j = 0; j < 100; j++)
d[i][j] = d[i - 1][j] + d[i][j - 1];
由于d[i][j]只依赖于d[i - 1][j], d[i][j - 1]，因此使用滚动数组实现如下：
int i, j, d[2][100];
for(i = 1; i < 100; i++)
for(j = 0; j < 100; j++)
d[i % 2][j] = d[(i - 1) % 2][j] + d[i % 2][j - 1];
此处%2也可以用&1。
