Yeefan's Blog: 2011-11-06

2011年11月12日星期六

C++ 單源最短路 Dijkstra算法鄰接表實現

直接上代碼：
#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;
int N,M;
int S; //源點
const int MAXN=0x7fffffff;

int Map[1000][100];
int Val[1000][100];
int Abut[1000]={0};
int dist[1000];
bool flag[1000];
int prev[1000];

void init()
{
    scanf("%d %d\n",&N,&M);
    cin>>S;
    for (int i=1;i<=M;i++)
    {
        int a,b,c;
        scanf("%d %d %d\n",&a,&b,&c);
        Abut[a]++;
        Map[a][Abut[a]]=b;
        Val[a][Abut[a]]=c;

        /*
        Abut[b]++;
        Map[b][Abut[b]]=a;
        Val[b][Abut[b]]=c;
        */
    }
    return;
}

void Dijkstra(int S)
{
    for (int i=1;i<=N;i++)
    {
        dist[i]=MAXN;
        flag[i]=false;
        prev[i]=0;
    }

    for (int i=1;i<=Abut[S];i++)
    {
        dist[Map[S][i]]=Val[S][i];
        prev[Map[S][i]]=S;
    }

    dist[S]=0;
    flag[S]=1;

    for (int i=2;i<=N;i++)
    {
        long long tmp=MAXN;
        int u=S;
        for(int j=1;j<=N;j++)
        {
            if( (!flag[j]) && dist[j]<tmp )
            {
                u=j;
                tmp=dist[j];
            }
        }
        flag[u]=1;

        for (int j=1;j<=Abut[u]; j++)
        {
            if ( (!flag[Map[u][j]]))
            {
                long long newdist=dist[u]+Val[u][j];
                if(newdist<dist[Map[u][j]])
                {
                    dist[Map[u][j]]=newdist;
                    prev[Map[u][j]]=u;
                }
            }
        }
    }
}

int main()
{
    freopen("d.in","r",stdin);
    freopen("d.out","w",stdout);
    init();
    Dijkstra(S);
    int E; //目標點
    cin>>E;

    for (int i=1;i<=N;i++)
        cout<<dist[i]<<" ";
    cout<<endl;
    cout<<dist[E]<<endl;
    return 0;
}

2011年11月11日星期五

C++ 較快速的gcd函數

以前學歐幾里德(Euclid)的輾轉相除算法，還膜拜了很長時間。現在，發現，位運算更快！

直接上程序：
    int gcd(int a,int b)
   {
while(b^=a^=b^=a%=b);
          return a;
   }

雖然很簡單，但是看不懂！！！跪求大牛指教！！

感謝czb大牛給我提供這個函數。

各種字符串Hash函數比較

本文轉載自：http://www.byvoid.com/blog/string-hash-compare/
轉載請註明出處。

常用的字符串Hash函数还有ELFHash，APHash等等，都是十分简单有效的方法。这些函数使用位运算使得每一个字符都对最后的函数值产生影响。另外还有以MD5和SHA1为代表的杂凑函数，这些函数几乎不可能找到碰撞。
常用字符串哈希函数有BKDRHash，APHash，DJBHash，JSHash，RSHash，SDBMHash，PJWHash，ELFHash等等。对于以上几种哈希函数，我对其进行了一个小小的评测。

Hash函数	数据1	数据2	数据3	数据4	数据1得分	数据2得分	数据3得分	数据4得分	平均分
BKDRHash	2	0	4774	481	96.55	100	90.95	82.05	92.64
APHash	2	3	4754	493	96.55	88.46	100	51.28	86.28
DJBHash	2	2	4975	474	96.55	92.31	0	100	83.43
JSHash	1	4	4761	506	100	84.62	96.83	17.95	81.94
RSHash	1	0	4861	505	100	100	51.58	20.51	75.96
SDBMHash	3	2	4849	504	93.1	92.31	57.01	23.08	72.41
PJWHash	30	26	4878	513	0	0	43.89	0	21.95
ELFHash	30	26	4878	513	0	0	43.89	0	21.95

其中数据1为100000个字母和数字组成的随机串哈希冲突个数。数据2为100000个有意义的英文句子哈希冲突个数。数据3为数据1的哈希值与 1000003(大素数)求模后存储到线性表中冲突的个数。数据4为数据1的哈希值与10000019(更大素数)求模后存储到线性表中冲突的个数。
经过比较，得出以上平均得分。平均数为平方平均数。可以发现，BKDRHash无论是在实际效果还是编码实现中，效果都是最突出的。APHash也是较为优秀的算法。DJBHash,JSHash,RSHash与SDBMHash各有千秋。PJWHash与ELFHash效果最差，但得分相似，其算法本质是相似的。
在信息修竞赛中，要本着易于编码调试的原则，个人认为BKDRHash是最适合记忆和使用的。
BYVoid原创，欢迎建议、交流、批评和指正。
附：各种哈希函数的C语言程序代码

unsigned int SDBMHash(char *str)
{
 unsigned int hash = 0;
 
 while (*str)
 {
  // equivalent to: hash = 65599*hash + (*str++);
  hash = (*str++) + (hash << 6) + (hash << 16) - hash;
 }
 
 return (hash & 0x7FFFFFFF);
}
 
// RS Hash Function
unsigned int RSHash(char *str)
{
 unsigned int b = 378551;
 unsigned int a = 63689;
 unsigned int hash = 0;
 
 while (*str)
 {
  hash = hash * a + (*str++);
  a *= b;
 }
 
 return (hash & 0x7FFFFFFF);
}
 
// JS Hash Function
unsigned int JSHash(char *str)
{
 unsigned int hash = 1315423911;
 
 while (*str)
 {
  hash ^= ((hash << 5) + (*str++) + (hash >> 2));
 }
 
 return (hash & 0x7FFFFFFF);
}
 
// P. J. Weinberger Hash Function
unsigned int PJWHash(char *str)
{
 unsigned int BitsInUnignedInt = (unsigned int)(sizeof(unsigned int) * 8);
 unsigned int ThreeQuarters = (unsigned int)((BitsInUnignedInt  * 3) / 4);
 unsigned int OneEighth  = (unsigned int)(BitsInUnignedInt / 8);
 unsigned int HighBits   = (unsigned int)(0xFFFFFFFF) << (BitsInUnignedInt - OneEighth);
 unsigned int hash    = 0;
 unsigned int test    = 0;
 
 while (*str)
 {
  hash = (hash << OneEighth) + (*str++);
  if ((test = hash & HighBits) != 0)
  {
   hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));
  }
 }
 
 return (hash & 0x7FFFFFFF);
}
 
// ELF Hash Function
unsigned int ELFHash(char *str)
{
 unsigned int hash = 0;
 unsigned int x = 0;
 
 while (*str)
 {
  hash = (hash << 4) + (*str++);
  if ((x = hash & 0xF0000000L) != 0)
  {
   hash ^= (x >> 24);
   hash &= ~x;
  }
 }
 
 return (hash & 0x7FFFFFFF);
}
 
// BKDR Hash Function
unsigned int BKDRHash(char *str)
{
 unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
 unsigned int hash = 0;
 
 while (*str)
 {
  hash = hash * seed + (*str++);
 }
 
 return (hash & 0x7FFFFFFF);
}
 
// DJB Hash Function
unsigned int DJBHash(char *str)
{
 unsigned int hash = 5381;
 
 while (*str)
 {
  hash += (hash << 5) + (*str++);
 }
 
 return (hash & 0x7FFFFFFF);
}
 
// AP Hash Function
unsigned int APHash(char *str)
{
 unsigned int hash = 0;
 int i;
 
 for (i=0; *str; i++)
 {
  if ((i & 1) == 0)
  {
   hash ^= ((hash << 7) ^ (*str++) ^ (hash >> 3));
  }
  else
  {
   hash ^= (~((hash << 11) ^ (*str++) ^ (hash >> 5)));
  }
 }
 
 return (hash & 0x7FFFFFFF);
}

[廣度優先搜索]NOIP模擬題：傳話 message 解題報告

[問題描述]

興趣小組的同學來自各個學校，爲了增加友誼，晚會上又進行了一個傳話遊戲，如果 a 認識 b ，那麼 a 收到某個消息，就會把這個消息傳給 b ，以及所有 a 認識的人。

如果 a 認識 b ， b 不一定認識 a 。

所有人從 1 到 n 編號，給出所有“認識”關係，問如果 i 發佈一條新消息，那麼會不會經過若干次傳話後，這個消息傳回給了 i ， 1<=i<=n 。

[輸入文件]

輸入文件 message.in 中的第一行是兩個數 n(n<1000) 和 m(m<10000) ，兩數之間有一個空格，表示人數和認識關係數。

接下來的 m 行，每行兩個數 a 和 b ，表示 a 認識 b 。 1<=a, b<=n 。認識關係可能會重複給出，但一行的兩個數不會相同。

[輸出文件]

輸出文件 message.out 中一共有 n 行，每行一個字符 T 或 F 。第 i 行如果是 T ，表示 i 發出一條新消息會傳回給 i ；如果是 F ，表示 i 發出一條新消息不會傳回給 i 。

[輸入樣例]

4 6

1 2

2 3

4 1

3 1

1 3

2 3

[輸出樣例]

【解題報告】

直接廣度優先搜索即可。

深度優先搜索只能過4組數據。

每一次bfs時間複雜度為O(n)，所以n次總時間複雜度O(n^2) 。

【我的代碼】

#include <cstdlib>
#include <cstdio>
#include <iostream>
using namespace std;
int N;
int M;
int Mat[1001][1001];
int Abut[1001]={0};

void init()
{
    scanf("%d %d\n",&N,&M);

    int a,b;
    for (int i=1;i<=M;i++)
    {
        scanf("%d %d\n",&a,&b);
        Mat[a][++Abut[a]]=b;
    }
}

bool bfs(int S)
{
    int big=1;
    int sma=0;
    int Q[1001]={0};
    bool used[2001]={false};
    Q[0]=S;
    while(sma<=big)
    {
        if(Q[sma]==S && sma!=0)
            return true;
        for (int i=1;i<=Abut[Q[sma]];i++)
        {
            if(used[Mat[Q[sma]][i]])
                continue;
            Q[big++]=Mat[Q[sma]][i];
            used[Mat[Q[sma]][i]]=true;
        }
        sma++;
    }
    return false;
}

int main()
{
    freopen("messagez.in","r",stdin);
    freopen("messagez.out","w",stdout);
    init();
    for (int i=1;i<=N;i++)
    {
        if(bfs(i))
            cout<<"T"<<endl;
        else
            cout<<"F"<<endl;
    }
    return 0;
}

在此留言者NOIP2011必過！！！！！

我先沙發一下！！！

NOIP2011
过过过过过过过过过过过过过过过过过过过
过过过过过过过过过过过过过过过过过过过
过过過过过过过過過過過過過过过过过过过
过过过過过过过過过过过过過过过过过过过
过过过過过过过過過過過过過过过过过过过
过过过过过过过過过过過过過过过过过过过
过过过过过过過過過過過過過過過过过过过
过過過過过过過过过过过过过过過过过过过
过过过過过过過过過過過過过过過过过过过
过过过過过过過过過过过過过过過过过过过
过过过過过过過过過過過過过过過过过过过
过过过過过过過过过过过过过过過过过过过
过过过過过过過过过过过过過过過过过过过
过过过過过过過过过过过过过過过过过过过
过过過过過过过过过过过过过过过过过过过
过過过过过過過過過過過過過過過過过过过
过过过过过过过过过过过过过过过过过过过
过过过过过过过过过过过过过过过过过过过

[基本練習][模擬]NOIP模擬題：吉祥數 ghilie 解題報告

[問題描述]

爲了迎接聖誕，信息學興趣小組的同學在輔導老師的帶領下，舉辦了一個盛大的晚會，晚會的第一項內容是做遊戲：猜數。老師給每位同學發一張卡片，每張卡片上都有一個編號 (此編號爲非負數，且小於255)，每個編號互不相同。老師制定了以下的遊戲規則：第一輪，每位同學將自己卡片上編號的各位數字進行平方後再相加得到一組新數，編號在這組新數中出現的同學淘汰出局，第二輪，餘下的同學再將編號的各位數字進行立方相加得到一組新數，編號在這組新數中出現的同學再淘汰出局，第三輪，餘下的同學再將編號的各位數字進行4次方相加得到一組新數，編號在這組新數中出現的同學再淘汰出局，……，以此類推，經過n輪後，仍留下來的同學，將獲得聖誕特別禮物，卡片上的數即爲2011年吉祥數。(假定班級人數不超過200人)

[輸入文件]

輸入文件 ghillie .in 有兩行，第1行爲1個正整數n(n<8)，表示有n輪遊戲,第二行是卡片上互不相同的編號。

輸出：剩下來的各個吉祥數，按從小到大順序輸出，每兩個數之間有一個空格。

[輸出文件]

輸出文件 ghillie .out 是 1 行，爲剩下來的各個吉祥數，按從小到大順序輸出，每兩個數之間有一個空格。

[輸入樣例]

24 123 2 12 20 14 4 6 36 72

[輸出樣例]

2 6 12 24 72 123

【分析】

模擬即可。只要讀清題就不會錯，注意最後一個數不剩的情況。

【我的代碼】

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

int N;
int M=0;
int Time=2;
int A[201];

void init()
{
    scanf("%d\n",&N);

    int tmp;
    while(cin>>tmp)
    {
        A[++M]=tmp;
    }

    return;
}

int sq(int num)
{
    int rs=1;
    for (int i=1;i<=Time;i++)
        rs*=num;
    return rs;
}

int GetTot(int num)
{
    int rs=0;
    int tmp[100]={0};
    int top=0;
    while(num)
    {
        tmp[++top]=num%10;
        num/=10;
    }
    for (int i=1;i<=top;i++)
        rs+=sq(tmp[i]);
    return rs;
}

int cmp(const void *a,const void *b)
{
    return *((int *)a)-*((int *)b);
}

void works()
{
    int lun=0;
    while(lun<N)
    {
        int tmp[201]={0};
        for (int i=1;i<=M;i++)
        {
            if(A[i]==-1)
                tmp[i]=-1;
            else
                tmp[i]=GetTot(A[i]);
        }

        for (int i=1;i<=M;i++)
        {
            if(A[i]==-1)
                continue;
            for (int j=1;j<=M;j++)
            {
                if(tmp[j]==-1)
                    continue;
                if(tmp[j]==A[i])
                {
                    A[i]=-1;
                    break;
                }
            }
        }
        Time++;
        lun++;
    }

    int Tmp[201]={0};
    int top=0;
    for (int i=1;i<=M;i++)
    {
        if(A[i]==-1)
            continue;
        Tmp[++top]=A[i];
    }

    if(top==0)
        return;

    qsort(Tmp+1,top,sizeof(Tmp[0]),cmp);

    for (int i=1;i<top;i++)
        cout<<Tmp[i]<<" ";

    cout<<Tmp[top]<<endl;

    return;
}

int main()
{
    freopen("ghillie.in","r",stdin);
    freopen("ghillie.out","w",stdout);
    init();
    works();
    return 0;
}

2011年11月10日星期四

[動態規劃]BYVoid魔獸世界模擬題 Stage.1 靈魂分流藥劑 soultap 解題報告

【問題描述】

幽暗城皇家鍊金師赫布瑞姆剛剛發明瞭一種用來折磨戰俘的新型藥劑，這種藥劑被稱爲靈魂分流藥劑。靈魂分流藥劑的妙處在於能夠給戰俘帶來巨大的痛苦，但是卻不會讓戰俘死去。這種藥劑中包含了一些治療的成分，所以即使戰俘想自盡，也會被救活。用這種求生不得，求死不能的感覺，來對付反對希爾瓦娜斯女王的狂徒們，實在是太美妙了。當然，靈魂分流藥劑要限定在一個用量範圍之內，過少會達不到效果，而過多會直接殺了戰俘。

最近，我們抓獲了一個來自暴風城的探子，他掌握了我們的許多重要情報。希爾瓦娜斯女王命令你用最痛苦的手段折磨他。你從你的導師，靈魂分流藥劑的發明者——皇家鍊金師赫布瑞姆那裏獲得了N瓶藥劑。每瓶按照藥性的不同裝在M個箱子中。每瓶藥劑都有一個規格：對服用者造成的肉體傷害w，對服用者造成的意志折磨v，所屬的箱子t，和對服用者造成的痛苦值p。

據我們測試，那個暴風城探子的生命值爲A，意志力爲B。你要從每個箱子中最多拿取1瓶藥劑餵給他。注意，餵給他的藥劑造成的總肉體傷害不能超過他的生命值A，否則他會死去，總意志折磨不能超過他的意志力B，否則他會精神崩潰，我們沒有必要給一個精神崩潰的傻瓜製造那麼多痛苦。在不讓他死去或者精神崩潰的前提下，你要儘可能多的給他製造痛苦，你能解決這個問題嗎？

輸入格式

第1行：四個整數N,M,A,B，M個箱子的編號爲1..M。

第2行至第N+1行：第i+1行四個整數w,v,t,p表示第i瓶藥劑的肉體傷害，意志折磨，所屬箱子的編號，和造成的痛苦值。

輸出格式

第1行：一個整數，表示能夠造成的最大的痛苦值。

樣例輸入

5 3 20 20

5 10 1 200

10 5 1 100

8 11 2 56

10 10 2 50

5 5 3 100

樣例輸出

300

數據規模

對於30%的數據

N<=30

M<=5

對於100%的數據

N<=100

M<=10

A,B<=100

【分析】

經典的動態規劃，0/1背包問題。

以每個箱子為階段劃分狀態，而每個箱子又是一個最優子問題。

狀態設定

Box[i].W[j]：第i個箱子中第j件物品的肉體傷害

Box[i].V[j]：第i個箱子中第j件物品的意志折磨

Box[i].P[j]：第i個箱子中第j件物品的傷害值

Box[i].num：第i個箱子中藥劑的總數

F[k][i][j] ：對於前k個箱子，當探子生命值為i，意志力為j時的最大傷害值

邊界條件：

F[0][i][j]=0

狀態轉移方程：

F[k][i][j]= Max{ Max{F[k-1][i-Box[k].W[m]][j-Box[k].V[m]]+Box[k].P[m]} , F[k-1][i][j] } (1<=m<=Box[k].num)

目標狀態：

F[M][A][B]

【我的代碼】

#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;
int F[11][101][101];

class BOX
{
public:
    int num;
    int W[101];
    int V[101];
    int P[101];
    BOX()
    {
        num=0;
    }
}Box[11];
int N,M;
int A,B;

void init()
{
    scanf("%d %d %d %d\n",&N,&M,&A,&B);
    int w,v,t,p;
    for (int i=1;i<=N;i++)
    {
        scanf("%d %d %d %d\n",&w,&v,&t,&p);
        Box[t].num++;
        Box[t].W[Box[t].num]=w;
        Box[t].V[Box[t].num]=v;
        Box[t].P[Box[t].num]=p;
    }
    return;
}

void dynamic()
{
    int tmp;
    for (int i=1;i<=A;i++)
        for (int j=1;j<=B;j++)
                F[0][i][j]=0;

    for (int k=1;k<=M;k++)
    {
        for(int i=1;i<=A;i++)
        {
            for (int j=1;j<=B;j++)
            {
                int Max=0;
                for (int m=1;m<=Box[k].num;m++)
                {
                    if(i-Box[k].W[m]>=0 && j-Box[k].V[m]>=0)
                    {
                        tmp=F[k-1][i-Box[k].W[m]][j-Box[k].V[m]]+Box[k].P[m];
                        if(tmp>Max)
                            Max=tmp;
                    }
                }
                if (F[k-1][i][j]>Max)
                    Max=F[k-1][i][j];
                F[k][i][j]=Max;
            }
        }
    }
    printf("%d\n",F[M][A][B]);
}

int main()
{
    freopen("soultap.in","r",stdin);
    freopen("soultap.out","w",stdout);
    init();
    dynamic();
    return 0;
}

【評測結果】

正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...
编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	10	0.000 s	724 KB	0
2	正确	10	0.006 s	724 KB	0
3	正确	10	0.001 s	724 KB	0
4	正确	10	0.001 s	724 KB	0
5	正确	10	0.005 s	724 KB	0
6	正确	10	0.006 s	724 KB	0
7	正确	10	0.006 s	724 KB	0
8	正确	10	0.006 s	724 KB	0
9	正确	10	0.006 s	724 KB	0
10	正确	10	0.006 s	724 KB	0

运行完成
运行时间 0.042 s
平均内存使用 724 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!

[字符串處理][字典樹]NOIP模擬題：好感統計 star 解題報告

【问题描述】

在LazyCat同学的影响下，Roby同学开始听韩国的音乐，并且越来越喜欢H.o.T，尤其喜欢安七炫和Tony，可是，爱学习爱思考的Roby同学想，如果以后喜欢的韩星越来越多怎么办呢？Roby怎么知道Roby最喜欢谁呢（Roby都不知道谁知道呢。。。。）？
于是，Roby同学求助于你。
Roby首先会给你一张表，表上是所有他认识的韩星的名字，一开始他对所有韩星的好感度都为0。
然后Roby会告诉你一些他对某个韩星的好感度变化。
最后，请按照Roby对他们好感从大到小的顺序输出他们。

[输入]
第一行一个个数N，表示Roby知道的韩星数目。
后面有N行，表示每一个Roby认识的韩星的名字。
再下面一行一个数K。
接下来2*K行，每两行为一组，上面一行为韩星的名字Name，下面一行为好感度变化量Change。

[输出]
N*2行，依据韩星们的受Roby好感度从大到小的顺序输出，每两行为一组，第一行输出韩星的名字，第二行输出受Roby的好感度。
[样例输入]
3
HhIsaGay
ZcLoveStudy
OneBlueOne
5
ZcLoveStudy
100
OneBlueOne
8888
ZcLoveStudy
20
OneBlueOne
8888
HhIsaGay
-1000

[样例输出]
OneBlueOne
17776
ZcLoveStudy
120
HhIsaGay
-1000
[数据范围]
对于20%的数据，保证N<=100，K<=100.
对于40%的数据，保证N<=10000，K<=30000.
对于100%的数据，保证N<=100000　-8888<=Change<=8888　K<=100000.
[时限]
2S

【分析】
字符串處理，建議用scanf讀入，方便快速。
我用了字典樹，用來記錄每個人在數組裡的編號。最後，對數組進行快速排序，輸出人名即可和好感度即可。

【我的代碼】
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;
int N,K;

const int sonnum=127;
const char base=0;
struct Trie
{
    bool isStr;
    int Num;
    struct Trie *son[sonnum];
};

Trie *Tree;
int Suki[100001];

class NUM
{
public:
    int n;
    int Suki;
    char str[100];
    NUM()
    {
        Suki=0;
    }
}Su[100001];

int top=0;

Trie *NewTrie()
{
    Trie *temp=new Trie;
    temp->isStr=false;
    temp->Num=0;
    for (int i=0;i<sonnum;i++)
        temp->son[i]=NULL;
    return temp;
}

void Insert(Trie *pnt,char *s,int len)
{
    top++;
    Su[top].n=top;
    Su[top].Suki=0;
    for (int i=0;i<len;i++)
        Su[top].str[i]=s[i];

    Trie *temp=pnt;
    for (int i=0;i<len;i++)
    {
        if (temp->son[s[i]-base]==NULL)
            temp->son[s[i]-base]=NewTrie();
        temp=temp->son[s[i]-base];
    }
    temp->isStr=true;
    temp->Num=top;
}

void check(Trie *pnt,char *s,int len,int change)
{
    Trie *temp=pnt;
    for (int i=0;i<len;i++)
        temp=temp->son[s[i]-base];
    Su[temp->Num].Suki+=change;
}

int cmp(const void *a,const void *b)
{
    class NUM *c=(class NUM *)a;
    class NUM *d=(class NUM *)b;
    return d->Suki-c->Suki;
    return 0;
}

void init()
{
    Tree=NewTrie();
    char str[100];
    scanf("%d\n",&N);
    for (int i=1;i<=N;i++)
    {
        memset(str,'\0',sizeof(str));
        scanf("%[^\n]\n",&str);
        Insert(Tree,str,strlen(str));
    }
    scanf("%d\n",&K);
    int tmp;
    for (int i=1;i<=K;i++)
    {
        memset(str,'\0',sizeof(str));
        scanf("%[^\n]\n",&str);
        scanf("%d\n",&tmp);
        check(Tree,str,strlen(str),tmp);
    }
    qsort(Su+1,top,sizeof(Su[0]),cmp);

    for (int i=1;i<=top;i++)
    {
        printf("%s\n%d\n",Su[i].str,Su[i].Suki);
    }
}

int main()
{
    freopen("star.in","r",stdin);
    freopen("star.out","w",stdout);
    init();
    return 0;
}

【評測結果】

正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...
编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	10	0.002 s	11208 KB	0
2	正确	10	0.002 s	11208 KB	0
3	正确	10	0.035 s	11208 KB	0
4	正确	10	0.035 s	11208 KB	0
5	正确	10	0.123 s	11208 KB	0
6	正确	10	0.127 s	11208 KB	0
7	正确	10	0.123 s	11208 KB	0
8	正确	10	0.129 s	11208 KB	0
9	正确	10	0.130 s	11208 KB	0
10	正确	10	0.135 s	11208 KB	0

运行完成
运行时间 0.839 s
平均内存使用 11208 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!

[數值遞推]OI練習題：整理牙刷 put 解題報告

【問題描述】

衆所周知，XW同學早晨起來是要刷牙的。

XW同學有 N 支牙刷，又有 N 個牙刷套 , 開始的時候，一支牙刷對應放在一個牙刷套中。可是有一天，XW同學把所有牙刷套裏的牙刷都拿出來，玩了一會兒，他又要把所有的牙刷都放回去。可是，他忽然一想，我可不可以使得沒有任何一支牙刷放回它原來的牙刷套裏面呢 ?

XW同學努力試了很久，卻一直沒有成功過一次。於是他斷定這個要求是無法達成的，你怎麼認爲的呢 ?

【輸入文件】

輸入文件 put.in 只包括一個整數 N ，表示牙刷和牙刷套的總數。

【輸出文件】

輸出文件 put.out ，如果存在滿足要求的方法，輸出放法方案總數 L 。因爲方案總數可能比較大，所以你可以將答案 Mod 1206 後再輸出。如果不存在滿足要求的方法，則輸出 "No Solution!”

【樣例輸入】

【樣例輸出】

【數據範圍】

對於 40 ％的數據，保證 N ≤ 9

對於 100 ％的數據，保證 N ≤ 100000

【分析】

就是一個公式，沒什麼好說的。

F[1]=0;

F[2]=1;

F[i]=(i-1)*(F[i-1]+F[i-2]) (i>=3)

注意同餘原理的應用。

【我的代碼】

#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;
unsigned long long F[100001];
int main()
{
    freopen("put.in","r",stdin);
    freopen("put.out","w",stdout);
    int N;
    scanf("%d\n",&N);
    F[1]=0;
    F[2]=1;
    for (int i=3;i<=N;i++)
        F[i]=((i-1)*(F[i-1]+F[i-2]))%1206;
    if(N<2)
        cout<<"No Solution!"<<endl;
    else
        cout<<F[N]<<endl;
    return 0;
}

[動態規劃]USACO Mar08 遊蕩的奶牛 ctravel 解題報告

【題目描述】
奶牛們在被劃分成N行M列(2 <= N <= 100; 2 <= M <= 100)的草地上遊走，試圖找到整塊草地中最美味的牧草。Farmer John在某個時刻看見貝茜在位置(R1, C1)，恰好T (0 < T <= 15)秒後，FJ又在位置(R2, C2)與貝茜撞了正着。FJ並不知道在這T秒內貝茜是否曾經到過(R2, C2)，他能確定的只是，現在貝茜在那裏。

設S爲奶牛在T秒內從(R1, C1)走到(R2, C2)所能選擇的路徑總數，FJ希望有一個程序來幫他計算這個值。每一秒內，奶牛會水平或垂直地移動1單位距離（奶牛總是在移動，不會在某秒內停在它上一秒所在的點）。草地上的某些地方有樹，自然，奶牛不能走到樹所在的位置，也不會走出草地。

現在你拿到了一張整塊草地的地形圖，其中'.'表示平坦的草地，'*'表示擋路的樹。你的任務是計算出，一頭在T秒內從(R1, C1)移動到(R2, C2)的奶牛可能經過的路徑有哪些。

程序名: ctravel

輸入格式:

第1行: 3個用空格隔開的整數：N，M，T

第2..N+1行: 第i+1行爲M個連續的字符，描述了草地第i行各點的情況，保證字符是'.'和'*'中的一個

第N+2行: 4個用空格隔開的整數：R1，C1，R2，以及C2

輸入樣例 (ctravel.in):

4 5 6

...*.

.....

1 3 1 5

輸入說明:

草地被劃分成4行5列，奶牛在6秒內從第1行第3列走到了第1行第5列。

輸出格式:

第1行: 輸出S，含義如題中所述

輸出樣例 (ctravel.out):

輸出說明:

奶牛在6秒內從(1,3)走到(1,5)的方法只有一種（繞過她面前的樹）。

【分析】

動態規劃。可以用加法原理，這和”過河卒“類似，動態規劃中並不作決策。

狀態設定

F[k][i][j]：前 k秒走到(i,j)的路徑數。

G[i][j]=1( (i,j)是草地 )，0（(i,j)是樹）

邊界條件：

F[0][R1][C1]=1;

狀態轉移方程：

F[k][i][j]+=Sum{F[k-1][i+1][j]*G[i+1][j],F[k-1][i][j+1]*G[i][j+1],F[k-1][i-1][j]*G[i-1][j],F[k-1][i][j-1]*G[i][j-1]}

目標狀態：

F[T][R2][C2]

【我的代碼】

#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;
int F[16][101][101];
int G[101][101];
int N,M,T;
int R1,C1;
int R2,C2;

void init()
{
    scanf("%d %d %d\n",&N,&M,&T);
    char c;
    for(int i=1;i<=N;i++)
    {
        for (int j=1;j<=M;j++)
        {
            if(j==M)
                scanf("%c\n",&c);
            else
                scanf("%c",&c);
            if(c=='.')
                G[i][j]=1;
            else
                G[i][j]=0;
        }
    }
    scanf("%d %d %d %d",&R1,&C1,&R2,&C2);
    F[0][R1][C1]=1;
}

void dynamic()
{
    int k=0;
    for (k=1;k<=T;k++)
    {
        for (int i=1;i<=N;i++)
        {
            for (int j=1;j<=M;j++)
            {
                if(!G[i][j])
                    continue;
                F[k][i][j]+=F[k-1][i+1][j]*G[i+1][j];
                F[k][i][j]+=F[k-1][i][j+1]*G[i][j+1];
                F[k][i][j]+=F[k-1][i-1][j]*G[i-1][j];
                F[k][i][j]+=F[k-1][i][j-1]*G[i][j-1];
            }
        }
    }
    printf("%d\n",F[T][R2][C2]);
}

int main()
{
    freopen("ctravel.in","r",stdin);
    freopen("ctravel.out","w",stdout);
    init();
    dynamic();
    return 0;
}

評測結果：

正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...
编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	10	0.014 s	948 KB	0
2	正确	10	0.002 s	948 KB	0
3	正确	10	0.001 s	948 KB	0
4	正确	10	0.001 s	948 KB	0
5	正确	10	0.007 s	948 KB	0
6	正确	10	0.001 s	948 KB	0
7	正确	10	0.004 s	948 KB	0
8	正确	10	0.001 s	948 KB	0
9	正确	10	0.006 s	948 KB	0
10	正确	10	0.004 s	948 KB	0

运行完成
运行时间 0.040 s
平均内存使用 568 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!

2011年11月9日星期三

[堆排序]NOIP2004 合併果子 fruit 堆排序算法(Heap)

具體的題目和解析的就不再貼出來啦，請看我以前的文章。

【小根堆算法一：快速排序建堆 0.053s】
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int N;
int top;
int A[20000];

int cmp(const void *a,const void *b)
{
    return *((int *)a)-*((int *)b);
}

void init()
{
    scanf("%d\n",&N);
    for (int i=1;i<=N;i++)
        scanf("%d",&A[i]);
    qsort(A+1,N,sizeof(A[0]),cmp);
    top=N;
    return;
}

void swap(int x,int y)
{
    int tmp;
    tmp=A[x];
    A[x]=A[y];
    A[y]=tmp;
}

void Insert(int x)
{
    A[++top]=x;
    int k=top;
    while(k>1 && A[k]<A[k>>1])
    {
        swap(k,k>>1);
        k=k>>1;
    }
}

void Delete(int x)
{
    int tmp;
    A[x]=A[top--];
    int k=x;
    while(k<<1<=top)
    {
        bool flag=true;
        tmp=k<<1;
        if(tmp+1<=top)
            if (A[tmp]>A[tmp+1])
                tmp++;
        if(A[k]>A[tmp])
        {
            flag=false;
            swap(k,tmp);
        }
        if(flag)
            break;
        k=tmp;
    }
}

void greedy()
{
    int S=0;
    int T;

    while(top>1)
    {
        int tmp=2;
        if(A[2]>A[3] && top>2)
            tmp=3;
        T=A[1]+A[tmp];
        S+=T;
        Delete(1);
        Delete(1);
        Insert(T);
    }
    printf("%d\n",S);
    return;
}

int main()
{
    freopen("fruit.in","r",stdin);
    freopen("fruit.out","w",stdout);
    init();
    greedy();
    return 0;
}
評測結果：
正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...
编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	10	0.000 s	352 KB	0
2	正确	10	0.001 s	352 KB	0
3	正确	10	0.001 s	352 KB	0
4	正确	10	0.004 s	352 KB	0
5	正确	10	0.004 s	352 KB	0
6	正确	10	0.009 s	352 KB	0
7	正确	10	0.008 s	352 KB	0
8	正确	10	0.009 s	352 KB	0
9	正确	10	0.008 s	352 KB	0
10	正确	10	0.008 s	352 KB	0

运行完成
运行时间 0.053 s
平均内存使用 352 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!

【小根堆算法二：向下維護建堆 0.037s】
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int N;
int top;
int A[20000];

int cmp(const void *a,const void *b)
{
    return *((int *)a)-*((int *)b);
}

void downshift(int i)
{
    int j,x;
    x=A[i];
    j=i<<1;
    while (j<=N)
    {
        if (A[j]>A[j+1] && j+1<=N)
            j++;
        if (x>A[j])
        {
            A[i]=A[j];
            i=j;
            j=j<<1;
        }
        else
            break;
    }
    A[i]=x;
}

void init()
{
    scanf("%d\n",&N);
    for (int i=1;i<=N;i++)
    {
        scanf("%d",&A[i]);
    }

    for (int i=N/2;i>=1;i--)
        downshift(i);
    top=N;
    return;
}

void swap(int x,int y)
{
    int tmp;
    tmp=A[x];
    A[x]=A[y];
    A[y]=tmp;
}

void Insert(int x)
{
    A[++top]=x;
    int k=top;
    while(k>1 && A[k]<A[k>>1])
    {
        swap(k,k>>1);
        k=k>>1;
    }
}

void Delete(int x)
{
    int tmp;
    A[x]=A[top--];
    int k=x;
    while(k<<1<=top)
    {
        bool flag=true;
        tmp=k<<1;
        if(tmp+1<=top)
            if (A[tmp]>A[tmp+1])
                tmp++;
        if(A[k]>A[tmp])
        {
            flag=false;
            swap(k,tmp);
        }
        if(flag)
            break;
        k=tmp;
    }
}

void greedy()
{
    int S=0;
    int T;

    while(top>1)
    {
        int tmp=2;
        if(A[2]>A[3] && top>2)
            tmp=3;
        T=A[1]+A[tmp];
        S+=T;
        Delete(1);
        Delete(1);
        Insert(T);
    }
    printf("%d\n",S);
    return;
}

int main()
{
    freopen("fruit.in","r",stdin);
    freopen("fruit.out","w",stdout);
    init();
    greedy();
    return 0;
}

評測結果：
正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...
编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	10	0.000 s	352 KB	0
2	正确	10	0.001 s	352 KB	0
3	正确	10	0.001 s	352 KB	0
4	正确	10	0.003 s	352 KB	0
5	正确	10	0.003 s	352 KB	0
6	正确	10	0.006 s	352 KB	0
7	正确	10	0.006 s	352 KB	0
8	正确	10	0.006 s	352 KB	0
9	正确	10	0.006 s	352 KB	0
10	正确	10	0.006 s	352 KB	0

运行完成
运行时间 0.037 s
平均内存使用 352 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!

[動態規劃]USACO Nov10 拜訪奶牛 vacation 解題報告

【題目描述】
經過了幾周的辛苦工作,貝茜終於迎來了一個假期.作爲奶牛羣中最會社交的牛,她希望去拜訪N(1<=N<=50000)個朋友.這些朋友被標號爲1..N.這些奶牛有一個不同尋常的交通系統,裏面有N-1條路,每條路連接了一對編號爲C1和C2的奶牛(1 <= C1 <= N; 1 <= C2 <= N; C1<>C2).這樣,在每一對奶牛之間都有一條唯一的通路.

FJ希望貝茜儘快的回到農場.於是,他就指示貝茜,如果對於一條路直接相連的兩個奶牛,貝茜只能拜訪其中的一個.當然,貝茜希望她的假期越長越好,所以她想知道她可以拜訪的奶牛的最大數目.

輸入格式:

第1行:單獨的一個整數N

第2..N行:每一行兩個整數,代表了一條路的C1和C2.

樣例輸入(vacation.in):

6 2

3 4

2 3

1 2

7 6

5 6

輸入說明:

貝茜認識7只奶牛,其中6和2相連,3和4相連,等等...最後形成這麼一個網絡:

1--2--3--4

5--6--7

輸出格式:

第一行:單獨的一個整數,代表了貝茜可以拜訪的奶牛的最大數目.

樣例輸出(vacation.out):

輸出解釋:

{1,3,5,7}或{1,4,5,7}或{2,4,5,7}

【數據範圍】

40%數據 n<=100

100%數據 n<=50000

【分析】

經典的樹形DP，直接遞歸找最優子狀態即可。

F[i][0] :不選第i個節點的最大利潤。

F[i][1] :選第i個節點的最大利潤。

邊界條件：F[i][1=1;

狀態轉移方程：

F[i][0]+=max{ F[x][0] , F[x][1] } (i與x鄰接)

F[i][1]+=F[x][0] (x與i鄰接)

【我的代碼】
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
const int MAXN=50001;
int F[MAXN][2];
int Mat[MAXN][10];
int Abut[MAXN]={0};
bool used[MAXN]={0};
int N;

void init()
{
    scanf("%d\n",&N);

    for (int i=1;i<=N;i++)
        F[i][1]=1;

    int a,b;
    for (int i=1;i<=N-1;i++)
    {
        scanf("%d %d\n",&a,&b);
        Abut[a]++;
        Abut[b]++;
        Mat[a][Abut[a]]=b;
        Mat[b][Abut[b]]=a;
    }
    return;
}

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

void dp(int x)
{
    used[x]=true;
    for (int i=1;i<=Abut[x];i++)
    {
        if(used[Mat[x][i]])
            continue;
        dp(Mat[x][i]);
        F[x][1]+=F[Mat[x][i]][0];
        F[x][0]+=max(F[Mat[x][i]][0],F[Mat[x][i]][1]);
    }
}

int main()
{
    freopen("vacation.in","r",stdin);
    freopen("vacation.out","w",stdout);
    init();
    dp(1);
    printf("%d\n",max(F[1][0],F[1][1]));
    return 0;
}

[動態規劃]NOIP模擬題：火車站飯店（最大利潤） profitz 解題報告

【題目描述】

政府邀請了你在火車站開飯店，但不允許同時在兩個相連的火車站開。任意兩個火車站有且只有一條路徑，每個火車站最多有 50 個和它相連接的火車站。

告訴你每個火車站的利潤，問你可以獲得的最大利潤爲多少？

例如下圖是火車站網絡：

最佳投資方案是 1 ， 2 ， 5 ， 6 這 4 個火車站開飯店可以獲得的利潤爲 90.

【輸入格式】

第一行輸入整數 N(<=100000), 表示有 N 個火車站，分別用 1,2,……..,N 來編號。接下來 N 行，每行一個整數表示每個站點的利潤，接下來 N-1 行描述火車站網絡，每行兩個整數，表示相連接的兩個站點。

【輸出格式】

輸出一個整數表示可以獲得的最大利潤。

【樣例輸入】

4 5

4 6

3 4

1 3

2 3

【樣例輸出】

【分析】

簡單的樹形動態規劃，直接遞歸找最優子問題即可。

F[i][0] :不選第i個節點的最大利潤。

F[i][1] :選第i個節點的最大利潤。

狀態轉移方程：

F[i][0]+=max{ F[x][0] , F[x][1] } (i與x鄰接)

F[i][1]+=Profit[i]+F[x][0] (x與i鄰接)

我同學Paulinsider的解題報告：傳送門

【我的代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
#define max(a,b) a>b?a:b
using namespace std;
const int MAXN=100001;
int N; //N個火車站
int Mat[MAXN][51]; //記錄每個節點與哪些節點相鄰
int Profit[MAXN]; //每個節點的權值（利潤）
int Abut[MAXN]={0}; //記錄與每個節點相鄰的節點的個數
int F[MAXN][2]; //F[i][0]不選i號節點的最大利潤 , F[i][1]選第i號節點的最大利潤
bool used[MAXN]={0};//記錄每個節點是否被用過

void init()
{
    scanf("%d\n",&N);
    for (int i=1;i<=N;i++)
    {
        scanf("%d\n",&Profit[i]);
        F[i][1]=Profit[i];
    }

    int a,b;
    for (int i=1;i<=N-1;i++)
    {
        scanf("%d %d\n",&a,&b);
        Abut[a]++;
        Mat[a][Abut[a]]=b;
        Abut[b]++;
        Mat[b][Abut[b]]=a;
    }
}

void dynamic(int x) //dynamic programming
{
    used[x]=true;
    for (int i=1;i<=Abut[x];i++)
    {
        if( !used[ Mat[x][i] ] )
        {
            dynamic(Mat[x][i]);
            F[x][0]+=max( F[ Mat[x][i] ][0] , F[ Mat[x][i] ][1] );
            F[x][1]+=F[ Mat[x][i] ][0];
        }
    }
}

int main()
{
    freopen("profitz.in","r",stdin);
    freopen("profitz.out","w",stdout);
    init();
    dynamic(1);
    printf("%d\n", max(F[1][0],F[1][1]));
    return 0;
}

訂閱：文章 (Atom)

申請SAE

2011年11月12日 星期六

2011年11月11日 星期五

2011年11月10日 星期四

【问题描述】

2011年11月9日 星期三

2011年11月12日星期六

2011年11月11日星期五

2011年11月10日星期四

2011年11月9日星期三