博客

  • NOIP 1998 普及组 巧妙填数 解题报告

      很简单的一个题目,没一次AC,因为忘记判断0了,有可能出现十位或个位上有零的情况,代码:
    #include <stdio.h>
    #include <string.h>
    int sum;
    int used[10];
    int ck[10];

    int check(int n)
    {
            int t;
            while(n){
                    t = n % 10;
                    if(ck[t] || (t == 0)){
                            //要考虑不能为0的情况 
                            return 0;
                    }
                    ck[t] = 1;
                    n /= 10;
            }
            return 1;
    }

    void srch(int now)
    {
            int i;
            if(now == 3){
                    memset(ck, 0, sizeof(ck));
                    if(check(sum) && check(2  sum) && check(3  sum)){
                            printf("%d %d %d\n", sum, 2  sum, 3  sum);
                    }
                    return;
            }
            sum = ((sum << 3) + (sum << 1));
            //sum *= 10;
            for(i = 1; i <= 9; i++){
                    sum += i;
                    srch(now + 1);
                    sum -= i;
            }
            sum /= 10;
    }

    int main(void)
    {
            srch(0);
    }

  • Noip 2007 提高组 字符串的展开 解题报告

      麻烦的题目,第一次只拿了30分,代码如下:

    #include <stdio.h>
    char str[101];
    char ans[1500];
    int i, j;
    int a, b, c;
    int spell = 0;

    void init(void)
    {
            scanf("%d%d%d\n", &a, &b, &c);
            if(a == 2){
                    spell = 0x20;
            }
    }

    void put(char c1, char c2)
    {
            int k;
            if(c1 > c2){
                    return;
            }
            if(c == 1){
                    if(a != 3){
                            for(k = 0; k < b; k++){
                                    ans[j++] = c1 – spell;
                            }
                    }else{
                            for(k = 0; k < b; k++){
                                    ans[j++] = ‘‘;
                            }
                    }
                    put(c1 + 1, c2);
            }else{
                    if(a != 3){
                            for(k = 0; k < b; k++){
                                    ans[j++] = c2 – spell;
                            }
                    }else{
                            for(k = 0; k < b; k++){
                                    ans[j++] = ‘
    ‘;
                            }
                    }
                    put(c1, c2 – 1);
            }
    }

    void change(void)
    {
            int k;
            if((str[i – 1] >= str[i + 1]) || 
                    (isalpha(str[i – 1]) && !isalpha(str[i +1])) ||
                    (isdigit(str[i – 1]) && !isdigit(str[i +1]))){
                                    //忘记写!了 
                    ans[j++] = str[i];
                    return ;
            }
            put(str[i – 1] + 1, str[i + 1] – 1);
    }

    int main(void)
    {
            int len;
    //      freopen("abc.txt", "r", stdin);
            init();
            scanf("%s", str);
            len = strlen(str);
            //刚刚忘记给len赋值了. 
            for(i = j = 0; i < len; i++){
                    if(str[i] == ‘-‘){
                            change();
                    }else{
                            ans[j++] = str[i];
                    }
            }
            ans[j] = ‘\0’;
            printf("%s\n", ans);
    //      getch();
            return 0;
    }

      后来认为是要处理整数,就是说比如:10-12展开就是101112,写了好久~!~!~!,还是错了,再一看数据,根本就不用。
      代码如下:
    #include <stdio.h>
    #include <ctype.h>
    #include <string.h>
    char str[101];
    int i, j;
    int a, b, c;
    int spell;

    void init(void)
    {
            scanf("%d%d%d\n", &a, &b, &c);
            if(a == 2){
                    spell = 0x20;
            }
    }

    void putcha(char c1, char c2)
    {
            int k;
            if(c1 > c2){
                    return;
            }
            if(a == 3){
                    for(k = 0; k < b; k++){
                            putchar(‘‘);
                    }
                    putcha(c1 + 1, c2);
                    return;
            }
            if(c == 1){
                    for(k = 0; k < b; k++){
                            putchar(c1 – spell);
                    }
                    putcha(c1 + 1, c2);
            }else{
                    for(k = 0; k < b; k++){
                            putchar(c2 – spell);
                    }
                    putcha(c1, c2 – 1);
            }
    }

    int getcount(int n)
    {
            int m = 0;
            while(n){
                    n /= 10;
                    m++;
            }
            return m;
    }

    void putnum(int c1, int c2)
    {
            int k, r;
            if(a == 3){
                    while(c1 <= c2){
                            r = getcount(c1);
                            for(k = 0; k < r
    b; k++){
                                    putchar(‘‘);
                            }
                            c1++;
                    }
                    return;
            }
            if(c == 1){
                    while(c1 <= c2){
                            r = getcount(c1);
                            for(k = 0; k < b; k++){
                                    printf("%d", c1);
                                    j += r;
                            }
                            c1++;
                    }
            }else{
                    while(c1 <= c2){
                            r = getcount(c2);
                            for(k = 0; k < b; k++){
                                    printf("%d", c2);
                                    j += r;
                            }
                            c2–;
                    }
            }
    }

    void change(void)
    {
            int k;
            if((isalpha(str[i – 1]) && !isalpha(str[i + 1])) && (isdigit(str[i – 1]) && !isdigit(str[i + 1]))){
                                    //忘记写!了 
                    putchar(str[i]);
                    return ;
            }
            if(isalpha(str[i – 1]) && (str[i – 1] < str[i + 1])){
                    putcha(str[i – 1] + 1, str[i + 1] – 1);
            }else if(isdigit(str[i – 1])){
                    int k, r, d;
                    for(d = i – 1; d >= 0 && isdigit(str[d]); d–){
                            ;
                    }
                    sscanf(&str[d + 1], "%d–%d", &k, &r);
                    if(k < r){
                            putnum(k + 1, r – 1);
                    }else{
                            putchar(‘-‘);
                    }
            }else{
                            putchar(‘-‘);
            }
    }

    int main(void)
    {
            int len;
            init();
            scanf("%s", str);
            len = strlen(str);
            //刚刚忘记给len赋值了. 
            for(i = j = 0; i < len; i++){
                    if(str[i] == ‘-‘){
                            change();
                    }else{
                            putchar(str[i]);
                    }
            }
            printf("\n");
            return 0;
    }
      正确代码还在撰写中。。。
      辛辛苦苦修改了一次,还只有70分,这个代码就不发上来了吧。
      根据数据修改了好几次,第一次没考虑到–的情况,第二次忘记考虑当a=2而转换数字时的情况。
      代码如下:
    #include <stdio.h>
    #include <ctype.h>
    #include <string.h>
    char str[101];
    int i;
    int a, b, c;
    int spell;

    void init(void)
    {
            scanf("%d%d%d\n", &a, &b, &c);
            if(a == 2){
                    spell = 0x20;
            }
    }

    void output(char c1, char c2)
    {
            int k;
            if(a == 3){
                    while(c1 <= c2){
                            for(k = 0; k < b; k++){
                                    putchar(‘
    ‘);
                            }
                            c1++;
                    }
                    return ;
            }
            if(isdigit(c1)){
                    //要考虑数字但是a=2的情况 
                    while(c1 <= c2){
                            for(k = 0; k < b; k++){
                                    putchar(c1);
                            }
                            c1++;
                    }
            }else if(c == 1){
                    while(c1 <= c2){
                            for(k = 0; k < b; k++){
                                    putchar(c1 – spell);
                            }
                            c1++;
                    }
            }else{
                    while(c1 <= c2){
                            for(k = 0; k < b; k++){
                                    putchar(c2 – spell);
                            }
                            c2–;
                    }
            }
    }

    void change(void)
    {
            int k;
            if((i == 0) || (str[i – 1] >= str[i + 1])){
                    putchar(‘-‘);
                    return;
            }
            if((isdigit(str[i – 1]) && isdigit(str[i + 1])) || 
                    (isalpha(str[i – 1]) && isalpha(str[i + 1]))){
                    output(str[i – 1] + 1, str[i + 1] – 1);
            }else{
                    putchar(‘-‘);
            }
    }

    int main(void)
    {
            int len;
            init();
            scanf("%s", str);
            len = strlen(str);
            //刚刚忘记给len赋值了. 
            for(i = 0; i < len; i++){
                    if(str[i] == ‘-‘){
                            change();
                    }else{
                            putchar(str[i]);
                    }
            }
            printf("\n");
            return 0;
    }

  • NOIP 2007 统计数字 解题报告

      这一题我的思路(应该)是O(nlogn)的,就是进行一趟快排加上对数组进行一次扫描。
      快排直接调用库函数,扫描就是用j记录当前自然数,c记录当前自然数出现的次数,如果num[i]和j相同,c++;不同就输出j和c,然后j=num[i], c = 1。在循环结束后还要将最后一个自然数输出。
      下面贴出代码:
    #include <stdio.h>
    int num[200000];

    int com(const void a, const void b)
    {
            return (int )a – (int )b;
    }

    int main(void)
    {
            int n;
            int i, j, c;
            scanf("%d", &n);
            for(i = 0; i < n; i++){
                    scanf("%d", &num[i]);
            }
            qsort(num, n, sizeof(int), com);
            j = num[0];
            //是num[0] 不是num[j] 
            c = 1;
            // c 要从1开始而不是0
            for(i = 1; i < n; i++){
                    if(num[i] != j){
                            printf("%d %d\n", j, c);
                            j = num[i];
                            c = 1;
                            // c 要从1开始而不是0
                    }else{
                            c++;
                    }
            }
            printf("%d %d\n", j, c);
            return 0;
    }

  • NOIP 2008 提高组 双栈排序 解体报告

      这个题目我的思路很简单,就是读入一个数据,判断是否小于s1的顶元素,如果是则讲数据压入s1,否则该数据是否小于s2的顶元素,如果是则将它压入栈s2。然后再判断s1的顶是否等于当前需要输出的值(就是安顺序来是不是对的),如果是就输出b。再同样判断s2,如果是就输出d。
      很可惜,只有30分,代码如下:
    #include <stdio.h>
    int num[1000];
    int s1[1000], s2[1000];
    int t1, t2;
    char ans[2000];
    int len;

    void add(char ch)
    {
            ans[len++] = ch;
    }

    int main(void)
    {
            int n;
            int i, j, r, t;
            scanf("%d", &n);
            for(i = 0; i < n; i++){
                    scanf("%d", &num[i]);
            }
            s1[0] = s2[0] = 10000;
            for(i = 1, j = 0; i <= n;){
                    r = j;
                    if(s1[t1] > num[j] && j < n){
                            s1[++t1] = num[j++];
                            add(‘a’);
                    }else if(s2[t2] > num[j] && j < n){
                            s2[++t2] = num[j++];
                            add(‘c’);
                    }
                    t = i;
                    if(s1[t1] == i){
                            t1–;
                            add(‘b’);
                            i++;
                    }
                    if(s2[t2] == i){
                            t2–;
                            i++;
                            add(‘d’);
                    }
                    if(t == i && r == j){
                            printf("0\n");
                            return 0;
                    }
            }
            for(i = 0; i < 2  n; i++){
                    if(i != 0){
                            printf(" ");
                    }
                    printf("%c", ans[i]);
            }
            printf("\n");
            return 0;
    }
      继续学习中。。
      额, 照着网上一个人抄的(当然是在理解的前提下, 再自己徒手打出来的.), 竟然没有AC, 然后试了试他自己的代码, 也没AC
      思路是这样的, 对于这样的数据i < j < k 且 num[k] < num[i] < num[j] 的情况下,i和j一定不能在同一个栈中,不然就是无解的情况,你想想啊,如果小的先入栈,大的又入栈,这能有解码?所以这里使用了二分图染色的算法,具体的解释看这位大牛和另一位的Blog: 
      http://www.byvoid.com/blog/noip2008-twostack/

      http://zhc105.info/blog/2010/06/双栈排序.html
      下面那个是90分的代码,上面那个是100分的代码。
      先贴代码吧:
    #include <stdio.h>
    #define minnum(a, b) ((a)<(b)?(a):(b))
    int num[1000];
    int min[1000];
    int map[1000][1000];
    int count[1000];
    int color[1000];

    void add(int i, int j)
    {
            map[i][count[i]++] = j;
    }

    int fill(int i, int c)
    {
            int j, t;
            color[i] = c;
            for(j = 0; j < count[i]; j++){
                    t = map[i][j];
                    if(color[t] == –1 && !fill(t, c ^ 1)){
                            return 0;
                    }else if(color[t] == c){
                            return 0;
                    }
            }
            return 1;
    }

    int s1[1000], s2[1000];
    int t1, t2;

    int main(void)
    {
            int n;
            int i, j;
            char 
    tmp;
            memset(min, 0x7F, sizeof(min));
            memset(color, 0xFF, sizeof(color));
            scanf("%d", &n);
            for(i = 0; i < n; i++){
                    scanf("%d", &num[i]);
            }
            for(i = n – 1; i >= 0; i–){
                    min[i] = minnum(min[i + 1], num[i]);
            }
            for(i = 0; i < n; i++){
                    for(j = i + 1; j < n; j++){
                            if(num[i] < num[j] && num[i] > min[j]){
                                    add(i, j);
                                    add(j, i);
                            }
                    }
            }
            for(i = 0; i < n; i++){
                    if(color[i] == –1){
                            if(!fill(i, 0)){
                                    printf("0\n");
                                    return 0;
                            }
                    }
            }
            j = 0;
            tmp = "";
            for(i = 1; i <= n; ){
                    if(s1[t1] == i){
                            printf("%sb", tmp);
                            t1–, i++;
                            continue;
                    }
                    if(s2[t2] == i && (j >= n || color[j])){
                            printf("%sd", tmp);
                            t2–, i++;
                            continue;
                    }
                    if(!color[j]){
                            printf("%sa", tmp);
                            tmp = " ";
                            s1[++t1] = num[j++];
                    }else{
                            printf("%sc", tmp);
                            tmp = " ";
                            s2[++t2] = num[j++];
                    }
            }
            printf("\n");
    //      getch();
            return 0;
    }

      但是将上述代码稍加修改后,就能够AC了:
    #include <stdio.h>
    #define minnum(a, b) ((a)<(b)?(a):(b))
    int num[1000];
    int min[1001];
    int map[1000][1000];
    int count[1000];
    int color[1000];

    void add(int i, int j)
    {
            map[i][count[i]++] = j;
    }

    int fill(int i, int c)
    {
            int j, t;
            color[i] = c;
            for(j = 0; j < count[i]; j++){
                    t = map[i][j];
                    if(color[t] == –1 && !fill(t, c ^ 1)){
                            return 0;
                    }else if(color[t] == c){
                            return 0;
                    }
            }
            return 1;
    }

    int s1[1000], s2[1000];
    int t1, t2;

    int main(void)
    {
            int n;
            int i, j;
            char *tmp;
            scanf("%d", &n);
            for(i = 0; i < n; i++){
                    scanf("%d", &num[i]);
            }
            min[n] = 10001;
            for(i = n – 1; i >= 0; i–){
                    min[i] = minnum(min[i + 1], num[i]);
            }
            for(i = 0; i < n; i++){
                    for(j = i + 1; j < n; j++){
                            if(num[i] < num[j] && num[i] > min[j]){
                                    add(i, j);
                                    add(j, i);
                            }
                    }
            }

            for(i = 0; i < n; i++){
                    color[i] = –1;
            }

            for(i = 0; i < n; i++){
                    if(color[i] == –1){
                            if(!fill(i, 0)){
                                    printf("0\n");
                                    return 0;
                            }
                    }
            }
            j = 0;
            tmp = "";
            for(i = 1; i <= n; ){
                    if(s1[t1] == i){
                            printf("%sb", tmp);
                            t1–, i++;
                            continue;
                    }
                    if(s2[t2] == i && (j >= n || color[j])){
                            printf("%sd", tmp);
                            t2–, i++;
                            continue;
                    }
                    if(!color[j]){
                            printf("%sa", tmp);
                            tmp = " ";
                            s1[++t1] = num[j++];
                    }else{
                            printf("%sc", tmp);
                            tmp = " ";
                            s2[++t2] = num[j++];
                    }
            }
            printf("\n");
    //      getch();
            return 0;
    }

  • Vim 第6章 使用语法高亮 的笔记

    :模式下的:

    syntax enable                                       打开语法高亮

    syntax clear                                           关闭当前编辑文件此次语法高亮

    syntax off                                                        彻底关闭语法高亮

     

    if &t_CO > 1                                          三行语句表示如果终端支持语法高亮才启用语法高亮

             syntax enable                              Ps: t_Co, Help了一下原来是终端支持颜色的个数

    endif

     

    solorscheme xxx                                  使用xxx颜色方案

    highlight xx yy=zz                                 设置xx在yy下变为zz, = =|||, (yy部分参见下面的语法高亮内容) 如:

                                                                     :highlight  Comment  cterm=green  guifg = green
                                                                    
    就是讲term和gui下的注释变为绿色

    runtime syntax/colortest.vim           查看常用颜色设置的效果

     

    hardcopy                                                打印当前文件 可以使用Visual模式选择要打印的范围

    source $VIMRUNTIME/syntax/2html.vim                用于自动生成Html文件



      查看$VIMRUNTIME/colors目录能够知道Vim支持的所有颜色高亮的方案. 



      在自定义Vim语法高亮时要用到下面的一些内容:

    term                             黑白终端的显示属性

    cterm                           彩色终端的显示属性

    ctermfg                        彩色终端的前景色

    ctermbg                      彩色终端的背景色

    gui                               GUI的显示属性

    guifg                            GUI的前景色

    guibg                           GUI的背景色

  • Http 服务器整好了

      上午9点钟起来,吃了饭就在弄昨天找到的一个Http服务器,总共只有200行不到的代码,很快就看完了,也理解了,唯一要到网上查阅一下的就是HTTP协议,大致能看懂一点,但是我想多看看。
      整了2个多小时,到近11点的时候就Ok了,把服务器弄好了,可以简单的浏览本地Html文件了,但是问题还有很多,比如子进程没有处理,让它们僵死了;还有这个程序只是用了一次读数据,内网倒不会有问题,外网的话,就不一定了,所以最好还是用循环的好。
      还有一些问题就是看Unix网络编程了,Unix网络编程前面的内容就是围绕着一个简单的程序进行讲解socket的,各种各样的问题,技术。
      这份代码以后我会重写,然后加入更多的元素,让它能够使用。服务器代码如下:
    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #include<unistd.h>
    #include<sys/socket.h>
    #include<netinet/in.h>
    #include<arpa/inet.h>
    #include<sys/stat.h>
    #include<fcntl.h>

    #define BACKLOG 3
    #define BUFSIZE 10244

    char not_found =
        "HTTP/1.1 404 Not Found\r\n" "Content-Type: text/html\r\n"
        "Content-Length: 40\r\n" "\r\n"
        "<HTML><BODY>File not found</BODY></HTML>";
    char bad_request =
        "HTTP/1.1 400 Bad Request\r\n" "Content-Type: text/html\r\n"
        "Content-Length: 39\r\n" "\r\n"
        "<h1>Bad Request (Invalid Hostname)</h1>";
    /
    char moved_permanently = 
         "HTTP/1.1 301 Moved Permanently\r\n"     "Content-Length: 147\r\n"        "Content-Type: text/html\r\n"       "Location: %s\r\n"          "\r\n"             "<head><title>Document Moved</title></head><body><h1>Object Moved</h1>This document may be found <a HREF="\" mce_HREF="\""%s\">here</a></body>"; 
    /
    char head_analysis(char p);
    void read_send(const char p, char pbuf, int connfd);

    int main(void)
    {
            int listenfd;
            struct sockaddr_in servAddr;
            unsigned port = 80;

            printf("HTTP Server is starting at port %d…\n", port);

            listenfd = socket(AF_INET, SOCK_STREAM, 0);
            if (listenfd == –1) {
                    printf("Invalid socket!\n");
                    return 1;
            }

            bzero(&servAddr, sizeof(servAddr));
            servAddr.sin_family = AF_INET;
            servAddr.sin_port = htons(port);
            servAddr.sin_addr.s_addr = htonl(INADDR_ANY);

            printf("Server is listening…\n");
            if (bind(listenfd, (struct sockaddr ) &servAddr,
                 sizeof(servAddr)) != 0) {
                    close(listenfd);
                    perror("Bind Error");
                    return 1;
            }
            printf("Binding server to port %d successfully.\n", port);

            if (listen(listenfd, BACKLOG) != 0)
            {
                    close(listenfd);
                    perror("Listen error");
                    return 1;
            }

            printf("Waiting client…\n");

            while (1) {
                    struct sockaddr_in cliAddr;
                    size_t cliAddrLen = sizeof(cliAddr);
                    pid_t pid;
                    char 
    p = NULL,
                        from[20],
                        file_name[100] = "/home/zqynux/network/",
                        rcvbuf[1024], sendbuf[BUFSIZE];

                    int connfd =
                        accept(listenfd, (struct sockaddr ) &cliAddr,
                               &cliAddrLen);
                    if (connfd < 0) {
                            close(listenfd);
                            printf("accept error\n");
                            return 1;
                    }

                    pid = fork();
                    if (pid == 0)
                    {
                            close(listenfd);
                            strcpy(from, inet_ntoa(cliAddr.sin_addr));
                            printf("\n\nclient %s CONNECTED.\n", from);

                            if (recv(connfd, rcvbuf, sizeof(rcvbuf), 0) > 0) {
                                    printf("%s\n", rcvbuf);
                                    p = head_analysis(rcvbuf);
                            } else {
                                    perror("Read Error");
                                    exit(0);
                            }
                            if (p != NULL) {
                                    strcat(file_name, p);
                                    printf("FILE NAME :%s\n", file_name);
                                    read_send(file_name, sendbuf, connfd);
                            } else{
                                    printf("No default html\n");
                                    send(connfd, bad_request,
                                         strlen(bad_request), 0);
                            }

                            close(connfd);
                            printf("DISCONNECTION TO CLIENT\n");
                            exit(0);
                    } else if (pid > 0)
                            close(connfd);
                    else
                            return 1;
            }

            close(listenfd);

            return 0;
    }

    char head_analysis(char p)
    {
            char 
    ptmp = p;

            if (strncmp(ptmp, "GET /", 5) == 0) {
                    ptmp += 5;
                    while (ptmp != ‘ ‘)
                            ptmp++;
                    
    ptmp++ = ‘\0’;

                    if (strncmp(ptmp, "HTTP/", 5) == 0)
                            return p + 5;
                    else
                            return NULL;
            }else
                    return NULL;
    }
    void read_send(const char p, char pbuf, int connfd)
    {
            int fd;
            size_t rdLen;
            fd = open(p, O_RDONLY);
            if (fd != –1) {
                    send(connfd,
                         "HTTP/1.1 200 OK\r\nContent-Type:text/html\r\n\r\n",
                         strlen
                         ("HTTP/1.1 200 OK\r\nContent-Type:text/html\r\n\r\n"),
                         0);

                    while ((rdLen = read(fd, pbuf, BUFSIZE)) > 0)
                            send(connfd, pbuf, rdLen, 0);

                    printf("WRITE TO CLIENT FINISHED\n");
                    close(fd);
            } else{
                    send(connfd, not_found, strlen(not_found), 0);
                    printf("FILE Not Find\n");
            }
    }
      至于客户端就是浏览器。

  • NOIP 2008 提高组 传纸条 解题报告

      这题我以前就看过,一直不会做,后来看到别人说双线程动态规划,我以为是多么多么的神奇的一个东西,把它看的和Linux源码一样神奇了,现在学了之后也就是简单的DP,我用的四维DP,别人都说是三维,我先用四维做,以后再考虑三维(也许不会再考虑这一题了咯。)
      我的方程如下:f[a][b][c][d] = max(f[a – 1][b][c – 1][d], f[a][b – 1][c – 1][d], f[a – 1][b][c][d – 1], f[a][b – 1][c][d – 1]) + map[a][b] + map[c][d].
      a,b代表第一个线程(说线程夸张了一点),c,d代表第二个线程的坐标,map就是对应坐标的值。
      代码如下:
    #include <stdio.h>
    #define max(a, b) ((a)>(b)?(a):(b))
    int f[51][51][51][51];
    int map[51][51];
    int m, n;
    int s[4];

    volatile void test(int a, int b, int c, int d, int t)
    {
            if(a < 0 || b < 0 || c < 0 || d < 0){
                    return;
            }
            
    t = max(*t, f[a][b][c][d]);
    }

    void dp(void)
    {
            int a = s[0], b = s[1], c = s[2], d = s[3];
            int t = 0;
            test(a – 1, b, c – 1, d, &t);
            test(a – 1, b, c, d – 1, &t);
            test(a, b – 1, c, d – 1, &t);
            test(a, b – 1, c – 1, d, &t);
            f[a][b][c][d] = t + map[a][b] + map[c][d];
    }

    void srch(int now)
    {
            int i, k;
            if(now == 4){
                    if(s[0] != s[2] || s[1] != s[3]){
                            dp();
                    }
                    return;
            }
            if(now & 1){
                    k = n;
            }else{
                    k = m;
            }
            for(i = 1; i <= k; i++){
                    s[now] = i;
                    srch(now + 1);
            }
    }

    int main(void)
    {
            int i, j, k, l;
            scanf("%d%d", &m, &n);
            for(i = 1; i <= m; i++){
                    for(j = 1; j <= n; j++){
                            scanf("%d", &map[i][j]);
                    }
            }
            f[1][1][1][1] = map[1][1];
            srch(0);

            s[0] = s[2] = m;
            s[1] = s[3] = n;
            dp();

            printf("%d\n", f[m][n][m][n]);
            return 0;
    }

  • USACO 3.3.3. Shopping Offers 商店购物

      一道DP题,DP的方程很简单:
      f[a][b][c][d][e] = min(f[a][b][c][d][e], f[a – cost[0][0]][b – cost[0][1]][c – cost[0][2]][d – cost[0][3]][e – cost[0][4]], f[a – cost[1][0]][b – cost[1][1]][c – cost[1][2]][d – cost[1][3]][e – cost[1][4]]…);
      代码如下:
    /
    LANG: C
    ID: zqynux2
    PROG: shopping
    /
    #include <stdio.h>
    #define min(a, b) ((a)<(b)?(a):(b))
    struct you{
            int len;
            struct thing{
                    int id, num;
            }buy[5];
            int priece;
    }buy[99];
    int money[6];
    int num[6];
    int good[1000];
    int f[6][6][6][6][6];
    int n, m;

    int s[6];

    void init(int now)
    {
            int i;
            if(now == m){
                    for(i = 0; i < m; i++){
                            f[s[0]][s[1]][s[2]][s[3]][s[4]] += money[i + 1] s[i];
                    }
                    return;
            }
            for(i = 0; i <= 5; i++){
                    s[now] = i;
                    init(now + 1);
            }
    }

    void deal(int now)
    {
            int used[6];
            int i;
            memset(used, 0, sizeof(used));
            for(i = 0; i < buy[now].len; i++){
                    used[good[buy[now].buy[i].id]] += buy[now].buy[i].num;
            }
            if(used[0] != 0){
                    return;
            }
            for(i = 0; i < 5; i++){
                    if(used[i + 1] > s[i]){
                            return;
                    }
            }
            f[s[0]][s[1]][s[2]][s[3]][s[4]] = min(f[s[0]][s[1]][s[2]][s[3]][s[4]], 
                    f[s[0] – used[1]][s[1] – used[2]][s[2] – used[3]][s[3] – used[4]][s[4] – used[5]]
                    + buy[now].priece);
    }

    void srch(int now)
    {
            int i;
            if(now == m){
                    for(i = 0; i < n; i++){
                            deal(i);
                    }
                    return;
            }
            for(i = 0; i <= 5; i++){
                    s[now] = i;
                    srch(now + 1);
                    //写成了init 
            }
    }

    int main(void)
    {
            int i, j;
            freopen("shopping.in", "r", stdin);
            freopen("shopping.out", "w", stdout);
            scanf("%d", &n);
            for(i = 0; i < n; i++){
                    scanf("%d", &buy[i].len);
                    for(j = 0; j < buy[i].len; j++){
                            scanf("%d%d", &buy[i].buy[j].id,
                                            &buy[i].buy[j].num);
                    }
                    scanf("%d", &buy[i].priece);
            }
            scanf("%d", &m);
            for(i = 1; i <= m; i++){
                    scanf("%d%d%d", &j, &num[i], &money[i]);
                    good[j] = i;
            }

            init(0);                       / 将价格进行初始化 /
            srch(0);                       /
     DP */

            printf("%d\n", f[num[1]][num[2]][num[3]][num[4]][num[5]]);
            return 0;
    }

  • NOIP 2008 笨小猴 解题报告

      这个题目很简单,不过我也提交了两次。。问题见注释。
    #include <math.h>
    #include <stdio.h>
    #include <string.h>
    char str[101];
    int count[26];

    int isprime(int n)
    {
            int li;
            int i;
            if(n == 0 || n == 1){
                    //0和1不算素数 
                    return 0;
            }
            li = sqrt(n);
            for(i = 2; i <= li; i++){
                    if(n % i == 0){
                            return 0;
                    }
            }
            return 1;
    }

    int main(void)
    {
            int i, len;
            int max = –1, min = 1000;
            int ans;
            scanf("%s", str);
            len = strlen(str);
            for(i = 0; i < len; i++){
                    count[str[i] – ‘a’]++;
            }
            for(i = 0; i < 26; i++){
                    if(max < count[i]){
                            max = count[i];
                    }
                    if(min > count[i] && count[i] != 0){
                                    //如果字符没有出现的话就不算 
                            min = count[i];
                    }
            }
            ans = max – min;
            if(isprime(ans)){
                    printf("Lucky Word\n");
                    printf("%d\n", ans);
            }else{
                    printf("No Answer\n0\n");
                            //忘记输出0了  
            }
    //      getch();
            return 0;
    }

  • NOIP 2008 火柴棒等式 解题报告

      刚刚拿到题目感觉非常容易,第一次提交,发现把数据写错了,6是6根火柴,我写的5根。第二次提交我发现题目不止是个位的运算,还可以十位,百位。。第三次提交,AC了,不过效率太慢了,代码如下:
    #include <stdio.h>
    int num[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
                        //数据写错了

    int count(int n)
    {
            int t = 0;
            if(n == 0){
                    t = num[0];
            }
            while(n){
                    t += num[n % 10];
                    n /= 10;
            }
            return t;
    }

    int main(void)
    {
            int n;
            int i, j;
            int ans = 0;
            scanf("%d", &n);
            for(i = 0; i <= 2000; i++){
                    for(j = 0; j <= 2000; j++){                           
                            if(count(i) + count(j) + count(i + j) + 4 == n){
                                    ans++;
                            }
                    }
            }
            printf("%d\n", ans);
            return 0;
    }
      后来看到七妹的代码,发现自己的代码太破了,本来我是想用数组记录一下的,后来发现这都不用。NOIP 2008 火柴棒等式 解题报告 - NeWorldMaker - My S-K-Y,修改后的代码如下:
    #include <stdio.h>
    int num[5001] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
                        //数据写错了
    int main(void)
    {
            int n;
            int i, j;
            int ans = 0;
            scanf("%d", &n);
            for(i = 10; i <= 5000; i++){
                    num[i] = num[i / 10] + num[i % 10];
            }
            for(i = 0; i <= 5000; i++){
                    for(j = 0; j <= 5000; j++){
                            if(i + j <= 5000 && num[i] + num[j] + num[i + j] + 4 == n){
                                    ans++;
                            }
                    }
            }
            printf("%d\n", ans);
            return 0;
    }