IzIy's Files

题目描述

给定一张包含N个点、N-1条边的无向连通图，节点从1到N编号，每条边的长度均为1。从1号节点出发并打算遍历所有节点，那么总路程至少是多少？

输入

第一行包含一个整数N，1<=N<=10^5

接下来N-1行，每行包含两个整数X和Y，表于X号节点和Y号节点之间有一条边，1<=X，Y<=N。

输出

输出总路程的最小值。

样例输入

4
1 2
1 3
3 4

样例输出

4

解题思路：

从题目描述来看姑且可以将题目输入看做是树，以根节点开始遍历，计算总路程。

关键在于如何判断最短路径。分析可知，除最后一个遍历的叶子节点到根节点的弧只需走一遍外，其它所有弧都要走两遍。

因此，只需要计算出树的深度为D。

结果为 ：

[N-1)*2 - (D-1)

编码待续。

RiscV作为一个新的开源指令集架构,由Aspire Lab开放,具有简单开放的特点,主要用于教育研究.

一个最主要的特点是其ISA通过支持自定义指令的方式，支持自定义硬件加速器，用于专用领域的计算加速设计。

本文简单介绍RiscV的RoCC，以及其与RiscV处理器核通信的接口RoCC Interface。

RiscV自定义指令

RiscV ISA定义了四种自定义指令用于与协处理器进行交互。

customX rd, rs1, rs2, funct

标准自定义指令格式如下：

其中rs1,rs2 为源寄存器，rd为目的寄存器，xd,xs1,xs2为寄存器有效位，分别指明rd,rs1,rs2是否已使用。

opcode为四种不同的custom指令(custom-0/1/2/3/)

要在FPGA开发板上调通RiscV主要需要两方面知识，一方面是简单的电子电路知识，二是软件层工具链和嵌入式开发知识。

在ARTY 35T FPGA开发板上运行RiscV还需要一个支持RiscV处理器核的JTag调试器，用于调试和下载程序。 官方使用的是Olimex ARM-USB-TINY-H。

主要流程分为三个部分：

1. 生成用于烧录到FPGA开发板上包含整个RiscV Soc的mcs文件
2. 安装RiscV gcc工具链，生成并上传软件代码程序。
3. 调试和测试软件程序

运行环境 整个过程使用Ubuntu 16.04完成，并且建议使用实体机器运行，100g以上硬盘空间，原因主要有几点：

1. 生成Sifive fe310处理器需要用到linux环境。
2. vivado 目前只支持Ubuntu1604而且是较老的Ubuntu1604.3
3. 减小USB插拔转换不必要的麻烦。
4. 运行效率和GUI体验。

一、安装和下载必要的软件

在开始之前需要准备好以下软件。

1. vivado HLx –> 用于生成arty的mcs文件和fpga烧写 大小17G左右 https://www.xilinx.com/support/download.html

2. sifive/freedom –> Github RiscV SoC 源代码

3. sifive/freedom-e-sdk –> Github Sifive提供的软件开发SDK 代码

4. 预编译gcc工具链和riscv OpenOCD –> 由Sifive官方网站Tools提供。

   https://www.sifive.com/boards/

5. Digilent/vivado-boards –> Github vivado arty开发板文件

6. Adept 2 –> Arty FPGA开发板驱动

   https://reference.digilentinc.com/reference/software/adept/start

下载和安装可以同时进行以节约时间

总结一下近半年来所做的工作吧，可怜的还需要去实验室网站，拉自己发的周报，才有可能回想起来做了些什么事。游戏伤身还伤心。

从去年国庆节回家后，就没有回庆科实习了，老师也同意在实验室完成一部分公司的实习工作，继续给我发一部分实习工资，以补贴学习期间的囊中羞涩。

实习期间主要做唤醒词的研发，目前来看效果还好，虽然达不到业界水平，有些产品也用上了。

FPGA相关

FPGA是十月份开始正式接触的一直到现在。

起先开始跑了一些官方的简单例程，比如亮个灯，从clk手动计数分频转接到LED，控制频闪。

学习简单的verlog语法和VHDL语法。同样也找了一些所谓的学习视频，但都比较老旧，圈子也比较小。很多涉及到的基础知识多也点到为止，不能透彻的了解其中细节原理。

断断续续折腾了一个月左右，发现入门有很大的困难，国内知识体系太过封闭，接触不到最新的处理器设计相关知识，仍然停留在一些简单的电路设计的层面。

题目是上上周末，同学发来的，当时分析了一阵，没有出最终结果。

直到上周末，才将关键加密部分，分析出来。

今天将分析过程记录于此。

一、前言

安卓的题目，多少会结合jni来个so，或者动态载入dex，再加一些加密手段，隐藏入口等等，本题目基本都调试方法都涉及到了。

但是，就单单解题来说，掌握一些常用的调试方法，逆向基础不弱，通过勤加苦练，也是可以在赛场上取得好成绩的。如今安全意识的普及，现实情况下，app多数会进行代码混淆，甚至不惜性能加个比较复杂的vm壳。

本题前后总共花有差不多15个小时的时间，但难度不高，层层剥壳，均有迹可寻。

二、程序信息

程序名：signed.apk
md5：56de5d88051a6f44d0e83e843172a6f9
sha1：084f1b51f8ac3b167b748ac24c474a00688c5652
大小：2.79 MB

下载地址：点击下载

信息如下：

在VPS上经常需要跑一些程序或脚本，自然会产生出很多日志。 但要是单单为一个几十行代码的程序去加一个日志管理的功能也显得臃肿。

造轮子是不可能造轮子的。

于是，又查了一遍system log相关的内容，有rsyslogd等等， 但不方便使用，而且是系统级别的。 后来发现像nginx,httpd，等等都是有通过一个名为logrotate的工具，自动对日志文件进行整理。

man logrotate

写得有些不知所云，英语是个二把刀。 花了几些时间整理一下用法。 程序功能比较简单，配置文件(/etc/logrotate.d/*)的参数有两大方面:

• 一是控制日志整理周期，保存方式等等。
• 二是对原程序的输出做接管，处理（通过kill发送信号量）。

日志输出程序只需输出日志到指定位置既可，其它所有对日志的整理操作由logrotate来完成。

未完，待续。