新零点

博客

  • 云打印beta测试版试用

    　　看到云打印的消息，打印机无驱动时代，那是怎么样的世界啊！一直都很喜欢Chrome，但用的一直是Stable（稳定版），没尝试过Dev版，今天为了云打印试一下。

  • 关于

    　　我啊，想知道我是谁不？不想知道就点击右上角的叉叉（Ubuntu是左上角。）我是岳阳市第四中学的一名高中生，现在16岁——张青阳！ 　　我挺喜欢开源的, , 大家记住我, My S-K-Y, Zqynux, yylogo (三个名字我都常用.) 　　平时的话比较喜欢Fedora, Chrome, C, Apache, MySQL, 对于Google公司特别感兴趣, 无论是它的Chrome还是Chrome OS, 又或者是手机操作系统Android, 不过最喜欢的还是Chrome和它的在线文档, 云计算标志性的程序, 网页上编辑文档, 表格, 绝对不必MS OFFICE差劲. 　　这个博客是自己搭建的LAMP W ——Linux, Apache, MySQL, PHP, WordPress.. 　　最近正在着手写自己的中近期伟大梦想——Zqynux内核，不会闭门造车的，吸收Linux的营养，遗传它的优秀基因，变异出适合自己的习惯的操作系统，以我之名命名的操作系统。 　　目前这个网站是CodeWays网友给我提供的美国VPS，如果他不提供的话那么我只有使用自己那台一天开机几个小时的，512MB的Linux了，同时感谢他给我寄了一本《算法导论》，由衷感谢。

    　　这里未完待续，我会慢慢地把未来三年规划一下（到高考打止的三年。），慢慢再发上来

    2010-12-16

  • Noip 2010 提高组 第三题 关押罪犯

    　　这题的话，就是贪心，把最大的罪恶值的两个囚犯都不关在一个牢房里，反复的贪心，但是数据太大，不允许使用邻接表和邻接矩阵，用什么结构来保存呢？我觉得（也是网上的资料里的咯）使用动态分配是个方法，因为最多10000条边，根据实际情况来分配，这样不会有浪费的空间，也就不会导致空间爆掉了。

    #include <stdio.h>
    #include <stdlib.h>
    int m, n;
    struct list{
            int a, b, v;
    }list[100001];
    struct link{
            int b;
            struct link next;
    }head[20000];
    int color[20000];
    int nowco = 1;

    int com(const void a, const void b)
    {
            return ((struct list    )b)->v – ((struct list)a)->v;
    }

    void add(int a, int b)
    {
            struct link     p;
            p = malloc(sizeof(struct link));
            p->b = b;
            p->next = head[a].next;
            head[a].next = p;
    }

    int other_color(int c)
    {
            if(c & 1){
                    return c + 1;
            }
            return c – 1;
    }

    int min(int a, int b)
    {
            return a > b ? b : a;
    }

    void dfs(int a)
    {
            struct link i;
            for(i = head[a].next; i != NULL; i = i->next){
                    if((color[i->b] – color[a] >= –1) && (color[i->b] – color[a] <= 1) && 
                            (min(color[i->b], color[a]) & 1)){
                            continue;
                    }
                    color[i->b] = other_color(color[a]);
                    dfs(i->b);
            }
    }

    #define d(a) #a

    int main(void)
    {
            int i, j;
            struct link     p;
            int a, b;
            freopen("prison"d(5)".in", "r", stdin);
            scanf("%d%d", &n, &m);
            for(i = 0; i < m; i++){
                    scanf("%d%d%d", &list[i].a, &list[i].b, &list[i].v);
                    list[i].a–, list[i].b–;
            }
            qsort(list, m, sizeof(struct list), com);
            for(i = 0; i < m; i++){
                    a = list[i].a;
                    b = list[i].b;
                    add(a, b);
                    add(b, a);
                    if(color[a] == 0 || color[b] == 0){
                            color[a] = nowco++;
                            color[b] = nowco++;
                            continue;
                    }else if(color[a] == 0){
                            color[b] = other_color(color[a]);
                            continue;
                    }else if(color[b] == 0){
                            color[a] = other_color(color[b]);
                            continue;
                    }
                    if(color[a] == color[b]){
                            break;
                    }
                    dfs(b);
            }
            printf("%d\n", list[i].v);
            getch();
            return 0;
    }

  • Noip 2010 提高组 第二题 乌龟棋

    　　在考场上我的思想是这么的，f[n +
    j] = max{当在n这个位置时还有布数为j的卡片|f[n] + map[n + j]}，后来发现这么是不行的，因为f[n + j]不是最大但也可能有更好的取值，因为它可以留下另外一张卡片，只有10分呢！
    　　后来，我又想了另外一种算法，用一个维护一个栈，然后判断所有的可能性（说白了就是暴力枚举。），很自然读者都想到了两字——Time Out(超时)，不过也有30分！
    　　经过我的冥思苦想，终于是想到了另外一个方程，题目说的很清楚，每种卡片最多40张，那么就用卡片来枚举，f[a][b][c][d] = max{f[a –
    1][b][c][d], f[a][b – 1][c][d], f[a][b][c – 1][d], f[a][b][c][d – 1]} + map[1
    a + 2     b + 3 c + 4 d];
    　　很自然的，这个方程式无敌的～AC了，只可惜是在家里而不是考场。。

    #include <stdio.h>
    #define max(a, b) ((a)>(b)?(a):(b))
    #define index_map
    int map[351];
    int f[41][41][41][41];
    int card[4];
    int used[4];

    void srch(int n)
    {
            int i;
            if(n == 4){
                    int t = 0;
                    if(used[0] != 0){
                            t = max(t, f[used[0] – 1][used[1]][used[2]][used[3]]);
                    }
                    if(used[1] != 0){
                            t = max(t, f[used[0]][used[1] – 1][used[2]][used[3]]);
                    }
                    if(used[2] != 0){
                            t = max(t, f[used[0]][used[1]][used[2] – 1][used[3]]);
                    }
                    if(used[3] != 0){
                            t = max(t, f[used[0]][used[1]][used[2]][used[3] – 1]);
                    }
                    f[used[0]][used[1]][used[2]][used[3]] = t + map[used[0] + used[1]  2 +  used[2]  3 + used[3] * 4 + 1];
                    return;
            }
            for(i = 0; i <= card[n]; i++){
                    used[n] = i;
                    srch(n + 1);
            }
    }

    int main(void)
    {
            int i, j, k, t;
            int n, m;
    //      freopen("tmp.in", "r", stdin);
            scanf("%d%d", &n, &m);
            for(i = 1; i <= n; i++){
                    scanf("%d", &map[i]);
            }
            for(i = 1; i <= m; i++){
                    scanf("%d", &t);
                    card[t – 1]++;
            }
            srch(0);
            printf("%d\n", f[card[0]][card[1]][card[2]][card[3]]);
    //      getch();
            return 0;
    }

  • Noip 2010 提高组 第一题 机器翻译

    　　纯水题，维护一个列队，作为内存列队，并且写两个操作：进列队、出列队；因为数据量十分的小（n<=1000）所以可以维护一个用于标记的数组，如果单词在列队中则置为1，不在则置为0，接着就是暴力——模拟就是。

    #include <stdio.h>

    int queue[1001];
    int used[1001];
    int tail, head;
    int ans = 0;

    void enqueue(int n)
    {
            ans++;
            queue[tail++] = n;
            used[n] = 1;
    }

    int exqueue(void)
    {
            used[queue[head]] = 0;
            return queue[head++];
    }

    int main(void)
    {
            int i, j;
            int m, n;
            scanf("%d%d", &m, &n);
            for(i = 0; i < n && tail – head != m; i++){
                    scanf("%d", &j);
                    if(!used[j]){
                            enqueue(j);
                    }
            }
            while(i < n){
                    scanf("%d", &j);
                    if(!used[j]){
                            exqueue();
                            enqueue(j);
                    }
                    i++;
            }
            printf("%d\n", ans);
            return 0;
    }

  • 素数统计

    　　这几天围着素数统计这一题就把我搞蒙了.. 题目是这样的: 输入一个整数n, 输出小于等于n的素数个数..
    　　刚开始, 觉得题目挺容易的,, 马上写了一个程序出来, 测试了一下, 结果没错.. 急急忙忙的就提交了,, 后来再把题目仔细看了看,, n的范围是1~二百万.. 时间要求时1s. 我自信的敲入了两百万.. 结果十分钟才把结果蹦出来… 我这么没用啊,,, 时间要求1s,, 我这里是10*60s…
    　　忽然看到内存的限制,, 这题是128M, 别的题目都是32M.. 我就想怎么利用这些内存呢~? 蠢主意马上出来了, 把1到两百万之间所有的素数都放在一个数组里,, 不就得了..然后再循环比较程序的效率不需要1毫秒就可以执行完的~! 马上行动. 用刚刚的程序生成了一个数组. 然后加几行代码.. KO了~!
    　　哈哈,, 感觉有点自豪, 但是毕竟没用到任何算法所以又感觉不怎么滴的.
    　　后来看到一幅图: 

  • 二进制表示方式

    　　以前学C, 反码补码就是不知道什么意思, 今天看了汇编的书才搞懂` 　　首先呢, 说一下现在不怎么用的一点东西, 在以前有符号的数字有三种表示方法, 一种是比较常见的, 把第一位作为符号位(最高位), 然后如果第一位是0的话, 代表正数, 1的话代表负数. 我先举个例子啊,, 比如 -1的表示方法是(以8位数字为例.) 10000001 这就是-1的表示方法, 第一个1就是符号位. 这种表示方法有一个致命的缺点, 有两种方法可以表示0(00000000, 10000000), 你可以分别叫他们正零和负零(+0, -0), 这种表示在编程的过程中会很难处理 　　好, 继续说第二种表示方法,, 那就是反码, 我觉得这个根本没必要说明的, 还是说一下吧, 毕竟是历史产物, 而且跟第三种, 也就是现在最常用的一种二进制表示方式有关系.. 反码, 顾名思义, 就和它的名字一样..反''''码嘛 就是反过来, 还是用-1的表示方式来做说明.. -1 前面说了, 在以前的表示方法中, 它的二进制是: 10000001 反码就是 01111110.. 这就是反码, 聪明的人肯定看出来了, (你没看出来也不一定说明你是蠢咯, 但是不认真是肯定的) .一样的有两种对0的表示方法..
    所以就出现了第三种表示方法, 补码. 补码是现在最常用的一种表示方法, 它通过使用简单的技巧使用正数来表示负数, 解决了第一种和第二中表示方法的运算问题 依然拿-1开刀(别怪我啊, -1, 谁叫是你负数中最大的整数呢?), 正1在二进制中的表示方法是:00000001, 然后首先反码 : 11111110(这是1的反码, 不是-1的, 别弄错了, 就是因为这个东西, 我以前就没搞懂,,,), 接着就是要在反码上加一 也就是 11111111. 这就是在补码的表示方法中-1的二进制.. 然后大家在考虑一下0的二进制表示方法(-1啊, 我用你兄弟开刀了, 开心点了吧?), 它在二进制中的表示方法是00000000, 这里没有什么+0和-0了, 前面说了是使用正数来表示负数, 没有说0, 因为在补码中00000000的反码是11111111, 然后+1就是00000000了.
    然后小提一下, 其实补码也可以用负数来表示正数, 比如 -1的二进制是 11111111(上面说了的), 首先反码00000000, 接着加一, 就是00000001了`
    还有一个问题,原来的-0去哪里了? 原来-0的二进制是怎么表示的? 1000000 对吧, 看样子这个数是个负数, 但是就像前面所说的, 0只有一个 那这个是什么呢? printf("%d", 0x80); 输出看看吧 就是这个原因, 所以有符号8位数能够表示-128~127 之间的数

    　　哎呀, 写着玩意儿累死我了, 大家如果有收获的话, 不留言就对不起我了, 更对不起被开了几次刀的-1了如果是没有看懂的话, 更加要留言, 因为我自己看书, 脑子里的问题一大堆, 因为书上介绍的不够详细, 细节没有说明, 我怕我这里还有没有说明的细节, 所以请大家把问题也指出来! 一是帮助以后会看这篇文章的人, 更加是帮了我自己` (^__^) 嘻嘻……..

    　　顺便给大家推荐一个工具, WIndows 自带的计算器, 在查看菜单下选择"科学型" 这个计算器挺好用的, 很方便, 在转换进制之间很灵活 大家试着尝试一下`

  • 算法: 求最长的回文字符串

    　　最近USACO写到了(第三次)1.3.3，这一题我用的是我自己原创的一个算法（可能也有别人想到了，但是对于我来说，确实是我自己独立思考出来的），在此发表一下。
    　　程序：输入：一行字符串，输出：最长的回文字符的长度以及把它们给输出来。
    　　如：
    　　　　输入：1596156432111234
    　　　　输出：6
    　　　　432111234

    　　回文的性质

    　　首先先把题目撇开，单说回文数的性质，如abcba是一个长度为5的回文数，那它有什么性质呢？
    　　回文数顾名思义，就是从左念和从右念是相同的，也可以说从左遍历和从右遍历是相同的，这些都是废话。因为它是回文数所以可以同时从左和右开始遍历，各个字符都是相同的。
    　　其实上面那些性质也没什么用，算是铺垫吧，接下来的才是重点，那怎么样去构成一个回文数呢？就用abcba做例子吧，这个回文数的构成是由单个字符c两边同时放置b，构成的bcb再两边同时放置一个a构成的。

    　　回文的判定

    　　那么假设要你判断abcba是不是有两种方法，但是我要说的不是两边同时开始遍历并且判断的方法，再用abcbad做例子吧，用程序判断它是不是一个回文数，我先把过程写出来，然后再把方式写出来。
    下面把回文数和回文混用。
    　　首先下标i=0…5，s[i]代表第i个字符。i从1开始递归，因为第一个字符不存在回文数，i=1时，当前回文长度为1，就是单个字符a。当前回文数长度是我自己定义的名词，就是说以i结尾的回文数的长度。然后i = 2时，当前回文数是单个字符c，长度为1；i=3时，这里需要注意一下了，从这里开始就有一些变化了，当前回文数的长度为3，为bcb，i=4时，当前回文数的长度为5，为abcba，接着i=5，当前回文长度为1，是单个字符d，这样它就不是一个回文数。

    　　当前回文数长度

    　　那么求当前回文数的长度(不是标准的语言)：
    　　i = 1
    　　while(i 3321吧，当i = 3时(123321)，start[i] = 2(123321) len[i] = 2；当i = 5时(123321)，start[i] = 0(123321)，len[i] = 6，也就是说当前回文数的取决于三种情况：
    　　第一种：start[i – 1]的前面一个字符等于i时，当前回文就是(start[i – 1] – 1) ~ i，长度就是len[i – 1] + 2。
    　　第二种：s[i – 1]等于s[i]，就是说两个相邻的字符相等的话，那么start[i] = i – 1;len[i] = 2。
    　　第三种：什么都不是，就是单个字符回文,start[i] = i, len[i] = 1。
    　　其实仔细想想可以把len[]这个数组去掉，因为len[i] = i – start[i] + 1;
    　　但是，因为这篇文章时根据USACO那题写的，那个题目的s中包含空格和标点符号，但是又把它们记入len[]中，所以这个代码只是一个模式，遇到不同的题目要有不同的待遇，但是这种思想我觉得很重要/神奇，类似于DP但又不是。

    　　解题

    　　那么上面的题目就好解了（只给出大致代码）：
    　　i = 1, ans = 0
    　　while(i < n){
    　　　　if(s[start[i – 1] – 1] == s[i]){
    　　　　　　start[i] = start[i – 1] – 1;
    　　　　　　len[i] = len[i – 1] + 2;
    　　　　}else if(s[i – 1] == s[i]){
    　　　　　　start[i] = i – 1;
    　　　　　　len[i] = 2;
    　　　　}else{
    　　　　　　start[i] = i;
    　　　　　　len[i] = 1;
    　　　　}
    　　　　if(ans < len[i]){
    　　　　　　ans = len[i];
    　　　　　　k = i;
    　　　　}
    　　}
    　　printf("%d\n", ans);
    　　for(i = start[k]; i <= k; i++){
    　　　　printf("%c", s[i]);
    　　}
    　　自己发明的算法，文本上没有什么可以参考的蓝本，写得不好请见谅。

  • Noip 2010之旅(下)

    　　昨晚上让柜台6:30把我们闹醒，结果7点钟他们才打电话来，真是懒，幸好我起来的早，6点半不到就醒了，不然考试不就错过了。
    　　早早地来到考场，虽然离考试还有一段时间，但是已经有非常多的人 在哪儿等候了，老师也碰到几个熟人，聊着聊着就开考了。
    　　哇，这种考试就是不一样，真大啊～宽敞的机房，虽然昨天来看过了，但是身在庐山中和不在完全不同呢！半个小时的试机时间里大家都在打代码，我却不知道要干什么，写了个Hello World就去玩扫雷去了，到半个小时快结束的时候才发现我可以把一些常用的算法写出来。

    　　桌面上有一个压缩文件里面是题目，但是被加密了，伴随着铃声密码给我们了，我很快地扫过第一题，发现很简单，大概半个小时不到就写完了，第二题感觉也很简单，但是花了好一阵子，一看时间，发现9：30了，只有1.5小时了！！心里马上就急了，但很快就知道是8：30开始考试的。。。。第三题和第四题也都想到算法了，对于NOIP的题目能够全部全部写出来对我来说就是一个挑战！！这回战胜自己了，哈哈哈哈。

    　　接下来就是等成绩了，吃完饭又回到理工学院，到处逛了下，想去图书馆，被学生卡挡住了，没有学生卡不能进入，在考场附近的一个草坪上看到一个人正在贴横条“当音乐和桌游碰撞”，有好多人在那里，我们也在那里休息了一下午（4～5个小时等成绩。），老师很快就和周公约会去了，我看他们弹吉他，玩桌游看了好久，那里有一个关于狼人的桌游感觉挺好玩的，好想玩～

    　　后来到了五点钟，在那里成绩还是没有出来，预计的时间总是不准，到了六点多才出来，雅礼有6个满分！！！我210分落幕这届NOIP。

    　　其实还有很多细节，但是这两天的细节太多了，不想写，，就这样潦潦草草的流水帐下吧。

  • 细胞核和病毒

    　　现在高中学到，没有细胞核的变形虫不能够进行新城代谢，以及细胞正常的活动和不能对对外界的刺激做出反应，但是当细胞核移植回去时一切生命活动又全部都恢复了，我觉得这个实验不仅说明细胞核对细胞的一系列的关系，也可能说明这“生命离不开细胞”这句话可能可以写成“生命离不开细胞核”，虽然我马上就推翻了自己这个说法：细菌没有细胞核，只有裸露的DNA，而且又是能够独立生活的生物；但是注意我的说法，“是能够独立生活的生物”，因为病毒是寄生在活细胞内的。