This post is written in Chinese. Please consider using Google Translate

==1002== 首先把单词按照规则替换为数字序列，构图，把电话号码的每一位作为一个顶点。增加一个0号顶点。

如果一个单词的数字序列能够匹配电话号码的A到B位，那么我们就在第A-1个顶点和第B+1个顶点上连接一条边，记录形成该边的单词。

求从0号顶点到N号顶点的最短路径，由于是无权图，直接宽搜即可。找到一条从0到N的最短路径，按照最短路径上的边对应的单词输出。

==1005== 动态规划， F[i,j]为前i个石头分为两堆，重量差值为j的状态是否存在

F[i,j]= or { F[i-1,j-W[i]] (j-W[i]>=0) 两堆差值扩大 F[i-1,W[i]+j] (W[i]+j<=MAX) 两堆差值减少但不超越 **F[i-1,W[i]-j] (W[i]-j>=0) 较少一堆超越较多一堆 }

目标结果就是 Ans=i (F[N,i]=true 且 i最小)

==1018== 明显的树形动态规划。首先是建立二叉树，由于上下不确定，我是先以邻接矩阵的方式读取了二叉树，然后以O(N^2)从1号节点开始遍历建立了二叉树。

状态设定 F[i,j]为 在以节点i为根的子树中，保留数量为j的树枝时，留下的最大的苹果数量。 i.left表示i的左子树，i.right表示i的右子树， i.lv表示i连接左子树的边的权值，i.rv表示i连接右子树的边的权值

状态转移方程 F[i,j]=Max { F[i.left,j-1] + i.lv F[i.right,j-1] + i.rv F[i.left,k] + F[i.right.j-k-2] + i.lv + i.rv (k=0..j-2) }

边界条件 F[i,0]=0;

目标解 Ans=F[N,Q]

==1021==

哈希或二分查找。由于数据范围不大，仅仅在2字节整型范围内，我用的是哈希。

由于C++开下标为负的数组还要指针运算，不太方便，我把读入的每一个数都加上了40000。

读入第一组数的时候，每个数a增加40000，设定Hash[a]=true。 读入第二组数，对于每个数a增加40000，如果Hash[90000-a]，则有可以配对的，输出YES。 如果找不到配对的，输出NO。

==1023== 博弈论，数学问题。

首先，假如我们一共有L+1个Button，那么先取者无论怎么取都会输。相似的，假如我们有q*(L+1)个扣子(q是正整数)，则先取者是必败的，也就是后取着是必胜的。

所以对这道题给定的K个Button，我们只需枚举最小的L(2<=L<=K)，使得K能整除(L+1)，后取着一定是必胜的。不存在没有必胜策略！

==1029== 动态规划或者最短路径。

看到这道题我马上就想到了最短路径，但是为了练习动态规划，我还是写了动态规划。

最短路径的方法：

首先把每个房间看成一个顶点，另外建立两个顶点，分表表示起始点和目标点。按照题中所给的三个规则，在顶点之间建立有向边，有向边(a,b)边权为b房间的费用。连接起始点和第一层楼所有顶点，以及顶层楼所有顶点和目标点。求从起始点到目标点的一条最短路径，最后输出路径上的每个点的位置。可能超时，注意优化。推荐使用SPFA算法。

动态规划的方法：

状态设定 F[i,j]表示到达第i层第j个官员的最小费用。

状态转移方程 F[i,j]=Min { F[i-1,j] F[i,j-1] F[i,j+1] } + Cost[i,j]

边界条件 F[1,i]=Cost[1,i]

目标结果 Min{F[N,i]} 从第一层到(N,i)点的路径就是结果。

在状态转移的过程中，对于每层要正向和逆向各扫描一边，分别处理F[i,j-1]和F[i,j+1]，避免后效性。

注意，题上给的数据范围是不对的，我按M最大为100提交时，一直在第6组数据出错，改成和N一样最大为500就过了。

以下是程序

1002

#include <iostream>
#define MAXW 50002
#define MAX 201
#define MAXL MAX

using namespace std;

class tQueue
{
public:
    class linklist
    {
    public:
        linklist* next;
        int value;
        linklist()
        {
            next=0;
            value=0;
        }
    };
    linklist *first,*last;
    int size;
    void ins(int p)
    {
        if (size==0)
            first=last=new linklist;
        else
            last=last->next=new linklist;
        last->value=p;
        size++;
    }
    int pop()
    {
        int rtn=first->value;
        linklist *tfirst=first;
        first=first->next;
        delete tfirst;
        size--;
        return rtn;
    }
    void reset()
    {
        size=0;
        first=last=0;
    }
    tQueue()
    {
        reset();
    }
};

int N,M;
int P[MAX];
int Word[MAX][MAX];
int adjl[MAX][MAX];
int sp[MAX],F[MAX];
char S[MAXL],T[MAXL];
char W[MAXW][MAXL];
tQueue Q;

inline char conv(char a)
{
    switch(a)
    {
        case 'i':case 'j':return '1';
        case 'a':case 'b':case 'c':return '2';
        case 'd':case 'e':case 'f':return '3';
        case 'g':case 'h':return '4';
        case 'k':case 'l':return '5';
        case 'm':case 'n':return '6';
        case 'p':case 'r':case 's':return '7';
        case 't':case 'u':case 'v':return '8';
        case 'w':case 'x':case 'y':return '9';
    }
    return '0';
}

void BFS()
{
    int i,j,k;
    Q.reset();
    Q.ins(0);
    while (Q.size)
    {
        i=Q.pop();
        for (k=1;k<=adjl[i][0];k++)
        {
            j=adjl[i][k];
            if (!sp[j])
            {
                sp[j]=sp[i]+1;
                F[j]=i;
                if (j==N)
                {
                    int L=sp[N];
                    k=0;
                    while (F[j])
                    {
                        i=F[j];
                        sp[++k]=Word[i][j];
                        j=i;
                    }
                    i=0;
                    sp[++k]=Word[i][j];
                    for (;k>1;k--)
                        printf("%s ",W[sp[k]]);
                    printf("%sn",W[sp[k]]);
                    return;
                }    
                Q.ins(j);
            }
        }
    }
    printf("No solution.n");
}

void init()
{
    int i,a,b,L;
    char *c;
    freopen("1002.in","r",stdin);
    freopen("1002.out","w",stdout);
    while (1)
    {
        cin >> S;
        if (S[0]=='-')
            return;
        N=strlen(S);
        for (i=0;i<=N;i++)
            adjl[i][0]=sp[i]=0;
        cin >> M;
        for (i=1;i<=M;i++)
        {
            scanf("%s",W[i]);
            for (L=0;W[i][L];L++)
                T[L]=conv(W[i][L]);
            T[L]=0;
            c=S-1;
            do
            {
                c=strstr(c+1,T);
                if (c)
                {
                    a=c-S;
                    b=a+L;
                    adjl[a][ ++adjl[a][0] ]=b;
                    Word[a][b]=i;
                }
            }
            while (c);
        }
        BFS();
    }
}

int main()
{
    init();
    return 0;
}

1005

#include <iostream>
#define MAX 21
#define ML 200000
using namespace std;

bool F[MAX][ML];
int N,Max=0,Ans;
int W[MAX];

void init()
{
    int i;
    freopen("1005.in","r",stdin);
    freopen("1005.out","w",stdout);
    cin >> N;
    for (i=1;i<=N;i++)
    {
        cin >> W[i];
        Max+=W[i];
    }
    Max=ML-1;
}

void dynamic()
{
    int i,j;
    F[0][0]=true;
    for (i=1;i<=N;i++)
    {
        for (j=0;j<=Max;j++)
        {
            F[i][j]=false;
            if (j-W[i]>=0)
                F[i][j] |= F[i-1][j-W[i]];
            if (W[i]+j<=Max)
                F[i][j] |= F[i-1][W[i]+j];
            if (W[i]-j>=0)
                F[i][j] |= F[i-1][W[i]-j];
        }
    }
    for (i=0;i<=Max;i++)
        if (F[N][i])
        {
            Ans=i;
            break;
        }
}

int main()
{
    init();
    dynamic();
    cout << Ans << endl;
    return 0;
}

1018

#include <iostream>
#define MAX 101

using namespace std;

class node
{
public:
    node *left,*right;
    int lv,rv,id;
    node(int t)
    {
        left=right=0;
        id=t;
        lv=rv=0;
    }
};

node *P[MAX];
int N,M,Ans;
int F[MAX][MAX];
int dis[MAX][MAX];

void Make(int a)
{
    int i;
    for (i=1;i<=N;i++)
    {
        if (dis[a][i]!=-1 && !P[i])
        {
            P[i]=new node(i);
            if (!P[a]->left)
            {
                P[a]->left=P[i];
                P[a]->lv=dis[a][i];
            }
            else
            {
                P[a]->right=P[i];
                P[a]->rv=dis[a][i];
            }
            Make(i);
        }
    }
}

void init()
{
    int i,j,a,b,v;
    freopen("1018.in","r",stdin);
    freopen("1018.out","w",stdout);
    cin >> N >> M;
    for (i=1;i<=N;i++)
    {
        for (j=1;j<=N;j++)
        {
            dis[i][j]=-1;
            F[i][j]=-1;
        }
        P[i]=0;
    }
    for (i=1;i<=N;i++)
    {
        cin >> a >> b >> v;
        dis[a][b]=dis[b][a]=v;
    }
    P[1]=new node(1);
    Make(1);
}

int dp(int i,int j)
{
    if (j==0)
        return 0;

    int t,max=0,k,l,a;

    if (P[i]->right)
    {
        a=P[i]->right->id;
        if (F[a][j-1]==-1)
            F[a][j-1]=dp(a,j-1);
        t=F[a][j-1]+P[i]->rv;
        if (t>max)
            max=t;
    }

    if (P[i]->left)
    {
        a=P[i]->left->id;
        if (F[a][j-1]==-1)
            F[a][j-1]=dp(a,j-1);
        t=F[a][j-1]+P[i]->lv;
        if (t>max)
            max=t;
    }

    for (k=0;k<=j-2;k++)
    {
        t=0;
        l=j-k-2;
        if (P[i]->left)
        {
            a=P[i]->left->id;
            if (F[a][k]==-1)
                F[a][k]=dp(a,k);
            t+=F[a][k];
        }
        if (P[i]->right)
        {
            a=P[i]->right->id;
            if (F[a][l]==-1)
                F[a][l]=dp(a,l);
            t+=F[a][l];
        }
        t+=P[i]->lv + P[i]->rv;
        if (t>max) max=t;
    }
    return max;
}

int main()
{
    init();
    Ans=dp(1,M);
    cout << Ans << endl;
    return 0;
}

1021

#include <iostream>
#define MAX 90000

using namespace std;

bool Hash[MAX],Ans;
int N;

void init()
{
    int i,a;
    freopen("1021.in","r",stdin);
    freopen("1021.out","w",stdout);
    cin >> N;
    for (i=1;i<=N;i++)
    {
        scanf("%d",&a);
        a+=40000;
        Hash[a]=true;
    }
    cin >> N;
    for (i=1;i<=N;i++)
    {
        scanf("%d",&a);
        a+=40000;
        if (Hash[90000-a])
        {
            Ans=true;
            return;
        }
    }
}

int main()
{
    init();
    if (Ans)
        printf("YESn");
    else
        printf("NOn");
    return 0;
}

1023

#include <iostream>
using namespace std;

int K,L;

int main()
{
    freopen("1023.in","r",stdin);
    freopen("1023.out","w",stdout);
    cin >> K;
    for (L=2;L<=K;L++)
    {
        if (K%(L+1)==0)
        {
            cout << L << endl;
            return 0;
        }
    }
    return 0;
}

1029

#include <iostream>
#define MAXN 501
#define MAXM 501
#define INF 10000000000
using namespace std;

typedef struct
{
    int x,y;
}point;

typedef long long Number;

Number F[MAXN][MAXM];
int C[MAXN][MAXM];
Number Ans[MAXM*MAXN],Ac;
point From[MAXN][MAXM];
int M,N;

void init()
{
    int i,j;
    freopen("1029.in","r",stdin);
    freopen("1029.out","w",stdout);
    scanf("%d%d",&M,&N);
    for (i=1;i<=M;i++)
    {
        for (j=1;j<=N;j++)
        {
            scanf("%d",&C[i][j]);
        }
    }
}

void dynamic()
{
    int i,j,min;
    point P;
    for (i=1;i<=N;i++)
        F[1][i]=C[1][i];
    for (i=2;i<=M;i++)
    {
        for (j=1;j<=N;j++)
        {
            F[i][j]=INF;
            if (F[i-1][j]+C[i][j]<F[i][j])
            {
                F[i][j]=F[i-1][j]+C[i][j];
                From[i][j].x=i-1;
                From[i][j].y=j;
            }
            if (j>1 && F[i][j-1]+C[i][j]<F[i][j])
            {
                F[i][j]=F[i][j-1]+C[i][j];
                From[i][j].x=i;
                From[i][j].y=j-1;
            }
        }
        for (j=N-1;j>=1;j--)
        {
            if (F[i][j+1]+C[i][j]<F[i][j])
            {
                F[i][j]=F[i][j+1]+C[i][j];
                From[i][j].x=i;
                From[i][j].y=j+1;
            }
        }
    }
    min=INF;
    for (i=1;i<=N;i++)
    {
        if (F[M][i]<min)
        {
            min=F[M][i];
            P.x=M;
            P.y=i;
        }
    }
    while (P.x)
    {
        Ans[++Ac]=P.y;
        P=From[P.x][P.y];
    }
}

int main()
{
    init();
    dynamic();
    for (;Ac>1;Ac--)
        printf("%d ",Ans[Ac]);
    printf("%dn",Ans[1]);
    return 0;
}