100字范文 > 南京大学软件学院夏令营小记

南京大学软件学院夏令营小记

时间：2020-11-08 22:05:44

相关推荐

南京大学软件学院夏令营小记

机试两道题目：1.算法题 2.面向对象编程

时间：3h

第一道题写的乱七八糟后来发现写乱了；

第二题没时间看了，十几个文件实现一些函数，感觉不难但是需要时间静下心看，理清之间的关系。

之前群里会给你练手用的练习题，给的例题很简单，考的题目却很麻烦。

我在这里只给出第一题的我个人的解题思路。当然，可能不完全对，还望批评指正。

1.算法题

这是我的草稿纸：思路大概就是，找到被侵略城市与其他城市的公共结点序列，找到最短的一条，然后断开最后一个结点与父亲的联系。

head.h

#pragma once#include <stdio.h>#include <iostream>#include <string>using namespace std;#define MAXNUM 60000class tree {public:tree(int n) {city = new int[n];}~tree() {delete[] city;}int *city;//盛放对应下标的父亲结点};struct innerlink {//就是个放int型的单链表int k;struct innerlink *next;};class linktable {public:linktable() :l(NULL){}linktable(int n) :value(n), l(NULL) {}void insert(int b);public:int value;//对应的城市结点struct innerlink *l;//到根节点的路径};

func.cpp

#include "head.h"void linktable::insert(int b) {innerlink *t = new innerlink;t->k = b;t->next = this->l;this->l = t;}

main.cpp

#include "head.h"void func(tree &t, int *a);int n, q;//结点数、袭击次数int main() {cin >> n >> q;tree t(n);int *a = new int[n];for (int i = 0; i < n; i++) {//给a数组全员赋0a[i] = 0;}t.city[0] = -1;//树根int cur;//临时变量for (int i = 1; i < n; i++) {cin >> cur;t.city[i] = cur - 1;//接口，因为内部数组下标从0计数}char switch_;//+或-int recruit;//城市结点for (int i = 0; i < q; i++) {cin >> switch_;cin >> recruit;if (switch_ == '+') {a[recruit - 1] = 1;//a数组指定位置遭遇袭击func(t, a);//传入函数处理}else if (switch_ == '-') {a[recruit - 1] = 0;//a数组指定位置解除危险func(t, a);传入函数处理}}cout << "Done" << endl;getchar(); getchar();return 0;}void func(tree &t, int *a) {int *b = new int[n];//最终要断开的结点数组int count = 0;//此次遭遇袭击的城市数目for (int i = 0; i < n; i++) {b[i] = 0;//初始化 b断开结点的数组if (a[i])++count;//袭击的城市数目加一}linktable *l = new linktable[count];//“断开的链表”int index = 0;for (int i = 0; i < n; i++) {//建立 “断开的链表”if (a[i]) {l[index].value = i;int j = i;while (t.city[j] != -1) {l[index].insert(j);j = t.city[j];}++ index;}}//处理每一个被袭击的城市结点，按照算法思路来for (int i = 0; i < count; i++) {int pos = l[i].value;//用于判断祖先是否断开while (t.city[pos] != 0 && b[t.city[pos]] == 0) {//找其祖先是否已经断开pos = t.city[pos];}if (t.city[pos] != 0) {//如果出现断开的continue;//下一个循环}else {//断开指定的一个结点与其父亲的连接int cur = MAXNUM;int cc;//临时变量innerlink *m, *n;for (int j = 0; j < count; j++) {cc = 0;//每次都要赋0值，别忘了m = l[i].l;n = l[j].l;while (m && n && m->k == n->k) {m = m->next;n = n->next;++cc;}if (cc > 0 && cc < cur) {//选择最小值curcur = cc;}}m = l[i].l;--cur;while (cur) {m = m->next;--cur;}b[m->k] = 1;//链表中找到对应位置，断开b的对应位置（赋1）}}//输出显示int cut_num = 0;int total = 0;int father;//下面要用到的变量for (int i = 0; i < n; i++) {if (b[i]) {++cut_num;}father = i;bool son = true;for (int j = 0; j < n; j++) {if (t.city[j] == i) {son = false;break;}}if (son) {while (father != 0) {if (b[father]) {total++;break;}father = t.city[father];}}}//显示结果cout << cut_num << " " << total - count << endl;cout << "***测试：查看b数组内的情况***" << endl;for (int i = 0; i < n; i++) {//cout << b[i] << " ";//}//cout << endl;//cout << "*****************************" << endl;}