亂貼小站公告欄

目前分類:CMD程式 (103)

瀏覽方式: 標題列表 簡短摘要

來源:魏小亮的博客 (作者是Facebook的移動技術總監)、http://blog.jobbole.com/33834/

有不少的朋友問過這個問題:在中學裡面參加NOI,在大學參加ACM/ICPC,TopCoder,最後對實際工作究竟有多少用處?我把自己的一些理解總結了一下跟大家討論。

我是在94~96年參加NOI和集訓隊,99~2000年參加ACM/ICPC,2002左右玩了半年TopCoder,後來就很少關注編程競賽了,所以可能對近幾年競賽模式的變化不瞭解。另外我目前主要在工業界工作,所以“實際工作”主要指的是在IT工業界的技術型工作。

我想競賽培養的能力可以分成幾個類型:

1、基本技術技能。我想參加競賽而且成績不錯的朋友,基本上都有三個非常出色而且難得的基本技術能力:算法設計、快速編程和自我調試。這是所有比賽都必須的: 給定一個問題,需要很快地設計出算法,很快地編寫出程序,並且在整個算法設計和編程過程中不斷拷問自己的設計和程序,儘早發現漏洞、完善設計,最後在提交結果之前通過一系列的測試儘量提高程序通過競賽評委測試的概率。 這三項基本能力是工作裡面非常有用的。 大部分公司的技術面試也集中在這三項基本技能裡面。競賽經驗的確讓優秀的參賽者在實際工作中獲得先發優勢,一般IOI/ICPC/TopCoder的優秀參賽者都很容易獲得公司錄取,並且在起始級別的工程師崗位上作得非常出色。

2、獨立學習的能力和自信心。我想大部分的NOI參 賽者都是中學就開始學習中學課程裡面不函括的內容:面向對象程序設計、數據結構、圖論和網絡流理論、算法理論、離散數學等等。如果一個參賽者是通過自己獨 立學習這些課外知識而在競賽裡面脫穎而出的,她一定有獨立學習的能力和自信心,同時相信自己能夠很快的學會各種新知識。這個能力和自信在工作中非常重要:計算機語言日新月異,從Pascal/C到C++/Java到Python/PHP/Javascript/Objective-C⋯⋯一個人不可能從一開始就懂得所有的知識,但只要自信自己能學會任何新的語言和概念(並且的確可以學會),那他就可以敢於面對未知的挑戰。在工作中,這些“敢吃螃蟹第一人”往往會得到更多機會去開發新項目、創建新公司。

3、表達能力。這一點我本人在吳文虎老師指導的NOI冬令營裡面獲益匪淺。當時吳老師要求每位冬令營選手挑選一個複雜的競賽問題深入研究解法,最後寫成論文,並且在冬令營裡面做報告。吳老師親自把關,指導論文 裡面寫不清楚或者報告裡面說不清楚的地方。這是我第一次學會如何把一個技術問題寫清楚、說清楚。這樣的訓練雖然跟競賽成績本身沒有直接的關係,但能夠讓競 賽選手的表達能力上了一個台階。表達能力對實際工作有非常重要的意義:現代的大型軟件系統開發不是一個英雄人物就能完成的,如果一個子系統的算法和程序不 能清晰地被理解,那這個子系統和它的作者就成為單一故障點(Single Point Of Failure) —— 只要作者一度假,就沒有人能維護或者擴展這部分。基於這種風險,大家寧願用一個更慢更費內存但能被其他人看懂的解決方案。在這兩年的招聘過程中,我看到不少這樣的可惜例子:不少ACM/ICPC的選手能在15分鐘之內寫出一個很巧妙的算法,在機器上編譯、測試例子都通過。 但在黑板上或程序註釋裡面,他們花20分鐘也沒能說清楚這個算法為什麼是對的,為什麼要用這個算法。

4、合作能力:NOI/IOI/TopCoder更多的是單槍匹馬,而ACM/ICPC對合作能力的培養更有幫助。三個編程高手共用一台機器,緊缺資源誰先用誰後用,如何分工,這些問題在實際工作中每天都會遇到,如果一個選手在ICPC裡面學會如何跟隊友協調、如何培養信任,那她在實際工作裡面就很容易融入一個團隊,在團隊裡面找到自己的發力點 ,很快為團隊作出貢獻。

5、志同道合的朋友圈:一般來說,願意花額外時間參加競賽的學生都是喜歡寫程序的,因為喜歡,他們往往更容易在這方面越做越好。我10年前在競賽過程中認識的老對手,現在還有很多是好朋友,不時能聯繫一下,得到他們的指導、交換最新的行業信息和趨勢。這一點雖然對實際工作沒有直接幫助,但我覺得是參加競賽獲得的最寶貴的東西。

這些大概是我在比賽裡面學到的最有用的一些東西。下次有時間的時候打算整理一下實際工作裡面有哪些是競賽裡面學不到的。

-----------------------

文章推薦:《編程競賽和邏輯謎題網站大集合》


和風信使 發表在 痞客邦 留言(0) 人氣()

#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include<sys/mman.h>
#include<sys/stat.h>
#include<unistd.h>
#include<fcntl.h>
#define FILE_LENGTH 10000

int main(int argc,char *argv[])
{
        if(argc!=2)
    {
        printf("Usage: %s filename\n",argv[0]);
        return 0;
    }
        int fd,count=0;
        char *map_memory,*ca;
        
        fd = open(argv[1], O_RDWR | O_CREAT, S_IRUSR | S_IWUSR);
        
        lseek(fd, FILE_LENGTH+1, SEEK_SET);
        write(fd, "", 1);
        lseek(fd, 0, SEEK_SET);
        map_memory =(char*) mmap(0, FILE_LENGTH, PROT_WRITE, MAP_SHARED, fd, 0);
        close(fd);
        
        ca = map_memory;
        while( FILE_LENGTH>count && fgets(ca,FILE_LENGTH-count,stdin)!=NULL )
        {
                int tmp = strlen(ca);
                count += tmp;
                ca += tmp;
        }
        
        munmap(map_memory, FILE_LENGTH);
        return 0;
}

 

#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include<sys/mman.h>
#include<sys/stat.h>
#include<unistd.h>
#include<fcntl.h>
#define FILE_LENGTH 10000

int main(int argc,char *argv[])
{
        if(argc!=4)
    {
        printf("Usage: %s filename start_pos end_pos\n",argv[0]);
        return 1;
    }
        int start_pos=0, end_pos=0;
        start_pos = atoi(argv[2]);
        end_pos = atoi(argv[3]);
        if(start_pos<0 || end_pos>FILE_LENGTH || start_pos>end_pos)
        {
                puts("start_pos or end_pos error. Please try again.");
        return 1;
        }
        int fd,i;
        char *map_memory;
        
        fd = open(argv[1], O_RDWR | O_CREAT, S_IRUSR | S_IWUSR);
        
        lseek(fd, FILE_LENGTH+1, SEEK_SET);
        write(fd, "", 1);
        lseek(fd, 0, SEEK_SET);
        map_memory =(char*) mmap(0, FILE_LENGTH, PROT_WRITE, MAP_SHARED, fd, 0);
        close(fd);
        
        printf("Substring from [%d] to [%d] is: ",start_pos,end_pos);
        for(i=start_pos-1;i<end_pos;i++)
                printf("%c",*(map_memory+i));
        puts("");
        
        munmap(map_memory, FILE_LENGTH);
        return 0;
}

和風信使 發表在 痞客邦 留言(0) 人氣()

#include<stdio.h>
#include<unistd.h>
#include<fcntl.h>
#include<string.h>

struct flock* file_lock(short type,short whence)
{
        static struct flock ret;
        ret.l_type = type;
        ret.l_start = 0;
        ret.l_whence = whence;
        ret.l_len = 0;
        ret.l_pid = getpid();
        return &ret;
}

int main()
{
        printf("1.exclusive lock(write lock)\n");
        printf("2.share lock(read lock)\n");
        printf("Choose lock type -> ");
        int ia;
        scanf("%d",&ia);
        int fd = open("lock.txt",O_RDWR|O_APPEND);
        //printf("fd = %d\n",fd);
        if(ia==1)
        {
                if(fcntl(fd, F_SETLK, file_lock(F_WRLCK, SEEK_SET))==0)
                        printf("F_WRLCK success.\n");
                else 
                {
                        printf("F_WRLCK fail.\n");
                        return 0;
                }
        }
        else
        {
                if(fcntl(fd, F_SETLK, file_lock(F_RDLCK, SEEK_SET))==0)
                        printf("F_RDLCK success.\n");
                else 
                {
                        printf("F_RDLCK fail.\n");
                        return 0;
                }
        }
        ia= 0;
        do
        {
                printf("If you want to unlock file and end program,\n");
                printf("please input 1 -> \n");
                scanf("%d",&ia);
        }while(ia!=1);
        fcntl(fd, F_SETLK, file_lock(F_UNLCK, SEEK_SET));
        close(fd);
}

 

#include<stdio.h>
#include<unistd.h>
#include<fcntl.h>
#include<string.h>

struct flock* file_lock(short type,short whence)
{
        static struct flock ret;
        ret.l_type = type;
        ret.l_start = 0;
        ret.l_whence = whence;
        ret.l_len = 0;
        ret.l_pid = getpid();
        return &ret;
}

int main()
{
        printf("1.exclusive lock(write lock)\n");
        printf("2.share lock(read lock)\n");
        printf("3.not use lock\n");
        printf("Choose lock type -> ");
        int ia;
        scanf("%d",&ia);
        int fd = open("lock.txt",O_RDWR|O_APPEND);
        if(ia==1)
        {
                if(fcntl(fd, F_SETLK, file_lock(F_WRLCK, SEEK_SET))!=0)
                        printf("F_WRLCK fail.\n");
                else 
                        printf("F_WRLCK success.\n");
        }
        else if(ia==2)
        {
                if(fcntl(fd, F_SETLK, file_lock(F_RDLCK, SEEK_SET))!=0)
                        printf("F_RDLCK fail.\n");
                else 
                        printf("F_RDLCK success.\n");
        }
        char ca[10000];
        if(read(fd, ca, 10000)<0)printf("Can't read file.\n");
        else
        {
                printf("Read file:\n");
                puts(ca);
        }
        strcpy(ca,"\n\nab write success.\n");
        if(write(fd, ca, strlen(ca))<0)printf("Can't write file.\n");
        else
        {
                printf("write file success.\n");
        }
        fcntl(fd, F_SETLK, file_lock(F_UNLCK, SEEK_SET));
        close(fd);
}

 

/*
mount /dev/sda1 /mnt
mount -o remount,mand /mnt
*/
#include<stdio.h>
#include<unistd.h>
#include<fcntl.h>
#include<string.h>

struct flock* file_lock(short type,short whence)
{
        static struct flock ret;
        ret.l_type = type;
        ret.l_start = 0;
        ret.l_whence = whence;
        ret.l_len = 0;
        ret.l_pid = getpid();
        return &ret;
}

int main()
{
        printf("1.exclusive lock(write lock)\n");
        printf("2.share lock(read lock)\n");
        printf("Choose lock type -> ");
        int ia;
        scanf("%d",&ia);
        int fd = open("mandlock.txt",O_RDWR|O_APPEND);
        //printf("fd = %d\n",fd);
        if(ia==1)
        {
                if(fcntl(fd, F_SETLK, file_lock(F_WRLCK, SEEK_SET))==0)
                        printf("F_WRLCK success.\n");
                else 
                {
                        printf("F_WRLCK fail.\n");
                        return 0;
                }
        }
        else
        {
                if(fcntl(fd, F_SETLK, file_lock(F_RDLCK, SEEK_SET))==0)
                        printf("F_RDLCK success.\n");
                else 
                {
                        printf("F_RDLCK fail.\n");
                        return 0;
                }
        }
        ia= 0;
        do
        {
                printf("If you want to unlock file and end program,\n");
                printf("please input 1 -> \n");
                scanf("%d",&ia);
        }while(ia!=1);
        fcntl(fd, F_SETLK, file_lock(F_UNLCK, SEEK_SET));
        close(fd);
}

 

#include<stdio.h>
#include<unistd.h>
#include<fcntl.h>
#include<string.h>

struct flock* file_lock(short type,short whence)
{
        static struct flock ret;
        ret.l_type = type;
        ret.l_start = 0;
        ret.l_whence = whence;
        ret.l_len = 0;
        ret.l_pid = getpid();
        return &ret;
}

int main()
{
        printf("1.exclusive lock(write lock)\n");
        printf("2.share lock(read lock)\n");
        printf("3.not use lock\n");
        printf("Choose lock type -> ");
        int ia;
        scanf("%d",&ia);
        int fd = open("mandlock.txt",O_RDWR|O_APPEND);
        if(ia==1)
        {
                if(fcntl(fd, F_SETLK, file_lock(F_WRLCK, SEEK_SET))!=0)
                        printf("F_WRLCK fail.\n");
                else 
                        printf("F_WRLCK success.\n");
        }
        else if(ia==2)
        {
                if(fcntl(fd, F_SETLK, file_lock(F_RDLCK, SEEK_SET))!=0)
                        printf("F_RDLCK fail.\n");
                else 
                        printf("F_RDLCK success.\n");
        }
        char ca[10000];
        if(read(fd, ca, 10000)<0)printf("Can't read file.\n");
        else
        {
                printf("Read file:\n");
                puts(ca);
        }
        strcpy(ca,"\n\nab write success.\n");
        if(write(fd, ca, strlen(ca))<0)printf("Can't write file.\n");
        else
        {
                printf("write file success.\n");
        }
        fcntl(fd, F_SETLK, file_lock(F_UNLCK, SEEK_SET));
        close(fd);
}

和風信使 發表在 痞客邦 留言(0) 人氣()

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<sstream>
using namespace std;

int freeFrameList[] = {4,7,8,5,1,2,11,12,10,13,14,15};
int freeFrameCnt = 12, freeFrameIndex = 0;
string frame[16] = {"ee","","","ww","","","gg","","","ff","","","","","",""};
string processA[] = {"ab","ef","cd","gh","xa","ta","ab","cg"};
string processB[] = {"rx","yy","zz","ww","mr","mk","fn","zx"};

void show_all(bool ba=false)
{
        if(!ba)
        {
                for(int i=0;i<79;i++)
                        cout<<"=";
                cout<<endl;
        }
        printf("\n%s\n","ProcessA");
        for(int i=0;i<8;i++)printf(" %-2d",i);
        puts("");
        for(int i=0;i<8;i++)printf("%3s",processA[i].c_str());
        printf("\n\n%s\n","ProcessB");
        for(int i=0;i<8;i++)printf(" %-2d",i);
        puts("");
        for(int i=0;i<8;i++)printf("%3s",processB[i].c_str());
        printf("\n\n%s\n","freeFrameList");
        for(int i=freeFrameIndex;i<freeFrameCnt;i++)printf("%3d",freeFrameList[i]);
        printf("\n\n%s\n","frame");
        for(int i=0;i<16;i++)printf(" %-2d",i);
        puts("");
        for(int i=0;i<16;i++)printf("%3s",frame[i].c_str());
        puts("");puts("");
}

int main()
{
        string sa;
        show_all(true);
        for(int i=0;i<freeFrameCnt && cout<<"Enter next (ProcessName/page No) -> " && getline(cin,sa);i++)
        {
                sa.erase(0,sa.size()-3);
                istringstream ssin(sa);
                char ca;
                int ia;
                ssin>>ca>>ia;
                switch(ca)
                {
                case 'a':case 'A':
                        frame[freeFrameList[freeFrameIndex++]] = processA[ia];
                        break;
                case 'b':case 'B':
                        frame[freeFrameList[freeFrameIndex++]] = processB[ia];
                        break;
                }
                show_all();
        }
}
/*
ProcessA 0
ProcessB 1
ProcessA 4
ProcessB 5
ProcessB 7
ProcessA 7
ProcessA 2
ProcessB 6
*/

和風信使 發表在 痞客邦 留言(0) 人氣()

/*
Step1: Using the fork() function to create a new process.

Step2: Using command line to kill the process.
        kill -kill 1899

Step3: Repeat step1 and use system calls to kill process.
        
*/
#include<stdio.h>
#include<unistd.h>

int main()
{
    pid_t newpid = fork();
    if(newpid==0)
    {
        for(;;)
            pause();
    }
    printf("pid = %d\n",newpid);
    wait(NULL);
    printf("Child process is finished.\n");
}

 

#include<stdio.h>
#include<unistd.h>
#include<signal.h>

int main()
{
    pid_t newpid;
    printf("Input the pid of the process you want to kill -> ");
    scanf("%d",&newpid);
    kill(newpid,SIGKILL);
}

 

#include<stdio.h>
#include<unistd.h>
#include<signal.h>

struct sigaction newact;

/* here is the signal handler */ 
void catch_alarm_2(int sig_num)   /* the argument is signal number  */
{   
    /* re-set the signal handler again to catch_int, for next time */
    sigaction(SIGINT, &newact, NULL);
}
void catch_int_1(int sig_num)   /* the argument is signal number  */
{   
    /* re-set the signal handler again to catch_int, for next time */
    signal(SIGINT, catch_int_1);
    printf("How are you?\n",sig_num);
}
void catch_int_2(int sig_num)   /* the argument is signal number  */
{   
    /* re-set the signal handler again to catch_int, for next time */
    signal(SIGINT, catch_int_2);
    printf("I am fine!\n",sig_num);
}
void catch_alarm_1(int sig_num)   /* the argument is signal number  */
{   
    /* re-set the signal handler again to catch_int, for next time */
    signal(SIGINT, catch_int_2);
    signal(SIGALRM, catch_alarm_2);
    alarm(3);
}

int main(int argc, char* argv[])
{
    sigaction(SIGINT, NULL, &newact);
    
    /* set the INT (Ctrl-C) signal handler to 'catch_int' */
    signal(SIGINT, catch_int_1);
    signal(SIGALRM, catch_alarm_1);
    alarm(3);

    /* now, lets get into an infinite loop of doing nothing. */
    for ( ;; )
        pause();
} 

和風信使 發表在 痞客邦 留言(0) 人氣()

/*
Compile Command:
    gcc -o a a.c -pthread
*/
#include<pthread.h>
#include<stdio.h>
#include<stdlib.h>

void *PrintHello(void *arg)
{
    printf("This is Hello Thread\n");
    printf("Thread ID:%lu\n",pthread_self());
    printf("Argument: %d\n",(int)arg);
    //printf("Argument: %d\n",*(int*)arg);
    pthread_exit(NULL);
}
 
int main()
{
    pthread_t thread;
    int rc,t=100;
    rc = pthread_create( &thread, NULL, PrintHello, (void*)t);
    if(rc)
    {
        printf("ERROR: return code from pthread_create() is %d\n",rc);
        exit(-1);
    }
    rc = pthread_join( thread, NULL);
    if(rc)
    {
        printf("ERROR: return code from pthread_join() is %d\n",rc);
        exit(-1);
    }
    return 0;
}

 

/*
Compile Command:
    gcc -o b b.c -pthread
 
Questions:
#   Observe all of the results you got, and think about what
    problem does it have? (10pts.)
#   Compare to fork() process by doing all the same thing to
    the global variable, can you figure out what’s the
    difference between them? (10pts.)
 
*/
#include<pthread.h>
#include<stdio.h>
#include<stdlib.h>
 
int count = 0;
 
void *PrintHello(void *arg)
{
    int ia=250000;
    //printf("%d) Start: count = %d\n",(int)arg, count);
    while(ia--)
    {
        count++;
        //usleep(1);
    }
    //printf("%d) End: count = %d\n",(int)arg, count);
    printf("Thread %d: ID %lu Completed.\n",(int)arg,pthread_self());
    pthread_exit(NULL);
}
 
int main()
{
    pthread_t thread[4];
    int rc,t;
    for(t=0;t<4;t++)
    {
        rc = pthread_create( &thread[t], NULL, PrintHello, (void*)t);
        if(rc)
        {
            printf("ERROR: return code from pthread_create() is %d\n",rc);
            exit(-1);
        }
    }
    for(t=0;t<4;t++)
    {
        rc = pthread_join( thread[t], NULL);
        if(rc)
        {
            printf("ERROR: return code from pthread_join() is %d\n",rc);
            exit(-1);
        }
    }
    printf("Value = %d\n",count);
    return 0;
}

 

/*
Compile Command:
    gcc -o c c.c -pthread
 
*/
#include<pthread.h>
#include<unistd.h>
#include<stdio.h>
#include<string.h>
#include<sys/types.h>
#include<sys/ipc.h>
#include<sys/msg.h>
#include<stdlib.h>
#include "msg_que.h"
 
long int ProgramID = 1; // 1 or 2
int closeMsgQue = 0;
 
void *MsgSend(void *arg)
{
    key_t key=0x1234;
        int msqid = msgget(key,IPC_CREAT | 0666);
        oslab_msg_st msg_buffer;
        while( printf("Enter some text: "),fgets(msg_buffer.msg_text,256,stdin))
        {
                msg_buffer.oslab_msg_type = ProgramID;
                msgsnd(msqid,(void*)&msg_buffer,sizeof(msg_buffer)-sizeof(long int),0);
                if(strcmp(msg_buffer.msg_text,"exit\n")==0)
                {
            closeMsgQue = 1;
                        break;
        }
        }
    pthread_exit(NULL);
}
void *MsgGet(void *arg)
{
    key_t key=0x1234;
        int msqid = msgget(key,IPC_CREAT | 0666);
        oslab_msg_st msg_buffer;
        struct msqid_ds msq_id;
        msgctl(msqid,IPC_STAT,&msq_id);
        while( msgrcv(msqid,(void*)&msg_buffer,sizeof(msg_buffer)-sizeof(long int),3-ProgramID,0) )
        {
                printf("Received: %s\n",msg_buffer.msg_text);
                if(strcmp(msg_buffer.msg_text,"exit\n")==0)
                {
                        if(closeMsgQue)msgctl(msqid,IPC_RMID,&msq_id);
                        break;
                }
        }
    pthread_exit(NULL);
}
 
int main()
{
    pthread_t thread[2];
    int rc,t;
    rc = pthread_create( &thread[0], NULL, MsgSend, (void*)t);
    if(rc)
    {
        printf("ERROR: return code from pthread_create() is %d\n",rc);
        exit(-1);
    }
    rc = pthread_create( &thread[1], NULL, MsgGet, (void*)t);
    if(rc)
    {
        printf("ERROR: return code from pthread_create() is %d\n",rc);
        exit(-1);
    }
    rc = pthread_join( thread[0], NULL);
    if(rc)
    {
        printf("ERROR: return code from pthread_join() is %d\n",rc);
        exit(-1);
    }
    rc = pthread_join( thread[1], NULL);
    if(rc)
    {
        printf("ERROR: return code from pthread_join() is %d\n",rc);
        exit(-1);
    }
    return 0;
}

和風信使 發表在 痞客邦 留言(1) 人氣()

// WA
// BY taichunmin
// NCPC 2011 pb
#include<iostream>
#include<fstream>
#include<sstream>
using namespace std;
int va[1000000];
int va_c;
int main()
{
        //freopen("pb.in","r",stdin);
        int ta;
        cin>>ta;
        string sa;
        while(ta--)
        {
                int ia,ib;
                cin>>ia;
                cin.get();
                getline(fin,sa);
                va_c=0;
                istringstream ssin(sa);
                while(ssin>>ib)
                {
                        bool ba=true;
                        for(int k=0;k<va_c;k++)
                                if(va[k]>=ib)
                                {
                                        va[k]=ib;
                                        ba=false;
                                        break;
                                }
                        if(ba)va[va_c++]=ib;
                }
                cout<<va_c<<endl;
        }
        return 0;
}

 

// WA
// BY taichunmin
// NCPC 2011 pd
#include<iostream>
#include<sstream>
#include<fstream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
int ia,ib;
struct ta_t
{
        string n;
        int v;
}attr[10];
int fa(string sa)
{
        bool is_num=true;
        for(int i=0;i<sa.size() && is_num;i++)
                if(!('0'<=sa[i] && sa[i]<='9')is_num=false;
        if(is_num)
        {
                istringstream ssin(sa);
                int temp;
                ssin>>temp;
                return temp;
        }
        else
        {
                for(int i=0;i<ia;i++)
                        if(attr[i].n==sa)return attr[i].v;
        }
        return 2147483647;
}
int main()
{
        //freopen("pd.in","r",stdin);
        int ta;
        cin>>ta;
        while(ta--)
        {
                cin>>ia>>ib;
                string sa,sname,sx,sy;
                for(int i=0;i<ia;i++)
                        cin>>attr[i].n>>attr[i].v;
                cin.get();
                bool ba=true;
                for(int i=0;i<ib;i++)
                {
                        getline(cin,sa);
                        if(!ba)continue;
                        istringstream ssin(sa);
                        ssin>>sname;
                        bool bb=true;
                        while(getline(ssin,sa,'('))
                        {
                                ssin>>sx;
                                getline(ssin,sy,')');
                                sy.erase(0,3);
                                //cout<<"sy = "<<sy<<endl;
                                if(fa(sx)<=fa(sy))
                                {
                                        bb=false;
                                        break;
                                }
                        }
                        if(bb)
                        {
                                ba=false;
                                cout<<sname<<endl;
                        }
                }
        }
}

 

// AC
// BY morris1028
// NCPC 2011 ph
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
int A[100000],HASH[1000000],size;
struct Node{
        int v,s;
        int next;
}Node[200000];
int insHash(int v,int index)
{
        int m = v%1000000;
        if(HASH[m]==0) {
                size++;
                HASH[m]=size;
                Node[size].v=v, Node[size].s=index;
                Node[size].next=0;
                return -1;
        }
        int now=HSAH[m],pre=0;
        while(now)
        {
                if(Node[now].v>v || (Node[now].v==v && Node[now].s>index))
                        break;
                else pre=now, now=Node[now].next;
        }
        size++;
        if(pre == 0) HASH[m]=size;
        else Node[pre].next=size;
        Node[size].v=v,Node[size].s=index;
        Node[size].next=now;
        return -1;
}
int find(int v,int index)
{
        int m=v%1000000;
        int now=HASH[m], pre=0;
        while(now)
        {
                if(Node[now].v==v && Node[now].s>index)
                        return Node[now].s;
                else pre=now, now=Node[now].next;
        }
        return -1;
}
int Print(){
        int now, pre, i=0;
        for(int i=0;i<10;i++)
        {
                now=HASH[i];
                while(now)
                {
                        printf("(%d,%d)->",Node[now].v,Node[now].s);
                        pre=now, now=Node[now].next;
                }
                puts("===");
        }
        return 0;
}
int main(){
        //freopen("ph.in","r",stdin);
        int n,k,i;
        while(scanf("%d", &n)==1 && n) {
                for(i=0;i<n;i++)
                        scanf("%d",&A[i];
                memset(HASH, 0, sizeof(HASH));
                scanf("%d", &k);
                int sum=0,tmp;
                size=1;
                for(i=0;i<n;i++)
                {
                        A[i]%=k;
                        sum+=A[i];
                        sum%=k;
                        if(sum<0) sum+=k;
                        insHash(sum,i);
                }
                /* Print();*/
                sum=0;
                int flag=0;
                tmp=find(0,-1);
                if(tmp!=-1)
                {
                        printf("%d %d\n",1,tmp+1);
                        flag=1;
                }
                for(i=0;i<n;i++){
                        A[i]%=k;
                        sum+=A[i];
                        sum%=k;
                        if(sum<0) sum+=k;
                        tmp=find(sum,i);
                        /* printf("%d\n",tmp);*/
                        if(tmp!=-1 && flag==0)
                        {
                                printf("%d %d\n",i+2,tmp+1);
                                flag=1;
                                break;
                        }
                }
                if(flag==0)
                        printf("no solutions.\n");
        }
        return 0;
}
/*
7
2 5 1 -4 5 9 3
10
11 -3 1 13 -5 6 1 -8 -4 5
10
*/

 

// AC
// BY morris1028
// NCPC 2011 pk
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#define oo 2147483647
int map[1000][1000],Mt[1000];
int gcd(int x,int y)
{
        int t;
        while(y)
                t=x, x=y, y=t%y;
        return x;
}
int Used[1000], Time[1000], Ans;
int DFS(int T,int now,int start) {
        int last= oo,i,tmp,flag=0,ttry=0;
        Time[now] = T;
        /*printf("%d %d\n",now,T);*/
        for(i=0;i<Mt[now];i++){
                if(Used[map[now][i]]==0) {
                        used[map[now][i]]=1;
                        tmp=DFS(T+1, map[now][i],0);
                        if(tmp>=T) flag=1;
                        last=tmp<last?tmp:last;
                        ttry++;
                } else {
                        tmp=Time[map[now][i]];
                        last=tmp<last?tmp:last;
                }
        }
        if(start==1) {
                if(ttry>1)
                        Ans++;
        } else {
                Ans += flag;
        }
        /*printf("key : %d %d\nn", now,flag);*/
        return last;
}
int main() {
        //freopen("pk.in","r",stdin);
        int T,i,j,A[1001],n;
        scanf("%d",&T);
        while(T--)
        {
                scanf("%d",&n);
                for(i=0;i<n;i++)
                        scanf("%d",&A[i]);
                memset(map, 0, sizeof(map));
                memset(Mt, 0, sizeof(Mt));
                memset(Used, 0, sizeof(Used));
                memset(Time, 0, sizeof(Time));
                Ans=0;
                for(i=0;i<n;i++) {
                        for(j=i+1;j<n;j++) {
                                int tmp=gcd(A[i],A[j]);
                                if(tmp!=1) {
                                        map[i][Mt[i]++]=j;
                                        map[j][Mt[j]++]=i;
                                }
                        }
                }
                for(i=0;i<n;i++)
                        if(Used[i]==0) {
                                Used[i] =1,Time[i] = 1;
                                DFS(1,i,1);
                        }
                printf("%d\n",Ans);
        }
        return 0;
}

和風信使 發表在 痞客邦 留言(0) 人氣()





好難得拿了個第一名@@ - team214

20110928-2.jpg  


和風信使 發表在 痞客邦 留言(0) 人氣()

這個是在我期末那周拚出來的數獨遊戲
其實很久以前就很想寫樹讀了
但是一來沒有什麼壓力
二來C++也不是合寫這種
三來我Visual C++不熟悉,寫不出這種東西
所以一直拖到了現在才寫出數獨遊戲!!
另外 裡面還有一些附屬檔案
我就放到下面的這個連結給大家抓吧

http://dl.dropbox.com/u/12113131/program/sudoku.rar


文章標籤

和風信使 發表在 痞客邦 留言(2) 人氣()

內容 :

「收的快」快遞公司成立之後,已經分別與市內許多中小企業公司簽訂郵件收送服務契約。由於有些公司是在同一棟大樓內,所以「收的快」需要收件的地點(收件點)最多只有m點 (1, 2, …, m),因此「收的快」僅先行採購了三輛貨車並聘用了三名司機,每天早上分別從收件地點 「1」, 「2」 及 「3」出發。而在與客戶的服務契約中有明訂「收的快」必須在客戶提出郵件寄送要求的隔天派人至該公司(地點)收件。為了能更有效率的服務客戶並節省收件時間,該公司設立了收件服務登記網站,客戶如有郵件需要寄送,必須在需要收件的前一天就先上網登記。因此「收的快」就可以利用晚上先行安排三位司機隔天的收件路線。每位司機至各地點收件的順序應與各公司上網登記的順序相符且必須能在最省油的情況下完成當天所有的收件服務。因此每位司機有可能需要在不同時間重複到同一地點收件,或不同的司機有可能需在不同的時間點前往同一地點收件。如下面範例二(收件公司地點依序為: 4 2 4 1 5 4 3 2 1)所示,雖然司機一一開始就已經在收件地點「1」了,但是他卻不能先把後面第四個登記的公司(地點「1」)郵件先收了再前往第一、第二、或第三個登記收件地點(地點「4」,「2」,「4」)收件。但是如果前三個登記收件的服務是由司機二或三來負責,則司機一就可以在地點「1」收了第四個登記的郵件後再前往後面所登記的地點收件。此外,在某些情況下,不一定每輛車都要收到貨,也就是說,最佳收件方式也有可能是只需出動一或兩輛車去收貨。請寫一個程式來幫「收的快」公司計算每天依預約順序至各收件地點收件的最少總耗油量。

輸入說明 :

輸入檔案第一行有一個整數 m,3 ≤ m ≤ 200,代表「收的快」公司收件的地點數,以1至m之間的整數代號來表示每個地點。接下來的m行(第2到第m+1行),每行有m個整數,代表一個矩陣 D。第 i+1行的第j個整數是D(i, j),D(i, j) 代表司機開車從收件點i到收件點j所需耗油量。最後有一行數串,數串之數字依序為前一天上網登記要求收件的公司地點代號,最多會有1000個收件請求。輸入檔案中任兩個相鄰的整數都以一個空白隔開。
注意:油量矩陣D滿足三角不等式,也就是說 D(i, j) ≤ D(i, k) + D(k, j),1 ≤ i, j, k ≤ m。因此,每輛車前往下一個收件地點時一定是直接前往,不必先繞道至其它地點再抵達下個收件地點。

輸出說明 :

請輸出一個整數,代表收件所需最少總耗油量。

範例輸出說明:

第一組、到每個請求收件地點的司機分別為1 1 1 1 3 3 2 2 2 1,因此司機1只需從起始點1移動到地點3,司機2只需停留在地點2,司機3從起始點3移動到地點4。 

第二組、到每個請求收件地點的司機分別為1 2 1 2 2 1 3 1 3,因此司機1只需從起始點1移動到地點4,再到地點2,司機2從起始點2移動到地點1,再到地點5,司機3只需從起始點3移動到地點1。

範例輸入 :

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
4
0 5 0 6
6 0 5 6
1 6 0 6
1 1 1 0
1 1 1 1 4 4 2 2 2 3
5
0 1 1 1 1
1 0 2 2 2
1 1 0 2 1
2 1 3 0 1
3 2 3 4 0
4 2 4 1 5 4 3 2 1

範例輸出 :

6
5

提示 :

出處 :

文章標籤

和風信使 發表在 痞客邦 留言(0) 人氣()

 作者  cses (5858)                                            看板  C_and_CPP
 標題  [問題] 關於 xa xb 的猜數字遊戲AI
 時間  Fri Jun 17 23:49:07 2011
───────────────────────────────────────

其實是最近老師開了這個題目給我們

要我們寫出一個簡單的AI來讓電腦跟我們玩 幾A幾B的猜數字遊戲

就是...我們自訂一組數字,而電腦就是隨機產生一組亂數來問我們幾A幾B

我們回答他幾A幾B , 一直到猜出數字 4A 0B 這樣

之前爬文有看到隨機產生1~9亂數這部分有看到一種方法是"增加某數字出現的權重"

想問問這種語法要怎麼寫呢 ?

由於本人是C的無敵新手,只看著課本找到srand()這個亂數函式

想問  那種可以控制亂數出現比例的方法 要怎麼寫...

文章標籤

和風信使 發表在 痞客邦 留言(0) 人氣()

題目:
20110618.jpg

題目的意思應該是輸入123456789
然後就會分別輸出下面的東西
我目前只想到輸出三角形的這個程式碼@@
(輸出的部分先用"*"表示)
可是答案當然不是長這樣= =
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
        int i,j,n=5;
        for(i=1; i<=n; i++) {
                for(j=1; j<=i; j++)
                        printf("*");
                printf("\n");
        }
        system("pause"); return(0);
}

然後我程式學的也不是很好,
剛剛一直把學過的東西在腦理想一遍
不知道要怎樣才能用所學的東西拼出這個程式> <
現在完全屬於卡住的狀態@@
P.S不瞞各位說這是期末作業,然後這題占總成績10%這樣QAQ
有請高手指點Q_Q

程式碼如下,請務必看懂,不懂請留言發問。


文章標籤

和風信使 發表在 痞客邦 留言(0) 人氣()

這個學期將要結束了

我來吧我這學期的所有程式碼貼上來

就當作這半學期課程中的一個紀錄吧


作業一


作業二


作業三



作業四



作業五


作業六


作業七


作業八

文章標籤

和風信使 發表在 痞客邦 留言(0) 人氣()

之前在網路上認識的聯合大學的學弟,說他被要求做一個OOXX的程式,我一時玩心大起,就寫了一個可以用方向鍵操控的O,並希望藉此引導那個學弟寫出足以拿出來炫耀的壓箱寶。

備註:一定要用Dev-C++編譯喔~

俊佑也看一下~李威誼加油。

真的比XX的學弟認真多了 = =


和風信使 發表在 痞客邦 留言(0) 人氣()

  • 這篇文章限定好友觀看。
    若您是好友,登入後即可閱讀。
  • 這篇文章限定好友觀看。
    若您是好友,登入後即可閱讀。

 


這一題是碩一庭瑋學長問我的作業
嘆氣阿~這樣的程式碼要花我兩天的功夫
我的腦袋真的是越來越鈍了
太久沒有練程式
去參加接下來的NCPC都有點心虛
怎麼辦?

下面是這一題的測資檔





和風信使 發表在 痞客邦 留言(0) 人氣()

這是視窗程式設計的作業一
趁題目還很簡單的時候
來給他瘋一下
以後就沒機會這麼玩了@@

話說 寫完整個就超有成就感的說XD 


和風信使 發表在 痞客邦 留言(0) 人氣()

學到新東西總是讓人雀躍不已阿
特別是曾經困擾過我的問題:)

上面這個是個很好玩的小知識
再來的這個
就是我剛剛所講困擾過我許久的問題
就是 scanf("%c",&ca); 會讀取到換行字元的問題
以前在大一的時候上C語言沒學到
沒想到在大二自願去當助教的時候學到了= =
原來有兩種方式可以處理阿
第一種是用 fflush(stdin); //清空緩衝區
第二種方法是在讀取%c之前加一個空格
scanf("_%c",&ca); // 要在那個底線的位置空格
學到這個用法我還是比較高興的
因為我之前只會笨笨的用C++的cin.get()來讀掉多餘的換行符號= =

還有還有
就是在C++裡面判斷型態的方法


和風信使 發表在 痞客邦 留言(1) 人氣()

  • 這是一篇加密文章,請輸入密碼
  • 密碼提示:asdfghjkl
  • 請輸入密碼: