==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;
}
上次修改时间 2017-02-03