新零点

分类： 算法

  • 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;
    }

  • tyvj 1005 采药

    　　01背包的例子，不过第一次写的时候不小心把01背包写成了无限背包，代码如下：

    #include <stdio.h>
    #define max(a, b) ((a)>(b)?(a):(b))
    int f[1001];

    int main(void)
    {
            int i, j;
            int t, m;
            int a, b;
            scanf("%d%d", &t, &m);
            for(i = 0; i < m; i++){
                    scanf("%d%d", &a, &b);
                    /
                    Mistack 1:
                    　　把01背包写成了无限背包 
                        /
    /              for(j = a; j <= t; j++){
                            f[j] = max(f[j], f[j – a] + b);
                    }    /
                    for(j = t; j >= a; j–){
                            f[j] = max(f[j], f[j – a] + b);
                    }
            }
            printf("%d\n", f[t]);
            return 0;
    }

  • tyvj 1004 滑雪

    　　上午写了一次(http://zqynux.blog.163.com/blog/static/1674995972010101325737526/)，只有70分，剩下的我也知道为什么错了，所以我的思路是不行的，但是我就想不到另外的方法了，到群里问了下，别人把代码发给我看了,, 汗, 好简单, 纯DP, 没有任何杂念, 我原本以为要排序, 但NOIP的题目似乎涉及不到这么高深的算法, 矩阵+排序+搜索, 就觉得我是想复杂了, 他这个代码太简单了…
    　　但是几乎是纯递归,我以为会爆掉(栈溢出), 结果用最最最大的可能用尽栈的数据测试, 结果没溢出, 后来测试发现,, 栈一般还是够用.. 
    　　但是我犯了一个很严重的错误, 记忆DP竟然没有给它记忆,, 所以导致最后一个数据超时了,,代码如下:

    #include <stdio.h>
    int map[100][100];
    int dis[100][100];
    int r, c;

    int check(int a,
    int b)
    {
            if(a < 0 || a >= r
    || b < 0 || b >= c){
                    return 0;
            }
            return 1;
    }

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

    #define deal(i, j) do{\
            if(check(i, j) && map[i][j] >
    map[a][b]){\
                    t = max(srch(i, j),
    t);\
            }\
    }while(0)

    int srch(int a, int b)
    {
            int t = 0;
            if(dis[a][b] != 0){
                    return dis[a][b];
            }
            deal(a +
    1, b);
            deal(a – 1, b);
            deal(a, b + 1);
            deal(a, b – 1);
            /
            Mistack 1:
            　　真是….不好怎么评价自己了,, 记忆DP, 我竟然忘记记忆了..
                /
            dis[a][b]
    = t + 1;
            return dis[a][b];
    }

    int main(void)
    {
            int ans = 1;
            int i, j,
    t;
            scanf("%d%d", &r,
    &c);
            for(i = 0; i < r; i++){
                    for(j = 0; j < c;
    j++){
                            scanf("%d",
    &map[i][j]);
                    }
            }
            for(i = 0; i < r;
    i++){
                    for(j = 0; j < c; j++){
                            t = srch(i,
    j);
                            if(ans <
    t){
                                    ans =
    t;
                            }
                    }
            }
            printf("%d\n", ans);
            return 0;
    }

  • [未AC]tyvj 1004 滑雪

    　　以前看过这题，没看懂，现在是看懂了，就是在这里面找一个最长的递减（递增）序列，我的思路是，从最小的值开始向四周搜索，把每一个比它大的都算是一条路径，结果，很遗憾提交了4次也只70分，现在发现是思路不行，比如最小的0周围都是最大的数字，那么我的程序直接输出2，但是正确答案却不是1，代码先贴上：
    　　AC的解答看这里:http://zqynux.blog.163.com/blog/static/16749959720101013105738935/

  • tyvj 1003 越野跑

    　　咋一看去感觉是一个很复杂的题目，不过仔细一想，可以以最坏时间O(n)来完成，因为来回一趟的路线是固定的——去一次，回一次，如果是平地的话需要的时间总量就是2f, 无论是上坡还是下坡, 来去一趟的时间都是u+d，所以就没什么考虑的了，输入一个就把要花的时间加上，判断下是否大于u，是就退出循环，不是就继续循环。。
    　　代码如下：

  • NOIP 2003 神经网络 解体报告

    　　其实这个题目很简单, 你们仔细想想,最像什么? 很多讨论图论第一个讨论得就是这个问题——拓扑排序, 不是吗? 几乎不用我提示了吧? 这里还有一个要注意的地方就是, 一个神经输入节点的u[i] > 0时也不回影响c[i]. 比如c[i] = 2, u[i]=100, 那么这个输入节点的c[i] 依然是2而不是-98。
    　　要说得救是这些, 代码如下:

    #include <stdio.h>
    #include <assert.h>
    #define MAX 200
    int c[200], u[200];

    int queue[MAX];
    int head, rear;

    void enqueue(int k)
    {
            queue[rear++] = k;
    }

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

    int map[200][200];
    int link[200][200];
    int in[200], out[200];

    void add(int a, int b, int d)
    {
            link[a][out[a]] = b;
            map[a][out[a]] = d;
            out[a]++, in[b]++;
    }

    int main(void)
    {
            int a, b, d;
            int n, p;
            int i, j;
            scanf("%d%d", &n, &p);
            for(i = 0; i < n; i++){
                    scanf("%d%d", &c[i], &u[i]);
                    /
                    Mistack 1:
                        把下面的c[i] > 0 写成了c[i] == 0
                        /
                    if(c[i] > 0){
                            enqueue(i);
                    }
                    /
                    Mistack 3:
                        作为输入神经, 无论u为多少, c都应该是固定的!
                        /
                    if(c[i] == 0){
                            c[i] -= u[i];
                    }
            }
            for(i = 0; i < p; i++){
                    scanf("%d%d%d", &a, &b, &d);
                    a–, b–;
                    add(a, b, d);
            }

            while(head != rear){
                    a = exqueue();
                    if(c[a] > 0){
                            for(i = 0; i < out[a]; i++){
                                    b = link[a][i];
                                    c[b] += map[a][i] c[a];
                                    in[b]–;
                                    assert(in[b] >= 0);
                                    if(in[b] == 0){
                                            enqueue(b);
                                    }
                            }
                    }
            }
            /
            Mistack 2:
            　　当都为0时要输出NULL
            */
            d = 1;
            for(i = 0; i < n; i++){
                    if(out[i] == 0 && c[i] > 0){
                            printf("%d %d\n", i + 1, c[i]);
                            d = 0;
                    }
            }
            if(d){
                    printf("NULL\n");
            }
            return 0;
    }

  • USACO 1.5.3 SuperPrime Rib

    　　这一题刚开始我是打算把所有的数都遍历一次，如当n=4时，就把1000~9999全部遍历，然后以此判断，但很快发现会超时，也可能是想起来以前刷的时候这个方法就是超时的，后来仔细想了一下，需要深搜！前遍历最高位，然后依次到个位，额，文字解释不清楚，用代码解释吧：

    　　问题出现了一些，但是因为是把程序的思路改了一两次，所以我就不好写哪里是错误了：
    /
    LANG: C
    ID: yylogoo2
    PROG: sprime
    /
    #include <math.h>
    #include <stdio.h>
    int n;

    int isprime(int num)
    {
            int i, li;
            if(num == 1){
                    return 0;
            }
            if(num == 2 || num == 3 || num == 5 || num == 7 || num == 11 ||
                            num == 13){
                    return 1;
            }
            if(num % 2 == 0 || num % 3 == 0 || num % 5 == 0 ||
                            num % 7 == 0 || num % 11 == 0 || num % 13 == 0){
                    return 0;
            }
            li = sqrt(num);
            for(i = 17; i <= li; i += 2){
                    if(num % i == 0){
                            return 0;
                    }
            }
            return 1;
    }

    int tmp = 0;

    void srch(int now)
    {
            int i;
            if(now == n){
                    printf("%d\n", tmp);
                    return ;
            }
            tmp *= 10;
            tmp -= 1;
            for(i = 1; i <= 9; i += 2){
                    
                    tmp += 2;
                    if(isprime(tmp)){
                            srch(now + 1);
                    }
            }
            tmp /= 10;
    }

    int count[6] = {2, 3, 5, 7};

    int main(void)
    {
            int i;
            freopen("sprime.in", "r", stdin);
            freopen("sprime.out", "w", stdout);
            scanf("%d", &n);
            for(i = 0; i < 4; i++){
                    tmp = count[i];
                    srch(1);
            }
            return 0;
    }