2016大數(shù)據(jù)研究中心夏令營上機考試
2016年北京大學(xué)計算機科學(xué)技術(shù)研究所優(yōu)秀大學(xué)生夏令營上機考試
12推免
- 石頭剪刀布
- 最簡真分?jǐn)?shù)
include<algorithm>
__gcd(a,b);
- encode decode 字符串的處理
- 大數(shù)牛哺，進(jìn)制轉(zhuǎn)換，
unsolved - 8數(shù)碼問題劳吠，和之前做的BFS不同的是引润，要存儲每一種可能的系統(tǒng)狀態(tài)
struct Node
{
int s[9];
int loc;//“0”的位置,把“x"當(dāng)0
int status;//康拖展開的hash值
string path;//路徑 更新：next.path=next.path+indexs[i];
};
- 熱血格斗場 和冷血格斗場要求不一樣
- 畫家問題 重復(fù)題
不能用BFS - 三角形 重復(fù)題，從下往上
- Lausanne Capitale Olympique
no answer
13推免（校外）
- 十進(jìn)制轉(zhuǎn)六進(jìn)制痒玩，無oj
- 電池的壽命淳附，找規(guī)律
令最大壽命為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
- 完美覆蓋别凹，遞推關(guān)系的尋找
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;
- 去掉冗余的括號，兩個標(biāo)準(zhǔn)：括號前是否是負(fù)號洽糟、括號里面是否有操作符號
- 坦克大戰(zhàn)炉菲，
done - sightseeing，混合圖歐拉路徑的判定
... - poyla計數(shù)坤溃，項鏈涂色問題
//背代碼
(long long)(pow(3.0,tmp*1.0));//格式為long long拍霜，3.0
13推免(校內(nèi))
- 字符串插入，沒有說怎么結(jié)尾薪介，讀入方式就是：
while(cin>>a>>b) - 書架祠饺，臨界條件
sum>=b - 最長子序列，動態(tài)規(guī)劃
if(a[j]<a[i]&&b[j]+1>b[i])
b[i]=b[j]+1;//b[i]從1開始
- 尋找正方形
變量和復(fù)雜度都會影響運行時間
//先排序再查找
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指向進(jìn)行查找的數(shù)組
//nmem為查找長度吠裆，一般為數(shù)組長度
//size為每個元素所占的字節(jié)數(shù)伐谈，一般用sizeof(...)表示烂完，comp指向比較子函數(shù)
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沒有從小大的順序 - 上臺階抠蚣，斐波那契數(shù)列
- 線段樹，二分履澳，
數(shù)字大的用scanf否則易超時嘶窄！POJ3264
#include<algorithm> max(a,b);
struct node//用來記錄每個葉結(jié)點，之所以不用指針是因為用tree[num]來記錄每個結(jié)點了（樹不需要動態(tài)操作所以可以這么用）
{
int l;
int r;
int max;
int min;
};
//用全局變量來記錄最大值
int findmax(int l,int r,int ceng)//層是tree[num]的編號
- 數(shù)獨距贷，DFS柄冲，用
grid[num][1-9]來標(biāo)記是否已經(jīng)用了這個數(shù)字 POJ2676 - 3D迷宮BFS
- 數(shù)字三角形，遞歸忠蝗。
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];
- 最小生成樹
上下限的設(shè)置 - 增廣方法求最大流 POJ1273
map和min_flow是全局變量现横，pre和flow在尋找每一條增廣路徑時更新，
14推免
- 單詞倒排
- DNA排序阁最，struct戒祠，qsort，count
- 踩方格速种，DFS深度優(yōu)先姜盈，回溯
- 走迷宮找最短路徑，BFS廣度優(yōu)先
- 二維背包問題
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;//個數(shù)+1
}
}
//dp:精靈球數(shù)量配阵，體力值——小精靈的個數(shù)
}
- 套匯馏颂，F(xiàn)loyed
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));//生成結(jié)點
typedef struct node//結(jié)構(gòu)定義
{
struct node *next[10];//0~9
int end,cover;
}*pnode;
14夏令營
- 人民幣支付，水
- 排隊游戲救拉，類似POJ對括號的處理
輸入不一定是()!!! - 取石子游戲矾芙，
巨坑！要么用a/b>=2近上， 要么用long long a,b; - 去除注釋剔宪，
cin.getline(s,200)之后對字符的處理、多種情況的考慮沒有測試 - 求逆序數(shù)對即是求歸并排序的交換次數(shù)壹无，背代碼
- 坦克大戰(zhàn)葱绒，BFS的處理
map越界！ - 背包問題斗锭，
d[j]=max(d[j-a]+b,d[j])//j是背包可承受的最大重量地淀，注意上限！
- 樹的處理岖是，找規(guī)律
- 寶昌縣長要修路帮毁，最小生成樹的編寫，雙邊距離
15推免
- 水
- 矩陣轉(zhuǎn)置
- 行程編碼
- 去除重復(fù)的數(shù)
- 分解因數(shù)豺撑，遞歸：
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 深度優(yōu)先
- 背包問題
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++)//這個數(shù)有多少個
if (j-x>=0)
dp[j]+=dp[j-x];
- 查找二叉樹烈疚；得到一行中不確定個數(shù)的數(shù)字
輸入有可能是0
while((c=getchar())!='\n')
{
if(c>='0'&&c<='9')
{
ungetc(c,stdin);
cin>>a[i++];
}
} - Floyd，找兩點之間所要經(jīng)過的最小“最大距離”聪轿。
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夏令營
- 水
- 水
- 數(shù)組的遍歷
考慮只有一行的情況！ - qsort不能有兩個cmp方法陆错，合影
- 相同字符串的尋找灯抛，題意的理解
- To Europe，動態(tài)規(guī)劃Ｒ舸伞：
t=l*1.0/s+result[j-1];//int變double对嚼，考慮到每一層的最優(yōu)情況
BFS，考慮的是方向不是距離
相鄰的點可以到達(dá)用普通的BFS不行绳慎，因為即使當(dāng)前的點是segment最少的點纵竖，也不能保證接下來找到點是segment最少的。
從原點開始偷线，把1步磨确、2步…能走到的點都放進(jìn)隊里。
而不是只找可以走到的一個點審題声邦！每一個輸入之后有一個空行memset(v,0,sizeof(v));二叉查找樹的建立
兩點之間的最短距離
16推免（check）
- 石頭剪刀布
- 字符串判斷乏奥，
'a'-'A'=32極值Z的處理 - 矩陣輸出順序
- DFS，背代碼亥曹，遞歸的利用
不是可能性邓了！是數(shù)獨的要求恨诱！
- 10000個數(shù)的計算，不能直接計算骗炉，而是每次計算都取余數(shù)照宝，類似背包問題用0、1存結(jié)果
1. %的結(jié)果可能是負(fù)的句葵！
2. 不管是+a[i]還是-a[i]都可能出現(xiàn)mod是負(fù)的厕鹃！
3. 動態(tài)規(guī)劃，用dp[10001][101]存儲乍丈！
- 畫家問題剂碴，和POJ的題不一樣，不能簡單的枚舉否則會超時轻专。
for(int k=0; k<pow(2.0, n); k++)
getLine(k);
void getLine(int k)
{
//通過二進(jìn)制枚舉第一行可能發(fā)生的所有情況
int j = n;
while(j>0)
{
line[j] = k % 2;//line[j]代表第一行的第j列翻轉(zhuǎn)
k /= 2;
j--;
}
}
- 最小生成樹忆矛、字符串的處理
not by me
string temp1;
if(temp1.compare(a[j])==0)
- 二叉樹路線的計算
not by me - Magical GCD的理解
動態(tài)規(guī)劃，gcd函數(shù)要自己寫
16夏令營
- 水
- 單詞翻轉(zhuǎn)请垛，調(diào)試
- 加密催训，矩陣的操作
- 文件結(jié)構(gòu)圖，目錄里的文件也要排序宗收，因此一定要用遞歸
recur(string s1,int N,int T) //T是test的序號漫拭，N是文件層次的序號
- 匯率計算，精度的改變镜雨，用兩個數(shù)組決定換不換
double update(double a)
{
a=a*100;
int y=int(a);
return y/100.0;
}
- BFS嫂侍，迷宮儿捧，背代碼
- 前序遍歷荚坞、中序遍歷變?yōu)楹笮虮闅v。讀取一行的兩個字符串
cin>>s1>>s2 - 最小生成樹
- 多米諾菲盾，f[i][j]為枚舉到第i個數(shù)差為j時最少交換了多少次颓影，要考慮j為負(fù)數(shù)的情況。
f[i][j]=min(f[i][j],f[i-1][j-(a[i]-b[i])],f[i-1][j+(a[i]-b[i])]+1)
