紫书训练 7.13

2024-03-20 17:08
文章标签 训练 7.13 紫书

本文主要是介绍紫书训练 7.13，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://vjudge.net/contest/310704  dp+点分治

密码：996996

A - Lighting System Design

这个题目毒的太累了，dp[i]代表选前i个灯最少的消费，先按电压从小到大排，方便后面的转移。

#include<bits/stdc++.h>
#define il inline
#define pb push_back
#define fi first
#define se second
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define sc(n) scanf("%d",&n)
#define SC(n,m) scanf("%d %d",&n,&m)
#define SZ(a) int((a).size())
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define drep(i,a,b)	for(int i=a;i>=b;--i)
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-9;
const int maxn=1e3+5;
struct node{int v,k,c,l;
}a[maxn];
bool cmp(node x,node y){return x.v<y.v;
}
int n,sum[maxn],dp[maxn]; 
int main(){std::ios::sync_with_stdio(0);while(cin>>n && n){rep(i,1,n) cin>>a[i].v>>a[i].k>>a[i].c>>a[i].l;sort(a+1,a+n+1,cmp);rep(i,1,n) sum[i]=sum[i-1]+a[i].l;ms(dp,0x3f),dp[0]=0;for(int i=1;i<=n;++i){for(int j=1;j<=i;++j){dp[i]=min(dp[i],dp[j-1]+a[i].k+a[i].c*(sum[i]-sum[j-1]));}}cout<<dp[n]<<endl;}return 0;
}

B - Partitioning by Palindromes

 dp[i]代表到i字符最多的回文串，转移也很简单，但是要先处理一下i~j是不是回文串，一个简单的区间dp。


#include<bits/stdc++.h>
#define il inline
#define pb push_back
#define fi first
#define se second
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define sc(n) scanf("%d",&n)
#define SC(n,m) scanf("%d %d",&n,&m)
#define SZ(a) int((a).size())
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define drep(i,a,b)	for(int i=a;i>=b;--i)
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-9;
const int maxn=1e3+5;
int T,dp[maxn];
bool isp[maxn][maxn];
int main(){std::ios::sync_with_stdio(0);cin>>T;string s;while(T--){cin>>s;s.insert(s.begin(),'#');ms(dp,0),ms(isp,0);int len=SZ(s)-1;rep(i,1,len) isp[i][i]=1;for(int le=2;le<=len;++le){for(int i=1;i+le-1<=len;++i){int j=i+le-1;if(s[i]==s[j] && (isp[i+1][j-1]==1 || le==2)) isp[i][j]=1;}}for(int i=1;i<=len;++i){dp[i]=i;for(int j=0;j<i;++j){if(isp[j+1][i]) dp[i]=min(dp[i],dp[j]+1);}}cout<<dp[len]<<endl;}return 0;
}

C - Color Length

 根本想不到啊，太难了。定义了ad[i][j]为某些已经出现了，但尚未出现的颜色个数，从而方便转移。

#include<bits/stdc++.h>
#define il inline
#define pb push_back
#define fi first
#define se second
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define sc(n) scanf("%d",&n)
#define SC(n,m) scanf("%d %d",&n,&m)
#define SZ(a) int((a).size())
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define drep(i,a,b)	for(int i=a;i>=b;--i)
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-9;
const int maxn=5e3+3;
int dp[maxn][maxn],ad[maxn][maxn];
int T,le1[30],ri1[30],le2[30],ri2[30];
int main(){std::ios::sync_with_stdio(0);cin>>T;string s1,s2;while(T--){cin>>s1>>s2;s1.insert(s1.begin(),'#'),s2.insert(s2.begin(),'#');ms(le1,0x3f),ms(ri1,0),ms(le2,0x3f),ms(ri2,0);for(int i=1;i<SZ(s1);++i){if(le1[s1[i]-'A']==inf) le1[s1[i]-'A']=i,ri1[s1[i]-'A']=i;else ri1[s1[i]-'A']=i;}for(int i=1;i<SZ(s2);++i){if(le2[s2[i]-'A']==inf) le2[s2[i]-'A']=i,ri2[s2[i]-'A']=i;else ri2[s2[i]-'A']=i;}for(int i=0;i<SZ(s1);++i){for(int j=0;j<SZ(s2);++j){int sum=0;for(int k=0;k<26;++k){if((le1[k]<=i || le2[k]<=j) && (ri1[k]>i || ri2[k]>j)) sum++;}ad[i][j]=sum;  //某些颜色已经出现了，但尚未出现结束的个数 }}dp[0][0]=0;for(int i=0;i<SZ(s1);++i){for(int j=0;j<SZ(s2);++j){if(i==0 && j==0) continue;if(i==0) dp[i][j]=dp[i][j-1]+ad[i][j];else if(j==0) dp[i][j]=dp[i-1][j]+ad[i][j];else dp[i][j]=min(dp[i-1][j],dp[i][j-1])+ad[i][j];}}cout<<dp[SZ(s1)-1][SZ(s2)-1]<<endl;}return 0;
}

D - Cutting Sticks

 读完题，就会发现其实这就是石子合并，n^3的复杂度，但是有低于n^3复杂度的，但没有思考，懒了


#include<bits/stdc++.h>
#define il inline
#define pb push_back
#define fi first
#define se second
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define sc(n) scanf("%d",&n)
#define SC(n,m) scanf("%d %d",&n,&m)
#define SZ(a) int((a).size())
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define drep(i,a,b)	for(int i=a;i>=b;--i)
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-9;
const int maxn=1e3+5; 
int L,n,sum[maxn],dp[maxn][maxn];
int a[maxn],x;
int main(){std::ios::sync_with_stdio(0);while(cin>>L && L){cin>>n;rep(i,1,n){cin>>a[i];sum[i]=sum[i-1]+a[i]-a[i-1];} sum[n+1]=sum[n]+L-a[n];ms(dp,0x3f);for(int i=1;i<=n+1;++i) dp[i][i]=0;for(int len=2;len<=n+1;++len){for(int i=1;i+len-1<=n+1;++i){int j=i+len-1,ss=sum[j]-sum[i-1];for(int k=i;k<=j-1;++k){dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+ss);}}}cout<<"The minimum cutting is "<<dp[1][n+1]<<"."<<endl;}return 0;
}

E - Headmaster's Headache

 一道状压dp，学好状压，必须要对位运算有一定的掌握，思路参考这个 参考链接

#include<bits/stdc++.h>
#define il inline
#define pb push_back
#define fi first
#define se second
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define sc(n) scanf("%d",&n)
#define SC(n,m) scanf("%d %d",&n,&m)
#define SZ(a) int((a).size())
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define drep(i,a,b)	for(int i=a;i>=b;--i)
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-9;
const int maxn=5e2+5;
int n,m,s,cost[maxn],tea[maxn],dp[maxn][maxn][maxn];
il int run(int cur,int s1,int s2){if(cur == m+n+1){if(s2 == (1<<s)-1){return 0;}else return inf;}	if(dp[cur][s1][s2] != -1) return dp[cur][s1][s2];dp[cur][s1][s2]=inf;if(cur >= m+1)  dp[cur][s1][s2]=run(cur+1,s1,s2);int ns2 = s2|(s1 & tea[cur]);int ns1 = s1|tea[cur];dp[cur][s1][s2]=min(dp[cur][s1][s2],cost[cur]+run(cur+1,ns1,ns2));return dp[cur][s1][s2];
}
int main(){std::ios::sync_with_stdio(0);while(cin>>s>>m>>n && (n || m || s)){string ss;rep(i,1,m+n){cin>>cost[i];getline(cin,ss);stringstream sss(ss);tea[i]=0;int x;while(sss>>x){tea[i] |= 1<<(x-1);}}ms(dp,-1);cout<<run(1,0,0)<<endl;}return 0;
}

F - Party at Hali-Bula

一道树型dp，//dp[i][0]表示不选i点得到的最大人数，dp[i][1]则为选该点//f[i][0]代表不选这种的方案是否唯一(1，0区分)，f[i][1]同 。原型是树的最大独立集，但是这个加了方案是否唯一。参考链接

#include<bits/stdc++.h>
#define il inline
#define pb push_back
#define fi first
#define se second
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define sc(n) scanf("%d",&n)
#define SC(n,m) scanf("%d %d",&n,&m)
#define SZ(a) int((a).size())
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define drep(i,a,b)	for(int i=a;i>=b;--i)
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-9;
const int maxn=2e5+5;
unordered_map<string,int> id;
int n,cnt,dp[maxn][2],f[maxn][2];
//dp[i][0]表示不选i点得到的最大人数，dp[i][1]则为选该点
//f[i][0]代表不选这种的方案是否唯一(1，0区分)，f[i][1]同 
vector<int> eg[maxn];
il int getid(string s){if(id.count(s)) return id[s];else return id[s]=cnt++;
} 
il int run(int u,int op){if(dp[u][op]!=0) return dp[u][op];f[u][op]=true,dp[u][op]=op;for(int i=0;i<SZ(eg[u]);++i){int son=eg[u][i];if(op){dp[u][op] += run(son,0);if(!f[son][0]) f[u][op]=false;}else{dp[u][op]+=max(run(son,0),run(son,1));if(dp[son][0] == dp[son][1]) f[u][op]=false;else if(dp[son][0] > dp[son][1] && !f[son][0]) f[u][op]=false;else if(dp[son][1] > dp[son][0] && !f[son][1]) f[u][op]=false;}}
//	cout<<u<<" "<<op<<" "<<dp[u][op]<<endl;return dp[u][op];}
int main(){std::ios::sync_with_stdio(0);while(cin>>n && n){cnt=0;string x,y;cin>>x,getid(x);rep(i,1,n-1){cin>>x>>y;eg[getid(y)].pb(getid(x));}cout<<max(run(0,1),run(0,0))<<" ";if(dp[0][1] == dp[0][0]) cout<<"No"<<endl;else if(dp[0][1] > dp[0][0] && !f[0][1]) cout<<"No"<<endl;else if(dp[0][0] > dp[0][1] && !f[0][0]) cout<<"No"<<endl;else cout<<"Yes"<<endl;ms(dp,0),id.clear();rep(i,0,n) eg[i].clear();}return 0;
}

G - Tree

点分治裸题，之前也是作过的。传送

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<cmath>
#include<sstream>
//#include<bits/stdc++.h>
#define il inline
#define pb push_back
#define fi first
#define se second
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define sc(n) scanf("%d",&n)
#define SC(n,m) scanf("%d %d",&n,&m)
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define drep(i,a,b)	for(int i=a;i>=b;--i)
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-9;
const int maxn=1e4+5;
int n,k,sz[maxn],root,mx,all,l,r;
ll dis[maxn],q[maxn],ans;
bool vis[maxn];
struct node{int to,w;
};
vector<node> mp[maxn];
il void getroot(int x,int fa){ //获取重心sz[x]=1;int num=0;for(int i=0;i<(int)(mp[x].size());++i){int nto=mp[x][i].to;if(vis[nto] || fa==nto) continue;getroot(nto,x);sz[x]+=sz[nto];num=max(num,sz[nto]);}num=max(num,all-num);if(num<mx){mx=num;root=x;}
}
il void getdis(int x,int fa){ //源点到该分支各点的距离q[++r]=dis[x];for(int i=0;i<(int)(mp[x].size());++i){int nto=mp[x][i].to,nw=mp[x][i].w;if(nto==fa || vis[nto]) continue;dis[nto]=dis[x]+nw;getdis(nto,x);}
}
il ll calc(int x,int v){ //计算满足的个数r=0,l=1,dis[x]=v;getdis(x,0);ll sum=0;sort(q+1,q+r+1);while(l<r){if(q[l]+q[r]<=k) sum+=r-l,l++;else r--;}return sum;
}
il void dfs(int x){ ans+=calc(x,0);vis[x]=1;for(int i=0;i<(int)(mp[x].size());++i){int nto=mp[x][i].to,nw=mp[x][i].w;if(vis[nto]) continue;ans-=calc(nto,nw); //减去不和条件的all=sz[x];mx=inf;getroot(nto,0);dfs(root);}
}
int main(){while(SC(n,k)!=EOF){if(n==0 && k==0) break;all=n,ans=0;int x,y,z;for(int i=1;i<=n-1;++i){sc(x),sc(y),sc(z);mp[x].pb(node{y,z});mp[y].pb(node{x,z});}mx=inf;getroot(1,0);dfs(root);cout<<ans<<endl;for(int i=0;i<=n+5;++i){mp[i].clear();vis[i]=0;}	}return 0;
}

 

这篇关于紫书训练 7.13的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/830164。

相关文章

MiniGPT-3D, 首个高效的3D点云大语言模型，仅需一张RTX3090显卡，训练一天时间，已开源

MiniGPT-3D, 首个高效的3D点云大语言模型，仅需一张RTX3090显卡，训练一天时间，已开源

项目主页：https://tangyuan96.github.io/minigpt_3d_project_page/ 代码：https://github.com/TangYuan96/MiniGPT-3D 论文：https://arxiv.org/pdf/2405.01413 MiniGPT-3D在多个任务上取得了SoTA，被ACM MM2024接收，只拥有47.8M的可训练参数，在一张RTX
阅读更多...
Spark MLlib模型训练—聚类算法 PIC(Power Iteration Clustering)

Spark MLlib模型训练—聚类算法 PIC(Power Iteration Clustering)

Spark MLlib模型训练—聚类算法 PIC(Power Iteration Clustering) Power Iteration Clustering (PIC) 是一种基于图的聚类算法，用于在大规模数据集上进行高效的社区检测。PIC 算法的核心思想是通过迭代图的幂运算来发现数据中的潜在簇。该算法适用于处理大规模图数据，特别是在社交网络分析、推荐系统和生物信息学等领域具有广泛应用。Spa
阅读更多...
SigLIP——采用sigmoid损失的图文预训练方式

SigLIP——采用sigmoid损失的图文预训练方式

SigLIP——采用sigmoid损失的图文预训练方式 FesianXu 20240825 at Wechat Search Team 前言 CLIP中的infoNCE损失是一种对比性损失，在SigLIP这个工作中，作者提出采用非对比性的sigmoid损失，能够更高效地进行图文预训练，本文进行介绍。如有谬误请见谅并联系指出，本文遵守CC 4.0 BY-SA版权协议，转载请联系作者并注
阅读更多...
Detectorn2预训练模型复现：数据准备、训练命令、日志分析与输出目录

Detectorn2预训练模型复现：数据准备、训练命令、日志分析与输出目录

Detectorn2预训练模型复现：数据准备、训练命令、日志分析与输出目录 在深度学习项目中，目标检测是一项重要的任务。本文将详细介绍如何使用Detectron2进行目标检测模型的复现训练，涵盖训练数据准备、训练命令、训练日志分析、训练指标以及训练输出目录的各个文件及其作用。特别地，我们将演示在训练过程中出现中断后，如何使用 resume 功能继续训练，并将我们复现的模型与Model Zoo中的
阅读更多...
多云架构下大模型训练的存储稳定性探索

多云架构下大模型训练的存储稳定性探索

一、多云架构与大模型训练的融合 （一）多云架构的优势与挑战 多云架构为大模型训练带来了诸多优势。首先，资源灵活性显著提高，不同的云平台可以提供不同类型的计算资源和存储服务，满足大模型训练在不同阶段的需求。例如，某些云平台可能在 GPU 计算资源上具有优势，而另一些则在存储成本或性能上表现出色，企业可以根据实际情况进行选择和组合。其次，扩展性得以增强，当大模型的规模不断扩大时，单一云平
阅读更多...
神经网络训练不起来怎么办（零）| General Guidance

神经网络训练不起来怎么办（零）| General Guidance

摘要：模型性能不理想时，如何判断 Model Bias， Optimization， Overfitting 等问题，并以此着手优化模型。在这个分析过程中，我们可以对Function Set，模型弹性有直观的理解。关键词：模型性能，Model Bias， Optimization， Overfitting。 零，领域背景 如果我们的模型表现较差，那么我们往往需要根据 Training l
阅读更多...
如何创建训练数据集

如何创建训练数据集

在 HuggingFace 上创建数据集非常方便，创建完成之后，通过 API 可以方便的下载并使用数据集，在 Google Colab 上进行模型调优，下载数据集速度非常快，本文通过 Dataset 库创建一个简单的训练数据集。 首先安装数据集依赖 HuggingFace datasetshuggingface_hub 创建数据集 替换为自己的 HuggingFace API key
阅读更多...
【YOLO 系列】基于YOLOV8的智能花卉分类检测系统【python源码+Pyqt5界面+数据集+训练代码】

【YOLO 系列】基于YOLOV8的智能花卉分类检测系统【python源码+Pyqt5界面+数据集+训练代码】

前言： 花朵作为自然界中的重要组成部分，不仅在生态学上具有重要意义，也在园艺、农业以及艺术领域中占有一席之地。随着图像识别技术的发展，自动化的花朵分类对于植物研究、生物多样性保护以及园艺爱好者来说变得越发重要。为了提高花朵分类的效率和准确性，我们启动了基于YOLO V8的花朵分类智能识别系统项目。该项目利用深度学习技术，通过分析花朵图像，自动识别并分类不同种类的花朵，为用户提供一个高效的花朵识别
阅读更多...
深度学习与大模型第3课：线性回归模型的构建与训练

深度学习与大模型第3课：线性回归模型的构建与训练

文章目录 使用Python实现线性回归：从基础到scikit-learn1. 环境准备2. 数据准备和可视化3. 使用numpy实现线性回归4. 使用模型进行预测5. 可视化预测结果6. 使用scikit-learn实现线性回归7. 梯度下降法8. 随机梯度下降和小批量梯度下降9. 比较不同的梯度下降方法总结 使用Python实现线性回归：从基础到scikit-learn 线性
阅读更多...
使用openpose caffe源码框架训练车辆模型常见错误及解决办法

使用openpose caffe源码框架训练车辆模型常见错误及解决办法

错误1：what():  Error: mSources.size() != mProbabilities.size() at 51, OPDataLayer, src/caffe/openpose/layers/oPDataLayer.cpp 原因：这是因为在网络模型中数据源sources和probabilities设置的参数个数不一样导致的，一个数据源对应一个概率 解决方法：只需要将网络文
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2