本次训练内容为结构体排序及深度优先搜索
1.4859: 分数线划定
NOIP2009普及组T2
这个一个比较经典的结构体排序题，一个人有两个信息，报名号和笔试成绩。
录取的时候按照向下取整，直接转换为int即可。
关于重分问题，可以参照暑假赛的队选拔，获取最后一个人分数即可，等于它的也都要计算和输出。
#include <bits/stdc++.h>
using namespace std;
struct T
{
int id, score;
} a[5005];
bool cmp(T a, T b)
{
//如果成绩不相等，成绩高的在前面
if (a.score != b.score)
return a.score > b.score;
//如果成绩相等，报名号小的在前面
return a.id < b.id;
}
int main()
{
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++)
{
cin >> a[i].id >> a[i].score;
}
sort(a, a + n, cmp);
//自动向下取整，但是下标从0开始，还需要减1
m = m * 1.5 - 1;
int t = 0;
for (int i = 0; i < n; i++)
{
if (a[i].score >= a[m].score)
{
t++;
}
}
cout << a[m].score << " " << t << "
";
for (int i = 0; i < t; i++)
{
cout << a[i].id << " " << a[i].score << "
";
}
return 0;
}
2.4851: 奖学金
NOIP2007普及组T1
这个题目关键字还是多的，有语文、数学、英语、总分和学号
但是这个题目只需要我们把结构体排序的cmp写好就可以。
先比总分，再比语文成绩，再比学号，最后输出前5个即可。
#include <bits/stdc++.h>
using namespace std;
struct T
{
//依次为语文、数学、英语、学号、总分
int ch,math,en,id,sum;
} a[305];
bool cmp(T a, T b)
{
//先比较总成绩，高的在前面
if (a.sum != b.sum)
return a.sum > b.sum;
//再比较语文，高的在前面
if (a.ch != b.ch)
return a.ch > b.ch;
//最后比较学号，小的在前面
return a.id < b.id;
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> a[i].ch >> a[i].math >> a[i].en;
a[i].sum = a[i].ch + a[i].math + a[i].en;
a[i].id = i + 1;
}
sort(a, a + n, cmp);
for (int i = 0; i < 5; i++)
cout << a[i].id << " " << a[i].sum << "
";
return 0;
}
3.5993: 棋盘
这个题目是一个二维图像，问你怎么从一个点到另一个点最短，这种题肯定要搜索了，可以用BFS+堆解决。
但是深搜写起来更简单，这个题目能用深搜解决吗？直接爆搜会超时，我们会加上记忆化(一个点不会计算多次)，剪枝(有些不需要走的提前结束)
1.用dis数组记录到达(i，j)时的最小花费，每次搜索前判断花费是否小于当前点的最小价值，否则不搜，这样可以结束掉非常多的循环
2.使用魔法后需要回溯
3.颜色存储时有颜色1红色，2黄色，0无色，未赋值即为无色
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int dir[4][2] = {
1, 0,
-1, 0,
0, 1,
0, -1};
int dis[105][105];
int a[110][110];
int m, n, ans = INF;
void dfs(int x, int y, int sum, bool flag)
{
if (x < 1 || y < 1 || x > m || y > m)return;
//不符合最优解,进行剪枝，这样可以提前结束掉很多循环
if (sum >= dis[x][y])return;
dis[x][y] = sum;
//到终点(m, m)了
if (x == m && y == m)
{
if (sum < ans)ans = sum;
return;
}
for (int i = 0; i < 4; i++)
{
int tx = x + dir[i][0], ty = y + dir[i][1];
if (a[tx][ty]) // 若下一格有色
{
if (a[tx][ty] == a[x][y])
{
//颜色相同，不花钱
dfs(tx, ty, sum, false);
}
else
{
// 否则花费+1
dfs(tx, ty, sum + 1, false);
}
}
//下一格无色而且没有用过魔法
else if (!flag)
{
a[tx][ty] = a[x][y];
//使用魔法
dfs(tx, ty, sum + 2, true);
//回溯，重新换为无色
a[tx][ty] = 0;
}
}
}
int main()
{
memset(dis, INF, sizeof(dis));
cin >> m >> n;
for (int i = 1; i <= n; i++)
{
int x, y, c;
cin >> x >> y >> c;
//1红色 2黄色 0无色
a[x][y] = c + 1;
}
//从(1,1)开始搜索，初始总和为0,没有使用魔法
dfs(1, 1, 0, false);
if (ans == INF)cout << -1;
else cout << ans;
return 0;
}
4.4871: 文化之旅
NOIP2012普及组T4
本题是错题，后来被证明没有靠谱的多项式复杂度的做法。测试数据非常的水，各种玄学做法都可以通过（比如反着扫），不代表算法正确。因此本题题目和数据仅供参考。
这个题直接深搜是可以过的，按照题意将所有边都遍历一遍，因为测试数据比较水，竟然是可以AC的，所以比赛要敢大胆得写出来，即使不拿全部分数也可以拿到部分分数
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int n, k, m, s, t, ans = INF;
int a[105][105], dis[105][105];
int c[105], vis[105];
//x表示当前搜索的点，sum表示距离
void dfs(int x, int sum)
{
//如果当前点是终点
if (x == t)
{
ans = min(ans, sum);
return;
}
vis[c[x]] = 1;
for (int i = 1; i <= n; i++)
{
//1.x和i之间没有通路2.文化i的文化排斥x的文化3.已经学习过
if (!dis[x][i] || a[c[i]][c[x]] || vis[c[i]])
continue;
dfs(i, sum + dis[x][i]);
}
//回溯
vis[c[x]] = 1;
}
int main()
{
cin >> n >> k >> m >> s >> t;
for (int i = 1; i <= n; i++)
cin >> c[i];
for (int i = 1; i <= k; i++)
for (int j = 1; j <= k; j++)
cin >> a[i][j];
for (int i = 1; i <= m; i++)
{
int x, y, z;
cin >> x >> y >> z;
dis[x][y] = z;
}
//初始点为s，总和为0
dfs(s, 0);
if (ans == INF)
cout << "-1";
else
cout << ans;
return 0;
}
当然也可以FLYOD求最短路
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int n, k, m, s, t;
int c[105];
int a[105][105], dis[105][105];
int main()
{
cin >> n >> k >> m >> s >> t;
for (int i = 1; i <= n; i++)
cin >> c[i];
for (int i = 1; i <= k; i++)
for (int j = 1; j <= k; j++)
cin >> a[i][j];
memset(dis, INF, sizeof(dis));
for (int i = 1; i <= m; i++)
{
int x, y, z;
cin >> x >> y >> z;
//可能有多条边且这条边权可能较小
if (!a[c[x]][c[y]])
dis[x][y] = min(dis[x][y], z);
if (!a[c[y]][c[x]])
dis[y][x] = min(dis[y][x], z);
}
for (int p = 1; p <= n; p++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dis[i][j] = min(dis[i][j], dis[i][p] + dis[p][j]);
if (dis[s][t] != INF)
cout << dis[s][t];
else
cout << -1;
}
5.4801: 统计数字
NOIP2007提高组T1
这道题还是比较简单的，我们可以先排序再计数，你把它封装为结构体也可以
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
struct T
{
int k;
int c = 1;
} a[N];
int n;
int cmp(T b, T a)
{
return b.k < a.k;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i].k;
sort(a, a + n, cmp);
for (int i = 0; i <= n; i++)
{
//如果相等
if (a[i].k == a[i + 1].k)
{
//把它变为0，且不再输出
a[i].k = 0;
//个数+1
a[i + 1].c += a[i].c;
}
if (a[i].k != 0)
cout << a[i].k << " " << a[i].c << "
";
}
return 0;
}
直接使用map简单粗暴
#include <bits/stdc++.h>
using namespace std;
int main()
{
//a用来计数
map<int, int> a;
int n;
cin >> n;
for (int i = 0, x; i < n; i++)
{
cin >> x;
a[x]++;
}
map<int,int>::iterator it;
for (it = a.begin(); it != a.end(); it++)
cout << it->first << " " << it->second << "
";
}
6.4778: 单词接龙
NOIP2003提高组T3
这是一道比较简单深度优先搜索题目，需要注意以下3点
1.一个单词最多用两次
2.不能在龙里出现包含关系
3.可以有重合部分
求重合部分可以从已经在龙里的最后一个单词的最后面开始枚举（从后向前枚举）直到找到最后一个单词的一个字母和想要接龙的单词的第一个字母相等，把那个单词的字母的位置记录为k，然后从已经在龙里的那个单词从k到尾进行循环枚举，同时想要接龙的单词从头到k进行枚举，如果有不相等的一个字母就返回0，否则返回那个单词的长度 -k
#include <bits/stdc++.h>
using namespace std;
const int N = 25;
int n, vis[N], ans, l[N], p;
string s[N];
char ch;
//是否能合并
int find(int x, int y)
{
int lx = l[x], ly = l[y];
for (int i = lx - 1; i >= 1; i--)
{
//发现字母相等
if (s[x][i] == s[y][0])
{
int k = 1;
for (int j = i + 1; j <= lx - 1; j++, k++)
{
//有一个字母不相等就返回0
if (s[x][j] != s[y][k])
{
return 0;
}
}
//全相等返回长度
return ly - k;
}
}
return 0;
}
//对单词进行搜索
void dfs(int x)
{
for (int i = 1; i <= n; i++)
{
//不能用两次且可以接龙
if (vis[i] < 2 && find(x, i))
{
vis[i]++;
//加上新单词的长度
ans += find(x, i);
dfs(i);
//回溯
vis[i]--, ans -= find(x, i);
}
}
if (ans > p) //求最大
{
p = ans;
}
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
cin >> s[i];
l[i] = s[i].length(); //存下所有单词的长度
}
cin >> ch;
for (int i = 1; i <= n; i++)
{
if (s[i][0] == ch) //得等于首字母才能接
{
ans = l[i]; //先加上首单词的长度
vis[i]++; //首单词用过了
dfs(i);
vis[i]--; //回溯
if (p > ans) //求最大
{
ans = p;
}
}
}
cout << ans;
return 0;
}
7.4793: 虫食算
NOIP2004提高组T4
这个题目还是非常难的，官方正解是高斯消元，对我们并不太友好，我们可以尝试用搜索+剪枝去解决下
我们可以利用类似高精度的方法来计算不同进制的加法，同时进行回溯搜索。
利用从上到下，从右到左的搜索顺序，如果搜索到的这个字母所代表的数字已经求出，则直接搜索下一个；否则就用两种方案：利用这一列另两个数（如果已经搜出）来求出这个字母所代表的数字；或者直接从n-1到0搜索。
#include <bits/stdc++.h>
using namespace std;
const int N = 30;
int n, flag[N];
string s[5];
int vis[N], f;
//将字符转换为数字
int charToInt(char ch)
{
return ch - 'A' + 1;
}
//深搜函数，x代表列，y代表行，t代表进位
void dfs(int x, int y, int t)
{
if (f)
return;
//从上到下，从右到左，x==-1表示搜到了最后一列
if (x == -1)
{
if (t == 0)
{
//满足条件，输出
cout << flag[1];
for (int i = 2; i <= n; i++)
cout << " " << flag[i] ;
cout << "
";
f = 1;
}
return;
}
for (int i = x - 1; i >= 0; i--) //剪枝1
{
//分别表示第一行，第二行，第三行代表的数字
int w1 = flag[charToInt(s[0][i])];
int w2 = flag[charToInt(s[1][i])];
int w3 = flag[charToInt(s[2][i])];
if (w1 == -1 || w2 == -1 || w3 == -1) //如果这个位置上还没被赋值，就返回
continue;
//如果无论进位与否，都不能整除对应的w3就说明字符串不匹配
if ((w1 + w2) % n != w3 && (w1 + w2 + 1) % n != w3)
return;
}
//如果这个位置上还没被赋值，就进行赋值操作
if (flag[charToInt(s[y][x])] == -1)
{
//倒着枚举比较快
for (int i = n - 1; i >= 0; i--)
if (!vis[i])
{
//分是不是最后一行
if (y != 2)
{
//标记用过，赋值，并搜索下一列
vis[i] = 1;
flag[charToInt(s[y][x])] = i;
dfs(x, y + 1, t);
//回溯
vis[i] = 0;
flag[charToInt(s[y][x])] = -1;
}
else
{
//两个数加上它们的进位
int w = flag[charToInt(s[0][x])] + flag[charToInt(s[1][x])] + t;
if (w % n != i)
continue;
//标记这个数用过，赋值，并搜索上一行
vis[i] = 1;
flag[charToInt(s[2][x])] = i;
dfs(x - 1, 0, w / n);
//回溯
vis[i] = 0;
flag[charToInt(s[2][x])] = -1;
}
}
}
else //如果这个位置上已经被赋值了
{
if (y != 2) //继续搜索
dfs(x, y + 1, t);
else
{
int w = flag[charToInt(s[0][x])] + flag[charToInt(s[1][x])] + t;
if (w % n != flag[charToInt(s[2][x])]) //剪枝 2
return;
//搜索下一列，进位需要改变
dfs(x - 1, 0, w / n);
}
}
}
int main()
{
cin >> n;
for (int i = 0; i < 3; i++)
cin >> s[i];
//将所有位置标记为未赋值
memset(flag, -1, sizeof(flag));
//从上到下，从右到左搜索
dfs(n, 0, 0);
return 0;
}