【机器学习】 应用简例 随机森林 交叉验证 网格化搜索.md

说明 - 2022-05-05

本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。

%matplotlib inline
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.ensemble import RandomForestClassifier
from sklearn.model_selection import train_test_split
from sklearn.model_selection import GridSearchCV
from sklearn.model_selection import cross_val_score
from sklearn.model_selection import GridSearchCV

导入数据


# 从excel表导入数据
df_t = pd.read_excel(r’D:\EdgeDownloadPlace\3dd40612152202ee8440f82a3d277008\train.xlsx’)

# 删除uid列
df_t = df_t.drop(columns='uid')

# 把数据中的'?'换成每一列的众数
for col in df_t.columns:
    idx = df_t[col].value_counts().index
    df_t[col][df_t[col] == '?'] = idx[0] if idx[0] != '?' else idx[1]

# 把pandas.DataFrame数据转化为numpy.darray数据 元素类型为np.float32
arr_t = df_t.values.astype(np.float32)

交叉验证找分数最高的n_estimators


score_tt = []
for i in range(0,300,15):
rfc = RandomForestClassifier(n_estimators = i+1
,n_jobs = -1
,random_state = 156535
)
score = cross_val_score(rfc, arr_t[:,:-1],arr_t[:,-1],cv=10).mean()
score_tt.append(score)
peak = [max(score_tt), score_tt.index(max(score_tt))*15+1]
plt.figure(figsize = [20,5])
plt.plot(range(1,301,15),score_tt)
plt.show()
peak

![在这里插入图片描述](https://img-blog.csdnimg.cn/20201031121122721.PNG?x-oss-
process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dsZGNtenk=,size_16,color_FFFFFF,t_70#pic_center)


score_tt = []
for i in range(peak[1]-15,peak[1]+15):
rfc = RandomForestClassifier(n_estimators = i+1
,n_jobs = -1
,random_state = 156535)
score = cross_val_score(rfc, arr_t[:,:-1],arr_t[:,-1],cv=10).mean()
score_tt.append(score)
peak = [max(score_tt), ([*range(peak[1]-15,peak[1]+15)][score_tt.index(max(score_tt))])]
plt.figure(figsize = [20,5])
plt.plot(range(peak[1]-15,peak[1]+15),score_tt)
plt.show()
peak

![在这里插入图片描述](https://img-blog.csdnimg.cn/20201031121129915.PNG?x-oss-
process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dsZGNtenk=,size_16,color_FFFFFF,t_70#pic_center)


n_peak = peak[1]

网格化搜索找最大深度


param_grid = {‘max_depth’ : np.arange(1,14)}

rfc =  rfc = RandomForestClassifier(n_estimators = n_peak
                                ,random_state = 156535
                                   ) 
GS = GridSearchCV(rfc,param_grid,cv=10)
GS.fit(arr_t[:,:-1],arr_t[:,-1])

#GS.best_params_ #返回最佳参数

#GS.best_score_ #返回最佳参数对应的准确率

[GS.best_score_, GS.best_params_]



depth_peak=GS.best_params_[‘max_depth’]

同理min_samples_split


param_grid = {‘min_samples_split’ : np.arange(2,30)}

rfc =  rfc = RandomForestClassifier(n_estimators = n_peak
                                ,random_state = 156535
                                ,max_depth = depth_peak
                                   )
GS = GridSearchCV(rfc,param_grid,cv=10)
GS.fit(arr_t[:,:-1],arr_t[:,-1])

#GS.best_params_ #返回最佳参数

#GS.best_score_ #返回最佳参数对应的准确率

[GS.best_score_, GS.best_params_]

同理 criterion


param_grid = {‘criterion’ : [‘gini’,‘entropy’]}

rfc =  rfc = RandomForestClassifier(n_estimators = n_peak
                                ,random_state = 156535
                                ,max_depth = depth_peak
                                   )
GS = GridSearchCV(rfc,param_grid,cv=10)
GS.fit(arr_t[:,:-1],arr_t[:,-1])

#GS.best_params_ #返回最佳参数

#GS.best_score_ #返回最佳参数对应的准确率

[GS.best_score_, GS.best_params_]

网格化搜索n_estimators


param_grid = {‘n_estimators’ : np.arange(1,300,15)}

rfc = RandomForestClassifier( random_state = 156535
                               
                                   )
GS = GridSearchCV(rfc,param_grid,cv=10)
GS.fit(arr_t[:,:-1],arr_t[:,-1])

#GS.best_params_ #返回最佳参数

#GS.best_score_ #返回最佳参数对应的准确率

[GS.best_score_, GS.best_params_]

【机器学习】应用简例 使用sklearn交叉验证随机森林.md

说明 - 2022-05-05

本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。

从excel中导入训练集+交叉验证随机森林


import numpy as np
import pandas as pd
from sklearn.ensemble import RandomForestClassifier
from sklearn.model_selection import cross_val_score
import matplotlib.pyplot as plt

# 从excel表导入数据
df_t = pd.read_excel(r'D:\EdgeDownloadPlace\3dd40612152202ee8440f82a3d277008\train.xlsx')

# 删除uid列
df_t = df_t.drop(columns='uid')

# 把数据中的'?'换成每一列的众数
for col in df_t.columns:
    idx = df_t[col].value_counts().index
    df_t[col][df_t[col] == '?'] = idx[0] if idx[0] != '?' else idx[1]

# 把pandas.DataFrame数据转化为numpy.darray数据 元素类型为np.float32
arr_t = df_t.values.astype(np.float32)

# 获得100次交叉验证的总体成绩 这100次验证决策树的个数为1-100
scores = []
for i in range(100):
    rfc = RandomForestClassifier(n_estimators = i+10, n_jobs = -1)
    rfc_s = cross_val_score(rfc,arr_t[:,:-1],arr_t[:,-1],cv=10).mean()
    scores.append(rfc_s)

# 画出来
plt.plot(range(1,101),scores,label = 'RandomForest')
plt.show()

【机器学习】应用简例 决策树 并用graphviz可视化树.md

说明 - 2022-05-05

本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。

导入库


import pandas as pd
import numpy as np
from sklearn import tree
from sklearn.model_selection import train_test_split

导入数据


df_t=pd.read_excel(r’D:\EdgeDownloadPlace\3dd40612152202ee8440f82a3d277008\train.xlsx’)
df_t=df_t.drop(columns=‘uid’)
df_t

![df_t](https://img-blog.csdnimg.cn/20201028221351794.png?x-oss-
process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dsZGNtenk=,size_16,color_FFFFFF,t_70#pic_center)
用众数替换问号


for col in df_t.columns:
df_t[col][df_t[col] == ‘?’] = df_t[col].value_counts().index[0] if df_t[col].value_counts().index[0] != ‘?’ else df_t[col].value_counts().index[1]
df_t

![df_t2](https://img-blog.csdnimg.cn/20201028221513308.png?x-oss-
process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dsZGNtenk=,size_16,color_FFFFFF,t_70#pic_center)
得到float类型矩阵


arr_t=df_t.values.astype(np.float32)
arr_t

array([[61., 0., 2., …, 0., 7., 0.],
[64., 1., 3., …, 0., 7., 1.],
[40., 0., 4., …, 0., 6., 1.],
…,
[65., 0., 3., …, 1., 3., 0.],
[63., 1., 4., …, 0., 7., 0.],
[55., 0., 4., …, 1., 7., 1.]], dtype=float32)
把训练集分成测试集训练集(倒入的全是训练集)

Xtrain,Xtest,Ytrain,Ytest = train_test_split(arr_t[:,:-1],arr_t[:,-1],test_size=0.3)

实例化决策树,训练模型,查看正确率


dtc = tree.DecisionTreeClassifier(criterion=“entropy”
,max_depth=4
,min_samples_split=10).fit(Xtrain,Ytrain)
score = dtc.score(Xtest,Ytest)
score

0.8140703517587939

画图


graph_tree = graphviz.Source(tree.export_graphviz(dtc
,feature_names = df_t.keys()[:-1]
,class_names = [‘患病’,‘不患病’]
,filled = True
,rounded = True))
graph_tree

![graph_tree](https://img-blog.csdnimg.cn/20201028221815494.png?x-oss-
process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dsZGNtenk=,size_16,color_FFFFFF,t_70#pic_center)

【机器学习】应用简例 随机森林 使用袋外数据(袋装法) + RandomForestClassifier的一些常用方法.md

说明 - 2022-05-05

本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。

import numpy as np
import pandas as pd
from sklearn.ensemble import RandomForestClassifier

# 从excel表导入数据
df_t = pd.read_excel(r'D:\EdgeDownloadPlace\3dd40612152202ee8440f82a3d277008\train.xlsx')

# 删除uid列
df_t = df_t.drop(columns='uid')

# 把数据中的'?'换成每一列的众数
for col in df_t.columns:
    idx = df_t[col].value_counts().index
    df_t[col][df_t[col] == '?'] = idx[0] if idx[0] != '?' else idx[1]

# 把pandas.DataFrame数据转化为numpy.darray数据 元素类型为np.float32
arr_t = df_t.values.astype(np.float32)



rfc = RandomForestClassifier(bootstrap=True #boostrap默认为True 即使用装袋法
,oob_score=True #oob_score默认为False 为True即使用袋外数据做测试集,训练模型时不需要划分训练集和测试集#
,max_depth=4
)
rfc = rfc.fit(arr_t[:,:-1],arr_t[:,-1])

print(rfc.oob_score_) #打印成绩


print(rfc.estimators_) #打印所有的树

print(rfc.feature_importances_) #打印特征的重要性

Xtrain,Xtest,Ytrain,Ytest = train_test_split(arr_t[:,:-1],arr_t[:,-1],test_size=0.3)

rfc = RandomForestClassifier(max_depth=4).fit(Xtrain,Ytrain)

print(rfc.apply(Xtest)) #返回测试集中 每一个样本 在每一颗树中的叶子节点的索引

print(rfc.predict(Xtest)) #返回模型预测的测试集的结果

print(rfc.predict_proba(Xtest)) #返回每一个样本被分到每一个标签的概率

【机器学习】应用简例 随机森林-小白无脑乱用.md

说明 - 2022-05-05

本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。

发现随机森林的正确率在0.76-0.86左右,多次用随机森林找一个正确率大于0.84的模型输出答案

这次用到的参数:
rfc=RandomForestClassifier(n_estimators=100 #决策树的数量
,criterion=“entropy” #分类标准-信息熵or基尼系数
,max_depth=4 #决策树最大深度
,min_samples_split=10) #至少有10个数据,树才会继续分支

把训练集分为新训练集和新问题集,在这上面验证准确性
Xtrain, Xtest, Ytrain, Ytest =
train_test_split(arr_t[:,:-1],arr_t[:,-1],test_size=0.3)
#(数据集,答案集,如何划分)0.3表示训练集和问题集三七分


import numpy as np
import pandas as pd
from sklearn.ensemble import RandomForestClassifier
#随机森林分类器
from sklearn.model_selection import train_test_split
#功能:将数据集分为训练集测试集 Xtrain,Xtest,Ytrain,Ytest

df_t=pd.read_excel(r'D:\EdgeDownloadPlace\3dd40612152202ee8440f82a3d277008\train.xlsx')
df_a=pd.read_excel(r'D:\EdgeDownloadPlace\3dd40612152202ee8440f82a3d277008\test.xlsx')

def get_data_array_float64(df,test=False):
    df = df.drop(columns='uid')
    #去列名对应的列
    if test == True:
        df=df.drop(columns ='target')
        #去列名对应的列
        
    col_mode_lst=[]
    for each_col in df.columns:#获得每一列的众数
        cnts = df[each_col].value_counts()
   		#得到每一列的所有值以及它们出现的次数 ,降序排列
        if '?' in cnts and cnts.index[0] == '?':
            idx=1
        else :
            idx=0
        col_mode_lst.append(cnts.index[idx])

    for i in range(len(df.columns)):
        df[df.columns[i]][df[df.columns[i]] == '?'] = col_mode_lst[i]
        #df[df.columns[i]]按照列名获得列
		#按照列名获得列,找到列中值为‘?’的元素,将其改成col_mode_lst[i]
		
    df_array = df.values.astype(np.float64)
    #df.values得到DataFrame对象的矩阵形式
    #,astype()方法为矩阵转化元素类型
    return df_array

arr_t=get_data_array_float64(df_t)
arr_a=get_data_array_float64(df_a,True)


Xtrain, Xtest, Ytrain, Ytest = train_test_split(arr_t[:,:-1],arr_t[:,-1],test_size=0.3)

while True:
    rfc=RandomForestClassifier(n_estimators=100
                                ,criterion="entropy"
                               ,max_depth=4
                               ,min_samples_split=10)
                           		#实例化随机森林
    rfc = rfc.fit(Xtrain,Ytrain)
    #训练模型
    score = rfc.score(Xtest,Ytest)
    #得到正确率
    if score>0.84:
        answer = rfc.predict(arr_a).astype(np.int8).tolist()
        break

answer_df=pd.DataFrame(answer)
answer_df.to_excel(r'D:\EdgeDownloadPlace\3dd40612152202ee8440f82a3d277008\20201028ans.xlsx')

【树形dp练习】洛谷 P2014选课 P1352没有上司的舞会P2016战略游戏.md

说明 - 2022-05-05

本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。

洛谷 P2014选课


#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
typedef long long LL;
const int N = 305;
int dp[N][N],score[N];
std::vectorson[N];
int n,m,f,g;

void dfs(int rt)
{
   dp[rt][1] = score[rt];
   dp[rt][0] = 1;
   for(int i=0; i<son[rt].size(); i++){
      int lt = son[rt][i];
      dfs(lt);
      dp[rt][0] += dp[lt][0];
   }
   int lim = std::min(dp[rt][0],m+1);
   for(int i=0; i<son[rt].size(); i++){
      int lt = son[rt][i];
      int limk = std::min(dp[lt][0],m+1);
      for(int j=lim; j>=2; j--){
         for(int k=1; k<=limk; k++){
            if(j-k <1) break;
            dp[rt][j] = std::max(dp[rt][j],dp[rt][j-k]+dp[lt][k]);
         }
      }
   }
}


int main()
{
memset(dp,0,sizeof(dp));
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++){
scanf("%d%d",&f,&g);
son[f].push_back(i);
score[i] = g;
}
score[0] = 0;
dfs(0);
std::cout << dp[0][m+1] << std::endl;
return 0;
}


二刷改良


#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
const int N = 305;


std::vector son[N];

int dp[N][N];
int val[N];
int n,m,f,v;

void dfs(int x)
{
   dp[x][0] = 1;
   dp[x][1] = val[x];
   for(int i=0; i<son[x].size(); i++){
      int y = son[x][i];
      dfs(y);
      dp[x][0] += dp[y][0];
      for(int j=m+1; j>=2; j--){
         int lim = std::min(dp[y][0],j);
         for(int k=1; k<j; k++){
            dp[x][j] = std::max(dp[x][j],dp[x][j-k]+dp[y][k]);
         }
      }
   }
}

int main()
{
   scanf("%d%d",&n,&m);
   val[0] = 0;
   for(int i=1; i<=n; i++){
      scanf("%d%d",&f,&v);
      val[i] = v;
      son[f].push_back(i);
   }
   dfs(0);
   printf("%d",dp[0][m+1]);
   return 0;
}

洛谷 P1352 没有上司的舞会


#include <bits/stdc++.h>
typedef long long LL;

const int N = 6e3+5;
std::vector<int> son[N];
int qu[N],has[N],dp[N][2];
int n,a,b,rt;

void dfs(int rt)
{
   dp[rt][0] = 0;
   dp[rt][1] = qu[rt];
   for(int i=0; i<son[rt].size(); i++){
      int lt = son[rt][i];
      dfs(lt);
      dp[rt][0] += std::max(dp[lt][0],dp[lt][1]);
      dp[rt][1] += dp[lt][0];
   }
}


int main(){
scanf("%d",&n);
for(int i=1; i<=n; i++){
scanf("%d",&qu[i]);
}
for(int i=1; i<n; i++){
scanf("%d%d",&a,&b);
has[a] = 1;
son[b].push_back(a);
}
for(int i=1; i<=n; i++){
if(!has[i]){
rt = i;
break;
}
}
dfs(rt);
printf("%d",std::max(dp[rt][0],dp[rt][1]));
return 0;
}


洛谷 P2016 战略游戏


#include
#include
#include
#include
#include
#include
typedef std::pair<int ,int> PP;
const int N = 1502;
std::vector son[N];
int n,k,u,v;
int dp[N][2];
void dfs(int x)
{
dp[x][0] = 0;
dp[x][1] = 1;
for(int i=0; i<son[x].size(); i++){
int y = son[x][i];
dfs(y);
dp[x][0] += dp[y][1];
dp[x][1] += std::min(dp[y][1],dp[y][0]);
}
}

int main()
{

   scanf("%d",&n);
   for(int i=0; i<n; i++){
      scanf("%d%d",&u,&k);
      for(int j=0; j<k; j++){
         scanf("%d",&v);
         son[u].push_back(v);
      }
   }
   dfs(0);
   printf("%d",std::min(dp[0][0],dp[0][1]));

   return 0;
}

【树状数组练习】洛谷 树状数组模板1、2 P1908 逆序对.md

说明 - 2022-05-05

本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。

洛谷 P3374 树状数组模板1


#include
#include
#include
#include
#include
#include
#include
#include
//typedef long long int LL;
typedef std::pair<std::string ,char> PP;
const int N = 5e5+5;
int tree[N];
int n,m,vv,op,a,b;

void add(int i,int v)
{
   while(i<=n){
      tree[i] += v;
      i += i&(-i);
   }
}

int query(int i)
{
   int re = 0;
   while(i>=1){
      re += tree[i];
      i -= i&(-i);
   }
   return re;
}

int main()
{
   scanf("%d%d",&n,&m);
   for(int i=1; i<=n; i++){
      scanf("%d",&vv);
      add(i,vv);
   }
   for(int i=0; i<m; i++){
      scanf("%d%d%d",&op,&a,&b);
      if(op == 1){
         add(a,b);
      }
      else{
         printf("%d\n",query(b)-query(a-1));
      }
   }
   return 0;
}

洛谷 P3368树状数组模板2

在区间中求某一单点的树状数组。初始化树状数组时,增加的值为"此点比上一个点大多少"


#include
#include
#include
#include
#include
#include
#include
#include
typedef long long int LL;
//typedef std::pair<std::string ,char> PP;
const int N = 5e5+5;
LL tree[N];
int n,m,op,a,b;
LL c,vv,ls;

void add(int i,LL v)
{
   while(i<=n){
      tree[i] += v;
      i += i&(-i);
   }
}

LL query(int i)
{
   LL re = 0;
   while(i>=1){
      re += tree[i];
      i -= i&(-i);
   }
   return re;
}

int main()
{
   scanf("%d%d",&n,&m);
   ls = 0;
   for(int i=1; i<=n; i++){
      scanf("%lld",&vv);
      add(i,vv-ls);
      ls = vv;
   }
   for(int i=0; i<m; i++){
      scanf("%d",&op);
      if(op == 1){
         scanf("%d%d%lld",&a,&b,&c);
         add(a,c);
         add(b+1,-c);
      }
      else{
         scanf("%d",&a);
         printf("%lld\n",query(a));
      }

   }
   return 0;
}

洛谷 P1908 逆序对

数据大小的范围是1e9,但是我们只需要知道他们的大小关系,所以可以压成5e5做


#include
#include
#include
#include
#include
#include
#include
#include
typedef long long int LL;
//typedef std::pair<int ,int> PP;
const int N = 5e5+5;
int tree[N],ord[N];
struct AA
{
int val,n;
}qu[N];
int n,v,idx;
LL ans;

void add(int i,int x)
{
   while(i<=n){
      tree[i] += x;
      i += i&(-i);
   }
}

LL qry(int i)
{
   LL re = 0;
   while(i>0){
      re += tree[i];
      i -= i&(-i);
   }
   return re;
}

bool cmp(AA x , AA y)
{
   if(x.val == y.val) return x.n<y.n;
   return x.val < y.val;
}

int main()
{
   //freopen("D:\\EdgeDownloadPlace\\P1908_11.in","r",stdin);
   ans = 0;
   scanf("%d",&n);
   for(int i=1; i<=n; i++){
      scanf("%d",&qu[i].val);
      qu[i].n = i;
   }
   std::sort(qu+1,qu+n+1,cmp);
   for(int i=1; i<=n; i++){
      ord[qu[i].n] = i;
   }
   for(int i=1; i<=n; i++){
      add(ord[i],1);
      ans += i-qry(ord[i]);
   }
   printf("%lld\n",ans);

   return 0;
}

【树的直径 dfs dp】P4408 [NOI2003] 逃学的小孩.md

说明 - 2022-05-05

本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。

P4408 [NOI2003] 逃学的小孩


#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
typedef long long int LL;
const int N = 2e5+5, M = -1, INF = 0x7fffffff;
int n,m,u,v,pid,tid;
LL w,plong,tlong;
int idx;
int head[N];
LL disa[N],disb[N];
struct Edge
{
int to,nxt;
LL w;
}edg[N<<1];
void addEdge(int fr,int to,LL w)
{
edg[idx].to = to;
edg[idx].nxt = head[fr];
edg[idx].w = w;
head[fr] = idx++;
}
void initial()
{
idx = 2;
}
void dfs(LL leng,int id,int efrom)
{
if(leng > plong){
plong = leng;
pid = id;
}
for(int e=head[id]; e; e=edg[e].nxt){
if((e^1) == efrom) continue;
dfs(leng+edg[e].w,edg[e].to,e);
}
}
void DFS(LL dis[],int x,int efrom,LL leng)
{
dis[x] = leng;
for(int e=head[x]; e; e=edg[e].nxt){
if((e^1) == efrom) continue;
int y = edg[e].to;
DFS(dis,y,e,leng+edg[e].w);
}
}
int main()
{
initial();
scanf("%d%d",&n,&m);
for(int i=0; i<m; i++) {
scanf("%d%d%lld",&u,&v,&w);
addEdge(u,v,w);
addEdge(v,u,w);
}
pid = 1, plong = 0;
dfs(0,pid,0);
tid = pid;
pid = tid, plong = 0;
dfs(0,pid,0);
DFS(disa,tid,0,0);
DFS(disb,pid,0,0);
tlong = 0;
for(int i=1; i<=n; i++){
tlong = std::max(tlong,std::min(disa[i],disb[i]));
}
printf("%lld",tlong+plong);
return 0;
}

【树的直径】树形DP求解.md

说明 - 2022-05-05

本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。

思路

每次记录每个子树从根到叶的最长的链, 然后把最长前2长的拼起来
先更新D再更新dp, 否则会求出一条最长链*2


void dfs(int x, int efr){
for(int e = head[x]; e; e = edg[e].nxt){
if((e ^ 1) == efr) continue;
int y = edg[e].to;
dfs(y, e);
D = std::max(D, dp[x] + dp[y] + 1);
dp[x] = std::max(dp[x], dp[y] + 1);
}
}

HDU 6201 transaction transaction transaction(非模题)


#include <bits/stdc++.h>
const int N = 1e5 + 4;
int val[N], dp[N][2], head[N];
struct Edge{
int to, nxt, va;
}edg[N << 1];
int idx, n, t, u, v, w, ans;
void addE(int fr, int to , int w){
edg[idx].to = to;
edg[idx].nxt = head[fr];
edg[idx].va = w;
head[fr] = idx ;
}
void dfs(int x, int efr){
dp[x][0] = val[x], dp[x][1] = -val[x];
for(int e=head[x]; e; e=edg[e].nxt){
if((e ^ 1) == efr) continue;
int y = edg[e].to;
dfs(y, e);
dp[x][0] = std::min(dp[x][0], dp[y][0] + edg[e].va);
dp[x][1] = std::min(dp[x][1], dp[y][1] + edg[e].va);
}
ans = std::min(ans, dp[x][0] + dp[x][1]);
}
int main(){
scanf("%d", &t);
while(t --){
scanf("%d", &n);
idx = 2, ans = 0;
for(int i=0; i<=n; i
) head[i] = 0;
for(int i=1; i<=n; i++) scanf("%d", &val[i]);
for(int i=1; i<n; i++){
scanf("%d%d%d", &u, &v, &w);
addE(u, v, w), addE(v, u, w);
}
dfs(1, -1);
printf("%d\n", -ans);
}
return 0;
}

【爬虫】 爬取云班课上老师发的视频资源 python.md

说明 - 2022-05-05

本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。

蒟蒻声明

这个程序虽然可以差强人意地实现功能但是烂的一批,也不打算做出较大改动了。后面会总结一些不足之处,以警示以后。

思路


1.
通过抓包发现云班课的视频时m3u8的,即一个m3u8的文件中记录了数个ts类型视频的链接,这些ts视频的时常一般为10秒。想爬取某个视频只需要获取视频对应的m3u8文件,依次把m3u8文件中的ts文件下载并通过os.system()调用命令行把一系列的ts文件合并为mp4
2.
步骤1是单独下载一个视频的思路,若想下载所有视频,只需要找出所有视频的m3u8,重复步骤1。

单独下载一个m3u8

笔者仅仅在要爬的课程中实验该程序可以达到目的,至于其他的m3u8就不清楚了
1.
获取m3u8文件后解析其内容,做到可以提取出所有的ts文件链接
2.
把所有的ts文件下载本地的同一个文件夹中
3.
调用命令行,例如这样:
os.system(‘copy /b ‘+os.path.abspath(tempworkpath)+’\ _.ts
‘+os.path.abspath(pathOUTPUT)+’\’+nameOUTPUT+’.mp4’)
合并所有ts文件为一个新的mp4文件
4.
把这一次下载的ts文件删掉,以备下一次操作
os.system('del ‘+os.path.abspath(tempworkpath)+’_.ts’)

import re
import requests
from bs4 import BeautifulSoup
import os


def DownOne(url,name):
    toIdxStr = lambda x : ('000000000'+str(x))[-10:]

    urlM3U8 = url
    nameOUTPUT = name.replace(' ','')
    pathOUTPUT = 'out'
    sch = re.search('(.+?/[0-9].{3}/[0-9].{1}/[0-9].{1}/)(.+?).m3u8',urlM3U8)
    headM3U8 = sch.group(1)
    nameM3U8 =sch.group(2)
    tempworkpath = 'aaabbbcccdddeeefffggghhhiii'
    
    resM3U8 = requests.get(urlM3U8)
    
    lstTS = re.findall('.+?ts',resM3U8.text)
    
    if not os.path.exists(tempworkpath):
        os.mkdir(tempworkpath)
    if not os.path.exists(pathOUTPUT):
        os.mkdir(pathOUTPUT)
    
    for i,each in enumerate(lstTS):
        print(i,'of',len(lstTS))
        res = requests.get(headM3U8+each)
        with open(tempworkpath+'/'+nameM3U8+toIdxStr(i)+'.ts', 'wb') as f:
            f.write(res.content)
    
    print('合并')
    print('copy /b '+os.path.abspath(tempworkpath)+'\\*.ts '+os.path.abspath(pathOUTPUT)+'\\'+nameOUTPUT+'.mp4')
    os.system('copy /b '+os.path.abspath(tempworkpath)+'\\*.ts '+os.path.abspath(pathOUTPUT)+'\\'+nameOUTPUT+'.mp4')
    os.system('del '+os.path.abspath(tempworkpath)+'\\*.ts')

if __name__ == '__main__':
    url = input('m3u8 url:')
    name = input('video name:')
    DownOne(url,name)

爬取全部的视频资源

下方代码中的import DownloaderM3U8 as DOWN,这个库是上面爬一个m3u8的那一坨
下面的程序这些部分我改了,爬的话要填自己的账号密码等

logData = { ‘account_name’ : ‘这里是我的账号’
,‘user_pwd’ : ‘这里是我的密码’
,‘remember_me’ : ‘N’
}
targetURL = ‘填需要获取资源的页面(云班课进入一个课程,再点资源,然后把链接复制过来)’
user-agent也改了,不太清楚这个是不是必要的

html解析思路

这是云班课储存资源的思路


​ <div1 这是包含所有视频的一块>
​ <div2 第一单元的所有视频> 所有的div2的集合对应程序里的d2
​ <div 视频> 一个div2中所有div的集合对应程序里的d3
​ <div 视频>
​ <div 视频>
​ <div 视频>
​ <div 视频>

​ <div2 第二单元的所有视频>
​ <div 视频>
​ <div 视频>
​ <div 视频>
​ <div 视频>
​ <div 视频>

​ <div2 第三单元的所有视频>
​ <div 视频>
​ <div 视频>
​ <div 视频>
​ <div 视频>
​ <div 视频>

值得一提的是我没有在网页的html中找到m3u8的链接,但是每个视频有一张图片,图片的链接和视频的m3u8链接有许多相同点。
其中图片的链接中有形如: '年份/月份/字符串’ 的格式,而m3u8的链接中有形如: ‘年份/月份/日期/字符串’
的格式,并且这两段格式中除了图片链接没有日期外,其他完全相同


​ #云班课视频资源获取 开始于2021/03/12
​ ‘’’
​ 目前没有任何try,纯莽

part1 登录 (成功)
part2 找到所有视频块div(成功)
part3 获取所有视频对应的m3u8链接(遇到问题)
问题:
html中没有找到对应的m3u8链接,但有一张图片的链接,其中有 #年份/月份/字符串# 的部分与我们需要的m3u8链接十分相似
需要的m3u8链接的该部分格式为 #年份/月份/日期/字符串# 所以尝试枚举已知月份中所有的日期暴力破解
事实证明这种方法有概率失败,因为有的m3u8链接会与图片连接中的月份有偏差,不保证能完全获取所有的m3u8链接
可能的解决方案:
1.尝试枚举一年中的所有日期而不是这个月的(需要时间长,但不失为一种方法,尚未尝试),
但不排除m3u8链接和img链接的年份也有偏差的可能
//-----------------------------------------------------------
2021/03/12:
若没有找到正确的m3u8链接,则尝试读取下一个月的所有日期
这样可以正确解析出更多的链接,但是仍然不能完全解决问题
//-----------------------------------------------------------

part4 针对每一个m3u8链接下载其中的所有js链接,并尝试调用命令行指令合并ts文件为mp4(尚未开始,太懒了)
    这一步脱离前三个part,独立进行
'''

import re
import requests
from bs4 import BeautifulSoup
import DownloaderM3U8 as DOWN

def monthIter(year,month):
    monthMap = { 1:  31 
                ,2:  28
                ,3:  31 
                ,4:  30
                ,5:  31
                ,6:  30
                ,7:  31
                ,8:  31
                ,9:  30
                ,10: 31
                ,11: 30
                ,12: 31
    }
    if month == 2:
        if year%400 == 0 or (year%4 == 0 and year%100 != 0):
            monthMap[2] += 1
    return range(1,monthMap[month]+1)


​ def toLinkStr(ss):
​ ss = str(ss)
​ return ‘0’+ss if len(ss) == 1 else ss


​ m3u8Head = ‘https://video-cdn-2.mosoteach.cn/mssvc/file
​ m3u8Tail = ‘m3u8’

logURL = r’https://www.mosoteach.cn/web/index.php?c=passport&m=account_login

session = requests.session()

logHeader = { 'Referer'      : 'https://www.mosoteach.cn/web/index.php?c=passport'
             ,'User-Agent'   : '填自己的,好像不填也行,不太清楚'
}
logData = {  'account_name' : '这里是我的账号'
            ,'user_pwd'     : '这里是我的密码'
            ,'remember_me'  : 'N'
} 

logRES = session.post(logURL ,headers = logHeader, data = logData)

targetURL = '填需要获取资源的页面(云班课进入一个课程,再点资源,然后把链接复制过来)'

res = session.get(targetURL)
soup = BeautifulSoup(res.text,features='lxml')
d1 = soup.find('div', id = 'res-list-box')
d2 = d1.find_all('div',class_ = 'hide-div')

namelst = []
lst = []
cnt = 0
jumplst = []
for i,one in enumerate(d2):
    #print('[第',i,'块]')
    d3 = one.find_all('div',class_ = 'res-row-open-enable res-row preview')
    for j,each in enumerate(d3):
        #print(' 第',j,'个',end = ' ')
        ss = each.find('img', class_ = 'res-icon')['src']
        linkKey = re.search('capture/([0-9].{3})/([0-9].{1})(.+?)jpg?',ss)
        m3u8Middle = m3u8Head + '/' + linkKey.group(1) + '/' + linkKey.group(2) + '/{day}' + linkKey.group(3) + m3u8Tail
        m3u8MiddlePLUS = m3u8Head + '/' + linkKey.group(1) + '/' + '{mth}' + '/{day}' + linkKey.group(3) + m3u8Tail
        cnt += 1 
        print(cnt)
        print(m3u8Middle)
        #'''
        found = False
        zyear  = int(linkKey.group(1))
        zmonth = int(linkKey.group(2))
        for EE in monthIter(zyear,zmonth):
            m3u8Final = m3u8Middle.format(day = toLinkStr(EE))
            rr = requests.get(m3u8Final)
            if re.search('Error',rr.text) == None:
                lst.append(m3u8Final)
                namelst.append(each.find('span',class_ = 'res-name')['title'])
                print(m3u8Final)
                found = True
                break
        if found == False:
            zmonth += 1
            if zmonth > 12:
                zmonth = 1
                zyear += 1
                m3u8Middle = m3u8MiddlePLUS
            for EE in monthIter(zyear,zmonth):
                m3u8Final = m3u8Middle.format(day = toLinkStr(EE), mth = toLinkStr(zmonth))
                rr = requests.get(m3u8Final)
                if re.search('Error',rr.text) == None:
                    lst.append(m3u8Final)
                    namelst.append(each.find('span',class_ = 'res-name')['title'])
                    print(m3u8Final)
                    found = True
                    break
        if found == False:
            print('##第',i,'块第',j,'个已被跳过')
            jumplst.append((i,j))
        print('---')
       # '''
            #print(each,end = ' ')
        #print(int(linkKey.group(1)),int(linkKey.group(2)))

print('共跳过个数:', len(jumplst), '\n分别为:')
for each in jumplst:
    print(each)

print('len(lst) == len(namelst) ?',len(lst),len(namelst))

print('开始抓取')
for i in range(len(lst)):
    print(namelst[i])
    DOWN.DownOne(lst[i],namelst[i])


​ print(‘共跳过个数:’, len(jumplst), ‘\n分别为:’)
​ for each in jumplst:
​ print(each)

不足 与 可以预期的改进(已经不会去改了,所以是可以预期的改进)

不足

这个程序的思路是找到整个页面中所有的m3u8存入一个列表,然后遍历列表依次下载。这样时间非常长,如果中途出错还要从头开始重新来。

没有try,没有写try的意识,等着以后迎接暴毙吧

可以预期的改进

1.分块获取m3u8,先获取每一个大块,再在每一个大块中获得这一大块中所有视频的m3u8
2.细化获取项,提供获取某一特定块中所有视频的选项
3.细化获取项,提供在某一特定块中获取某一特定视频的选项
4.做出图形界面,以一级二级标签分好大块和每个大块中的视频,可以阵对视频多选,阵对块多选,进行下载