月份:2016年12月

Decision Tree – ID3算法 (editing)

Decision Tree – ID3算法 (editing)

1.决策树概念
机器学习中,决策树是一个预测模型;他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象,而每个分叉路径则代表的某个可能的属性值,而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出,若欲有复数输出,可以建立独立的决策树以处理不同输出。 数据挖掘中决策树是一种经常要用到的技术,可以用于分析数据,同样也可以用来作预测。
从数据产生决策树的机器学习技术叫做决策树学习,通俗说就是决策树。[Wikipedia]
所以在我的理解中,决策树就是由一定数据生成的一棵树,这棵树包含了由数据中各种关系产生的判断条件。我们可以通过另外一组数据,通过这些判断条件来推测出我们所需要的值。
举一个经典的例子:打网球。
+—–+———-+————-+———-+——-+——+
| DAY | OUTLOOK | TEMPERATURE | HUMIDITY | WINDY | PLAY |
+—–+———-+————-+———-+——-+——+
| 1 | SUNNY | 85 | 85 | FALSE | NO |
+—–+———-+————-+———-+——-+——+
| 2 | SUNNY | 80 | 90 | TRUE | NO |
+—–+———-+————-+———-+——-+——+
| 3 | OVERCAST | 83 | 78 | FALSE | YES |
+—–+———-+————-+———-+——-+——+
| 4 | RAIN | 70 | 96 | FALSE | YES |
+—–+———-+————-+———-+——-+——+
| 5 | RAIN | 68 | 80 | FALSE | YES |
+—–+———-+————-+———-+——-+——+
| 6 | RAIN | 65 | 70 | TRUE | NO |
+—–+———-+————-+———-+——-+——+
| 7 | OVERCAST | 64 | 65 | TRUE | YES |
+—–+———-+————-+———-+——-+——+
| 8 | SUNNY | 72 | 95 | FALSE | NO |
+—–+———-+————-+———-+——-+——+
| 9 | SUNNY | 69 | 70 | FALSE | YES |
+—–+———-+————-+———-+——-+——+
| 10 | RAIN | 75 | 80 | FALSE | YES |
+—–+———-+————-+———-+——-+——+
| 11 | SUNNY | 75 | 70 | TRUE | YES |
+—–+———-+————-+———-+——-+——+
| 12 | OVERCAST | 72 | 90 | TRUE | YES |
+—–+———-+————-+———-+——-+——+
| 13 | OVERCAST | 81 | 75 | FALSE | YES |
+—–+———-+————-+———-+——-+——+
| 14 | RAIN | 71 | 80 | TRUE | NO |
+—–+———-+————-+———-+——-+——+
这样一个数据表就可以用来构建一个决策树。我们需要选择的是到底要不要打网球,那么我们把要不要打网球作为根,然后是天气,如果晴天,那么考虑湿度,如果是雨天,看是否刮风,还有阴天,是4/4都是要去打网球。这样就构建出了一个决策树。
2.ID3算法
ID3算法是一个通过信息熵增减来进行决策的算法。
(待续)

HIHOCODER-WEEK127 后缀自动机一·基本概念

HIHOCODER-WEEK127 后缀自动机一·基本概念

讲道理我还没弄懂= =不过先把题目做出来了
并不知道怎么在求SAM的时候求出ENDPOS只好求完SAM之后再枚举子串在SAM中匹配到state然后再输出结果
我知道我蠢qwq
=================

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace HIHOCODER_WEEK127
{
    class Program
    {
        const int MAXLEN = 100;
        static string S;
        static void Main(string[] args)
        {
            S = Console.ReadLine();
            State[] st = new State[MAXLEN * 2];
            for (int i = 0; i < MAXLEN * 2; i++)
            {
                st[i] = new State();
            }
            int sz = 0, last = 0;
            st[0].len = 0;
            st[0].link = -1;
            ++sz;
            int charpos = 0;
            foreach (char c in S)
            {
                charpos++;
                int cur = sz++;
                st[cur].len = st[last].len + 1;
                int p;
                for (p = last; p != -1 && (!st[p].next.ContainsKey(c)); p = st[p].link)
                {
                    st[p].next.Add(c, cur);
                }
                if (p == -1)
                {
                    st[cur].link = 0;
                }
                else
                {
                    int q = st[p].next;
                    if (st[p].len + 1 == st[q].len)
                    {
                        st[cur].link = q;
                    }
                    else
                    {
                        int backup = sz++;
                        st[backup].len = st[p].len + 1;
                        st[backup].next = new Dictionary<char, int>(st[q].next);
                        st[backup].link = st[q].link;
                        for (; p != -1 && (st[p].next == q); p = st[p].link)
                        {
                            st[p].next = backup;
                        }
                        st[q].link = st[cur].link = backup;
                    }
                }
                last = cur;
            }
            for (int i = 0; i < S.Length; i++)
            {
                st[0].endpos.Add(i);
            }
            for (int i = 0; i < S.Length; i++)
            {
                for (int j = i + 1; j < S.Length + 1; j++)
                {
                    string substr = S.Substring(i, j - i);
                    int state = Match(substr, st);
                    if (state != -1)
                    {
                        st[state].endpos.Add(j);
                        st[state].sub.Add(substr);
                    }
                }
            }
            int n = Convert.ToInt32(Console.ReadLine().Trim());
            for (int i = 0; i < n; i++)
            {
                string q = Console.ReadLine();
                foreach (var t in st)
                {
                    if (t.sub.Contains(q))
                    {
                        int max = 0;
                        int min = 0x3f3f3f3f;
                        string maxstring = "";
                        string minstring = "";
                        foreach (var ts in t.sub)
                        {
                            if (ts.Length > max) { max = ts.Length; maxstring = ts; }
                            if (ts.Length < min) { min = ts.Length; minstring = ts; }
                        }
                        Console.Write("{0} {1} ", minstring, maxstring);
                        foreach (var v in t.endpos)
                        {
                            Console.Write("{0} ", v);
                        }
                        Console.WriteLine();
                    }
                }
            }

        }

        static int Match(string s,State[] st)
        {
            bool m = true;
            int l = s.Length;
            if (!st[0].next.ContainsKey(s[0])) return -1;
            int cur = 0;
            while (l-- > 0)
            {
                char c = s[s.Length - l - 1];
                if (!st[cur].next.ContainsKey(c))
                {
                    m = false;
                    break;
                }
                cur = st[cur].next;
            }
            return m ? cur : -1;
        }
    }
    public class State
    {
        public int len, link;
        public HashSet<string> sub;
        public HashSet<int> endpos;
        public Dictionary<char, int> next = new Dictionary<char, int>();
        public State()
        {
            len = 0;
            link = 0;
            sub = new HashSet<string>();
            endpos = new HashSet<int>();
            next = new Dictionary<char, int>();
        }
    }
}

[C#]Stack

[C#]Stack

    public class Stack<T>
    {
        private StackNode<T> Head;
        Exception NullTopEx = new Exception("Null stack head");
        public Stack()
        {
            Head = null;
        }
        public void Push(T data)
        {
            StackNode<T> s = new StackNode<T>(data)
            {
                Next = Head
            };
            Head = s;
        }
        public void Pop()
        {
            if (Head == null)
            {
                throw NullTopEx;
            }
            Head = Head.Next;
        }
        public T GetTop()
        {
            if (Head == null)
            {
                throw NullTopEx;
            }
            return Head.Data;
        }
        public int GetHeight()
        {
            StackNode<T> t = Head;
            int len = 0;
            while (t != null)
            {
                ++len;
                t = t.Next;
            }
            return len;
        }
    }
    public class StackNode<T>
    {
        public T Data;
        public StackNode<T> Next;
        public StackNode()
        {
            Data = default(T);
            Next = null;
        }
        public StackNode(T data)
        {
            Data = data;
            Next = null;
        }
        public StackNode(StackNode<T> next)
        {
            Data = default(T);
            Next = next;
        }
        public StackNode(T data, StackNode<T> next)
        {
            Data = data;
            Next = next;
        }
    }
[C#]LinkedList

[C#]LinkedList

    public class LinkedList<T>
    {
        Exception NullLinkListEx = new Exception("Null LinkList");
        Exception NullLLorNoIndx = new Exception("Null LinkList or index out of range");
        Exception OutofIndexRang = new Exception("Index out of range");
        public T this[int index]
        {
            get
            {
                return GetElem(index);
            }
            set
            {
                EditElem(index, value);
            }
        }
        private LinkListNode<T> Head { get; set; }
        public LinkedList()
        {
            Head = null;
        }
        public int GetLength()
        {
            LinkListNode<T> p = Head;
            int len = 0;
            while (p != null)
            {
                ++len;
                p = p.Next;
            }
            return len;
        }
        public void Clear()
        {
            Head = null;
        }
        public bool IsEmpty()
        {
            if (Head == null)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
        public void Append(T item)
        {
            LinkListNode<T> q = new LinkListNode<T>(item);
            LinkListNode<T> p = new LinkListNode<T>();
            if (Head == null)
            {
                Head = q;
                return;
            }
            p = Head;
            while (p.Next != null)
            {
                p = p.Next;
            }
            p.Next = q;
        }
        public void Insert(T item, int i)
        {

            if (IsEmpty() || i < 1 || i > GetLength())
            {
                throw NullLLorNoIndx;
            }
            if (i == 1)
            {
                LinkListNode<T> q = new LinkListNode<T>(item)
                {
                    Next = Head
                };
                Head = q;
                return;
            }
            LinkListNode<T> p = Head;
            LinkListNode<T> r = new LinkListNode<T>();
            int j = 1;
            while (p.Next != null && j < i)
            {
                r = p;
                p = p.Next;
                ++j;
            }
            if (j == i)
            {
                LinkListNode<T> q = new LinkListNode<T>(item)
                {
                    Next = p
                };
                r.Next = q;
            }
        }
        public void InsertPost(T item, int i)
        {
            if (IsEmpty() || i < 1 || i > GetLength())
            {
                throw NullLLorNoIndx;
            }
            if (i == 1)
            {
                LinkListNode<T> q = new LinkListNode<T>(item)
                {
                    Next = Head.Next
                };
                Head.Next = q;
                return;
            }
            LinkListNode<T> p = Head;
            int j = 1;
            while (p != null && j < i)
            {
                p = p.Next;
                ++j;
            }
            if (j == i)
            {
                LinkListNode<T> q = new LinkListNode<T>(item)
                {
                    Next = p.Next
                };
                p.Next = q;
            }
        }
        public T Delete(int i)
        {
            if (IsEmpty() || i < 0 || i > GetLength())
            {
                throw NullLLorNoIndx;
            }
            LinkListNode<T> q = new LinkListNode<T>();
            if (i == 1)
            {
                q = Head;
                Head = Head.Next;
                return q.Data;
            }
            LinkListNode<T> p = Head;
            int j = 1;
            while (p.Next != null && j < i)
            {
                ++j;
                q = p;
                p = p.Next;
            }
            if (j == i)
            {
                q.Next = p.Next;
                return p.Data;
            }
            else
            {
                throw OutofIndexRang;
            }
        }
        public void EditElem(int i, T data)
        {
            if (IsEmpty() || i < 0)
            {
                throw NullLinkListEx;
            }
            LinkListNode<T> p = new LinkListNode<T>();
            p = Head;
            int j = 0;
            while (p.Next != null && j < i)
            {

                ++j;
                p = p.Next;
            }
            if (j == i)
            {
                p.Data = data;
            }
            else
            {
                throw OutofIndexRang;
            }
        }
        public T GetElem(int i)
        {
            if (IsEmpty() || i < 0)
            {
                throw NullLinkListEx;
            }
            LinkListNode<T> p = new LinkListNode<T>();
            p = Head;
            int j = 0;
            while (p.Next != null && j < i)
            {

                ++j;
                p = p.Next;
            }
            if (j == i)
            {
                return p.Data;
            }
            else
            {
                throw OutofIndexRang;
            }
        }
        public int Locate(T value)
        {
            if (IsEmpty())
            {
                throw NullLinkListEx;
            }
            LinkListNode<T> p = new LinkListNode<T>();
            p = Head;
            int i = 1;
            while (!p.Data.Equals(value) && p.Next != null)
            {
                p = p.Next;
                ++i;
            }
            return i;
        }
    }
    public class LinkListNode<T>
    {
        public T Data { get; set; }
        public LinkListNode<T> Next { get; set; }
        public LinkListNode(T item, LinkListNode<T> p)
        {
            Data = item;
            Next = p;
        }
        public LinkListNode(LinkListNode<T> p)
        {
            Next = p;
        }
        public LinkListNode(T val)
        {
            Data = val;
            Next = null;
        }
        public LinkListNode()
        {
            Data = default(T);
            Next = null;
        }
    }
REPORT HIHOCODER1354-积水的城市

REPORT HIHOCODER1354-积水的城市

SPFA
本来想是做一个图然后把积水点相连的路径删掉然后发现这样做好蠢
这个程序的C#代码我写得很难看……贴http://blog.csdn.net/piaocoder/article/details/52173939的代码吧

#include <iostream>
#include <set> 
#include <queue>
#include <cstring>
  
#define INF 0x3f3f3f3f  
using namespace std;  
  
const int N = 505;  
const int M = 505;  
const int dx[] = {-1,0,1,0};  
const int dy[] = {0,1,0,-1};  
  
struct node{  
    int x,y,d;  
    node(int a,int b,int c) : x(a),y(b),d(c){}  
    bool operator < (const node &s) const{  
        return d > s.d;  
    }  
};  
  
int n,m;  
int A[M];  
int B[N];  
int vis[N][M];  
set<pair<int, int> > dead;  
  
int solve(int x,int y,int p,int q){  
    priority_queue<node> pq;  
    pq.push(node(x,y,0));  
    vis[x][y] = 0;  
    while(!pq.empty()){  
        node cur = pq.top();  
        pq.pop();   
        for(int i = 0; i < 4; ++i) {  
            int xx = cur.x + dx[i];  
            int yy = cur.y + dy[i];  
            if(xx <= 0 || yy <= 0 || xx > n || yy > m || dead.find(make_pair(xx, yy)) != dead.end())  
                continue;  
            int d = dx[i] == 0 ? cur.d + A[min(cur.y, yy)]:cur.d + B[min(cur.x, xx)];  
            if (vis[xx][yy] <= d)  
                continue;  
            if (xx != p || yy != q)  
                pq.push(node(xx, yy, d));  
            vis[xx][yy] = d;  
        }//
    }  
    return vis[p][q] == INF?-1:vis[p][q];  
}  
  
int main(){  
    while(~scanf("%d%d",&n,&m)){  
        for(int i = 1; i < n; ++i)  
            scanf("%d",&B[i]);  
        for(int i = 1; i < m; ++i)  
            scanf("%d",&A[i]);  
        int k;  
        scanf("%d",&k);  
        for(int i = 0; i < k; ++i){  
            int x, y;  
            scanf("%d%d",&x,&y);  
            dead.insert(make_pair(x, y));  
        }  
        int Q;  
        scanf("%d",&Q);  
        for(int i = 0; i < Q; ++i){  
            int x,y,p,q;  
            scanf("%d%d%d%d",&x,&y,&p,&q);  
            memset(vis,INF,sizeof(vis));  
            printf("%d\n",solve(x,y,p,q));  
        }  
    }  
    return 0;  
}