2018年10月

一棵树,每个节点有权值,儿子与父亲不能同时取,求解从树上选取点能获得的最大权值

dpi表示不取,dpi表示取。

设j为i的儿子节点,dpi += max(dpj, dpj), dpi += dpj;

入度为零的点是根,从根开始进行深搜。 递归到底部然后按照转移公式开始取最优

#include <iostream>
#include <vector>
#include <cstring>
#include <cstdio>
using namespace std;

typedef long long LL;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

const int maxn = 6e3+10;
int N;
int dp[maxn][2];
bool in[maxn];
vector<int> tr[maxn];

void dfs(int u){
    //遍历到底部回硕 
    //遍历节点 并且根据关系 dp[u][1] 代表的是选取当前的节点加上子节点不选
    //dp[u][0] 代表的是不取当前节点,取子节点或者子节点不选的值得最大 
    for(int i = 0;i<tr[u].size();i++){
        int v = tr[u][i];
        dfs(v);
        dp[u][1] += dp[v][0];
        dp[u][0] += max(dp[v][1],dp[v][0]);
    }
}

int main(int argc, char** argv) {
    while(~scanf("%d",&N)){
        memset(in,0,sizeof(in));
        memset(dp,0,sizeof(dp));
        for(int i = 0;i <= N;i++){
            tr[i].clear();
        }
        for(int i = 1;i<=N;i++){
            scanf("%d",&dp[i][1]);
        }
        int root = 1;
        int u,v;
        while(scanf("%d%d",&u,&v),u + v){
            tr[v].push_back(u);//v是u的上级 
            in[u] = 1;//u入度为1 
        }
        for(int i = 1;i<=N;i++){
            if(in[i] == 0){//入度为0的是根节点 
                root = i;
            }
        }
        dfs(root);
        printf("%d\n",max(dp[root][0],dp[root][1]));
    }
    return 0;

设计原则

  • 找出应用中可能需要变化之处,把它们独立出来,不要和那些不需要变化的代码混在一起。
  • 针对接口编程,而不是针对实现编程。

域名系统DNS(Domain Name System)

  • 分布式系统
  • UDP方式(把带解析的域名放在udp报文中 发送到DNS服务器上 如果DNS不存在此域名解析结果则继续向下递归)

级别最高的写在最右边 级别最低的写在最左边 如:www.baidu.com .com最高 baidu.com次之 www.baidu.com 最低

域名类型:

  • 国际顶级域名 nTLD: cn中国 us美国 uk英国……
  • 通用顶级域名 gTLD: .com .net .org ……
  • 基础结构域名: .arpa 用于反向域名解析
  • 新顶级域名
  • 根域名服务器 服务器的最高层次的域名服务器 所有的根域名服务器 都知道所有的顶级域名服务器的域名和IP地址
    全世界有A-M个根域名服务器

根域名服务器不直接提供IP地址而是告诉DNS下一步应该找哪一个顶级域名服务器进行查询。

  • 顶级域名服务器 .com .net .cn……
  • 权限域名服务器 DNS提供商如DNSPOD
  • 本地域名服务器 本地DNS 如114

主机向本地域名服务器查询一般都是采用递归查询
主机向根域名服务器的查询一般都是采用迭代查询

本地域名服务器一般采用高速缓存 把取到的IP地址跟域名进行关联 定时会更新缓存。

文件传送协议FTP(File Transfer Protocol)

FTP基于TCP
TFTP基于UDP

  • 特点:操作都基于文件的副本(拷贝一份)
  • 联机访问

文件共享协议NFS(Netwrok File System) 基于TCP/IP

FTP的基本工作原理 在不同操作系统之间传输信息 的难点:

  • 计算机存储数据格式的不同
  • 文件的目录结构和文件命名的规定
  • 对于相同的文件存取功能 操作系统使用的命令不同
  • 访问控制方法不同

FTP主要是减少或消除在不同操作系统下处理文件的不兼容性。
FTP有两个端口一个是 控制端口 一个是传输端口

NFS仅对操作的数据进行传输 比如我只打开文件头就只传输文件头过来。

简单文件传送协议TFTP

特点:

  • 每次传送的数据包中有512字节的数据 但最后一次可不足512字节
  • 数据报文按序编号
  • 支持ASCII码或二进制传送
  • 可对文件进行读或写
  • 使用很简单的首部
    TFTP有类似TCP的停止等待协议 每发送完一个文件块后会等待对方的确认 规定时间内收不到确认就要重发数据

端口:69
若最后一个文件块刚好满足512则要再发一个仅含首部的空数据报。

远程终端协议

万维网WWW(World Wide Web)

统一资源定位符URL

URL组成:
<协议>://<主机>:<端口>/<路径>

HTTP1.0缺点每个请求将都要重新建立握手
HTTP1.1解决了此问题
HTTP1.1有两种工作方式: 非流水线工作方式(每个请求等待确认再去进行下一个请求)、流水线工作方式(无需等待确认直接进行下一个请求)

HTTP报文结构

  • 请求报文
    方法 URL 版本 (header)

首部字段名: 值
………………

body

  • 响应报文
    版本 状态码 短语 (header)

普通字段名: 值
………………

支持的方法:

  • OPTION 请求一些选项信息
  • GET 获取信息
  • HEAD 请求读取由URL所标志的信息头部
  • POST 给服务器添加信息
  • PUT 指明URL下存储一个文档
  • DELETE 删除
  • TRACE 回环测试报文
  • CONNECT 用于连接代理服务器

HTTP状态码

1xx 表示通知信息
2xx 表示成功
3xx 表示重定向
4xx 表示客户的差错 如请求报文错误
5xx 表示服务器的差错 如服务器失效无法完成请求

Cookie工作原理

HTTP报文中的Header返回Set-cookie 然后设置值 客户端就会存储到cookie中 并且接下来的报文中都会附加这个cookie

超文本标记语言(HyperText Markup Language)

XML(Extensible Markup Language) 可拓展标记语言 主要用于传输数据

动态万维网文档

在浏览的时候才创建
增加了一个机制 通用网关接口CGI(Common Gateway Interface) 是一个标准、定义了动态文档如何创建,输入数据应如何提供给应用程序,以及输出结果应如何使用。
cgi程序又称为cgi脚本 也称为cgi-bin

SMTP协议(Simple Mail Transfer Protocol)

邮件系统应该具有:

  • 邮件发送协议(SMTP)
  • 邮件读取协议(POP3 Post Office Protocol版本3)

用户可借助代理工具(QQ邮箱等)发送邮件
发送邮件时会跟SMTP服务器建立TCP连接 然后把邮件依次发送出去
收件人收信时运行计算机的用户代理 使用POP3协议读取发送给自己的邮件

SMTP协议过程

  • 建立连接
    建立完成后发送220 Service ready

STMP采用单对单协议 直接建立连接

先发送MAIL命令 后面跟发件人地址 如果服务器接受后返回状态码
然后进入RCPT命令 RCPT TO:收件人地址
发送完毕后客户端发送QUIT命令

常见的邮件读取协议有:POP3 和IMAP(Internet Message Access Protocol)

在邮件中夹杂附件可以使用MIME方法(互联网邮件扩充)
头部:

  • MIME-Version
  • Content-Description
  • Content-Id
  • Content-Transfer-Encoding
  • Content-Type

DHCP(Dynamic Host Configuration Protocol)

机器在刚开机的时候会像局域网发送一个 请求报文 然后DHCP服务器接收到此报文进行回应 然后客户机接收到后单独给此IP发送DHCP信息

简单网络管理协议SNMP

可以通过此协议对网络状态进行监控和管理

网路管理模型:

  • 管理器(网络运行中心NOC(Network Operations Center))
  • 被管设备

在每个被管设备中都要运行一个网络管理代理程序 来跟管理器进行通信

应用进程跨越网络的通信

美国加利福尼亚大学伯克利分校 为UNIX操作系统定义了一种API 叫为套接字接口(socket interface)

  • 当应用进程需要使用网络进行通信时,必须发送出socket系统调用 请求系统分配相关资源 然后返回一个"套接字描述符"

服务端 首先要调用bind来指明套接字的本地端口和IP地址,还必须调用listen来设置为被动监听方式 然后调用accept来获取到已连接到服务器的客户套接字 当我们accept到一个客户端的套接字 我们可以采用新建一个从进程传递此套接字 然后就由此进程维护即可。

发送数据用send
接收数据用recv
连接释放用close

UDP可忽略accept和listen

p2p(peer to peer)

没有中央服务器 采用的是对等方式传输 即是客户端也是服务端
采用分布式散列表DHT(Distributed Hash Table) 保存ip关系 利用散列函数把资源名k及其存放的结点ip地址N都分别映射为资源名标志符KID和结点标志符NID Chord 把多个结点串成一个环

我们将一维数组看作是一条直线,并且用前面的元素值来更新后面的元素值,我们有两种选择,一是从前往后更新,二是从后往前更新,但这两种更新的效果完全不同:

从前往后更新,我们选择的是根据当前的状态值来更新本次的结果,从后往前更新,我们选择的是根据上一次的状态值来更新本次的结果。

0-1背包问题的状态转移方程是:fi = max(fi-1, fi-1] + value[i]);这个方程有如下特点:

1.fi的值只与上一行的值f[i-1][]有关

2.更新fi时,要用到上一行的旧值,

当用一维数组表示时,f[i] = max(f[i], f[i-weight[j]]+value[j]){注意:括号中的f[i]表示的是上一次的状态值},我们选择倒叙更新 

完全背包的状态转移方程是:fi = max(fi-1, fi] + value[i]);由于一个物品可以被选择多次,更新fi时,

fi]可能因为放入物品i而发生变化。

用一维数组表示为:f[i] = max(f[i], f[i-weight[j]] + value[j]);选择正序更新。

Problem Description
A number sequence is defined as follows:

f(1) = 1, f(2) = 1, f(n) = (A f(n - 1) + B f(n - 2)) mod 7.

Given A, B, and n, you are to calculate the value of f(n).

Input
The input consists of multiple test cases. Each test case contains 3 integers A, B and n on a single line (1 <= A, B <= 1000, 1 <= n <= 100,000,000). Three zeros signal the end of input and this test case is not to be processed.

Output
For each test case, print the value of f(n) on a single line.

Sample Input
1 1 3
1 2 10
0 0 0

Sample Output
2
5

解题关键:常规做递归的话时间复杂度会爆 就算用备忘录也会 所以只能寻找他的规律 我们发现他有%7这个很关键 也就是说它的值怎么着也是0-6 根据这个特性我们发现他这个是会在一个周期内进行循环 问题在于怎么去找这个周期 我们现在先定一个上限值为1000 然后对在循环中如果dp[i-2] == 1 && dp[i-1] == 1 && i != 2 则说明到达了周期 则直接break; 然后回到外面 取n%(i-1) 因为i是到了周期的第一个 所以要-1 返回到周期的末尾

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskB solver = new TaskB();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskB {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int a, b, n;
            while (in.hasNext()) {
                a = in.nextInt();
                b = in.nextInt();
                n = in.nextInt();
                if (a == 0 && b == 0 && n == 0) {
                    break;
                }
                int dp[] = new int[1000];
                dp[0] = 1;
                dp[1] = 1;
                int i = 2;
                for (; i < 1000; i++) {
                    dp[i] = (a * dp[i - 1] + b * dp[i - 2]) % 7;
                    if (dp[i - 2] == 1 && dp[i - 1] == 1 && i != 2) {
                        break;
                    }
                }
                out.println(dp[(n - 1) % (i - 2)]);
            }
        }

    }
}