2016大数据研究中心夏令营上机考试
2016年北京大学计算机科学技术研究所优秀大学生夏令营上机考试
12推免
- 石头剪刀布
- 最简真分数
include<algorithm>
__gcd(a,b);
- encode decode 字符串的处理
- 大数，进制转换，
unsolved - 8数码问题，和之前做的BFS不同的是，要存储每一种可能的系统状态
struct Node
{
int s[9];
int loc;//“0”的位置,把“x"当0
int status;//康拖展开的hash值
string path;//路径 更新：next.path=next.path+indexs[i];
};
- 热血格斗场 和冷血格斗场要求不一样
- 画家问题 重复题
不能用BFS - 三角形 重复题，从下往上
- Lausanne Capitale Olympique
no answer
13推免（校外）
- 十进制转六进制，无oj
- 电池的寿命，找规律
令最大寿命为x，其余寿命和为sum，若sum>x，则可以全部用完 ans=(sum+x)/2
否则 只能用sum的寿命
if(2*x[n-1]>ans)
ans-=x[n-1];
else ans*=0.5;
- 重建二叉树
typedef struct node
- 完美覆盖，递推关系的寻找
f(n)=3f(n-2)+2[f(n-4)+...f(0)]
f(n-2)=3f(n-4)+2[f(n-6)+...f(0)]
thus: f(n)=4f(n-2)-f(n-4)
f(0)=1, f(2)=3;
- 去掉冗余的括号，两个标准：括号前是否是负号、括号里面是否有操作符号
- 坦克大战，
done - sightseeing，混合图欧拉路径的判定
... - poyla计数，项链涂色问题
//背代码
(long long)(pow(3.0,tmp*1.0));//格式为long long，3.0
13推免(校内)
- 字符串插入，没有说怎么结尾，读入方式就是：
while(cin>>a>>b) - 书架，临界条件
sum>=b - 最长子序列，动态规划
if(a[j]<a[i]&&b[j]+1>b[i])
b[i]=b[j]+1;//b[i]从1开始
- 寻找正方形
变量和复杂度都会影响运行时间
//先排序再查找
void *bsearch(const void *key, const void *base, size_t nmem, size_t size, int (*comp)(const void *, const void *));
eg. (point_type*) bsearch ((const void*) key...)
//key指向所要查找的元素，base指向进行查找的数组
//nmem为查找长度，一般为数组长度
//size为每个元素所占的字节数，一般用sizeof(...)表示，comp指向比较子函数
int compare(const void* e1,const void* e2)
{
const point_type* p1=(const point_type*) e1;
const point_type* p2=(const point_type*) e2;
if (p1->x!=p2->x)//先比较x
return p1->x-p2->x;
else//x相同就比较y
return p1->y-p2->y;
}
//cmp的写法
qsort(p,n,sizeof(point_type),compare);
//qsort写法
key->x=x2+y1-y2;
key->y=y2+x2-x1;
//只往一个方向上找，
13夏令营
- 水
- map，冷血格斗场
输入的id没有从小大的顺序 - 上台阶，斐波那契数列
- 线段树，二分，
数字大的用scanf否则易超时！POJ3264
#include<algorithm> max(a,b);
struct node//用来记录每个叶结点，之所以不用指针是因为用tree[num]来记录每个结点了（树不需要动态操作所以可以这么用）
{
int l;
int r;
int max;
int min;
};
//用全局变量来记录最大值
int findmax(int l,int r,int ceng)//层是tree[num]的编号
- 数独，DFS，用
grid[num][1-9]来标记是否已经用了这个数字 POJ2676 - 3D迷宫BFS
- 数字三角形，递归。
if(map[i+1][j]>map[i+1][j+1])
map[i][j]=map[i+1][j]+map[i][j];
else
map[i][j]=map[i+1][j+1]+map[i][j];
- 最小生成树
上下限的设置 - 增广方法求最大流 POJ1273
map和min_flow是全局变量，pre和flow在寻找每一条增广路径时更新，
14推免
- 单词倒排
- DNA排序，struct，qsort，count
- 踩方格，DFS深度优先，回溯
- 走迷宫找最短路径，BFS广度优先
- 二维背包问题
for(i=0;i<c;i++)
{
cin>>temp1>>temp2;
for(j=a;j>=temp1;j--)
{
for(k=b;k>=temp2;k--)
{
if(dp[j][k]<dp[j-temp1][k-temp2]+1)
dp[j][k]=dp[j-temp1][k-temp2]+1;//个数+1
}
}
//dp:精灵球数量，体力值——小精灵的个数
}
- 套汇，Floyed
map<string,int>STL;
dist[i][i]=1; //自己到自己初始为1
dist[i][j] < dist[i][k] * dist[k][j];//更新条件
- trie树，对树的操作：
void clean ()
root->next[i]=NULL;
void delete(root)
{
if(root->next[i])
delete(root->next[i]);
free(root);
}
pnode p1= (pnode)malloc(sizeof(node));//生成结点
typedef struct node//结构定义
{
struct node *next[10];//0~9
int end,cover;
}*pnode;
14夏令营
- 人民币支付，水
- 排队游戏，类似POJ对括号的处理
输入不一定是()!!! - 取石子游戏，
巨坑！要么用a/b>=2， 要么用long long a,b; - 去除注释，
cin.getline(s,200)之后对字符的处理、多种情况的考虑没有测试 - 求逆序数对即是求归并排序的交换次数，背代码
- 坦克大战，BFS的处理
map越界！ - 背包问题，
d[j]=max(d[j-a]+b,d[j])//j是背包可承受的最大重量，注意上限！
- 树的处理，找规律
- 宝昌县长要修路，最小生成树的编写，双边距离
15推免
- 水
- 矩阵转置
- 行程编码
- 去除重复的数
- 分解因数，递归：
if(a==1) return 1;
if(b==1) return 0;
if(a%b==0) return func(a/b,b)+func(a,b-1)
else return func(a,b-1)
- DFS 深度优先
- 背包问题
64-bit unsigned integer:%I64d
dp[0]=1;
for (i=1; i<=num; i++)//对于从小到大的序号
for (j=n; j>=0; j--)
for (x=1; x<=h[i]; x++)//这个数有多少个
if (j-x>=0)
dp[j]+=dp[j-x];
- 查找二叉树；得到一行中不确定个数的数字
输入有可能是0
while((c=getchar())!='\n')
{
if(c>='0'&&c<='9')
{
ungetc(c,stdin);
cin>>a[i++];
}
} - Floyd，找两点之间所要经过的最小“最大距离”。
for(k=1; k<=n; k++)
for(i=1; i<=n-1; i++)
for(j=i+1; j<=n; j++)
if(path[i][k]<path[i][j] && path[k][j]<path[i][j])
//则走i->k->j路线，否则走i->j路线
if(path[i][k]<path[k][j])
path[i][j]=path[j][i]=path[k][j];
else
path[i][j]=path[j][i]=path[i][k];
15夏令营
- 水
- 水
- 数组的遍历
考虑只有一行的情况！ - qsort不能有两个cmp方法，合影
- 相同字符串的寻找，题意的理解
- To Europe，动态规划！：
t=l*1.0/s+result[j-1];//int变double，考虑到每一层的最优情况
BFS，考虑的是方向不是距离
相邻的点可以到达用普通的BFS不行，因为即使当前的点是segment最少的点，也不能保证接下来找到点是segment最少的。
从原点开始，把1步、2步…能走到的点都放进队里。
而不是只找可以走到的一个点审题！每一个输入之后有一个空行memset(v,0,sizeof(v));二叉查找树的建立
两点之间的最短距离
16推免（check）
- 石头剪刀布
- 字符串判断，
'a'-'A'=32极值Z的处理 - 矩阵输出顺序
- DFS，背代码，递归的利用
不是可能性！是数独的要求！
- 10000个数的计算，不能直接计算，而是每次计算都取余数，类似背包问题用0、1存结果
1. %的结果可能是负的！
2. 不管是+a[i]还是-a[i]都可能出现mod是负的！
3. 动态规划，用dp[10001][101]存储！
- 画家问题，和POJ的题不一样，不能简单的枚举否则会超时。
for(int k=0; k<pow(2.0, n); k++)
getLine(k);
void getLine(int k)
{
//通过二进制枚举第一行可能发生的所有情况
int j = n;
while(j>0)
{
line[j] = k % 2;//line[j]代表第一行的第j列翻转
k /= 2;
j--;
}
}
- 最小生成树、字符串的处理
not by me
string temp1;
if(temp1.compare(a[j])==0)
- 二叉树路线的计算
not by me - Magical GCD的理解
动态规划，gcd函数要自己写
16夏令营
- 水
- 单词翻转，调试
- 加密，矩阵的操作
- 文件结构图，目录里的文件也要排序，因此一定要用递归
recur(string s1,int N,int T) //T是test的序号，N是文件层次的序号
- 汇率计算，精度的改变，用两个数组决定换不换
double update(double a)
{
a=a*100;
int y=int(a);
return y/100.0;
}
- BFS，迷宫，背代码
- 前序遍历、中序遍历变为后序遍历。读取一行的两个字符串
cin>>s1>>s2 - 最小生成树
- 多米诺，f[i][j]为枚举到第i个数差为j时最少交换了多少次，要考虑j为负数的情况。
f[i][j]=min(f[i][j],f[i-1][j-(a[i]-b[i])],f[i-1][j+(a[i]-b[i])]+1)
