首页 > 代码库 > NOIP2016初赛总结(提高组)
NOIP2016初赛总结(提高组)
题目：https://www.zhihu.com/question/51865837/answer/127892121
注：我是HE的，不是JS的，照片是ZYJ神犇的
单选
第一题，水过，小学生都会。D
第二题，当时我们场好多人错了。。坑点如下：
1.和pj组的不同，是来回按键。
2.让你求第81个字符，而不是第81个按键。
所以我们可以得出输出的是是个字符一循环：ASDSAasdsa
所以第81个是A，选A
第三题，异或运算就是不同得1，相同得0，列竖式算一下不得了。
我们考场某人竟然不知道异或是什么。选B
第四题，我记得去年考的是16进制小数是0.8，今年成了8进制了。
想一想就明白了。选B。
第五题，可以想成N个人打乒乓球，决出冠军，最少打N-1场。选B。
第六题，得仔细说说啊。后缀表达式又叫做逆波兰表达式，就是按照从前到后的顺序把操作数和运算符压进一个栈，如果压进了一个运算符，就把栈顶的两个操作数弹出，并与该运算符进行运算，把运算结果放入栈。这题按照计算顺序，应该是先算a*(b+c)，然后是分别算a和b+c并把乘号压进栈，b+c的逆波兰式是bc+，所以应该是abc+*，然后把d压进去，再压进去减号，表达式就变成了abc+*d-。答案为B。
第七题，答案是sum(每一个节点孩子为空的数目)。根节点的左孩子是叶子节点，答案+=2。根节点右孩子的左孩子也是空节点，答案+=2。根节点右孩子的右孩子左孩子为空，答案+=1，其右孩子是空节点，答案+=2.所以答案是7。(我是智障，一张图解决一段话不得了)
下面这张图中，黑色部分表示原二叉树，红线表示指向NULL指针，红圈表示NULL，所以一共有7个。选B。
第八题，我是这么想的，先构建一个8个顶点的最稠密无向连通图，可以根据公式((8-1)*8)/2知道这张图有28条边。再添加一个孤立的节点使得这张图成为非连通图，所以选B。
第九题，常识性问题。我们说的"32位系统"理论上最多支持4GB内存就是说的这个。所以选B。
第十题。自己模拟去。用devc++或人脑均可。选D。
第十一题。枚举。注意重复情况，设三个盘子苹果量是a,b,c，在枚举时使a<=b<=c即可。下面是那八种情况。选B。
第十二题。我这里找不到图。只要找到所有是Lucia的朋友而不是Jacob的朋友就行了(Jacob本人除外)。选A。
第十三题，自己想即可。很简单。选C。
第十四题，我不会233333333333，选C。
第十五题，Search函数的第二行判断的是当前元素是否为峰顶，所以第三行是c.return L[k]。第四行判断的是当前元素从左到右是否呈上升趋势，据题意可知，如果呈上升趋势峰顶应该在右边，所以是a.search(k+1,n)。第六行就是b了。所以选A。
不定项
第一题。常识问题。最重要的是我尽然选错了，把D也选上了。以太网不是无线的。。。答案是ABC
第二题。同理也是常识问题。光驱是连接光盘的，鼠标是连接手的，显卡是连接显示屏的。答案是A
第三题。看过书的都知道。(计数排序比较少见，可能有人也选了)答案是AB
第四题。自己想就行了。我这里没有图。答案是A
第五题。有人竟然选C，不带衣服进考场。。。此人一定是受到pj组单选第20题的迷惑了。答案是ABD
问题求解
第一题。我这个约瑟夫竟然画了个树状图，画到第6层发现可以直接求结果，然后算出来是55(竟然对了)。
正解是斐波那契数列，设f(1)=2,f(2)=3,求f(8)。f(1)=2,f(2)=3,f(3)=5,f(4)=8,f(5)=13,f(6)=21,f(7)=34,f(8)=55。
第二题。答案是3,，通用技术、化学、政治一起考，物理、历史一起考，生物、地理一起考。
阅读程序写结果
我把代码弄过来了。。。若君问吾代码从何来？吾曰："手打。"
第一题。
输出：6,5,4,3,2,1,
#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;
}
考点：将数组倒序存储
坑点：最后一个逗号
第二题。
输入：3
AB:ACDEbFBkBD
AR:ACDBrT
SARS:Severe Atypical Respiratory Syndrome
输出：YES,NO,YES,
#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][j]; 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;
}
考点：匹配不连续的字串
坑点：同第一题
第三题。
输出：5
#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;
}
考点：不知道 最长回文字串(模拟即可)
坑点：没什么
第四题。
输入：11
1 2
1 3
2 4
2 5
2 6
3 7
7 8
7 11
6 9
9 10
输出：2 5
#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;
}
考点：深度优先遍历求树的重心
坑点：无
完善程序
第一题。答案在上面。第一空是快排条件，第二空、第三空和第五空照抄即可(上面有差不多的)，第四孔就是判断应该选高的还是矮的。
第二题。答案在上面。第一空是spfa的d[1]=0，第二空是松弛，判断是否可以更新，第三空是取消访问标记，第四空是判断是否走得这条路径(我没写上来)，第五空是标记访问。
NOIP2016初赛总结(提高组)