新零点

分类： OI路程

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

  • USACO 1.5.2 Prime Palindromes

    　　这一题我用的依然是以前的解法，现只求回文数，而且偶数回文数不需要求（如：312213）必定是11的倍数但是11要特殊处理，反正这一次我错了不少地方。
    　　1，把变量名写错了，上面分明是给a赋值，下面却写成了对b进行操作。

    　　2，对于回文数的制造的下标弄错了（不好细说，看代码里的注释和上下文把。）
    　　3，循环的范围错误，也是制造回文的错误！
    　　4，字符串的结尾忘记’\0’了。
    　　5，搜索的范围错误！！
    　　一次AC，代码如下：
    /
    LANG: C
    ID: yylogoo2
    PROG: pprime
    /
    #include <math.h>
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    int a, b;

    int isprime(int num)
    {
            int i, li;
            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++){
                    if(num % i == 0){
                            return 0;
                    }
            }
            return 1;
    }

    void check(int num)
    {
            if(num > b){
                    exit(0);
            }
            if(num < a){
                    return ;
            }
            if(isprime(num)){
                    printf("%d\n", num);
            }
    }

    char tmp[9];

    int makenum(int num)
    {
            int i, j;
            sprintf(tmp, "%d", num);
            i = j = strlen(tmp);
            /
            Mistack 2:
            　　i的初始值错误!
                /
            i -= 2;
            /
            Mistack 3:
            　　范围错误了,, 应该是i >= 0, 不是i != 0
                /
            while(i >= 0){
                    tmp[j] = tmp[i];
                    i–, j++;
            }
            /
            Mistack 4:
            　　字符串没有以’\0’结尾
                /
            tmp[j] = ‘\0’;
            sscanf(tmp, "%d", &num);
            return num;
    }

    void srch(int i, int j)
    {
            int num;
            while(i <= j){
                    num = makenum(i);
                    /
                    Mistack 1:
                    　　把下面的参数num写成了i, 所以导致错误!
                        /
                    check(num);
                    i++;
            }
    }

    int main(void)
    {
            int i;
            freopen("pprime.in", "r", stdin);
            freopen("pprime.out", "w", stdout);
            scanf("%d%d", &a, &b);
            check(5);
            check(7);
            check(11);
            /
            Mistack 5:
            　　应该是从10开始, 而不是100
                /
            srch(10, 9999);
            return 0;
    }

  • USACO 1.5.1 Number Triangles

    　　明显是一个动态规划，有两种思路，一种是至上而下的，一种是至下而上的，让我联想到了几个大国家的革命和改革，我支持改革，革命总是要留下一些历史痕迹，漏洞，所以我选择的是至下而上的改革。至下而上的DP有什么好处呢？好处多了，因为没有任何特殊情况要考虑，如果是至上而下的DP的话，首先有特殊情况，对于每一个内层循环的值等于外层的值的话，但是这个处理得好的话还是可以做到不要多余的if来判断i是否等于j，在输出答案时不需要遍历底层，在这里的代码我犯了一个小错误导致我的代码丢了最后一个点。
    　　犯的错误：数组的下标使用错误了，在极限值（1000）时会溢出！
    　　提交了两次，代码如下：

    /
    LANG: C
    ID: yylogoo2
    PROG: numtri
    /
    #include <stdio.h>
    #define max(a, b) ((a)>(b)?(a):(b))
    int f[1000][1000];
    int n;

    int main(void)
    {
            int i, j;
            freopen("numtri.in", "r", stdin);
            freopen("numtri.out", "w", stdout);
            scanf("%d", &n);
            for(i = 0; i < n; i++){
                    for(j = 0; j <= i; j++){
                            scanf("%d", &f[i][j]);
                    }
            }
            /
            Mistack 1:
            　　下面的i我写的是i–, 因为前面的代码. 但是删掉之后忘记修改这里了,
            i要从n – 2开始枚举..
                /
            for(i = n – 2; i >= 0; i–){
                    for(j = 0; j <= i; j++){
                            f[i][j] += max(f[i + 1][j], f[i + 1][j + 1]);
                    }
            }
            printf("%d\n", f[0][0]);
            return 0;
    }