【考试记录】2018 山东省队集训第一轮D4(雾)
2024-09-04 03:08:27
T1题意:
给你一个$n\times m$的矩阵$B$,求它能由最少多少个形如两个向量之积$(n\times 1)\times(1\times m)$的矩阵相加得到。
题解:
考虑上界,最多需要$min(n,m)$次相加。以$n$次为例:
每次的矩阵由一个形如$(B_{i,1},B_{i,2},\cdots ,B_{i,m})$的行向量乘一个第$i$行为$1$其余行为$0$的列向量得到。
那么如何减少相加次数呢?我们发现若矩阵中一个行向量能表示成其他若干个行向量乘一个系数$k_i$的形式,
那么这个行向量不需要浪费一次相加的次数,将答案中上述若干个行向量的系数加上$k_i$便等价于加上该向量。
现在问题就转变成了求这$n$行中不能被其他行表示出的行数,发现这就等于高斯消元后非零行的个数。
列向量同理,分别计算行列答案后取$min$即可。
T2题意:
构造$k$棵生成树满足任意两颗生成树没有相同的边,且生成树上任意两点间的路径通过的点均不同(除了起点和终点)。
输出点数$n$(满足$n<=5k$)和$k$棵生成树。
题解:
听dalao们说形如两个菊花拼在一起是可行的。
想了一下,将点分成两部分,每部分$k$个,左边编号奇数,右边偶数。
第$i$棵生成树取第$2i-1$与第$2i$个点作为根,两边开花,中间连线就完事了。
但怎么顺着推到这个结论就不会了……
T3题意:
有一个数字串$s$,你要将$s$切成若干段使得每段的数严格递增。
要求满足最后一个数最小。若有多种方案则满足所有数构成的数列的字典序最大。
题解:
正着dp再倒着dp一遍,能否转移满足单调性可以二分转移位置,随便用什么字符串算法判断两个串组成的数字大小即可。
本来能A的一题,然而两个半小时三道省选题的安排实在是……
最新文章
- C# List 排序各种用法与比较
- php后管理分类导航菜单
- 一起Polyfill系列:Function.prototype.bind的四个阶段
- css实现鼠标经过导航文字偏位效果
- rsyslog 日志服务器接收日志权限问题
- forEach遍历对象数组案例
- 使用Jetty运行Java Web项目(Maven)
- BZOJ_1654_[Usaco2007 Open]City Horizon 城市地平线_扫描线
- Codeforces Round #524 (Div. 2) F
- NHibernate4使用Oracle.ManagedDataAccess.dll连接oracle及配置多个数据库连接
- 第三十七篇-BottomNavigationVIew底部导航的使用
- 委托, 泛型委托,Func<;T>;和Action<;T>;
- SpringBoot系列六:SpringBoot整合Tomcat
- android 实现QQ好友列表
- vlc的应用之三:动态调用vlc-0.9.4的libvlc.dll【转】
- 浅谈c#垃圾回收机制(GC)
- Sqli-labs less 10
- java模拟从http上下载文件
- CSS隐藏滚动条但又能滚动,不用js实现
- [51nod1220] 约数之和(杜教筛+莫比乌斯反演)
热门文章
- firfox 和 chrome 移动端Web开发页面调试
- Use trained sklearn model with pyspark
- 语义分割(semantic segmentation) 常用神经网络介绍对比-FCN SegNet U-net DeconvNet,语义分割,简单来说就是给定一张图片,对图片中的每一个像素点进行分类;目标检测只有两类,目标和非目标,就是在一张图片中找到并用box标注出所有的目标.
- Collaborative Index Embedding for Image Retrieval
- HihoCoder1650 : 扁平化管理([Offer收割]编程练习赛38)(二分)
- linux 几个逼格高实用的命令
- robotium 测试APK<;一>; 建立测试工程
- bzoj 3456 城市规划 —— 分治FFT / 多项式求逆 / 指数型生成函数(多项式求ln)
- POJ2349(求生成树中符合题意的边)
- win7 64位搭建Mantis 缺陷管理系统