新零点

分类： 技术

  • USACO 2.2.3 Runaround Numbers 解题报告

    这题首先是一个枚举，从输入的数加一开始每个数字都看是不是题目所要的数。判断方法如下： 先把数字用字符串保存起来，然后读取一个数字并且标记为’x’，再读取一个，判断是否为’x’，如果为x就不是要求的数字，如果不是就继续读取，直到每个数字都被读取了，并且最后指针回到了第一个位置，那么这就是所需要的那个数字。因该说清楚了吧，简单的说就是模拟一边，代码如下： de lang="c"> / LANG: C ID: yylogoo1 PROG: runround / #include #include int check(int n) { int len, i, j, t; int used[10]; char num[10]; memset(used, 0, sizeof(used)); sprintf(num, "%d", n); len = strlen(num); for(i = 0; i

  • USACO 2.2.2 Subset Sums 解题报告

    这一题是一个动态规划题，f[i][j]是i个数字（1, 2, 3, 4, .., i）能够组成和为i的个数，那么方程式是f[i][j] = {f[i – 1][j – k] + f[i – 1][j]} (1 <= k <= i)，再DP就是的，代码如下： / LANG: C ID: yylogoo1 PROG: subset / #include long long f[781]; int main(void) { int n, i, j, k; int max = 0; freopen("subset.in", "r", stdin); freopen("subset.out", "w", stdout); scanf("%d", &n); if(((n + 1) n / 2) & 1){ printf("0\n"); return 0; } f[0] = 1; for(i = 1; i = i; j--){ f[j] += f[j - i]; } } printf("%ld\n", f[(n + 1) n / 4] / 2); return 0; }

  • USACO 2.2.1 Preface Numbering 解题报告

    这题一开始确实会感觉很难，但是罗马数字的个位只有可能是{"I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"}，同理，十位上的数字也永远都是固定的，所以还是简单吧，实现代码如下： / LANG: C ID: yylogoo1 PROG: preface / #include char num[4][10][5] = { {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"}, {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"}, {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"}, {"", "M", "MM", "MMM"}}; int have[7]; void addnum(int n) { int i = 0; char s; while(n){ s = num[i][n % 10]; while(s != '\0'){ switch(*s){ case 'I': have[0]++; break; case 'V': have[1]++; break; case 'X': have[2]++; break; case 'L': have[3]++; break; case 'C': have[4]++; break; case 'D': have[5]++; break; case 'M': have[6]++; break; } s++; } i++; n /= 10; } } char st[7] = {'I', 'V', 'X', 'L', 'C', 'D', 'M'}; int main(void) { int n; int i; freopen("preface.in", "r", stdin); freopen("preface.out", "w", stdout); scanf("%d", &n); for(i = 1; i 0){ printf("%c %d\n", st[i], have[i]); } } return 0; }

  • USACO 2.1.5 Hamming Codes 解题报告

    这题的话，话说感觉就是一个暴力的枚举，没多余要考虑的，一方面对所有整数开始枚举，设当前枚举的是i，那么在用i和所有已知的海明码进行比较，海明距离大于等于D的话就成为一个新的海明码，一直枚举出N个海明码。 得出海明距离也很简单，就从第一个位开始，一个不同的就记录一下，我直接把8位都枚举一次，所以B这个数据对我却是没有用，代码如下： de lang="c">/ LANG: C ID: yylogoo1 PROG: hamming / #include int num[64]; int count = 0; int ham(int a, int b) { int c = 0 ; int i; for(i = 0; i <8 i ifa="(b" c a><= 1, b <<= 1; } return c; } int main(void) { int n, b, d; int i, j; freopen("hamming.in", "r", stdin); freopen("hamming.out", "w", stdout); scanf("%d%d%d", &n, &b, &d); for(i = 0; count != n; i++){ for(j = 0; j de>

  • USACO 2.1.4 Healthy Holsteins 解题报告

    咋一看，真是一个爆难的题目，但是仔细一想，其实也很简单，怎么个简单呢？对于每种食物来说，只有两种选择：吃或不吃，对吧，暴力枚举就是，只有2^15种方案，虽然数字还是非常大的，但是一秒钟的时限还是超不了，代码晚点发，在Linux下。 代码来了： / ID: yylogoo1 PROG: holstein LANG: C / #include #include int have[15][25]; int need[25]; int v, g; int got[25]; int used[15], ans[15]; int tot = 26, tmp; void check(void) { int i; if(tot tmp){ tot = tmp; memcpy(ans, used, sizeof(used)); }else if(tot == tmp){ for(i = 0; i ans[i]){ tot = tmp; memcpy(ans, used, sizeof(used)); return; }else if(used[i] <ans i return void srchint now int i check ifnow="= g){" return srchnow tmp usednow="1;" fori="0;" i v i goti="have[now][i];" srchnow tmp-- usednow="0;" fori="0;" i v i goti -="have[now][i];" int mainvoid int i j freopenholsteinin r stdin freopenholsteinout w stdout scanfd v fori="0;" i v i scanfd needi scanfd g fori="0;" i g i forj="0;" j v j scanfd haveij srch printfd tot fori="0;" i g i ifansi printf d i printfn return code>

  • USACO 2.1.3 Sorting A Three-Valued Sequence 解题报告

    首先用两个数组分别保存排了序的数组和没排序的数组，然后再根据这两个判断，当前这个位置上应该是放什么数，而实际上放的是什么数，如果两个位置上需要的都正好是对方所有的，那么这是最好的，进行循环，把所有这种的都交换掉，然后累计交换次数。 但是最后会有这么一种情况，三个位置需要的分别是1, 2, 3，而他们有的分别是3, 1, 2，这时就要交换两次了，而且仔细考虑的话会发现当前面循环完了之后，就只可能剩下这么一种情况了，当然，对数可能不止一对，所以就累计需要的和拥有的不相同的那些，统计起来，处以三再除以二，就是交换次数，结果就出来了。 代码如下： / ID: yylogoo1 PROG: sort3 LANG: C / #include int n; int have[1000]; int need[1000]; int com(void const a, void const b) { return (int )a - (int )b; } int ans; int main(void) { int i, j; freopen("sort3.in", "r", stdin); freopen("sort3.out", "w", stdout); scanf("%d", &n); for(i = 0; i

  • USACO 2.1.2 Ordered Fractions 解题报告

    这题我的方法就是下面这个，不然的话就要爆搜，这个规律不知道平时用的上不，但现在这会儿挺好用： 

    0/1                                                              1/1                                1/2                   1/3                      2/3         1/4              2/5         3/5                 3/4     1/5      2/7     3/8    3/7   4/7   5/8       5/7         4/5

    利用这个规律可以非常快的解决，不过至于为什么你们自己想去吧（我也没想通，反正能用的规律就OK了，AC就是王道。） 代码晚一点发上来，在Linux那台电脑里。

    2010 年 12 月 28 日 12:14:36

    我的那个Fedora坏了，又忘记备份/home了，又全部更新了硬盘的文件系统，代码就被。。。就用标称算了，反正是一样的。 

    #include  #include  #include  #include    int n; FILE fout;   / print the fractions of denominator  n) / cut off recursion /   return;    genfrac(n1,d1, n1+n2,d1+d2);  fprintf(fout, "%d/%d\n", n1+n2, d1+d2);  genfrac(n1+n2,d1+d2, n2,d2); }   void main(void) {  FILE *fin;    fin = fopen("frac1.in", "r");  fout = fopen("frac1.out", "w");  assert(fin != NULL && fout != NULL);    fscanf(fin, "%d", &n);    fprintf(fout, "0/1\n");  genfrac(0,1, 1,1);  fprintf(fout, "1/1\n"); }

  • USACO 2.1.1The Castle 结题报告

    第二章第一题，难度不是很大，算法也比较简单。

  • 快速排序

    第一节 快速排序

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