新零点

分类： 技术

  • 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。

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

  • Noip 2010 题解

    第一题——机器翻译

  • Noip 2010之旅(上)

    　　学校第37届运动会闭幕式刚结束, 李智老师就准备带着我去长沙了. 他先带我去和别的老师一起吃了一餐饭, 然后就出发了!

    　　好久没来火车站了, 发现这里比以前要好很多了, 以前我爸带我到这里, 跟我说以前是怎么逃票的, 后来好像本来是要带我逃票的吧, 好像是我良心过不去, 所以就没了, 不太记得了, 反正现在进去就要先查票, 然后把行李放到那个检查的地方, 然后用测电子仪器的东西"搜身", 检查身份证. 搜身的时候她还问了我一句, 你是学生啊? 去干吗? 你看有多么的严谨了!

    　　岳阳走的时候老师碰到了一个熟人, 也是去长沙的..到了长沙在动车旁边照了相. 一出火车站老师把他带的药给他爸爸(老师顺便带了点药给她母亲, 他父亲过来拿.)一的士冲到雅礼, 梦寐以求好久了, 不过我还是在四中待着吧,  一个头发几乎没有的女的给我们签到, 我好害怕, 生怕以后和她一样, 这么恐怖..

    　　后来一辆702到了长沙理工学院, 坐了1个多小时的车~~~ (后来发现到了这里是长沙县).

    　　理工学院好大啊~ 像个小城是一样的, 在门口有校内的公交车, 一个半敞棚, 透明的车, 司机坐在上面等乘客, 从入口处到我考试的场所, 走了十几二十分钟的路, 而且这才是门口的地图上的一小根横线. 在校外, 我看到学校的栏杆从侧面看好整齐, 好杀气, 有一种威武的感觉, 想在它前面照一张, 老师没照, 就算了~~(可惜中..)

    　　到了我考试的机房, 好大啊~ 一个教室一个教室都是机房, 透明的窗户, 里面的电脑看的清清楚楚, 一排排液晶电脑, 真想冲上去玩下啊….

    　　看完机房后, 就找位置住, 找了好久好久~~ 第一家没有双人房, 说要我们去隔壁, 结果他喊另外一个人带我们去那家去看, 不过没电了,她说这一篇都没有, 就到这里住啦, 老师没理她.

    　　找了好久, 都没有电, 大部分也都没有双人间, 最后运气好, 发现那里还有一个商务宾馆, 虽然没有双人间, 但住在一个好大的单人间! 有台电脑, 简单的复习了一下, 看了下电视就睡了..

  • Noip 2005 篝火晚会

    　　纠结了不知道好久，最后发现题目的意思理解错了(b1, b2, ….., bm)这些b是任意选择的, 也就是说可以选择(1, 5, 7)之类的。那么把题目理解正确了就好说了，输出的就是没有站好的人数（就是位置站错了的），所以就很简单了。
    　　首先一个初始列队，一个目标列队（即每个人理想的左右的人。）如果无法实现那么输出-1，不然的话就开始判断在正确位置上的人的个数，然后再用n-这个个数(要最大)。
    　　代码如下：

    #include <stdio.h>
    #include
    <stdlib.h>
    int left[50000],
    right[50000], p[50000];
    int hash[50000], bits[50000];
    int n;

    void output(int k)
    {
            printf("%d\n",
    k);
            getch();
            exit(0);
    }

    void init(void)
    {
            int i, j;
            scanf("%d",
    &n);
            for(i = 0; i < n; i++){
                    scanf("%d%d", &left[i],
    &right[i]);
                    left[i]–,
    right[i]–;
            }

            j = 0;
            for(i =
    0; i < n; i++){
                    p[i] =
    j;
                    if(bits[left[j]]){
                            j =
    right[j];
                    }else{
                            j =
    left[j];
                    }
                    if(bits[j]){
                            output(-1);
                    }
                    bits[j] = 1;
            }
    }

    #define
    loop(j)     do{\
            for(i = 0; i < n; i++){\
                    if(p[j] >= i){\
                            hash[p[j] – i]++;\
                    }else{\
                            hash[p[j] – i + n]++;\
                    }\
            }\
            for(i = 0; i < n; i++){\
                    if(hash[i] > max){\
                            max = hash[i];\
                    }\
            }\
    }while(0)

    int main(void)
    {
            int i, max = 0;
            init();
            loop(i);
            memset(hash,
    0, sizeof(hash));
            loop(n – i – 1);
            output(n – max);
    }

  • tvyj 1006 isbn

    　　对我面向对象的能力越来越喜欢了，对于抽离函数的能力，自认为已经算是比较强大的了！当然，还远远不够咯，但是这一切都是慢慢来的，发现我挺喜欢面向对象的，但是我又不喜欢C++，哈哈，题外话不说了。
    　　这一题其实比较简单，估计也没几个不能AC的，但是我就提交了两次，因为当不输出Right的时候我没把isbn输出，而只输出了最后的尾数。
    #include <stdio.h>
    int ans = 0;
    /
    Mistack 2:
    　　当不输出Right时要输出的是完整的isbn号, 而不是单单尾数. 
    /
    char str[14];
    int now;

    /
    Mistack 1:
    　　下面的函数应该是读取n个数, 但是从主函数是独立出来的时候忘记修改循环次数为n而不是3了 
    /
    void deal(int n)
    {
            static int count = 1;
            int i, c;
            for(i = 1; i <= n; i++, now++){
                    c = str[now] – ‘0’;
                    ans += c * (count++);
            }
            now++;
    }

    int main(void)
    {
            int c;
            scanf("%s", &str);
            deal(1), deal(3), deal(5);
            ans %= 11;
            c = str[now];
            if(c == ‘X’){
                    c = 10;
            }else{
                    c -= ‘0’;
            }
            if(c != ans){
                    str[now] = ‘\0’;
                    printf("%s", str);
                    if(ans == 10){
                            printf("X\n");
                    }else{
                            printf("%d\n", ans);
                    }
            }else{
                    printf("Right\n");
            }
            return 0;
    }