Ural 1002 1005 1018 1021 1023 1029
==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;
}