題目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=)