NOIP 2017全国青少年信息学奥林匹克联赛提高组初赛试题答案

cout << endl; return 0; } 输入: 3

输出: 17 24 1 8 15 3. #include

using namespacestd;

int n, s,a[100005], t[100005], i; void mergesort(intl, int r){ if (l == r)

return; int mid = (l + r) / 2; int p = l; int i = l; int j = mid + 1； mergesort (l, mid); mergesort (mid + 1, r); while (i <= mid && j<= r){

if (a[j] < a[i]){

– i+1;

a[j]; p++; j++;

} else {

a[i];

i++;

} }

while (i <= mid){

s += mid t[p] = t[p] = p++; t[p] = a[i]; p++; i++; }

while (j <= r){

t[p] = a[j]; p++; j++; }

for (i = l; i <= r; i++ )

a[i] = t[i]; }

int main() { cin >> n;

for (i = 1; i <= n; i++) cin>> a[i]; mergesort (1, n); cout << s << endl; return 0; } 输入: 6

2 6 3 4 5 1 输出: 8 4. #include

using namespacestd; int main() { int n, m; cin >> n >> m; int x = 1; int y = 1; int dx = 1; int dy = 1; int cnt = 0;

while (cnt != 2) { cnt = 0; x = x + dx; y = y + dy;

if (x == 1 || x == n) { ++cnt; dx = -dx; }

if (y == 1 || y == m) { ++cnt; dy = -dy; } }

cout << x << \ return 0; }

输入1: 4 3

输出1: 1 3 (2 分) 输入2: 2017 1014 输出2: 2017 1 (3 分) 输入3: 987 321 输出3: 1 321 (3分)

五、完善程序（共 2 题，每题 14 分，共计 28 分） 1.

大整数除法：给定两个正整数p和q，其中p不超过10100，q不超过100000，求p除以q的商和余数。（第一空2分，其余3分）?

输入：第一行是p的位数n，第二行是正整数p，第三行是正整数q。 输出：两行，分别是p除以q的商和余数。 #include

using namespacestd; int p[100]; int n, i, q,rest; char c; int main(){

cin >> n;

for (i = 0; i < n; i++){

cin >> c;

p[i] = c – ‘0’； } cin >> q; rest = p[0]; i = 1;

while (rest< q && i < n){

rest = rest * 10 + p[i]; i++; }

if (rest < q)

cout << 0 <

cout << rest / q; while (i < n){

rest = rest % q * 10 + p[i];

i++; cout<< rest / q;

}

cout << endl; } cout << rest % q<< endl; return 0; } 2.

最长路径：给定一个有向五环图，每条边长度为1，求图中的最长路径长度。（第五空 2 分，其余 3 分）

输入：第一行是结点数n（不超过100）和边数m，接下来m行，每行两个整数a,b，表示从结点a到结点b有一条有向边。结点标号从0到(n-1)。 输出：最长路径长度。

提示：先进行拓扑排序，然后按照拓扑排序计算最长路径。 #include

using namespacestd;

int n, m, i, j,a, b, head, tail, ans; int graph[100][100]; // 用邻接矩阵存储图 int degree[100]; // 记录每个结点的入度

int len[100]; // 记录以各结点为终点的最长路径长度 int queue[100]; // 存放拓扑排序结果 int main() { cin >> n >> m;

for (i = 0; i < n; i++)

for (j = 0;j < n; j++) for (i = 0; i < n; i++) degree[i] =0; for (i = 0; i < m; i++){ cin>> a >>b; graph[a][b]= 1; degree[b]++; } tail = 0;

for (i = 0; i < n; i++) if (degree[i] == 0){

} head = 0;

while (tail < n-1){

for (i = 0;i < n; i++) queue[tail]= i;

tail++;

head++;

graph[i][j]= 0; queue[tail]= i; tail++; if(graph[queue[head]] [i] == 1){ degree[i]--; if(degree[i] == 0){ } }