全部知识点
(最短路径问题)无向连通图 G 有 n 个结点，依次编号为 0,1,2,…,(n−1)。用邻接矩阵的形式给出每条边的边长,要求输出以结点 0 为起点出发,到各结点的最短路径长度。
使用 Dijkstra 算法解决该问题：
利用 dist 数组记录当前各结点与起点的已找到的最短路径长度;
每次从未扩展的结点中选取 dist 值最小的结点 v 进行扩展，更新与 v 相邻的结点的 dist 值；
不断进行上述操作直至所有结点均被扩展，此时 dist 数据中记录的值即为各结点与起点的最短路径长度。
#include <iostream>
using namespace std;
const int MAXV = 100;
int n, i , j, v;
int w[MAXV][MAXV]; // 邻接矩阵，记录边长
// 其中 w[i][j] 为连接结点 i 和结点 j 的无向边长度，若无边则为 -1
int dist[MAXV];
int used[MAXV]; // 记录结点是否已扩展（0：未扩展；1：已扩展）
int main() {
cin >> n;
for (i = 0; i < n; i+ +)
for (j = 0; j < n; j++)
cin >> w[i][j];
dist[0] = 0;
for (i = 1; i < n; i+ +)
dist[i] = -1;
for (i = 0; i < n; i+ +)
used[i] = 0;
while (true) {
① ;
for (i = 0; i < n; i++)
if (used[i] != 1 && dist[i] != -1 && (v == -1 || ② ))
③ ;
if(v == -1)
break;
④ ;
for (i = 0; i < n; i++)
if (w[v][i] != -1 && (dist[i] == -1 || ⑤ ))
dist[i] = dist[v] + w[v][i];
}
for (i = 0; i < n; i++)
cout << dist[i] << endl;
return 0;
}从一个 4×4 的棋盘（不可旋转）中选取不在同一行也不在同一列上的两个方格，共有（ ）种方法。
约定二叉树的根节点高度为 1。一棵结点数为 2016 的二叉树最少有（①）个叶子结点；一棵结点数为2016 的二叉树最小的高度值是（②）。
#include <iostream>
using namespace std;
int main()
{
int max, min, sum, count = 0;
int tmp;
cin >> tmp;
if (tmp==0) return 0;
max = min = sum = tmp;
count++;
while (tmp != 0) {
cin >> tmp;
if (tmp != 0)
{
sum += tmp;
count++;
if (tmp > max) max = tmp;
if (tmp < min) min = tmp;
}
}
cout << max << "," << min << "," << sum / count << endl;
return 0;
}输入：
1 2 3 4 5 6 0 7
输出：（ ）
#include <iostream>
using namespace std;
int main()
{
int i=100,x=0,y=0;
while (i>0)
{
i--;
x=i%8;
if (x==1) y++;
}
cout<<y<<endl;
return 0;
}输出：（ ）
#include <iostream>
using namespace std;
int main()
{
int a[6] = {1, 2, 3, 4, 5, 6};
int pi = 0;
int pj = 5;
int t, i;
while (pi < pj)
{
t = a[pi];
a[pi] = a[pj];
a[pj] = t;
pi++;
pj--;
}
for (i = 0; i < 6; i++)
cout << a[i] << ",";
cout << endl;
return 0;
}输出：（ ）
#include <iostream>
using namespace std;
int main()
{
int i,length1, length2;
string s1, s2;
s1 = "I have a dream.";
s2 = "I Have A Dream.";
length1 = s1.size();
length2 = s2.size();
for (i = 0; i < length1; i++)
if (s1[i] >= 'a' && s1[i] <= 'z')
s1[i] -= 'a'-'A';
for (i = 0; i < length2; i++)
if (s2[i] >= 'a' && s2[i] <= 'z')
s2[i] -= 'a'-'A';
if (s1 == s2) cout << "=" << endl;
else if (s1 > s2) cout << ">" << endl;
else cout << "<" << endl;
return 0;
}输出：（ ）
（读入整数）请完善下面的程序，使得程序能够读入两个 int 范围内的整数，并将这两个整数分别输出，每行一个。
输入的整数之间和前后只会出现空格或者回车。输入数据保证合法。
例如:
输入:
123 -789
输出:
123
-789
#include <iostream>
using namespace std;
int readint() {
int num = 0; // 存储读取到的整数
int negative = 0; // 负数标识
char c;
c = cin.get(); // 存储当前读取到的字符
while ((c < '0' || c > '9') && c != '-')
c = ① ;
if (c == '-')
negative = 1;
else
② ;
c = cin.get();
while ( ③ ) {
④ ;
c=cin.get();
}
if (negative == 1)
⑤ ;
return num;
}
int main() {
int a, b;
a = readint();
b = readint();
cout << a << endl << b << endl;
return 0;
}（郊游活动）有 n 名同学参加学校组织的郊游活动，已知学校给这 n 名同学的郊游总经费为 A 元，与此 同时第 i 位同学自己携带了 Mi 元。为了方便郊游，活动地点提供 B(≥n) 辆自行车供人租用，租用第j 辆自行车的价格为 Cj 元，每位同学可以使用自己携带的钱或者学校的郊游经费，为了方便账务管理，每位同学只能为自己租用自行车，且不会借钱给他人，他们想知道最多有多少位同学能够租用到自行车。
本题采用二分法。对于区间 [l, r]， 我们取中间点 mid 并判断租用到自行车的人数能否达到 mid。判断的过程是利用贪心算法实现的。
#include <iostream>
using namespace std;
#define MAXN 1000000
int n, B, A, M[MAXN], C[MAXN], l, r, ans, mid;
bool check(int nn) {
int count = 0, i, j;
i = ① ;
j = 1;
while (i <= n) {
if( ② )
count += C[j] - M[i];
i++;
j++;
}
return ③ ;
}
void sort(int a[], int l, int r) {
int i = l, j = r, x = a[(l + r) / 2], y;
while (i <= j) {
while (a[i] < x) i++;
while (a[j] > x) j--;
if (i <= j) {
y = a[i];a[i] = a[j]; a[j] = y;
i++; j--;
}
}
if (i < r) sort(a, i, r);
if (l < j) sort(a, l, j);
}
int main() {
int i;
cin >> n >> B >> A;
for (i = 1; i <= n; i++)
cin >> M[i];
for (i = 1; i <= B; i++)
cin >> C[i];
sort(M, 1, n);
sort(C, 1, B);
l = 0;
r = n;
while (l <= r) {
mid = (l + r) / 2;
if ( ④ ) {
ans = mid;
l = mid + 1;
}
else
r = ⑤ ;
}
cout << ans << endl;
return 0;
}一个 1×8 的方格图形（不可旋转）用黑、白两种颜色填涂每个方格。如果每个方格只能填涂一种颜色，且不允许两个黑格相邻，共有_____种填涂方案。
某中学在安排期末考试时发现，有 7 个学生要参加 7 门课程的考试，下表列出了哪些学生参加哪些考试（用√表示要参加相应的考试）。 最少要安排_____个不同的考试时间段才能避免冲突？
#include <iostream>
using namespace std;
int main() {
int a[6] = {1, 2, 3, 4, 5, 6};
int pi = 0;
int pj = 5;
int t , i;
while (pi < pj) {
t = a[pi];
a[pi] = a[pj];
a[pj] = t;
pi++;
pj--;
}
for (i = 0; i < 6; i++)
cout << a[i] << ",";
cout << endl;
return 0;
}输出 ：____
#include <iostream>
using namespace std;
int main() {
char a[100][100], b[100][100];
string c[100];
string tmp;
int n, i = 0, j = 0, k = 0, total_len[100], length[100][3];
cin >> n;
getline(cin, tmp);
for (i = 0; i < n; i++) {
getline(cin, c[i]);
total_len[i] = c[i].size();
}
for (i = 0; i < n; i++) {
j = 0;
while (c[i][j] != ':') {
a[i][k] = c[i][j];
k = k + 1;
j++;
}
length[i][1] = k - 1;
a[i][k] = 0;
k = 0;
for (j = j + 1; j < total_len[i]; j++) {
b[i][k] = c[i][j];
k = k + 1;
}
length[i][2] = k - 1;
b[i][k] = 0;
k = 0;
}
for (i = 0; i < n; i++) {
if (length[i][1] >= length[i][2])
cout << "NO,";
else {
k = 0;
for (j = 0; j < length[i][2]; j++) {
if (a[i][k] == b[i][j])
k = k + 1;
if (k > length[i][1])
break;
}
if (j == length[i][2])
cout << "NO,";
else
cout << "YES,";
}
}
cout << endl;
return 0;
}输入 :
3
AB:ACDEbFBkBD
AR:ACDBrT
SARS:Severe Atypical Respiratory Syndrome
输出 : ____
（注：输入各行前后均无空格）
#include<iostream>
using namespace std;
int lps(string seq, int i, int j) {
int len1, len2;
if (i == j)
return 1;
if (i > j)
return 0;
if (seq[i] == seq[j])
return lps(seq, i + 1, j - 1) + 2;
len1 = lps(seq, i, j - 1);
len2 = lps(seq, i + 1, j);
if (len1 > len2)
return len1;
return len2;
}
int main() {
string seq = "acmerandacm";
int n = seq.size();
cout << lps(seq, 0, n - 1) << endl;
return 0;
}输出 ：____
#include <iostream>
#include <cstring>
using namespace std;
int map[100][100];
int sum[100], weight[100];
int visit[100];
int n;
void dfs(int node) {
visit[node] = 1;
sum[node] = 1;
int v, maxw = 0;
for (v = 1; v <= n; v++) {
if (!map[node][v] || visit[v])
continue;
dfs(v);
sum[node] += sum[v];
if (sum[v] > maxw)
maxw = sum[v];
}
if (n - sum[node] > maxw)
maxw = n - sum[node];
weight[node] = maxw;
}
int main() {
memset(map, 0, sizeof(map));
memset(sum, 0, sizeof(sum));
memset(weight, 0, sizeof(weight));
memset(visit, 0, sizeof(visit));
cin >> n;
int i, x, y;
for (i = 1; i < n; i++) {
cin >> x >> y;
map[x][y] = 1;
map[y][x] = 1;
}
dfs(1);
int ans = n, ansN = 0;
for (i = 1; i <= n; i++)
if (weight[i] < ans) {
ans = weight[i];
ansN = i;
}
cout << ansN << " " << ans << endl;
return 0;
}输入 :
11
1 2
1 3
2 4
2 5
2 6
3 7
7 8
7 11
6 9
9 10
输出 : ____
（交朋友）根据社会学研究表明，人们都喜欢找和自己身高相近的人做朋友。 现在有 n 名身高两两不相同的同学依次走入教室，调查人员想预测每个人在走入教室的瞬间最想和已经进入教室的哪个人做朋友。当有两名同学和这名同学的身高差一样时，这名同学会更想和高的那个人做朋友。比如一名身高为 1.80 米的同学进入教室时，有一名身高为 1.79 米的同学和一名身高为 1.81 米的同学在教室里，那么这名身高为1.80 米的同学会更想和身高为 1.81 米的同学做朋友。对于第一个走入教室的同学我们不做预测。
由于我们知道所有人的身高和走进教室的次序，所以我们可以采用离线的做法来解决这样的问题，我们用排序加链表的方式帮助每一个人找到在他之前进入教室的并且和他身高最相近的人。
#include <iostream>
using namespace std;
#define MAXN 200000
#define infinity 2147483647
int answer[MAXN], height[MAXN], previous[MAXN], next[MAXN]; int rank[MAXN];
int n;
void sort(int l, int r) {
int x = height[rank[(l + r) / 2]], i = l, j = r, temp;
while (i <= j)
{
while (height[rank[i]] < x) i++;
while (height[rank[j]] > x) j--;
if ( ___(1)___ ) {
temp = rank[i]; rank[i] = rank[j]; rank[j] = temp;
i++; j--;
}
}
if (i < r) sort(i, r);
if (l < j) sort(l, j);
}
int main()
{
cin >> n;
int i, higher, shorter;
for (i = 1; i <= n; i++) {
cin >> height[i];
rank[i] = i;
}
sort(1, n);
for (i = 1; i <= n; i++) {
previous[rank[i]] = rank[i - 1];
___(2)___ ;
}
for (i = n; i >= 2; i--){
higher = shorter = infinity;
if (previous[i] !=0)
shorter = height[i] - height[previous[i]];
if (next[i] != 0)
___(3)___ ;
if ( ___(4)___ )
answer[i] = previous[i];
else
answer[i] = next[i];
next[previous[i]] = next[i];
___(5)___ ;
}
for (i = 2; i <= n; i++)
cout << i << ":" << answer[i];
return 0;
}(交通中断）有一个小国家，国家内有 n 座城市和 m 条双向的道路，每条道路连接着两座不同的城市。其中 1 号城市为国家的首都。由于地震频繁可能导致某一个城市与外界交通全部中断。这个国家的首脑想知道，如果只有第i(i>1) 个城市因地震而导致交通中断时，首都到多少个城市的最短路径长度会发生改变。如果因为无法通过第 i 个城市而导致从首都出发无法到达某个城市，也认为到达该城市的最短路径长度改变。
对于每一个城市 i，假定只有第 i 个城市与外界交通中断，输出有多少个城市会因此导致到首都的最短路径长度改变。
我们采用邻接表的方式存储图的信息，其中 head[x] 表示顶点 x 的第一条 边的编号，next[i] 表示第 i 条边的下一条边的编号, point[i] 表示第 i 条边的终点，weight[i] 表示第 i 条边的长度。
#include <iostream>
#include <cstring>
using namespace std;
#define MAXN 6000
#define MAXM 100000
#define infinity 2147483647
int head[MAXN], next[MAXM], point[MAXM], weight[MAXM];
int queue[MAXN], dist[MAXN], visit[MAXN];
int n, m, x, y, z, total = 0, answer;
void link(int x,int y,int z) {
total++;
next[total] = head[x]; head[x] = total; point[total] = y; weight[total] = z; total++;
next[total] = head[y]; head[y] = total; point[total] = x; weight[total] = z;
}
int main() {
int i, j, s, t; cin >> n >> m;
for (i = 1; i <= m; i++) {
cin >> x >> y >> z;
link(x, y, z);
}
for (i = 1; i <= n; i++) dist[i] = infinity;
___(1)___ ;
queue[1] = 1;
visit[1] = 1;
s = 1;
t = 1;
// 使用 SPFA 求出第一个点到其余各点的最短路长度
while (s <= t) {
x = queue[s % MAXN];
j = head[x];
while (j != 0) {
if ( ___(2)___ ) {
dist[point[j]] = dist[x] + weight[j];
if (visit[point[j]] == 0) {
t++;
queue[t % MAXN] = point[j];
visit[point[j]] = 1;
}
}
j = next[j];
}
___(3)___ ;
s++;
}
for (i = 2; i <= n; i++) {
queue[1] = 1;
memset(visit, 0, sizeof(visit));
visit[1] = 1;
s = 1;
t = 1;
while (s <= t) { // 判断最短路长度是否不变
x = queue[s];
j = head[x];
while (j != 0) {
if (point[j] != i && ___(4)___ &&visit[point[j]] == 0) {
___(5)___ ;
t++;
queue[t] = point[j];
}
j = next[j];
}
s++;
}
answer = 0;
for (j = 1; j <= n; j++)
answer += 1 - visit[j];
cout << i << ":" << answer - 1 << endl;
}
return 0;
}一个人站在坐标（0，0）处，面朝 x 轴正方向。第一轮，他向前走 1 单位距离，然后右转；第二轮，他向前走 2 单位距离，然后右转；第三轮，他向前走 3 单位距离，然后右转……他一直这么走下去。请问第 2017 轮后，他的坐标是：（___ , ___）。
如下图所示，共有 13 个格子。对任何一个格子进行一次操作，会使得它自己以及与它上下左右相邻的格子中的数字改变（由 1 变 0，或由 0 变 1）。现在要使得所有的格子中的数字都变为 0，至少需要_____次操作。
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
int t[256];
char s[10];
int i;
scanf("%s", s);
for(i = 0; i < 256; i++) t[i] = 0;
for(i = 0; i < strlen(s); i++) t[s[i]]++;
for(i = 0; i < strlen(s); i++)
if(t[s[i]] == 1) {
cout << s[i] << endl;
return 0;
}
cout << "no" << endl;
return 0;
}输入：
xyzxyw
输出：（ ）