Algorithms

这里面的代码需要能够熟练写出。

ACM在线模板

dp总结

二分图的最大匹配

二分图的最大匹配、完美匹配和匈牙利算法

整数运算 x&(-x)，当x为0时结果为0；x为奇数时，结果为1；x为偶数时，结果为x中2的最大次方的因子。

树状数组

树状数组

//用于求区间和 
#include <iostream>
#include <cstdio>
#include <cstring>
#include<cmath>
using namespace std;

int n;代表数组的长度

int lowbit(int x)
{
    return x&(-x);///返回的是x的二进制末尾0的个数
}

void update(int i,int x)///单点更新
{
    while(i<=n)
    {
        c[i]+=x;
        i+=lowbit(i);///父节点也要进行更新
    }
}

int _sum(int k)///求前k项和
{
    while(k>0)
    {
        sum+=c[k];
        k-=lowbit(k);
    }
    return sum;
}

浏览器缓存机制浅析

浏览器缓存机制浅析

RMQ问题

//用于求区间最小值	
void RMQ_init(const vector<int> &A){
		int n = A.size();
		for(int i = 0 ; i < n ; i++) d[i][0] = A[i];
		for(int j = 0 ; (1<<j)<n; j++)
			for(int i = 0 ; i+(1<<j)-1 < n ; i++)
				d[i][j] = min((d[i][j-1]),d[i+(1<<(j-1))][j-1])
	}
	//范围最小值问题，参考自白书
	void RMQ(int L , int  R){
		int k = 0 ;
		while(1<<(k+1) <= R-L+1) k++;
		return min(d[L][k],d[R-(1<<k)+1][k]);
	}

B树 B+树

MySQL

//B 树
//https://zhuanlan.zhihu.com/p/27700617
public class BTree<Key extends Comparable<Key>, Value> 
{
  // max children per B-tree node = M-1
  // (must be even and greater than 2)
  private static final int M = 4;

  private Node root;    // root of the B-tree
  private int height;   // height of the B-tree
  private int n;      // number of key-value pairs in the B-tree

  // helper B-tree node data type
  private static final class Node 
  {
    private int m;               // number of children
    private Entry[] children = new Entry[M];  // the array of children

    // create a node with k children
    private Node(int k) 
    {
      m = k;
    }
  }

  // internal nodes: only use key and next
  // external nodes: only use key and value
  private static class Entry 
  {
    private Comparable key;
    private Object val;
    private Node next;   // helper field to iterate over array entries
    public Entry(Comparable key, Object val, Node next) 
    {
      this.key = key;
      this.val = val;
      this.next = next;
    }
  }

  /**
   * Initializes an empty B-tree.
   */
  public BTree() 
  {
    root = new Node(0);
  }

  /**
   * Returns true if this symbol table is empty.
   * @return {@code true} if this symbol table is empty; {@code false} otherwise
   */
  public boolean isEmpty() 
  {
    return size() == 0;
  }

  /**
   * Returns the number of key-value pairs in this symbol table.
   * @return the number of key-value pairs in this symbol table
   */
  public int size() 
  {
    return n;
  }

  /**
   * Returns the height of this B-tree (for debugging).
   *
   * @return the height of this B-tree
   */
  public int height() 
  {
    return height;
  }


  /**
   * Returns the value associated with the given key.
   *
   * @param key the key
   * @return the value associated with the given key if the key is in the symbol table
   *     and {@code null} if the key is not in the symbol table
   * @throws NullPointerException if {@code key} is {@code null}
   */
  public Value get(Key key) 
  {
    if (key == null) 
    {
      throw new NullPointerException("key must not be null");
    }
    return search(root, key, height);
  }

  @SuppressWarnings("unchecked")
  private Value search(Node x, Key key, int ht) 
  {
    Entry[] children = x.children;

    // external node到最底层叶子结点，遍历
    if (ht == 0) 
    {
      for (int j = 0; j < x.m; j++)       
      {
        if (eq(key, children[j].key)) 
        {
          return (Value) children[j].val;
        }
      }
    }

    // internal node递归查找next地址
    else 
    {
      for (int j = 0; j < x.m; j++) 
      {
        if (j+1 == x.m || less(key, children[j+1].key))
        {
          return search(children[j].next, key, ht-1);
        }
      }
    }
    return null;
  }


  /**
   * Inserts the key-value pair into the symbol table, overwriting the old value
   * with the new value if the key is already in the symbol table.
   * If the value is {@code null}, this effectively deletes the key from the symbol table.
   *
   * @param key the key
   * @param val the value
   * @throws NullPointerException if {@code key} is {@code null}
   */
  public void put(Key key, Value val) 
  {
    if (key == null) 
    {
      throw new NullPointerException("key must not be null");
    }
    Node u = insert(root, key, val, height); //分裂后生成的右结点
    n++;
    if (u == null) 
    {
      return;
    }

    // need to split root重组root
    Node t = new Node(2);
    t.children[0] = new Entry(root.children[0].key, null, root);
    t.children[1] = new Entry(u.children[0].key, null, u);
    root = t;
    height++;
  }

  private Node insert(Node h, Key key, Value val, int ht) 
  {
    int j;
    Entry t = new Entry(key, val, null);

    // external node外部结点，也是叶子结点，在树的最底层，存的是内容value
    if (ht == 0) 
    {
      for (j = 0; j < h.m; j++) 
      {
        if (less(key, h.children[j].key)) 
        {
          break;
        }
      }
    }

    // internal node内部结点，存的是next地址
    else 
    {
      for (j = 0; j < h.m; j++) 
      {
        if ((j+1 == h.m) || less(key, h.children[j+1].key)) 
        {
          Node u = insert(h.children[j++].next, key, val, ht-1);
          if (u == null) 
          {
            return null;
          }
          t.key = u.children[0].key;
          t.next = u;
          break;
        }
      }
    }

    for (int i = h.m; i > j; i--)
    {
      h.children[i] = h.children[i-1];
    }
    h.children[j] = t;
    h.m++;
    if (h.m < M) 
    {
      return null;
    }
    else     
    {  //分裂结点
      return split(h);
    }
  }

  // split node in half
  private Node split(Node h) 
  {
    Node t = new Node(M/2);
    h.m = M/2;
    for (int j = 0; j < M/2; j++)
    {
      t.children[j] = h.children[M/2+j];     
    }
    return t;  
  }

  /**
   * Returns a string representation of this B-tree (for debugging).
   *
   * @return a string representation of this B-tree.
   */
  public String toString() 
  {
    return toString(root, height, "") + "\n";
  }

  private String toString(Node h, int ht, String indent) 
  {
    StringBuilder s = new StringBuilder();
    Entry[] children = h.children;

    if (ht == 0) 
    {
      for (int j = 0; j < h.m; j++) 
      {
        s.append(indent + children[j].key + " " + children[j].val + "\n");
      }
    }
    else 
    {
      for (int j = 0; j < h.m; j++) 
      {
        if (j > 0) 
        {
          s.append(indent + "(" + children[j].key + ")\n");
        }
        s.append(toString(children[j].next, ht-1, indent + "   "));
      }
    }
    return s.toString();
  }


  // comparison functions - make Comparable instead of Key to avoid casts
  private boolean less(Comparable k1, Comparable k2) 
  {
    return k1.compareTo(k2) < 0;
  }

  private boolean eq(Comparable k1, Comparable k2) 
  {
    return k1.compareTo(k2) == 0;
  }


  /**
   * Unit tests the {@code BTree} data type.
   *
   * @param args the command-line arguments
   */
  public static void main(String[] args) 
  {
    BTree<String, String> st = new BTree<String, String>();

    st.put("www.cs.princeton.edu", "128.112.136.12");
    st.put("www.cs.princeton.edu", "128.112.136.11");
    st.put("www.princeton.edu",  "128.112.128.15");
    st.put("www.yale.edu",     "130.132.143.21");
    st.put("www.simpsons.com",   "209.052.165.60");
    st.put("www.apple.com",    "17.112.152.32");
    st.put("www.amazon.com",    "207.171.182.16");
    st.put("www.ebay.com",     "66.135.192.87");
    st.put("www.cnn.com",     "64.236.16.20");
    st.put("www.google.com",    "216.239.41.99");
    st.put("www.nytimes.com",   "199.239.136.200");
    st.put("www.microsoft.com",  "207.126.99.140");
    st.put("www.dell.com",     "143.166.224.230");
    st.put("www.slashdot.org",   "66.35.250.151");
    st.put("www.espn.com",     "199.181.135.201");
    st.put("www.weather.com",   "63.111.66.11");
    st.put("www.yahoo.com",    "216.109.118.65");


    System.out.println("cs.princeton.edu: " + st.get("www.cs.princeton.edu"));
    System.out.println("hardvardsucks.com: " + st.get("www.harvardsucks.com"));
    System.out.println("simpsons.com:   " + st.get("www.simpsons.com"));
    System.out.println("apple.com:     " + st.get("www.apple.com"));
    System.out.println("ebay.com:     " + st.get("www.ebay.com"));
    System.out.println("dell.com:     " + st.get("www.dell.com"));
    System.out.println();

    System.out.println("size:  " + st.size());
    System.out.println("height: " + st.height());
    System.out.println(st);
    System.out.println();
  }
}

Trie树

//参考https://blog.csdn.net/vickyway/article/details/49995107
package com.vicky.datastructure.tree.trie;

/**
 * <p>
 * 一个支持前缀查找以及精确查找的Trie树
 * </p>
 *
 * @author Vicky
 * @email vicky01200059@163.com
 * @2015年11月23日
 *
 */
public class PrefixTrie {
    private TrieNode root = new TrieNode('a');// TrieTree的根节点

    /**
     * 插入
     * 
     * @param word
     */
    public void insertWord(String word) {
        TrieNode index = this.root;
        for (char c : word.toLowerCase().toCharArray()) {
            index = index.addChild(c);
            index.addPrefixCount();
        }
        index.addCount();
        return;
    }

    /**
     * 查找
     * 
     * @param word
     * @return
     */
    public boolean selectWord(String word) {
        TrieNode index = this.root;
        for (char c : word.toLowerCase().toCharArray()) {
            index = index.getChild(c);
            if (null == index) {
                return false;
            }
        }
        return index.getCount() > 0;
    }

    /**
     * 查找前缀出现的次数
     * 
     * @param prefix
     * @return
     */
    public int selectPrefixCount(String prefix) {
        TrieNode index = this.root;
        for (char c : prefix.toLowerCase().toCharArray()) {
            index = index.getChild(c);
            if (null == index) {
                return 0;
            }
        }
        return index.getPrefixCount();
    }

    /**
     * TrieTree的节点
     */
    private class TrieNode {
        /** 该节点的字符 */
        private final char nodeChar;//
        /** 一个TrieTree的节点的子节点 */
        private TrieNode[] childNodes = null;
        private int count = 0;// 单词数量，用于判断一个单词是否存在
        private int prefixCount = 0;// 前缀数量，用于查找该前缀出现的次数

        public TrieNode(char nodeChar) {
            super();
            this.nodeChar = nodeChar;
        }

        public TrieNode addChild(char ch) {
            int index = ch - 'a';
            if (null == childNodes) {
                this.childNodes = new TrieNode[26];
            }
            if (null == childNodes[index]) {
                childNodes[index] = new TrieNode(ch);
            }
            return childNodes[index];
        }

        public TrieNode getChild(char ch) {
            int index = ch - 'a';
            if (null == childNodes || null == childNodes[index]) {
                return null;
            }
            return childNodes[index];
        }

        public void addCount() {
            this.count++;
        }

        public int getCount() {
            return this.count;
        }

        public void addPrefixCount() {
            this.prefixCount++;
        }

        public int getPrefixCount() {
            return this.prefixCount;
        }

        @Override
        public String toString() {
            return "TrieNode [nodeChar=" + nodeChar + "]";
        }

    }
}

package com.vicky.datastructure.tree.trie;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.regex.Pattern;

import org.junit.Before;
import org.junit.Test;

public class TrieUsedTest {
    private PrefixTrie trie;

    @Before
    public void before() throws IOException {
        Pattern pattern = Pattern.compile("[a-zA-Z]+");

        // 从文件中读取单词，构建TriedTree
        InputStreamReader read = new InputStreamReader(this.getClass().getResourceAsStream("words.txt"));
        BufferedReader reader = new BufferedReader(read);
        trie = new PrefixTrie();
        String line = null;
        while (null != (line = reader.readLine())) {
            line = line.trim();
            if (!pattern.matcher(line).matches()) {// 去除非法单词，如包含“-”
                continue;
            }
            trie.insertWord(line);
        }
    }

    /**
     * 测试使用TriedTree搜索前缀出现的次数
     */
    @Test
    public void searchPrefixWords() {
        String prefix = "vi";
        System.out.println(trie.selectPrefixCount(prefix));
        System.out.println(trie.selectWord("Vicky"));
    }
}

Dijstra

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int INF = 1000000000;
const int MAXN = 100 ;
//all shortest path from v[0]
int n , m ; //num of node ,num of  edge
int v[MAXN], G[MAXN][MAXN], d[MAXN];

int main(){
	
	scanf("%d%d",&n,&m);
	for(int i = 0 ; i < n ; i++)
		for (int j = 0 ; j < n ; j++){
			G[i][j] = INF;
		}
		
	for (int i = 0 ; i < m ; i++){
		int a , b, c;
		scanf("%d%d%d",&a,&b,&c);
		G[a][b] = c ;
	}
	
	memset(v,0,sizeof(v));
	for(int i = 0 ; i < n; i++) d[i] = (i==0? 0 :INF);
	for(int i = 0 ; i < n; i++){
		int x , m =INF;
		for(int y = 0 ; y < n; y++) if(!v[y] && d[y] <= m) m = d[x=y];
		v[x] = 1;
		for(int y = 0; y < n; y++) d[y] = min(d[y], d[x] + G[x][y]);
	}
	
	for(int i = 0 ; i< n ; i++){
		printf("%d\n",d[i]);
	}
	return  0 ; 
} 

/*边权均为正
6 7
0 1 1
0 2 4
1 3 3
1 4 2
2 4 1
3 5 3
4 5 2
*/

DijstraHeap(待续)

Floyd

for(k=0;k<n;k++)
 　　{ 
	  　　for(i=0;i<n;i++)
		 　　for(j=0;j<n;j++)
			 　　if(A[i][j]>(A[i][k]+A[k][j]))
			 　　{
				   　　A[i][j]=A[i][k]+A[k][j];
				   　　path[i][j]=k;
			  　 } 
	　}

BellFord

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;

const int INF = 1000000000;
const int MAXN = 1000;
const int MAXM = 100000;

int n, m;
int first[MAXN], d[MAXN];
int u[MAXM], v[MAXM], w[MAXM], next[MAXM];

int main() {
  scanf("%d%d", &n, &m);
  for(int i = 0; i < n; i++) first[i] = -1;
  for(int e = 0; e < m; e++) {
	scanf("%d%d%d", &u[e], &v[e], &w[e]);
	next[e] = first[u[e]];
	first[u[e]] = e;
  }

  queue<int> q;
  bool inq[MAXN];
  for(int i = 0; i < n; i++) d[i] = (i==0 ? 0 : INF);
  memset(inq, 0, sizeof(inq));
  q.push(0);
  while(!q.empty()) {
	int x = q.front(); q.pop();
	inq[x] = false;
	for(int e = first[x]; e != -1; e = next[e]) if(d[v[e]] > d[x]+w[e]) {
	  d[v[e]] = d[x] + w[e];
	  if(!inq[v[e]]) {
		inq[v[e]] = true;
		q.push(v[e]);
	  }
	}
  }

  for(int i = 0; i < n; i++)
	printf("%d\n", d[i]);
  return 0;
}

Prim

#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;

class MatrixUDG {
	#define MAX    100
	#define INF    (~(0x1<<31))        // 无穷大(即0X7FFFFFFF)
	private:
		char mVexs[MAX];    // 顶点集合
		int mVexNum;             // 顶点数
		int mEdgNum;             // 边数
		int mMatrix[MAX][MAX];   // 邻接矩阵

	public:
		// 创建图(自己输入数据)
		MatrixUDG();
		// 创建图(用已提供的矩阵)
		//MatrixUDG(char vexs[], int vlen, char edges[][2], int elen);
		MatrixUDG(char vexs[], int vlen, int matrix[][9]);
		~MatrixUDG();

		// 深度优先搜索遍历图
		void DFS();
		// 广度优先搜索（类似于树的层次遍历）
		void BFS();
		// prim最小生成树(从start开始生成最小生成树)
		void prim(int start);
		// 打印矩阵队列图
		void print();

	private:
		// 读取一个输入字符
		char readChar();
		// 返回ch在mMatrix矩阵中的位置
		int getPosition(char ch);
		// 返回顶点v的第一个邻接顶点的索引，失败则返回-1
		int firstVertex(int v);
		// 返回顶点v相对于w的下一个邻接顶点的索引，失败则返回-1
		int nextVertex(int v, int w);
		// 深度优先搜索遍历图的递归实现
		void DFS(int i, int *visited);

};

/* 
 * 创建图(自己输入数据)
 */
MatrixUDG::MatrixUDG()
{
	char c1, c2;
	int i, j, weight, p1, p2;
	
	// 输入"顶点数"和"边数"
	cout << "input vertex number: ";
	cin >> mVexNum;
	cout << "input edge number: ";
	cin >> mEdgNum;
	if ( mVexNum < 1 || mEdgNum < 1 || (mEdgNum > (mVexNum * (mVexNum-1))))
	{
		cout << "input error: invalid parameters!" << endl;
		return ;
	}
	
	// 初始化"顶点"
	for (i = 0; i < mVexNum; i++)
	{
		cout << "vertex(" << i << "): ";
		mVexs[i] = readChar();
	}

	// 1. 初始化"边"的权值
	for (i = 0; i < mVexNum; i++)
	{
		for (j = 0; j < mVexNum; j++)
		{
			if (i==j)
				mMatrix[i][j] = 0;
			else
				mMatrix[i][j] = INF;
		}
	}
	// 2. 初始化"边"的权值: 根据用户的输入进行初始化
	for (i = 0; i < mEdgNum; i++)
	{
		// 读取边的起始顶点，结束顶点，权值
		cout << "edge(" << i << "): ";
		c1 = readChar();
		c2 = readChar();
		cin >> weight;

		p1 = getPosition(c1);
		p2 = getPosition(c2);
		if (p1==-1 || p2==-1)
		{
			cout << "input error: invalid edge!" << endl;
			return ;
		}

		mMatrix[p1][p2] = weight;
		mMatrix[p2][p1] = weight;
	}
}

/*
 * 创建图(用已提供的矩阵)
 *
 * 参数说明：
 *     vexs  -- 顶点数组
 *     vlen  -- 顶点数组的长度
 *     matrix-- 矩阵(数据)
 */
MatrixUDG::MatrixUDG(char vexs[], int vlen, int matrix[][9])
{
	int i, j;
	
	// 初始化"顶点数"和"边数"
	mVexNum = vlen;
	// 初始化"顶点"
	for (i = 0; i < mVexNum; i++)
		mVexs[i] = vexs[i];

	// 初始化"边"
	for (i = 0; i < mVexNum; i++)
		for (j = 0; j < mVexNum; j++)
			mMatrix[i][j] = matrix[i][j];

	// 统计边的数目
	for (i = 0; i < mVexNum; i++)
		for (j = 0; j < mVexNum; j++)
			if (i!=j && mMatrix[i][j]!=INF)
				mEdgNum++;
	mEdgNum /= 2;
}

/* 
 * 析构函数
 */
MatrixUDG::~MatrixUDG() 
{
}

/*
 * 返回ch在mMatrix矩阵中的位置
 */
int MatrixUDG::getPosition(char ch)
{
	int i;
	for(i=0; i<mVexNum; i++)
		if(mVexs[i]==ch)
			return i;
	return -1;
}

/*
 * 读取一个输入字符
 */
char MatrixUDG::readChar()
{
	char ch;

	do {
		cin >> ch;
	} while(!((ch>='a'&&ch<='z') || (ch>='A'&&ch<='Z')));

	return ch;
}


/*
 * 返回顶点v的第一个邻接顶点的索引，失败则返回-1
 */
int MatrixUDG::firstVertex(int v)
{
	int i;

	if (v<0 || v>(mVexNum-1))
		return -1;

	for (i = 0; i < mVexNum; i++)
		if (mMatrix[v][i]!=0 && mMatrix[v][i]!=INF)
			return i;

	return -1;
}

/*
 * 返回顶点v相对于w的下一个邻接顶点的索引，失败则返回-1
 */
int MatrixUDG::nextVertex(int v, int w)
{
	int i;

	if (v<0 || v>(mVexNum-1) || w<0 || w>(mVexNum-1))
		return -1;

	for (i = w + 1; i < mVexNum; i++)
		if (mMatrix[v][i]!=0 && mMatrix[v][i]!=INF)
			return i;

	return -1;
}

/*
 * 深度优先搜索遍历图的递归实现
 */
void MatrixUDG::DFS(int i, int *visited)
{
	int w;

	visited[i] = 1;
	cout << mVexs[i] << " ";
	// 遍历该顶点的所有邻接顶点。若是没有访问过，那么继续往下走
	for (w = firstVertex(i); w >= 0; w = nextVertex(i, w))
	{
		if (!visited[w])
			DFS(w, visited);
	}
	   
}

/*
 * 深度优先搜索遍历图
 */
void MatrixUDG::DFS()
{
	int i;
	int visited[MAX];       // 顶点访问标记

	// 初始化所有顶点都没有被访问
	for (i = 0; i < mVexNum; i++)
		visited[i] = 0;

	cout << "DFS: ";
	for (i = 0; i < mVexNum; i++)
	{
		//printf("\n== LOOP(%d)\n", i);
		if (!visited[i])
			DFS(i, visited);
	}
	cout << endl;
}

/*
 * 广度优先搜索（类似于树的层次遍历）
 */
void MatrixUDG::BFS()
{
	int head = 0;
	int rear = 0;
	int queue[MAX];     // 辅组队列
	int visited[MAX];   // 顶点访问标记
	int i, j, k;

	for (i = 0; i < mVexNum; i++)
		visited[i] = 0;

	cout << "BFS: ";
	for (i = 0; i < mVexNum; i++)
	{
		if (!visited[i])
		{
			visited[i] = 1;
			cout << mVexs[i] << " ";
			queue[rear++] = i;  // 入队列
		}
		while (head != rear) 
		{
			j = queue[head++];  // 出队列
			for (k = firstVertex(j); k >= 0; k = nextVertex(j, k)) //k是为访问的邻接顶点
			{
				if (!visited[k])
				{
					visited[k] = 1;
					cout << mVexs[k] << " ";
					queue[rear++] = k;
				}
			}
		}
	}
	cout << endl;
}

/*
 * 打印矩阵队列图
 */
void MatrixUDG::print()
{
	int i,j;

	cout << "Martix Graph:" << endl;
	for (i = 0; i < mVexNum; i++)
	{
		for (j = 0; j < mVexNum; j++)
			cout << setw(10) << mMatrix[i][j] << " ";
		cout << endl;
	}
}

/*
 * prim最小生成树
 *
 * 参数说明：
 *   start -- 从图中的第start个元素开始，生成最小树
 */
void MatrixUDG::prim(int start)
{
	int min,i,j,k,m,n,sum;
	int index=0;         // prim最小树的索引，即prims数组的索引
	char prims[MAX];     // prim最小树的结果数组
	int weights[MAX];    // 顶点间边的权值

	// prim最小生成树中第一个数是"图中第start个顶点"，因为是从start开始的。
	prims[index++] = mVexs[start];

	// 初始化"顶点的权值数组"，
	// 将每个顶点的权值初始化为"第start个顶点"到"该顶点"的权值。
	for (i = 0; i < mVexNum; i++ )
		weights[i] = mMatrix[start][i];
	// 将第start个顶点的权值初始化为0。
	// 可以理解为"第start个顶点到它自身的距离为0"。
	weights[start] = 0;

	for (i = 0; i < mVexNum; i++)
	{
		// 由于从start开始的，因此不需要再对第start个顶点进行处理。
		if(start == i)
			continue;

		j = 0;
		k = 0;
		min = INF;
		// 在未被加入到最小生成树的顶点中，找出权值最小的顶点。
		while (j < mVexNum)
		{
			// 若weights[j]=0，意味着"第j个节点已经被排序过"(或者说已经加入了最小生成树中)。
			if (weights[j] != 0 && weights[j] < min)
			{
				min = weights[j];
				k = j;
			}
			j++;
		}

		// 经过上面的处理后，在未被加入到最小生成树的顶点中，权值最小的顶点是第k个顶点。
		// 将第k个顶点加入到最小生成树的结果数组中
		prims[index++] = mVexs[k];
		// 将"第k个顶点的权值"标记为0，意味着第k个顶点已经排序过了(或者说已经加入了最小树结果中)。
		weights[k] = 0;
		// 当第k个顶点被加入到最小生成树的结果数组中之后，更新其它顶点的权值。
		for (j = 0 ; j < mVexNum; j++)
		{
			// 当第j个节点没有被处理，并且需要更新时才被更新。
			if (weights[j] != 0 && mMatrix[k][j] < weights[j])
				weights[j] = mMatrix[k][j];
		}
	}

	// 计算最小生成树的权值
	sum = 0;
	for (i = 1; i < index; i++)
	{
		min = INF;
		// 获取prims[i]在mMatrix中的位置
		n = getPosition(prims[i]);
		// 在vexs[0...i]中，找出到j的权值最小的顶点。
		for (j = 0; j < i; j++)
		{
			m = getPosition(prims[j]);
			if (mMatrix[m][n]<min)
				min = mMatrix[m][n];
		}
		sum += min;
	}
	// 打印最小生成树
	cout << "PRIM(" << mVexs[start] << ")=" << sum << ": ";
	for (i = 0; i < index; i++)
		cout << prims[i] << " ";
	cout << endl;
}

int main()
{
	char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
	int matrix[][9] = {
			 /*A*//*B*//*C*//*D*//*E*//*F*//*G*/
	  /*A*/ {   0,  12, INF, INF, INF,  16,  14},
	  /*B*/ {  12,   0,  10, INF, INF,   7, INF},
	  /*C*/ { INF,  10,   0,   3,   5,   6, INF},
	  /*D*/ { INF, INF,   3,   0,   4, INF, INF},
	  /*E*/ { INF, INF,   5,   4,   0,   2,   8},
	  /*F*/ {  16,   7,   6, INF,   2,   0,   9},
	  /*G*/ {  14, INF, INF, INF,   8,   9,   0}};
	int vlen = sizeof(vexs)/sizeof(vexs[0]);
	MatrixUDG* pG;

	// 自定义"图"(输入矩阵队列)
	//pG = new MatrixUDG();
	// 采用已有的"图"
	pG = new MatrixUDG(vexs, vlen, matrix);

	//pG->print();   // 打印图
	//pG->DFS();     // 深度优先遍历
	//pG->BFS();     // 广度优先遍历
	pG->prim(0);     // prim算法生成最小生成树

	return 0;
}

Kruscal

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

const int INF = 1000000000;
const int MAXN = 1000;
const int MAXM = 100000;

int n, m;
int u[MAXM], v[MAXM], w[MAXM], r[MAXM],p[MAXM];

int cmp(const int i, const int j){
	return w[i] < w[j];
}
int find(int x ){
	return p[x]==x? x: p[x] = find(p[x]);
}

int Kruskal(){
	int ans = 0;
	for(int i = 0 ; i< n ; i++) p[i] = i; //父节点
	for(int j = 0 ; j< m ; j++) r[j] = j; //结点编号
	sort(r,r+m,cmp);
	for(int i = 0 ; i < m ; i++){
		int e = r[i];
		int x = find(u[e]);
		int y = find(v[e]);
		if(x!=y) {
			ans += w[e];
			p[x] = y;
		}
	}
	
	return ans;
}
int main() {
  scanf("%d%d", &n, &m);
  
  for(int e = 0; e < m; e++) {
	scanf("%d%d%d", &u[e], &v[e], &w[e]);
  }
  
  int gt = Kruskal();
  printf("%d",gt);
  

  
}

BigInt

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

const int maxn = 200;
struct bign{
  int len, s[maxn];

  bign() {
	memset(s, 0, sizeof(s));
	len = 1;
  }

  bign(int num) {
	*this = num;
  }

  bign(const char* num) {
	*this = num;
  }

  bign operator = (int num) {
	char s[maxn];
	sprintf(s, "%d", num);
	*this = s;
	return *this;
  }

  bign operator = (const char* num) {
	len = strlen(num);
	for(int i = 0; i < len; i++) s[i] = num[len-i-1] - '0';
	return *this;
  }

  string str() const {
	string res = "";
	for(int i = 0; i < len; i++) res = (char)(s[i] + '0') + res;
	if(res == "") res = "0";
	return res;
  }

  bign operator + (const bign& b) const{
	bign c;
	c.len = 0;
	for(int i = 0, g = 0; g || i < max(len, b.len); i++) {
	  int x = g;
	  if(i < len) x += s[i];
	  if(i < b.len) x += b.s[i];
	  c.s[c.len++] = x % 10;
	  g = x / 10;
	}
	return c;
  }

  void clean() {
	while(len > 1 && !s[len-1]) len--;
  }

  bign operator * (const bign& b) {
	bign c; c.len = len + b.len;
	for(int i = 0; i < len; i++)
	  for(int j = 0; j < b.len; j++)
		c.s[i+j] += s[i] * b.s[j];
	for(int i = 0; i < c.len-1; i++){
	  c.s[i+1] += c.s[i] / 10;
	  c.s[i] %= 10;
	}
	c.clean();
	return c;
  }

  bign operator - (const bign& b) {
	bign c; c.len = 0;
	for(int i = 0, g = 0; i < len; i++) {
	  int x = s[i] - g;
	  if(i < b.len) x -= b.s[i];
	  if(x >= 0) g = 0;
	  else {
		g = 1;
		x += 10;
	  }
	  c.s[c.len++] = x;
	}
	c.clean();
	return c;
  }

  bool operator < (const bign& b) const{
	if(len != b.len) return len < b.len;
	for(int i = len-1; i >= 0; i--)
	  if(s[i] != b.s[i]) return s[i] < b.s[i];
	return false;
  }

  bool operator > (const bign& b) const{
	return b < *this;
  }

  bool operator <= (const bign& b) {
	return !(b > *this);
  }

  bool operator == (const bign& b) {
	return !(b < *this) && !(*this < b);
  }

  bign operator += (const bign& b) {
	*this = *this + b;
	return *this;
  }
};

istream& operator >> (istream &in, bign& x) {
  string s;
  in >> s;
  x = s.c_str();
  return in;
}

ostream& operator << (ostream &out, const bign& x) {
  out << x.str();
  return out;
}

int main() {
  bign a;
  cin >> a;
  cout << a*a << endl;
  a += "123456789123456789000000000";
  cout << a*2 << endl;
  return 0;
}

package gt.wangyi;

import java.util.Scanner;
//大数相乘
//
public class HuaWei3 {

    public static String xiangcheng  (String a, String b) {
        int result[] = new int[a.length() + b.length()];
        int num1[] = new int[a.length()];
        int num2[] = new int[b.length()];
        StringBuffer sb = new StringBuffer();

        for(int i = 0; i < a.length();i++)
            num1[i] = a.charAt(i)-'0';
        for(int i = 0; i <  b.length();i++)
            num2[i] = b.charAt(i)-'0';
        for(int i =0 ; i < a.length(); i++){
            for(int j =0; j <  b.length(); j++){
                result[i+j]+=num1[i]*num2[j]; //result[i+j]表示第i位和第j位相乘的数 表示后面有这么多个0
            }
        }
        for(int i =result.length-1; i > 0 ;i--){
            result[i-1] += result[i] / 10;
            result[i] = result[i] % 10;
        }


        for(int i = 0; i < result.length-1; i++){
           // resultStr+=""+result[i];
            sb.append(result[i]);
        }
        return sb.toString();
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String a = sc.nextLine();
        String b = sc.nextLine();
        System.out.println(xiangcheng(a, b));

        System.out.println();

    }
}

BiSearch

#include<stdio.h>
#include<assert.h>

int A[] = {1,2,3,4,5,6,7,8,9,10,11};

int bsearch(int* A, int x, int y, int v) {
  int m = x + (y-x)/2;
  if(y <= x) return -1;
  if(A[m] == v) return m;
  else return A[m]>v ? bsearch(A,x,m,v) : bsearch(A,m+1,y,v);
}

int main() {
  int i;
  for(i = 1; i <= 11; i++)
	assert(bsearch(A, 0, 11, i) == i-1);
  printf("Ok!\n");
  return 0;
}

#include<stdio.h>
#include<assert.h>

int A[] = {1,2,3,4,5,6,7,8,9,10,11};

int bsearch(int* A, int x, int y, int v) {
  int m;
  while(x < y) {
	m = x+(y-x)/2;
	if(A[m] == v) return m;
	else if(A[m] > v) y = m;
	else x = m+1;
  }
  return -1;
}

int main() {
  int i;
  for(i = 1; i <= 11; i++)
	assert(bsearch(A, 0, 11, i) == i-1);
  printf("Ok!\n");
  return 0;
}

BFS

//BFS 迷宫
#include<stdio.h>
#include<string.h>
#define MAXN 105
int n, m, xs, ys, xt, yt;
int maze[MAXN][MAXN], vis[MAXN][MAXN], fa[MAXN][MAXN], dist[MAXN][MAXN], last_dir[MAXN][MAXN], num[MAXN][MAXN];

int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};
char name[] = "UDLR";

int q[MAXN*MAXN];
void bfs(int x, int y) {
  int front=0, rear=0, d, u;
  u = x*m+y;
  vis[x][y] = 1; fa[x][y] = u; dist[x][y] = 0;
  q[rear++] = u;
  while(front<rear) {
	u = q[front++];    
	x = u/m; y = u%m;
	for(d = 0; d < 4; d++) {
	  int nx = x+dx[d], ny = y+dy[d];
	  if(nx>=0 && nx<n && ny>=0 && ny<m && maze[nx][ny] && !vis[nx][ny]) {
		int v = nx*m+ny;
		q[rear++] = v;
		vis[nx][ny] = 1;
		fa[nx][ny] = u;
		dist[nx][ny] = dist[x][y]+1;
		last_dir[nx][ny] = d;
	  }
	}
  }
}

void print_path(int x, int y) {
  int fx = fa[x][y]/m;
  int fy = fa[x][y]%m;
  if(fx != x || fy != y) {
	print_path(fx, fy);
	putchar(name[last_dir[x][y]]);
  }
}

int dir[MAXN*MAXN];
void print_path2(int x, int y) {
  int c = 0;
  for(;;) {
	int fx = fa[x][y]/m;
	int fy = fa[x][y]%m;
	if(fx == x && fy == y) break;
	dir[c++] = last_dir[x][y];
	x = fx;
	y = fy;
  }
  while(c--)
	putchar(name[dir[c]]);
}

int main() {
  int i, j;
  scanf("%d%d%d%d%d%d", &n, &m, &xs, &ys, &xt, &yt);
  for(i = 0; i < n; i++)
	for(j = 0; j < m; j++)
	  scanf("%d", &maze[i][j]);
  memset(vis, 0, sizeof(vis));
  bfs(xs, ys);
  print_path(xt, yt);
  putchar('\n');
  print_path2(xt, yt);
  putchar('\n');
  return 0;
}
/*
6 5 0 0 0 4
1 1 0 1 1
1 0 1 1 1
1 0 1 0 0
1 0 1 1 1
1 1 1 0 1
1 1 1 1 1	
*/

private static void bfs(HashMap<Character, LinkedList<Character>> graph, HashMap<Character, Integer> dist, char start)
   {
       Queue<Character> q=new LinkedList<>();
       q.add(start);//将s作为起始顶点加入队列
       dist.put(start, 0);
       int i=0;
       while(!q.isEmpty())
       {
           char top=q.poll();//取出队首元素
           i++;
           System.out.println("The "+i+"th element:"+top+" Distance from s is:"+dist.get(top));
           int d=dist.get(top)+1;//得出其周边还未被访问的节点的距离
           for (Character c : graph.get(top)) {
               if(!dist.containsKey(c))//如果dist中还没有该元素说明还没有被访问
               {
                   dist.put(c, d);
                   q.add(c);
               }
           }
       }
   }

DFS

//topo sort
#include<stdio.h>
#include<string.h>
const int MAXN = 1000;
int n, m, G[MAXN][MAXN];
int c[MAXN];
int topo[MAXN], t;
bool dfs(int u){
  c[u] = -1;
  for(int v = 0; v < n; v++) if(G[u][v]) {
	if(c[v]<0) return false;
	else if(!c[v]) dfs(v);
  }
  c[u] = 1; topo[--t]=u;
  return true;
}

bool toposort(){
  t = n;
  memset(c, 0, sizeof(c));
  for(int u = 0; u < n; u++) if(!c[u])
	if(!dfs(u)) return false;
  return true;
}

int main() {
  scanf("%d%d", &n, &m);
  memset(G, 0, sizeof(G));
  for(int i = 0; i < m; i++) {
	int u, v;
	scanf("%d%d", &u, &v);
	G[u][v] = 1;
  }
  if(toposort()) {
	for(int i = 0; i < n; i++)
	  printf("%d\n", topo[i]);
  }
  else
	printf("No\n");
}
/*
4 3
0 1
2 1
3 2
*/

public static int count = 0;
  private static void dfs(HashMap<Character , LinkedList<Character>> graph, HashMap<Character, Boolean> visited)
  {
      visit(graph, visited, 'u');//为了和图中的顺序一样，我认为控制了DFS先访问u节点
      visit(graph,visited,'w');
  }
  private static void visit(HashMap<Character , LinkedList<Character>> graph,HashMap<Character, Boolean> visited,char start)
  {
      if(!visited.containsKey(start))
      {
          count++;
          System.out.println("The time into element "+start+":"+count);//记录进入该节点的时间
          visited.put(start, true);
          for (char c : graph.get(start))
          {
              if(!visited.containsKey(c))
              {
                  visit(graph,visited,c);//递归访问其邻近节点
              }
          }
          count++;
          System.out.println("The time out element "+start+":"+count);//记录离开该节点的时间
      }
  }

点线相关

// UVa11178 Morley's Theorem
// Rujia Liu
#include<cstdio>
#include<cmath>

struct Point {
  double x, y;
  Point(double x=0, double y=0):x(x),y(y) { }
};

typedef Point Vector;

Vector operator + (const Vector& A, const Vector& B) { return Vector(A.x+B.x, A.y+B.y); }
Vector operator - (const Point& A, const Point& B) { return Vector(A.x-B.x, A.y-B.y); }
Vector operator * (const Vector& A, double p) { return Vector(A.x*p, A.y*p); }
double Dot(const Vector& A, const Vector& B) { return A.x*B.x + A.y*B.y; }//点积
double Length(const Vector& A) { return sqrt(Dot(A, A)); }
double Angle(const Vector& A, const Vector& B) { return acos(Dot(A, B) / Length(A) / Length(B)); }//向量夹角
double Cross(const Vector& A, const Vector& B) { return A.x*B.y - A.y*B.x; }//叉乘

Point GetLineIntersection(const Point& P, const Point& v, const Point& Q, const Point& w) {
  Vector u = P-Q;
  double t = Cross(w, u) / Cross(v, w);
  return P+v*t;
}//两条直线交点

Vector Rotate(const Vector& A, double rad) {
  return Vector(A.x*cos(rad)-A.y*sin(rad), A.x*sin(rad)+A.y*cos(rad));
}//向量旋转 rad表示旋转弧度

Point read_point() {
  double x, y;
  scanf("%lf%lf", &x, &y);
  return Point(x,y);
}

Point GetLineIntersection(const Point& P, const Vector& v, const Point& Q, const Vector& w) { 
  Vector u = P-Q;
  double t = Cross(w, u) / Cross(v, w);
  return P+v*t;
}

bool SegmentProperIntersection(const Point& a1, const Point& a2, const Point& b1, const Point& b2) {
  double c1 = Cross(a2-a1,b1-a1), c2 = Cross(a2-a1,b2-a1),
  c3 = Cross(b2-b1,a1-b1), c4=Cross(b2-b1,a2-b1);
  return dcmp(c1)*dcmp(c2)<0 && dcmp(c3)*dcmp(c4)<0;
}//判断线是否相交

bool OnSegment(const Point& p, const Point& a1, const Point& a2) {
  return dcmp(Cross(a1-p, a2-p)) == 0 && dcmp(Dot(a1-p, a2-p)) < 0;
}//一个端点是否在另一个端点上


Point getD(Point A, Point B, Point C) {
  Vector v1 = C-B;
  double a1 = Angle(A-B, v1);
  v1 = Rotate(v1, a1/3);

  Vector v2 = B-C;
  double a2 = Angle(A-C, v2);
  v2 = Rotate(v2, -a2/3);

  return GetLineIntersection(B, v1, C, v2);
}

int main() {
  int T;
  Point A, B, C, D, E, F;
  scanf("%d", &T);
  while(T--) {
	A = read_point();
	B = read_point();
	C = read_point();
	D = getD(A, B, C);
	E = getD(B, C, A);
	F = getD(C, A, B);
	printf("%.6lf %.6lf %.6lf %.6lf %.6lf %.6lf\n", D.x, D.y, E.x, E.y, F.x, F.y);
  }
  return 0;
}

凸包

辗转相除

package com.jk.gcddemo;

/**
 * @author jk
 *         这段代码写的是辗转除来求最大的公约数，其实想想也蛮简单的，首先是我们需要其实之前我们都可以不用思考，只需要思考最后一步，因为是公约数，
 *         然后返回值肯定是n，这里m>n;
 *         这里可能有的人会思考，为什么通过取余来得到m，n，其实仔细想想，我们通过取余去掉的都是r=m%n,n的倍数
 *         ，如果n是m的公约数那么r=0是符合，否则就只能去n剩下的里面去找了。
 * 
 */

public class test {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int res = gcd(8, 6);
		System.out.println(res);
	}

	private static int gcd(int i, int j) {
		int m, n, r;
		// 使m>n
		if (i > j) {
			m = i;
			n = j;
		} else {
			m = j;
			n = i;
		}
		// 通过辗转除来求的最大公约数
		r = m % n;
		while (r != 0) {
			m = n;
			n = r;
			r = m % n;
		}
		// 返回最大公约数
		return n;

	}

}

多角形面积

qsort调用

进制转换

网络流

/*dfs找增广路*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int INF = 1000000000;
const int MAXN = 1000;

int n, m, s, t;
int vis[MAXN], p[MAXN], cap[MAXN][MAXN], flow[MAXN][MAXN];

int path(int u){
  int d;
  vis[u] = 1;
  if(u == t) return INF;
  else for(int v = 0; v < n; v++)
	if(!vis[v] && cap[u][v]>flow[u][v] && (d = path(v)) > 0){
	  p[v] = u;
	  return min(d, cap[u][v]-flow[u][v]);
  }
  return 0;
}

int main() {
  scanf("%d%d", &n, &m);
  memset(cap, 0, sizeof(cap));
  memset(flow, 0, sizeof(flow));
  for(int i = 0; i < m; i++) {
	int u, v, c;
	scanf("%d%d%d", &u, &v, &c);
	cap[u][v] = c;
  }
  s = 0;
  t = n-1;
  int ans = 0;
  for(;;) {
	memset(vis, 0, sizeof(vis));
	int d = path(s);
	if(d == 0) break;
	for(int u = t; u != s; u = p[u]) {
	  flow[p[u]][u] += d;
	  flow[u][p[u]] -= d;
	};
	ans += d;
  }
  printf("%d\n", ans);
  return 0;
}

//Edmonds-Karp算法，BFS找增广路
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int INF = 1000000000;
const int MAXN = 1000;

int n, m, s, t;
int a[MAXN], p[MAXN], cap[MAXN][MAXN], flow[MAXN][MAXN];

int main() {
  scanf("%d%d", &n, &m);
  memset(cap, 0, sizeof(cap));
  for(int i = 0; i < m; i++) {
	int u, v, c;
	scanf("%d%d%d", &u, &v, &c);
	cap[u][v] = c;
  }
  s = 0;
  t = n-1;
  int ans = 0;

  queue<int> q;
  memset(flow, 0, sizeof(flow));
  for(;;) {
	memset(a, 0, sizeof(a));
	a[s] = INF;
	q.push(s);
	while(!q.empty()) {
	  int u = q.front(); q.pop();
	  for(int v = 0; v < n; v++) if(!a[v] && cap[u][v]>flow[u][v]){
		p[v] = u; q.push(v);
		a[v] = min(a[u], cap[u][v]-flow[u][v]);
	  }
	}
	if(a[t] == 0) break;
	for(int u = t; u != s; u = p[u]) {
	  flow[p[u]][u] += a[t];
	  flow[u][p[u]] -= a[t];
	}
	ans += a[t];
  }

  printf("%d\n", ans);
  return 0;
}

最小费用流

//连续最短路算法，Bellman-Ford找最短增广路
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int INF = 1000000000;
const int MAXN = 1000;

int n, m, s, t;
int a[MAXN], d[MAXN], p[MAXN], cap[MAXN][MAXN], cost[MAXN][MAXN], flow[MAXN][MAXN];

int main() {
  scanf("%d%d", &n, &m);
  memset(cap, 0, sizeof(cap));
  memset(cost, 0, sizeof(cost));
  for(int i = 0; i < m; i++) {
	int u, v;
	scanf("%d%d", &u, &v);
	scanf("%d%d", &cap[u][v], &cost[u][v]);
	cost[v][u] = -cost[u][v];
  }
  s = 0;
  t = n-1;
  int f = 0, c = 0;

  queue<int> q;
  int d[MAXN];
  memset(flow, 0, sizeof(flow));
  for(;;) {
	bool inq[MAXN];
	for(int i = 0; i < n; i++) d[i] = (i==s ? 0 : INF);
	memset(inq, 0, sizeof(inq));
	q.push(s);
	while(!q.empty()) {
	  int u = q.front(); q.pop();
	  inq[u] = false;
	  for(int v = 0; v < n; v++) if(cap[u][v]>flow[u][v] && d[v]>d[u]+cost[u][v]) {
		d[v] = d[u] + cost[u][v];
		p[v] = u;
		if(!inq[v]) {
		  inq[v] = true;
		  q.push(v);
		}
	  }
	}
	if(d[t] == INF) break;
	int a = INF;
	for(int u = t; u != s; u = p[u]) a = min(a, cap[p[u]][u] - flow[p[u]][u]);
	for(int u = t; u != s; u = p[u]) {
	  flow[p[u]][u] += a;
	  flow[u][p[u]] -= a;
	}
	c += d[t]*a;
	f += a;
  }

  printf("%d %d\n", f, c);
  return 0;
}

线段树

线段树详解

#define maxn 100007  //元素总个数
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
int Sum[maxn<<2],Add[maxn<<2];//Sum求和，Add为懒惰标记 
int A[maxn],n;//存原数组数据下标[1,n] 
//PushUp函数更新节点信息 ，这里是求和
void PushUp(int rt){Sum[rt]=Sum[rt<<1]+Sum[rt<<1|1];}
//Build函数建树 
void Build(int l,int r,int rt){ //l,r表示当前节点区间，rt表示当前节点编号
	if(l==r) {//若到达叶节点 
		Sum[rt]=A[l];//储存数组值 
		return;
	}
	int m=(l+r)>>1;
	//左右递归 
	Build(l,m,rt<<1);
	Build(m+1,r,rt<<1|1);
	//更新信息 
	PushUp(rt);
}

void Update(int L,int C,int l,int r,int rt){//l,r表示当前节点区间，rt表示当前节点编号
	if(l==r){//到叶节点，修改 
		Sum[rt]+=C;
		return;
	}
	int m=(l+r)>>1;
	//根据条件判断往左子树调用还是往右 
	if(L <= m) Update(L,C,l,m,rt<<1);
	else       Update(L,C,m+1,r,rt<<1|1);
	PushUp(rt);//子节点更新了，所以本节点也需要更新信息 
} 

void Update(int L,int R,int C,int l,int r,int rt){//L,R表示操作区间，l,r表示当前节点区间，rt表示当前节点编号 
	if(L <= l && r <= R){//如果本区间完全在操作区间[L,R]以内 
		Sum[rt]+=C*(r-l+1);//更新数字和，向上保持正确
		Add[rt]+=C;//增加Add标记，表示本区间的Sum正确，子区间的Sum仍需要根据Add的值来调整
		return ; 
	}
	int m=(l+r)>>1;
	PushDown(rt,m-l+1,r-m);//下推标记
	//这里判断左右子树跟[L,R]有无交集，有交集才递归 
	if(L <= m) Update(L,R,C,l,m,rt<<1);
	if(R >  m) Update(L,R,C,m+1,r,rt<<1|1); 
	PushUp(rt);//更新本节点信息 
} 

void PushDown(int rt,int ln,int rn){
	//ln,rn为左子树，右子树的数字数量。 
	if(Add[rt]){
		//下推标记 
		Add[rt<<1]+=Add[rt];
		Add[rt<<1|1]+=Add[rt];
		//修改子节点的Sum使之与对应的Add相对应 
		Sum[rt<<1]+=Add[rt]*ln;
		Sum[rt<<1|1]+=Add[rt]*rn;
		//清除本节点标记 
		Add[rt]=0;
	}
}

int Query(int L,int R,int l,int r,int rt){//L,R表示操作区间，l,r表示当前节点区间，rt表示当前节点编号
	if(L <= l && r <= R){
		//在区间内，直接返回 
		return Sum[rt];
	}
	int m=(l+r)>>1;
	//下推标记，否则Sum可能不正确
	PushDown(rt,m-l+1,r-m); 
	
	//累计答案
	int ANS=0;
	if(L <= m) ANS+=Query(L,R,l,m,rt<<1);
	if(R >  m) ANS+=Query(L,R,m+1,r,rt<<1|1);
	return ANS;
}

并查集

package suanfa;

public class Main {
	public static void main(String[] args) throws Exception {
		//parent[1]=0表示：1的双亲是0,若出现parent[2]=2表示：2是根节点
		int[] parent = new int[1000];
	}
	
	public static int findParent(int target,int[] parent){
		int parentIndex = target;
		//当一个数组等于角标时，说明找到了根节点
		//从while循环出来的temp即为target对应的树的根节点所在patent数组的下标
		while(parent[parentIndex] != parentIndex){
			parentIndex = parent[parentIndex];
		}
		//路径压缩
		int i = target;
		//把target以及target的双亲节点的全部赋值为根节点
		while(i!=parentIndex){
			//找到i对应的双亲节点
			i = parent[i];
			//把i的双亲节点直接赋值为根节点，达到路径压缩的目的
			parent[i] = parentIndex;
		}
		return parentIndex;
	}
	//要将两个树合并，分别找个两个树的根节点，把其中一个赋值为另一个的父节点即完成两颗树合并
	public static void join(int target1,int target2,int[] parent){
		int root1 = findParent(target1, parent);
		int root2 = findParent(target2, parent);
		if(root1!=root2){
			parent[root1] = root2;
		}
	}
}

LCS

//dp 求解最长公共子序列
//http://blog.csdn.net/u012102306/article/details/53184446
public static int lcs(String str1, String str2) {
    int len1 = str1.length();
    int len2 = str2.length();
    int c[][] = new int[len1+1][len2+1];
    for (int i = 0; i <= len1; i++) {
        for( int j = 0; j <= len2; j++) {
            if(i == 0 || j == 0) {
                c[i][j] = 0;
            } else if (str1.charAt(i-1) == str2.charAt(j-1)) {
                c[i][j] = c[i-1][j-1] + 1;
            } else {
                c[i][j] = max(c[i - 1][j], c[i][j - 1]);
            }
        }
    }
    return c[len1][len2];
}

最长递增子串

//http://blog.csdn.net/qq_34681949/article/details/52186675
//dp思想
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[10010];
int dp[10010]; //保存的是以ai结尾的最长递增子串
int main()
{
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		for(int i=0;i<n;i++)
		{
			scanf("%d",&a[i]);
			dp[i]=1;
		}
		int ans=0;
		for(int i=1;i<n;i++)
		{
			for(int j=0;j<i;j++)
			{
				if(a[j]<a[i])
				{
					dp[i]=max(dp[j]+1,dp[i]);
				}
			}
			ans=max(ans,dp[i]);
		}
		printf("%d\n",ans);
	}
	return 0;
 }

三角剖分

记忆化dp

博弈树

二进制法

最大团

最大独立集

判断点在多边形内

查分约束系统

双向广度搜索

A*算法

最小耗散优先

主元素问题

主元素问题：通过抵消的方法来做。

#include<iostream>
#include<vector>
#include<map>
using namespace std;
vector<int> majorityElement(vector<int>& nums) 
{
    vector<int>res;
    int n = nums.size();
	if(n<1)return res;
    int cnt1=1,cnt2=1,tmp1=nums[0],tmp2=nums[0];
    for (int i = 1; i < n; i++) {
        if (nums[i] == tmp1)
            cnt1++;
        else if (nums[i] == tmp2)
            cnt2++;
        else if (cnt1 == 0) {
            tmp1 = nums[i];
            cnt1 = 1;
        } else if (cnt2 == 0) {
            tmp2 = nums[i];
            cnt2 = 1;
        } else {
            cnt1--;
            cnt2--;
        }
    }
    int count1=0,count2=0,tmp=0;
    for(int i=0;i<n;i++){
        if(nums[i]==tmp1)
            count1++;
        else if(nums[i]==tmp2)
            count2++;
    }
    if(count1>n/3)
        res.push_back(tmp1);
    if(count2>n/3)
        res.push_back(tmp2);
    return res;
}
int majorityElement2(vector<int>& nums) 
{
    int cnt = 1,tmp = nums[0],n = nums.size();
    for(int i=1;i<n;i++){
        if(0 == cnt)
            tmp = nums[i];
        if(nums[i]==tmp)
            cnt++;
        else cnt--;
    }
    return tmp;
}
int majorityElement3(vector<int>& nums) 
{
    int n = nums.size();
    int cnt1=1,cnt2=1,tmp1=nums[0],tmp2=nums[0];
    for (int i = 1; i < n; i++) {
        if (nums[i] == tmp1)
            cnt1++;
        else if (nums[i] == tmp2)
            cnt2++;
        else if (cnt1 == 0) {
            tmp1 = nums[i];
            cnt1 = 1;
        } else if (cnt2 == 0) {
            tmp2 = nums[i];
            cnt2 = 1;
        } else {
            cnt1--;
            cnt2--;
        }
    }
    int count1=0,count2=0,tmp=0;
    for(int i=0;i<n;i++){
        if(nums[i]==tmp1)
            count1++;
        else if(nums[i]==tmp2)
            count2++;
    }
    if(count1>count2)
		return tmp1;
	else return tmp2;
}
int majorityElement4(vector<int>& nums) 
{
    int n = nums.size();
    int cnt1=1,cnt2=1,cnt3=1;
	int tmp1=nums[0],tmp2=nums[0],tmp3=nums[0];
    for (int i = 1; i < n; i++) {
        if (nums[i] == tmp1)
            cnt1++;
        else if (nums[i] == tmp2)
            cnt2++;
		else if(nums[i]==tmp3)
			cnt3++;
        else if (cnt1 == 0) {
            tmp1 = nums[i];
            cnt1 = 1;
        } else if (cnt2 == 0) {
            tmp2 = nums[i];
            cnt2 = 1;
        }else if (cnt2 == 0) {
            tmp2 = nums[i];
            cnt2 = 1;
        }else {
            cnt1--;
            cnt2--;
			cnt3--;
        }
    }
    int count1=0,count2=0,count3=0;
    for(int i=0;i<n;i++){
        if(nums[i]==tmp1)
            count1++;
        else if(nums[i]==tmp2)
            count2++;
		else if(nums[i]==tmp3)
			count3++;
    }
	int c = max(count1,max(count2,count3));
	map<int, int> mymap;
    mymap.insert(pair<int, int>(count1, tmp1));
    mymap.insert(pair<int, int>(count2, tmp2));
    mymap.insert(pair<int, int>(count3, tmp3));
    map<int, int>::iterator  iter = mymap.find(c);
    return iter->second;
}

int main()
{
	int arr2[]={2,3,2,5,2,1,2};
	int arr3[]={1,4,3,3};
	int arr[]={1,2,3,2,5,2,1,2,1,1};
	vector<int>vec2(arr2,arr2+7);
	vector<int>vec3(arr3,arr3+4);
	vector<int>vec(arr,arr+10);
	vector<int>result;
	int a,b,c;
	a = majorityElement2(vec2);
	b = majorityElement3(vec3);
	c = majorityElement4(vec3);
	result = majorityElement(vec);
	cout<<"出现1/2次以上的数："<<a<<endl;
	cout<<"出现1/3次以上的数："<<b<<endl;
	cout<<"出现1/4次以上的数："<<c<<endl;
	cout<<"所有出现概率1/3以上的数:";
	for(vector<int>::iterator iter=result.begin();iter !=result.end();++iter)
		cout<<*iter<<" ";
	cout<<endl;
	return 0;
}

import java.util.*;
import java.util.Map.Entry;
public class Solution {
    /**
     * @param nums: A list of integers
     * @param k: An integer
     * @return: The majority number
     */
    
    public int majorityNumber(List<Integer> nums, int k) {
        // write your code here
       if(nums.size()<= 0)
        {
            return 0;
        }
        int maxCount = -1;
        int maxNum = nums.get(0);
        Map<Integer, Integer> numCountMap = new HashMap<Integer, Integer>();
        Map<Integer, Integer> resultCountMap = new HashMap<Integer, Integer>();
       // System.out.println(nums.size());
       // System.out.println(nums.get(10));
        for(int i = 0 ; i < nums.size() ; i++){
            int num = nums.get(i);
            if(!numCountMap.containsKey(num) ){
                numCountMap.put(num,1);
            }else {
                numCountMap.put(num, numCountMap.get(num)+1);
            }

            if(numCountMap.size()==k){
            //    System.out.println(numCountMap.toString());
                Iterator<Map.Entry<Integer, Integer> > iterator = numCountMap.entrySet().iterator();
                while(iterator.hasNext()){
                    Map.Entry<Integer , Integer> entry = iterator.next();
                    if(entry.getValue() == 1){
                        iterator.remove();
                    }else{
                        numCountMap.put(entry.getKey(), entry.getValue() -1 );
                    }
                }

          //      System.out.println(numCountMap.toString());
            }

        }
      //  System.out.println(numCountMap.toString());
	//注意最后依然需要重复统计
       for(int i = 0 ; i < nums.size() ; i++){
           int numTmp = nums.get(i);
           if(numCountMap.containsKey(numTmp) ){
               if (resultCountMap.containsKey(numTmp)){
                   int newCount = resultCountMap.get(numTmp)+1;
                   if (newCount > maxCount){
                       resultCountMap.put(numTmp, newCount);
                       maxCount = newCount ;
                       maxNum = numTmp ;
                   }
               }else {
                   resultCountMap.put(numTmp, 1);
               }
           }
       }

        return maxNum;
    }
}

最小子串覆盖

//给定一个字符串source和一个目标字符串target，在字符串source中找到包括所有目标字符串字母的子串。
//关键点在于
public class Solution {
    /**
     * @param source : A string
     * @param target: A string
     * @return: A string denote the minimum window, return "" if there is no such a string
     */
    public String minWindow(String source , String target) {
        // write your code here
        int[] sourceArray = new int[129];
        int[] targetArray = new int[129];
        int count = target.length();
        for(int i = 0 ; i< target.length() ; i++){
            targetArray[target.charAt(i)]++;
        }
        int start = 0, begin = -1, end = source.length(), minLength = source.length();
        
        for(int j = 0 ; j < source.length(); j++ ){
            sourceArray[source.charAt(j)]++;
            if(sourceArray[source.charAt(j)] <= targetArray[source.charAt(j)])
                count--;
            if(count == 0){
                while(start < j && sourceArray[source.charAt(start)] > targetArray[source.charAt(start)]){
                    sourceArray[source.charAt(start)]--;
                    start++;
                }
                if(j - start < minLength){
                    minLength = j - start ; 
                    end = j ;
                    begin = start ;
                }
                
                sourceArray[source.charAt(start)]--;
                count++;
                start++;
            }
            
        }
        
        return begin>=0? source.substring(begin,end + 1): "";
        
    }
}

Word Ladder

枚举当前单词对应下一个单词的所有可能性，用一个set来保存是否下一个单词是否访问过，层次便利。

//http://blog.csdn.net/mine_song/article/details/68951974
import java.util.*;
public class word {
	public int ladderLength(String beginWord, String endWord, List<String> wordList) {
		if (beginWord == null || endWord == null || beginWord.length() == 0 || endWord.length() == 0
				|| beginWord.length() != endWord.length())
			return 0;
		// 此题关键是去重，还有去除和beginWord，相同的单词
		Set<String> set = new HashSet<String>(wordList);
		if (set.contains(beginWord))
			set.remove(beginWord);
		Queue<String> wordQueue = new LinkedList<String>();
		int level = 1; // the start string already count for 1
		int curnum = 1;// the candidate num on current level
		int nextnum = 0;// counter for next level
		// 或者使用map记录层数
		// Map<String, Integer> map = new HashMap<String, Integer>();
		// map.put(beginWord, 1);
		wordQueue.add(beginWord);

		while (!wordQueue.isEmpty()) {
			String word = wordQueue.poll();
			curnum--;
			// int curLevel = map.get(word);
			for (int i = 0; i < word.length(); i++) {
				char[] wordunit = word.toCharArray();
				for (char j = 'a'; j <= 'z'; j++) {
					wordunit[i] = j;
					String temp = new String(wordunit);

					if (set.contains(temp)) {
						if (temp.equals(endWord))
							// return curLevel + 1;
							return level + 1;
						// map.put(temp, curLevel + 1);
						nextnum++;
						wordQueue.add(temp);
						set.remove(temp);
					}
				}
			}
			if (curnum == 0) {
				curnum = nextnum;
				nextnum = 0;
				level++;
			}
		}
		return 0;
	}
}

周围区域问题

//https://www.cnblogs.com/little-YTMM/p/5480942.html
//注意四个方向的写法
import java.util.LinkedList;
import java.util.Queue;

class Node {
    int x;
    int y;
    public Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
class Regions {
    private int[] rowdi = {-1, 1, 0, 0};
    private int[] coldi = {0, 0, -1, 1};
    
    /**
     * BFS. 
     * Search begin from the edge to the interior. 
     * @param val
     * @return
     */
    public int[][] check(int[][] val) {
        if(val == null || val.length == 0 || val[0].length == 0)
            return val;
        Queue<Node> q = new LinkedList<Node>();
        int row = val.length;
        int col = val[0].length;
        for(int i=0; i<row; i++) {
            if(val[i][0] == 0) {
                Node n = new Node(i, 0);
                q.add(n);
                val[i][0] = 2;
            }
            if(val[i][col-1] == 0) {
                Node n = new Node(i, col-1);
                q.add(n);
                val[i][col-1] = 2;
            }
        }
        for(int j=1; j<col-1; j++) {
            if(val[0][j] == 0) {
                Node n = new Node(0, j);
                q.add(n);
                val[0][j] = 2;
            }
            if(val[row-1][j] == 0) {
                Node n = new Node(row-1, j);
                q.add(n);
                val[row-1][j] = 2;
            }
        }
        while(!q.isEmpty()) {
            Node n = q.remove();
            for(int i=0; i<rowdi.length; i++) {
                if( n.x+rowdi[i]<row && n.y+coldi[i] < col
                        && n.x+rowdi[i] >= 0 && n.y+coldi[i] >= 0) {
                    if(val[n.x+rowdi[i]][n.y+coldi[i]] == 0) {
                        Node t = new Node(n.x+rowdi[i], n.y+coldi[i]);
                        q.add(t);
                        val[n.x+rowdi[i]][n.y+coldi[i]] = 2;
                    }
                }
            }
        }
        for(int i=0; i<row; i++) {
            for(int j=0; j<col; j++) {
                if(val[i][j] == 2)
                    val[i][j] = 0;
                else if(val[i][j] == 0)
                    val[i][j] = 1;
            }
        }
        return val;
    }
}


public class SurroundedRegions {

    public static void main(String[] args) {
        int[][] val = {
                {1,1,1,1,1},
                {1,0,0,1,0},
                {1,1,1,1,0},
                {1,0,1,0,0},
                {1,1,1,1,1}};
        Regions region = new Regions();
        int[][] res = region.check(val);
        for(int i=0; i<res.length; i++) {
            for(int j=0; j<res[0].length; j++)
                System.out.print(res[i][j] + " ");
            System.out.println();
        }
    }

}

最短回文数划分

//动态规划 http://blog.csdn.net/wyg1997/article/details/52188738
#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
int main()
{
	int dp[5011];
	char str[5011];
	scanf ("%s",str+1);
	str[0] = '@';
	int l = strlen(str);
	dp[0] = 0;
	dp[1] = 1;
	for (int i = 2 ; i < l ; i++)
	{
		dp[i] = i + 1;
		for (int j = 1 ; j <= i ; j++)
		{
			bool flag = true;		//从j到i是否是回文串
			int st = j;
			int endd = i;
			while (endd >= st)
			{
				if (str[endd] != str[st])
				{
					flag = false;
					break;
				}
				endd--;
				st++;
			}
			if (flag)
				dp[i] = min (dp[i] , dp[j-1] + 1);
		}
	}
	printf ("%d\n",dp[l-1]);
	return 0;
}

八皇后问题

public class Test {

    public static void main(String[] args) {
        Empress a=new Empress();
        a.find(0);
        System.out.println("八皇后问题共有："+a.map+"种可能");
    }
}

class Empress{
    public int[][] arry=new int[8][8];    //棋盘，放皇后
    public  int map=0;     //存储方案结果

    public   boolean rule(int arry[][],int k,int j){    //判断节点是否合适
        for(int i=0;i<8;i++){       //行列冲突
             if(arry[i][j]==1)
                return false;
        }
        for(int i=k-1,m=j-1;i>=0&&m>=0;i--,m--){    //左对角线
            if(arry[i][m]==1)
                return false;
        }
        for(int i=k-1,m=j+1;i>=0&&m<=7;i--,m++){    //右对角线
            if(arry[i][m]==1)
                return false;
        }
        return true;
    }


    public void find(int i){    //寻找皇后节点
        if(i>7){    //八皇后解  
            map++;
            print();
            return;
        }
        for(int m=0;m<8;m++){       //深度优先,递归算法
            if(rule(arry,i,m)){
                arry[i][m]=1;
                find(i+1);
                arry[i][m]=0;
                }
        }   
    }

    public void print(){      //打印方法结果
        System.out.print("方案"+map+":");
        for(int i=0;i<8;i++){
            for(int m=0;m<8;m++){
                if(arry[i][m]==1){  
                    System.out.print("皇后"+(i+1)+"在第"+i+"行，第"+m+"列\t");

                }
            }
        }
        System.out.println();
    }
}

LCA问题

//tarjan的做法 倍增http://blog.csdn.net/jarjingx/article/details/8183240
//
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;

const int maxn=10010;//顶点数
const int maxq=100;//最多查询次数，根据题目而定，本题中其实每组数据只有一个查询.

//并查集
int f[maxn];//根节点
int find(int x)
{
    if(f[x]==-1)
        return x;
    return f[x]=find(f[x]);
}
void unite(int u,int v)
{
    int x=find(u);
    int y=find(v);
    if(x!=y)
        f[x]=y;
}
//并查集结束

bool vis[maxn];//节点是否访问
int ancestor[maxn];//节点i的祖先
struct Edge
{
    int to,next;
}edge[maxn*2];
int head[maxn],tot;
void addedge(int u,int v)//邻接表头插法加边
{
    edge[tot].to=v;
    edge[tot].next=head[u];
    head[u]=tot++;
}

struct Query
{
    int q,next;
    int index;//查询编号，也就是输入的顺序
}query[maxq*2];
int ans[maxn*2];//存储每次查询的结果,下表0~Q-1，其实应该开maxq大小的。
int h[maxn],tt;
int Q;//题目中需要查询的次数

void addquery(int u,int v,int index)//邻接表头插法加询问
{
    query[tt].q=v;
    query[tt].next=h[u];
    query[tt].index=index;
    h[u]=tt++;
    query[tt].q=u;//相当于两次查询，比如查询  3，5 和5，3结果是一样的，以3为头节点的邻接表中有5，以5为头节点的邻接表中有3
    query[tt].next=h[v];
    query[tt].index=index;
    h[v]=tt++;
}

void init()
{
    tot=0;
    memset(head,-1,sizeof(head));
    tt=0;
    memset(h,-1,sizeof(h));
    memset(vis,0,sizeof(vis));
    memset(f,-1,sizeof(f));
    memset(ancestor,0,sizeof(ancestor));
}

void LCA(int u)
{
    ancestor[u]=u;
    vis[u]=true;
    for(int i=head[u];i!=-1;i=edge[i].next)//和顶点u相关的顶点
    {
        int v=edge[i].to;
        if(vis[v])
            continue;
        LCA(v);
        unite(u,v);
        ancestor[find(u)]=u;//将u的左右孩子的祖先设为u
    }
    for(int i=h[u];i!=-1;i=query[i].next)//看输入的查询里面有没有和u节点相关的
    {
        int v=query[i].q;
        if(vis[v])
            ans[query[i].index]=ancestor[find(v)];
    }
}
bool flag[maxn];//用来确定根节点的

int t;
int n,u,v;

int main()
{
    int a,b,c;
    scanf("%d(%d):%d",&a,&b,&c);
    cout<<a<<b<<c;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        init();
        memset(flag,0,sizeof(flag));
        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&u,&v);
            flag[v]=true;//有入度
            addedge(u,v);
            addedge(v,u);
        }
        Q=1;//题目中只有一组查询
        for(int i=0;i<Q;i++)
        {
            scanf("%d%d",&u,&v);
            addquery(u,v,i);
        }
        int root;
        for(int i=1;i<=n;i++)
        {
            if(!flag[i])
            {
                root=i;
                break;
            }
        }
        LCA(root);
        for(int i=0;i<Q;i++)
            printf("%d\n",ans[i]);
    }
    return 0;
}

单纯形算法

//http://uoj.ac/problem/179
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=25;
const double eps=1e-8,INF=1e15;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}
    return x*f;
}
int n,m,type;
double a[N][N],ans[N];
int id[N<<1];
int q[N];
void Pivot(int l,int e){
    swap(id[n+l],id[e]);
    double t=a[l][e]; a[l][e]=1;
    for(int j=0;j<=n;j++) a[l][j]/=t;
    for(int i=0;i<=m;i++) if(i!=l && abs(a[i][e])>eps){
        t=a[i][e]; a[i][e]=0;
        for(int j=0;j<=n;j++) a[i][j]-=a[l][j]*t;
    }
}
bool init(){
    while(true){
        int e=0,l=0;
        for(int i=1;i<=m;i++) if(a[i][0]<-eps && (!l||(rand()&1))) l=i;
        if(!l) break;
        for(int j=1;j<=n;j++) if(a[l][j]<-eps && (!e||(rand()&1))) e=j;
        if(!e) {puts("Infeasible");return false;}
        Pivot(l,e);
    }
    return true;
}
bool simplex(){
    while(true){
        int l=0,e=0; double mn=INF;
        for(int j=1;j<=n;j++) 
            if(a[0][j]>eps) {e=j;break;}
        if(!e) break;
        for(int i=1;i<=m;i++) if(a[i][e]>eps && a[i][0]/a[i][e]<mn)
            mn=a[i][0]/a[i][e],l=i;
        if(!l) {puts("Unbounded");return false;}
        Pivot(l,e);
    }
    return true;
}
int main(){
    freopen("in","r",stdin);
    srand(317);
    n=read();m=read();type=read();
    for(int i=1;i<=n;i++) a[0][i]=read();
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++) a[i][j]=read();
        a[i][0]=read();
    }
    for(int i=1;i<=n;i++) id[i]=i;
    if(init() && simplex()){
        printf("%.8lf\n",-a[0][0]);
        if(type){
            for(int i=1;i<=m;i++) ans[id[n+i]]=a[i][0];
            for(int i=1;i<=n;i++) printf("%.8lf ",ans[i]);
        }
    }
}

矩阵连乘问题

//https://www.cnblogs.com/PJQOOO/p/4474354.html
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<stdlib.h>
using namespace std;
const int MAX = 100;
int n;
int p[MAX+1],m[MAX][MAX],s[MAX][MAX];
//p用来记录矩阵，m[i][j]表示第i个矩阵到第j个矩阵的最优解，s[][]记录从哪里断开可以得到最优解
void matrixChain()
{
    for(int i=1; i<=n; i++)//初始化数组
        m[i][i]=0;
    for(int r=2; r<=n; r++)//对角线循环
    {
        for(int i=1; i<=n-r+1; i++) //行循环
        {
            int j=i+r-1;//列的控制
            m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];//找m[i][j]的最小值，初始化使k=i;
            s[i][j]=i;
            for(int k=i+1; k<j; k++)
            {
                int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
                if(t<m[i][j])
                {
                    s[i][j]=k;//在k位置断开得到最优解
                    m[i][j]=t;
                }
            }
        }
    }
}
void traceback(int i,int j)
{
    if(i==j)
        return;
    traceback(i,s[i][j]);
    traceback(s[i][j]+1,j);
    cout<<"Multiply A"<<i<<","<<s[i][j]<<"and A"<<s[i][j]+1<<","<<j<<endl;
}
int main()
{
    cin>>n;
    for(int i=0; i<=n; i++)
        cin>>p[i];
    matrixChain();
    traceback(1,n);
    cout<<m[1][n]<<endl;
    return 0;
}

Select和Epoll的区别

http://itindex.net/detail/54039-linux-epoll-%E6%A8%A1%E5%BC%8F