C. C. Blog

题目描述

Hacker Bill has accidentally lost all the information from his workstation's hard drive and he has no backup copies of its contents. He does not regret for the loss of the files themselves, but for the very nice and convenient directory structure that he had created and cherished during years of work. Fortunately, Bill has several copies of directory listings from his hard drive. Using those listings he was able to recover full paths (like "WINNT32~186") for some directories. He put all of them in a file by writing each path he has found on a separate line. Your task is to write a program that will help Bill to restore his state of the art directory structure by providing nicely formatted directory tree.

题目描述

输入一系列整数，建立二叉排序数，并进行前序，中序，后序遍历。

输入

输入第一行包括一个整数n(1<=n<=100)。接下来的一行包括n个整数。

输出

可能有多组测试数据，对于每组数据，将题目所给数据建立一个二叉排序树，并对二叉排序树进行前序、中序和后序遍历。每种遍历结果输出一行。每行最后一个数据之后有一个空格。

题目描述

给定一个短字符串（不含空格），再给定若干字符串，在这些字符串中删除所含有的短字符串。

输入

输入只有1组数据。 输入一个短字符串（不含空格），再输入若干字符串直到文件结束为止。

输出

删除输入的短字符串(不区分大小写)并去掉空格,输出。

题目描述

小明和小红在玩欧几里得游戏。他们从两个自然数开始，第一个玩家小明，从两个数的较大数中减去较小数的尽可能大的正整数倍，只要差为非负即可。然后，第二个玩家小红，对得到的两个数进行同样的操作，然后又是小明。就这样轮流进行游戏，直至某个玩家将较大数减去较小数的某个倍数之后差为0为止，此时游戏结束，该玩家就是胜利者。

输入

输入包含多组测试数据。每组输入两个正整数，表示游戏一开始的两个数，游戏总是小明先开始。 当输入两个0的时候，输入结束。

输出

对于每组输入，输出最后的胜者，我们认为他们两个都是顶尖高手，每一步游戏都做出了最佳的选择。 具体输出格式见输出样例。

题目描述

现给定一棵二叉树的先序遍历序列和中序遍历序列，要求你计算该二叉树的高度。

输入

输入包含多组测试数据，每组输入首先给出正整数N（<=50），为树中结点总数。下面2行先后给出先序和中序遍历序列，均是长度为N的不包含重复英文字母（区别大小写）的字符串。

输出

对于每组输入，输出一个整数，即该二叉树的高度。

题目描述

哈夫曼树，第一行输入一个数n，表示叶结点的个数。需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出所有结点的值与权值的乘积之和。

输入

输入有多组数据。 每组第一行输入一个数n，接着输入n个叶节点（叶节点权值不超过100，2<=n<=1000）。

输出

输出权值。

题目描述

一天小明和小红在玩取石子游戏，游戏规则是这样的：
（1）本游戏是一个二人游戏；
（2）有一堆石子，共有n个；
（3）两人轮流进行；
（4）每走一步可以取走1~m个石子；
（5）最先取光石子的一方为胜。
如果游戏的双方使用的都是最优策略，请输出哪个人能赢。

输入

输入的第一行是一个正整数C（C<=100），表示有C组测试数据。
每组输入两个整数n和m（1<=n,m<=1000），n和m的含义见题目描述。

输出

对于每组输入，如果先走的人能赢，请输出"first"，否则请输出"second"。

一、引入

出栈序

二、推导（摘自百度百科）

对于每一个数来说，必须进栈一次、出栈一次。我们把进栈设为状态'1'，出栈设为状态'0'。n个数的所有状态对应n个1和n个0组成的2n位二进制数。由于等待入栈的操作数按照1‥n的顺序排列、入栈的操作数b大于等于出栈的操作数a(a≤b)，因此输出序列的总数目=由左而右扫描由n个1和n个0组成的2n位二进制数，1的累计数不小于0的累计数的方案种数。

在2n位二进制数中填入n个1的方案数为c(2n,n),不填1的其余n位自动填0。从中减去不符合要求（由左而右扫描，0的累计数大于1的累计数）的方案数即为所求。

不符合要求的数的特征是由左而右扫描时，必然在某一奇数位2m+1位上首先出现m+1个0的累计数和m个1的累计数，此后的2(n-m)-1位上有n-m个 1和n-m-1个0。如若把后面这2(n-m)-1位上的0和1互换，使之成为n- m个0和n-m-1个1，结果得1个由n+1个0和n-1个1组成的2n位数，即一个不合要求的数对应于一个由n+1个0和n-1个1组成的排列。

反过来，任何一个由n+1个0和n-1个1组成的2n位二进制数，由于0的个数多2个，2n为偶数，故必在某一个奇数位上出现0的累计数超过1的累计数。同样在后面部分0和1互换，使之成为由n个0和n个1组成的2n位数，即n+1个0和n-1个1组成的2n位数必对应一个不符合要求的数。

因而不合要求的2n位数与n+1个0，n－1个1组成的排列一一对应。

显然，不符合要求的方案数为c(2n,n+1)。由此得出输出序列的总数目=c(2n,n)-c(2n,n-1)=c(2n,n)/(n+1)=h(n)。

三、应用

给定n对括号，求括号匹配的种数。

出栈限制类问题。

一、队伍训练

　　可以称得上去训练的算是两场邀请赛及其热身赛吧。

　　这两次发挥的不理想，具体问题在于西安的没写出bfs题，南昌的我推错了结论。但根本原因却不在这，稍后分析。

二、个人训练情况

　　两场邀请赛，蓝桥杯国赛。

　　其它都是简单题，没啥好说的。

三、综合分析

　　1. 比赛情况

　　西安邀请赛：打铁，离铜牌差了几十分钟，对于我个人而言，几乎算没有上机，而且在旁边做出的贡献也不大，这一点我检讨，和英文水平低也有关系。

　　蓝桥杯国赛：听说比去年加大难度，打暴力得了二等，很多东西都是乱搞，心态也受到旁边人影响（不给学长递过去东西还释放不明气体），因此比赛结果和解题能力关系不大。

　　南昌邀请赛：打铁，差一道题（并且如果这道题在最后过也没奖），原因是我推错了结论（和网络赛很像），由于太肯定队友也没继续推，第一次写线段树一直以为是线段树出错，最后几分钟试试换方法遇到了CB闪退（即使不闪退，结论也是错的从做不出来）。这个锅我也背。

　　2. 遇到的问题

　　简单来说，太菜，具体分为以下几个方面：

　　对比赛环境不熟悉，不会调试，其他编译器，不熟悉系统。

　　对比赛不适应，团队协调性不好，英文题目读错，不上机贡献小（就我个人而言，这个问题很大，可能队友也有一点）。

　　个人水平太差，能做的只有暴力和简单智力题，遇到板子题也不知道。

　　3. 解决方案

　　使用比赛系统编译器做题。

　　提升英文水平，做题时不着急交多想，提升纸上功夫。

　　全面提升算法水平，这个会在个人的规划中有。

一、队伍训练

　　The Preliminary Contest for ICPC China Nanchang National Invitational 　　南昌邀请赛网络赛4题

二、个人训练情况

　　Time Limited，总结一下南昌网络赛，去晚了，去了一会队友做出来A，跟榜暴力写M第一遍T了，然后短路优化还有各种瞎搞勉强过了，发现H的结论，队友写了，最后一直在搞K，写了三个函数模拟，弄了一个类似杨辉三角的三角形，复制到word找规律，一开始暴力找T了，发现异或前缀和，mod分成4类，还是WA，后来规范了一下过程A了，还有不到十分钟，就看队友算别的题了。。。

三、遇到的问题&可行的解决方案

　　Time Limited

　　No response