题目在这里。
一、报数
【解析】模拟
此题为字符串处理，没有什么技巧，完全考基本功，得分容易，拿满分一定要仔细，只要细心地考虑每一种情况，就可以AC。
二、跑步
【解析】关键点
可以依次枚举除了1点和N点外的每个点（设当前枚举点为i），然后从1点开始DFS，看能不能不经过i点就遍历到N点。如果不能，那i就是关键点。时间复杂度为O（n^2）。
三、装备运输
【解析】动态规划0-1背包
本题为加了一个限制条件的0-1背包，但是解法与传统的0-1背包完全一样。
- 状态：f[i][j][k]表示前i件物品，火车的体积为j、重量为k时的最大火力值；
- 状态转移方程：f[i][j][k] = max(f[i-1][j-V[i]][k-G[i]]+T[i], f[i][j][k])
- 目标状态：f[n][v][g]
- 时间复杂度：O(n*v*g)
由于前i件物品只与i-1件物品有关，于是可以降为二维。
【参考代码】
[cpp]
#include <cstdio>
FILE *fin, *fout;
int V, G, n, max=0;
int f[401][401], t[401], v[401], g[401];
int main(void)
{
fin = fopen(“transport.in”, “r”);
fout = fopen(“transport.out”, “w”);
fscanf(fin, “%d%d%d”, &V, &G, &n);
for (int i=1; i<=n; ++i)
fscanf(fin, “%d%d%d”, &t[i], &v[i], &g[i]);
for (int i=1; i<=n; ++i)
for (int j=V; j>=v[i]; –j)
for (int k=G; k>=g[i]; –k)
if (f[j][k]<f[j-v[i]][k-g[i]]+t[i])
f[j][k]=f[j-v[i]][k-g[i]]+t[i];
fprintf(fout, “%d\n”, f[V][G]);
return 0;
}[/cpp]
【练习题】潜水
四、翻转游戏
【解析】位运算，广度优先搜索（BFS）
例：
bwbw
wwww
bbwb
bwwb
按输入顺序（从0到15），我们把这个状态转换为
数组num[i]的值为2^i（i=0,1…15），对于输入过程中的每一个“b”，我们通过按位或运算，可以把上面的二进制表示的状态1001101100000101，转换成10进制状态39685。对每一个状态，我们可依次选择第0到第15个位置进行翻转尝试。对位置i可以通过i/4取得它在棋盘中所在的行号，可以通过i%4取得它在棋盘中所在的列号。然后再通过循环改变它相邻位置物件，此处通过异或运算求出选择在该位置翻转时得到的状态，判断这个状态是不是出现过，没出现过就入队，做相应的标记。直到出现目标状态即可退出搜索，或者队列为空时无解。此题中用到了按位或运算（|）、按位异或运算（^）及左移运算（<<）。
【参考代码】
[cpp]
#include <cstdio>
const int flip[]= {51200, 58368, 29184, 12544, 35968, 20032, 10016,
4880, 2248, 1252, 626, 305, 140, 78, 39, 19};
int map[70000], step[70000], h=0, t=1;
bool hash[70000];
int main(void)
{
for (int i=1; i<=4; ++i, getchar())
{
char t[4];
scanf(“%s”, t);
for (int j=0; j<4; ++j)
{
map[1]<<=1;
if (t[j]==’b’)
++map[1];
}
}
hash[map[1]]=true;
if (map[1]==0 || map[1]==(1<<16)-1)
{
printf(“0\n”);
return 0;
}
while (h<t)
{
++h;
for (int i=0; i<=15; ++i)
{
int des = map[h]^flip[i];
if (hash[des])
continue;
else
hash[des]=true, map[++t]=des, step[t]=step[h]+1;
if (des==0 || des==(1<<16)-1)
{
printf(“%d\n”, step[t]);
return 0;
}
}
}
printf(“Impossible\n”);
return 0;
}[/cpp]
【转载请注明本文出处，谢谢】
Leave a Reply