题目1 列表补全
题目描述
在商城的某个位置有一个商品列表，该列表是由L1、L2两个子列表拼接而成。当用户浏览并翻页时，需要从列表L1、L2中获取商品进行展示。展示规则如下：
- 用户可以进行多次翻页，用offset表示用户在之前页面已经浏览的商品数量，比如offset为4，表示用户已经看了4个商品；
- n表示当前页面需要展示的商品数量；
- 展示商品时首先使用列表L1，如果列表L1长度不够，再从列表L2中选取商品；
- 从列表L2中补全商品时，也可能存在数量不足的情况。
请根据上述规则，计算列表L1和L2中哪些商品在当前页面被展示了
样例
in:
2 4 4 4
1 2 4 4
4 1 3 3
out:
2 4 0 2
1 3 0 0
3 3 1 2
输入描述
每个测试输入包含1个测试用例，包含四个整数，分别表示偏移量
offset
、元素数量
n
，列表L1的长度
l1
，列表L2的长度
l2
。
输出描述
在一行内输出四个整数分别表示L1和L2的区间start1，end1，start2，end2，每个数字之间有一个空格。
注意，区间段使用半开半闭区间表示，即包含起点，不包含终点。如果某个列表的区间为空，使用[0, 0)表示，如果某个列表被跳过，使用[len, len)表示，len表示列表的长度。
题目解析
这个题目非常简单，其实就是划分一些情况而已，而且4种情况中3种情况已经在样例中给你展示出来了，所以说这个题是送分题。样例中的情况有：
- offset在list1中，但是展示的数目也没有超过List1；
- offset在list1中，但是展示的数目顺延到了list2中，并且list2够用；
- offset在list1中，但是展示的数目顺延到了list2中，list2不够用；
- offset在list1和list2中，但是展示的数目没有超过list2；
- offset在list1和list2中，但是展示的数目超过了list2；
- offset>L1+L2的情况，那自然，使用使用[len, len)表示即可。
代码
#include<iostream>
using namespace std;
int main()
{
int offset, n, list1, list2;
int start1, end1, start2, end2;
while (cin >> offset >> n >> list1 >> list2)
{
//offset还在list1中--start
if (offset<list1)
{
start1 = offset;
//展示都在list1时
if (n < list1 -offset )
{
end1 = offset + n;
start2 = 0;
end2 = 0;
}
//当展示填满了list1，去了list2
else
{
end1 = list1;
start2 = 0;
if ((n - (list1 - offset)) < list2)//当list2够用的时候
end2 = n - (list1 - offset);
//当list2不够用的时候
else
end2 = list2;
}
}
//如果offset在list1最后一个或者到了list2的时候
else if ((offset >= list1) &&(offset<=list1+list2))
{
start1 = list1;
end1 = list1;
start2 = offset - list1;
//list2够用的话
if (n < (list2 - (offset - list1)))
{
end2 = offset - list1 + n;
}
//如果list2不够用的话
else
end2 = list2;
}
else
{
start1 = list1;
end1 = list1;
start2 = list2;
end2 = list2;
}
cout << start1 << " " << end1 << " " << start2 << " " << end2 << endl;
}
system("pause");
return 0;
}
周年庆
拼多多王国的城市和道路的拓扑结构比较特别，是一个树状结构：
每个城市是树的一个节点；
城市之间的道路是树的一条边；
树的根节点是首都。
拼多多周年庆马上就要到了，这是拼多多王国的一个大日子。为了活跃气氛，国王想在道路上布置花灯。花灯可是很贵的东西，尽管国王想要在所有道路上都布置花灯，但是如果要花太多钱的话，是过不了财政大臣那一关的。国王把这个计划告诉财政大臣，最后他们商讨出来这么一个方案：
一条道路要么不布置花灯，要么整条布置花灯，不能选择其中的某一段布置；
除非没有道路通向首都，否则至少为一条通向首都的道路布置花灯；
所有布置花灯的道路构成的子图是连通的，这保证国王从首都出发，能通过只走布置了花灯的道路，把所有的花灯游览完；
如果某个城市（包括首都）有大于等于2条道路通向子城市，为了防止铺张浪费，最多只能选择其中的两条路布置花灯；
布置花灯的道路的总长度设定一个上限。
在上述方案下，国王想要使得布置花灯的道路长度越长越好，你帮国王想想办法。
每个测试输入包含1个测试用例。
输入的第一行是一个正整数m，0输入的第二行是一个正整数n，n<=100n<=100，表示城市的个数。
紧接着是n-1行输入，每行三个正整数u、v、d，表示下标为u的城市有一条长度为d的道路通向它的一个子城市v，其中0<=u
输出一个正整数，表示能布置花灯的道路长度的最大值。
输入输出样例
in:
5
0 1 1
0 2 2
0 3 3
0 4 4
out:
代码实现
#include <iostream>
#include<vector>
#include<set>
using namespace std;
using Array = vector<int>;
set<int> dfs(int root, vector<Array> &sons, Array &d, int m)
{
if (sons[root].size() == 0)
return set<int>({ 0 });
vector<set<int> > sts;
for (auto it = sons[root].begin(); it != sons[root].end(); ++it) {
sts.push_back(dfs(*it, sons, d, m));
}
set<int> ret({ 0 });
for (auto it = sts.begin(); it != sts.end(); ++it)
for (auto it2 = it->begin(); it2 != it->end(); ++it2)
if (d[sons[root][it - sts.begin()]] + *it2 <= m)
ret.insert(d[sons[root][it - sts.begin()]] + *it2);
for (auto it_i = sts.begin(); next(it_i) != sts.end(); ++it_i) {
for (auto it_j = it_i + 1; it_j != sts.end(); ++it_j) {
for (auto it = it_i->begin(); it != it_i->end(); ++it) {
for (auto it2 = it_j->begin(); it2 != it_j->end(); ++it2) {
if (d[sons[root][it_i - sts.begin()]] + d[sons[root][it_j - sts.begin()]] + *it + *it2 <= m)
ret.insert(d[sons[root][it_i - sts.begin()]] + d[sons[root][it_j - sts.begin()]] + *it + *it2);
}
}
}
}
return ret;
}
int main()
{
for (int m, n; cin >> m >> n; ) {
vector<Array > sons(n);
Array father(n, -1), d(n, 0);
int root = 0;
for (int i = 0, u, v, dd; i < n - 1; i++)
cin >> u >> v >> dd, d[v] = dd, sons[u].push_back(v), father[v] = u;
for (; root < (int)father.size() && father[root] != -1; ++root) {}
set<int> st(dfs(root, sons, d, m));
cout << (st.size() == 0 ? 0 : *st.rbegin()) << endl;
}
system("pause");
return 0;
} （修改自他人代码，感谢原作者的讲解）
数三角形
给出平面上的n个点，现在需要你求出，在这n个点里选3个点能构成一个三角形的方案有几种。
第一行包含一个正整数n，表示平面上有n个点（n<=100)
第2行到第n + 1行，每行有两个整数，表示这个点的x坐标和y坐标。(所有坐标的绝对值小于等于100，且保证所有坐标不同）
输出一个数，表示能构成三角形的方案数。
4
0 0
0 1
1 0
1 1
解析
这个题就是三层循环直接读取三个点，然后利用三个点共线条件判断三个点是否共线，若共线则不可能成为三角形，否则可以是三角形。
三角形共线条件：
(y3−y1)(x2−x1)−(y2−y1)(x3−x1)=0（斜率相等）
或者
x1y2+x2y3+x3y1-x1y3-x2y1-x3y2=0（三角形面积为0）
我这里用的是第二个条件
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
int main()
{
int n;//点数
int count=0;//计数
cin >> n;
vector<vector<int> >point(n, vector<int>(2));
for (int i = 0; i < n; i++)
{
cin >> point[i][0] >> point[i][1];
}
for (int i = 0; i < n - 2; i++)
{
for (int j = i + 1; j < n - 1; j++)
{
int temp1 = point[i][0] * point[j][1] - point[i][1] * point[j][0];
for (int k = j + 1; k < n; k++)
{
int temp2 = point[j][0] * point[k][1] - point[j][1] * point[k][0];
int temp3 = point[k][0] * point[i][1] - point[k][1] * point[i][0];
if ((temp1 + temp2 + temp3) != 0)
++count;
}
}
}
cout << count;
system("pause");
return 0;
}
最大乘积
给定一个无序数组，包含正数、负数和0，要求从中找出3个数的乘积，使得乘积最大，要求时间复杂度：O(n)，空间复杂度：O(1)
第一行是数组大小n，第二行是无序整数数组A[n]
满足条件的最大乘积
输入
3 4 1 2
输出
24
既然是输出三个乘积最大值，只有两种情况：
- 三个最大正整数相乘；
- 两个最小负数和一个最大正整数相乘。
其它任何一种情况，乘数都只可能小于等于上面两种情况，所以本题其实就是在O(n)的时间复杂度内实现寻找这5个数的方法，O(1)的空间复杂度表示了我们不能使用例如数组之类的来进行辅助存储。所以我们要做的就是找出这两种情况的乘积进行比较，返回最大的那一个。
#include <iostream>
#include <cmath>
using namespace std;
#define MAXSIZE 1000
int main()
{
long long mmin=0,min=0,max1=0,max2=0,max3 = 3;
//这个题的关键就在于学会在O(n)的时间复杂度寻找大于最小的2个值和最大的3个值
//以后还可以递推到最小的m个值和最大的n个值等
int n;//数组大小
int i;
long long a[MAXSIZE];
cin >> n;
for (i = 0; i < n; i++)
{
cin >> a[i];
}
for (i = 0; i < n; i++)
{
if (a[i] < mmin)
{
min = mmin;
mmin = a[i];
}
else if (a[i] < min)
min = a[i];
else if (a[i] > max3)
{
max1 = max2;
max2 = max3;
max3 = a[i];
}
else if ((a[i] > max2)&&(a[i]<max3))//这里一定要判断小于max3
{
max1 = max2;
max2 = a[i];
}
else if ((a[i] > max1)&&(a[i]<max2))//这里一定要判断小于max2
max1 = a[i];
}
long long result;
long long res1 = mmin*min*max3;
long long res2 = max1*max2*max3;
result = (res1 > res2) ? res1 : res2;
cout << result;
//system("pause");
return 0;
}
小熊吃糖
有n只小熊，他们有着各不相同的战斗力。每次他们吃糖时，会按照战斗力来排，战斗力高的小熊拥有优先选择权。前面的小熊吃饱了，后面的小熊才能吃。每只小熊有一个饥饿值，每次进食的时候，小熊们会选择最大的能填饱自己当前饥饿值的那颗糖来吃，可能吃完没饱会重复上述过程，但不会选择吃撑。
现在给出n只小熊的战斗力和饥饿值，并且给出m颗糖能填饱的饥饿值。
求所有小熊进食完之后，每只小熊剩余的饥饿值。
第一行两个正整数n和m，分别表示小熊数量和糖的数量。（n <= 10, m <= 100）
第二行m个正整数，每个表示着颗糖能填充的饥饿值。
接下来的n行，每行2个正整数，分别代表每只小熊的战斗力和当前饥饿值。
题目中所有输入的数值小于等于100。
输出n行，每行一个整数，代表每只小熊剩余的饥饿值。
2 5
5 6 10 20 30
4 34
3 35
模拟出来即可。这里我用了一个bear类用来存储每一个熊的情况，id是为了后续的用处。
我的思路就是对所有的熊先按照战斗力由大到小进行排序，这样后面for循环的时候，战斗力强的熊先吃。
由于先吃能量值最大的糖，所以对糖由大道小进行排序，这样for循环的时候，熊先吃能量值最大的糖。
最后要输出的时候是按照输入的顺序输出，所以我设置了一个id对熊进行编号，这样我再按照id对熊恢复原来输入的顺序，这样输出即可。
所以设置了三个compare函数用在sort函数之中。
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
class Bear {
public:
Bear(int f = 0, int h = 0, int id = 0) :fight(f), hungry(h), id(id) {}
int fight;//战斗力
int hungry;//饥饿值
int id;//熊的ID
};
//定义几个比较
bool cmp_fight(const Bear &a, const Bear &b)
{
return a.fight > b.fight;
}
bool cmp_id(const Bear &a, const Bear &b)
{
return a.id < b.id;
}
bool cmp_sugar(const int a, const int b)
{
return a > b;
}
//主函数
int main()
{
int n = 0, m = 0;//n个熊，m颗糖
int i;
cin >> n >> m;
vector<int> sugar(m);
vector<Bear> bear(n);
for (i = 0; i < m; i++)
{
cin >> sugar[i];
}
sort(sugar.begin(), sugar.end(), cmp_sugar);
for (i = 0; i < n; i++)
{
cin >> bear[i].fight >> bear[i].hungry;
bear[i].id = i;
}
//为了方便让战斗力强的先吃到，就排序，让战斗力强的在前面
sort(bear.begin(), bear.end(), cmp_fight);
//下面开始吃
for (i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
//如果饥饿值大于等于糖的能量才吃，否则就不吃
if (bear[i].hungry >= sugar[j])
{
bear[i].hungry -= sugar[j];
sugar[j] = 0;
}
}
}
//把熊的排序恢复过来
sort(bear.begin(), bear.end(), cmp_id);
for (i = 0; i < n; i++)
{
cout << bear[i].hungry << endl;
}
system("pause");
return 0;
}
![吴恩达logistic回归实现[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)