树的深度优先搜索 问题引入 PTA A1004 问题描述 有一个树，求每个层次的叶节点数目。通俗的理解就是，给个家谱，求每代没后代的。 输入描述 先给出结点数n和叶节点数m，在接下来的m行的每行里，先给出父节点的编号ID，再给出子节点的个数K，在给出K个子节点的编号ID[1]、ID[2]······、ID[K]。 输出描述 依次给出每个层次的叶节点数目。 问题分析 树的遍历有两种，DFS和BFS，这里以DFS为例。 #include <iostream> #include <vector> #include <cstring> using...

最短路之最大点权问题 问题引入：PTA A1003 问题分析： 直接分析输入输出。 输入 点数n、边数m、起点st、终点ed 点权 边权 输出 最短路条数 最短路里最大点权和 题解 最短路算法无非dijkstra、Floyd、SPFA，这里以dijkstra算法为例。 在dijkstra的基础上再引入三个数组：we***权，w[]记录最大点权，way[]记录最短路条数。 下面分析dij()函数： //邻接矩阵G[][],最短路数组dis[],访问数组vis[] void dij(int st, int ed)//传入起点、终点...

Default关键字 在Java面向对象编程中，可能会用到Default关键字。该关键字可以用来修饰抽象类，使其具有实体。 例如在普通接口中 interface Person() { void run(); } 该抽象方法是不能具有实体的，而加了Default关键字后，可以改成如下: interface Person() { Default void run() { System.out.println("Running..."); } } 这样，其子类就可以不用重写这个方法，其他类在调用子类的这个方法时，就调用该方法。...

MySQL MySQL产品的安装与配置 MySQL服务的启动和停止 计算机--右击管理--服务 通过管理员方式运行 net start 服务名（启动服务） net stop 服务名（停止服务） 若没有设置开机自动启动，则关机重启后，会显示连接不上(error:10061)，此时需手动打开MySQL服务，即如上所示。 MySQL服务的登录和退出 通过MySQL自带的客户端（仅限root用户） 通过DOS命令登录 mysql [ -h 主机名 -P 端口号] -u 用户名 -p密码 退出：exit或Ctrl + C...

Git是什么？ ​ git是是一个强大的分布式版本控制系统软件，而且是开源、免费的，还不用联网，程序员应当都应当了解这款软件。 Git如何使用？ ​ 我下面介绍的是linux系统下的操作，当然windows、Mac也可以用，但我这里不做介绍（因为我没用过）。 Git下载 ​ 首先你得下载一个git，一般情况下你下的linux系统都会自带git，你可以输入 #git --version 来检查你的系统是否已经安装了git，若没有，则输入以下指令进行安装。 #sudo apt update #sudo apt install git 这里说一下，linux系统下安装软...

放苹果 题目描述： 把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。 Input 第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。 Output 对输入的每组数据M和N，用一行输出相应的K。 Sample Input 1 7 3 Sample Output 8 话不多说，上AC代码： #include <iostream> #include <cstdio> ...

突击战 蓝书P2，UVA11729，一道贪心题。 书上用了vector容器，我直接用结构体数组，我为每个士兵新定义了一个变量t，表明该士兵从接受任务到完成任务在“我”的眼里花费的时间，并定义了一个变量free，用来表示之前某个士兵完成任务需要的时间的剩余值的最大值。答案就是所有士兵t的总和。 AC代码如下： #include<bits/stdc++.h> using namespace std; struct soldier{ int b, j, t; }; struct cmp{ bool operator() (const soldier &am...

最大子序列和 典型的动态规划问题，递推公式为d[i] = d[i-1] >= 0 ? d[i-1]+a[i] : a[i]; 有了递推式，不难列出完整代码： #include<bits/stdc++.h> using namespace std; const int maxn = (int)1e5 + 10; int arr[maxn], d[maxn]; int main() { int n; scanf("%d", &n); for (int i = 0; i < n; ++i) sc...

一道模拟题：http://poj.org/problem?id=1835 直接将宇航员当前方向、相对头顶方向、相对左边方向写出来即可。 代码如下： #include <iostream> #include <cstdio> #include <cstring> using namespace std; int main() {     char s[10];     int t, step; ...

一道简单的贪心模板题 http://poj.org/problem?id=2393 将每天的价格都放到最低就行了 核心思路：第i天最低的价格 = min(第i-1天最低的价格+s,第i天原本的价格) 有了思路，代码随便打 #include <iostream> #include <algorithm> using namespace std; #define maxn 10005 typedef long long ll; ll c[maxn], y[maxn]; int main() { ll cost = 0; ll n, s; ...

Now tell you two nonnegative integer a and b. Find the nonnegative integer X and integer Y to satisfy X*a + Y*b = 1. If no such answer print "sorry" instead. Input The input contains multiple test cases. Each case two nonnegative integer a,b (0<a, b<=2^31) Output outp...

虽说是宽搜模板题，但是用深搜也是可以解决的 代码如下： #include <iostream> #include <cstdlib> #include <cstdio> using namespace std; int r, c; char map[45][45]; int vis[45][45]; int minn = 1600; void bfs(int x, int y, int steps) { if(x >= r||y >= c||x < 0||y < 0) return; if(x...

DFS + 打表 代码入下： #include <cstdio> #include <iostream> #include <cstdlib> #include <cstring> using namespace std; // 棋盘 答案 int chess[12], s[12]; int ans, n; void dfs(int k)//设置第k行，即前k-1行已经设置好了 { if(k == n){//到头了，说明此路走得通，计数器+1 ++ans; return; }...

模板题，题目就不说了 思路就是新建一个标签数组，如果两个油田是联通的，那么他们的编号是相同的，然后进行遍历，每找到一块新的油田，那么标签+1，标签即答案 代码如下： #include <cstdio> char grid[105][105]; int tag[105][105]; int n, m; void dfs(int x, int y, int mark) { //越界检查 if(x < 0||y < 0||x >= n||y >= m) return; //若不是油田或者已经被标记了 if...