C# week1

OOP 面向过程编程及其先天的缺陷 软件由若干个子过程组成,当数据准备完毕之后,软件代码的执行次序就会被确定。 但是这个方法在用于大的工程的时候,程序员在测试的时候就需要追踪大量的程序分支,造成调试的诸多不便。在程序员协同工作的时候,很容易出现十分混乱的情况。 OOP 我们将指令集划分成几个单独的模块,在这里就叫做类,几个对象之间通过相互传递消息来激活对方的指令集来交互协作,从而达到执行程序的目的。这样,对模块的创建或者维护就相对容易了。 类型 强类型的语言 c#使用了兼容性的原则,当不相兼容的类型之间存在操作的时候,编译器就会报出一个错误。当然,对于可以兼容的类型,C#提供了隐式转换的方式来将一种类型转化成为一个可以和其兼容的语言。 引用类型:引用类型指的是其本身并不包含这个对象,而是包含了指向这个对象的位置。就是在栈中存储相应的指针,而在堆中存储相应的数据。 值类型:其本身保存了其真正的值。直接在栈中存储相应的信息。 c#中的主要类型 简单类型 枚举类型:用于创建符号常量,特别是和常量有关的对象。 结构类型:包含和类类似的方法和数据,但是十分不同的是结构类型就是一个值类型 类类型:定义一个对象的类别和创建对象的蓝图。 数组类型:保存少量或者大量数据集合的对象,数组中的数据项必须相同。 接口类型:指定一个或者多个方法头来规定抽象的行为 string类 栈和堆的关系 所有的引用空间所指向的对象都会被.NET框架所控制,在结束程序的时候,堆的空间会自动被回收,所以我们不需要考虑内存空间泄漏的问题。

04 Mar 2017

Polya Theory

问题的给出 先看一个十分简单的问题,如果使用2种颜色给一个正方形染色,那么一共会存在多少种情况呢? 如果承认顶点是两两不同的,我们就可以看到一共存在24=16种方法。 但是,如果考虑同构又要怎么做呢? 我们可以发现,全染成一种颜色,一共2种方法,2,2分,2种方法,1,3分2种方法,所以存在着6种不同的方法。 更多的思考 我们先有了下面的一些定义: 对称: 设一个几何图形α, 我们令其运动到和其本身重合的图形叫做这个几何图形的一个对称,我们可以使用一个置换来表示这个对称。 着色: 就是将1−n的点着色成为c1..cn的颜色,这样的关系同样也是可以使用一个置换来进行表示。 我们在这里定义,两个着色c1,c2关于G等价,就是在G中存在这样的置换,使得有下面的式子成立. 稳定核: 对于一种着色,我们定义G(c)是其稳定核,而且这个稳定核是置换群。 很容易证明这个代数系统的结合律,单位元和逆元的存在性。 推论1: 设c是C中的一个着色,那么和c等价的着色数等于G中的置换个数除以c中的稳定核中的置换的数目. 证明: 存在|G|个着色可以从置换群处理得到,但是,对于每个置换,又会存在G(c)个置换和其产生的效果相同,我们很容易就得到了这样的解。 Burnside定理: G是X的置换群,而且C是X中满足下面的一个着色集合,对于G中所有的g和C中所有的c,g∗c还在C中,则非等价着色数是由下面的定理给出: Polya计数原理 对于任何的一个置换,我们可以将其分解成多个循环节,我们立刻就可以得到下面的一个很强的结论: 在这种情况下两种着色要能通过置换得到等价,必须将循环节中的结点染色成相同的颜色。就是: 我们就可以简化上面的定理,来减小算法的复杂度了。

01 Mar 2017

Suffix Array

基本概念 在了解后缀数组之前,很显然我们需要了解一些基本的概念。 字符集:构造了一个全序的关系,即集合里面的元素要么是大于关系要么是小于关系。 子串:记为$S[i..j]$,表示字符串第i个字符到j-1个字符的子序列 后缀:记为$Suffix(i)$,表示从第i个字符到结尾的子串。 后缀数组:将S的n个后缀经过排序之后得到的数组。(以开头位置代替了实际的后缀) 名次数组:就是后缀数组的反函数,$rank[i]$的意思就是$Suffix(i)$的排序。 构造方法 很显然,我们可以使用暴力排序的方法来解决,但是那样的复杂度就会相当的高,最少也是$O(n^2)$,但是,我们在这里还是可以使用二分的思想来解决构造的问题。 算法如下所示: 首先我们对单个字符进行排序,得到一个序列。 其次,我们以第一关键字为$rank[i]$,第二关键字为$rank[i+l]$对字符串再次进行排序。其中l从1开始使用倍增的策略。在这里,我们很显然可以采用基数排序来解决这个问题。 memset(cntA,0,sizeof(cntA)); for(i=1;i<=n;i++)cntA[arr[i]]++; for(i=1;i<=n;i++)cntA[i] += cntA[i-1]; for(i=n;i>=1;i--)sa[cntA[arr[i]]--] = i; ranki[sa[1]] = 1; for(i=2;i<=n;i++){ ranki[sa[i]] = ranki[sa[i-1]]; if(arr[sa[i]]!=arr[sa[i-1]]) ranki[sa[i]]++; } for(l=1;ranki[sa[n]]<n;l<<=1){ memset(cntA,0,sizeof(cntA)); memset(cntB,0,sizeof(cntB)); for(i=1;i<=n;i++){ cntA[A[i]=ranki[i]]++;...

13 Jan 2017

一个有意思的DP

题目描述 给定一棵含有 n 个结点的树,结点从 1 标号。你从 1 号结点驾车出发,希望遍历一些关键结点(访问到就好,不需要按照这些关键结点的输入顺序)。每条边有两个权值,c0, c1 分别表示步行和驾车经过这条边的代价。每次你可以选择驾车经过一条边(当且仅当有车),或者将车停放在当前所在的结点(如果有车),步行经过一条边。 求遍历完所有关键结点的最少代价。 注意: 你可以在任意结点结束遍历,即使当前没有车。 解题思路 在这里说句实话,这道题我从看开始到今天解决这个问题,一共用了大半年的时间。不过今天终于是解决了。看来今天晚上可以睡个好觉了。 首先是划分子问题,这里对一棵子树的遍历可以采用5种方式,走路遍历且回来,开车遍历且回来,走路遍历不一定回来,开车遍历人一定回来但是车不一定回来,开车遍历人和车都不一定回来。 走路遍历且回来和开车遍历且回来这两种十分简单: 3.下面看一看这几种情况: 首先是走路去但是不一定回来,这个问题还是比较好解决的,就是挑选一棵子树只是去遍历但是不回来,公式如下: 然后就是开车去而车不一定回来,这个也是比较简单的,就是存在一个替换就好了: 最后一个问题就不是那么简单的了,开车去但是人和车都不一定回来。我们需要分两种情况进行讨论,一种是遍历到最后一棵子树的时候还有车,请注意,这个时候我们也不一定必须要用车,走路也是可以的呀,所以,我们得到下面的公式: 下面一种情况就比较复杂了,就是车最后所在的位置和人不在同一棵子树当中,我们这个时候使用贪心的思维: 找出$min(dp[dest][3]+w0(cur,dest)+w1(cur,dest)−t,0)$ 找出$min(dp[dest][2]+w0(cur,dest)−t,0)$ 但是,两个所代表的点又可能是相同的点,所以我们需要找的是前两个最小的数来解决这个问题。 最后一点,如果这棵子树当中不存在关键节点,那么我们没有必要对其进行动态规划操作,所以可以事先使用一个DFS遍历剪枝。 Code #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std;...

19 Dec 2016

一个有意思的博弈

题目描述 有两个人玩游戏,轮流取物品。每个物品对不同的人都会存在不同的价值。对手使用的贪心原则,也就是说在每一步对手都会选择对他价格最大的物品。当存在多个物品价格相同的时候,对手会随机选择一个物品。这个时候问我们可以最多得到多大的结果。 解题过程 咋一看,这是个明显贪心过程,我们按照两个关键字排序之后对两个人都采用贪心策略模拟就可以了。但是,事实上,这样做是不对的。因为A要取的物品也可能是对B很重要的物品,而B正在取的物品则对A没有那么重要,推迟一些取也是可以的。那么,到底怎么做呢? 我做出了一个比较强的结论:在使用了两个关键字排序之后,对于任意的i<n,我们都知道在前i个物品中A至少会取得i/2个物品。 证明: 前i个物品至少需要i/2轮才可以取完。 这个完全不需要证明,每轮两个人各取1个物品,最快取完需要i/2轮 我们按照A的逻辑顺序排序,所以A总是会取价值最大的元素,也就是标号较小的元素,即在前i/2轮,A一定不会取标号大于i的物品。 我们证明了这样的定理。 那么也就是说,在前i个物品中,我们最多取i/2个。 这样,就可以得到下面的转移方程: 迭代,就可以得到解 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<utility> using namespace std; #define LL long long #define MAXN 1005 #define pi pair<LL,LL> LL dp[MAXN][MAXN]; int t,n;...

18 Nov 2016