文章列表
Tencent面试回顾和总结
- 博客分类：
- 经验之谈
昨天参加完了Tencent的面试，作为人生中第一次正式的面试。我显然表现得非常的紧张，但是同时，还是学习到了很多经验。虽然悲剧，但是还是很要必要总结一下的。
面试的题目大概回忆如下：
1.Self Introduction
在这一块，一 ...
一 相关下载
(1)Java JDK下载:
进入该网页: http://java.sun.com/javase/downloads/index.jsp (或者直接点击下载)如下图:
选择 Download JDK 只下载JDK，无需下载jre.
(2)Eclipse下载
进入该网页: http://www.eclipse.org/downloads/ (或者直接点击下载:BT下载 HTTP下载)如下图:
本题是一道DP较为经典的题目，将规模分解变小。题意非常简单，求n个点的连通图个数。（n<=50）由于数据量较大，必须使用高精度，代码会显得非常长。这里使用java秒过。思路：使用n个点构成图全部方案数减去不连通图的个数。设F[n]表示n个点的不连通图的个数设a[n]表示n个点的连通图的个数则F[n]=sum{ c(n-1,k-1) * 2^(c(n-k,2)) * a[k] } 1<=k<=n//除去第n个点，我们需要从剩余的n-1个点中选取k-1个点，作为第n个点所在的连通分支并且连通分支的总点数位k，剩余的n-k个点任意构图，最后再乘以k个点可以构成的连通图的个数即可。 ...
poj 2823 Sliding Window
- 博客分类：
- dp
一道非常经典的单调队列问题。
使用了递增和递减型两种单调队列。
注意单调队列构造的基本形式
int head=0,tail=1;
for(int i=1;i<=m;i++)
{
while(head<=tail && a[deque[tail]]<=a[i]) tail--;
deque[++tail]=i;
}
单调队列里一般我们都是存放的数据对应的角标。
本题就是要求对于一个给定的数列，求出他所有的长度为m的子序列的最大值和最小值。
使用单调队列进行维护，输出单调队列队首元素即可。这种代码比较具有对称 ...
fzu 1894 单调队列
- 博客分类：
- dp
单调队列，顾名思义，单调的队列。
能够用单调队列优化的问题一定符合一个性质：在你加入一个元素后，不优于这个元素的元素没有存在的必要了。
本题题意不再赘述。
用一个普通队列维护本来的队伍，FIFO，保证入队与出队的顺序。
再用一个单调队列维护最大人品，队首一定对应最大人品的序号。
为了防止最大人品对应的人已经出队，需要进行判断，处理完这些，这道题也差不多了。
#include <stdio.h>
#include <string.h>
char s[10];
int rp;
int deque[1000001];
int queue[ ...
NENU 最大连续和
- 博客分类：
- 数论
模板题，直接使用最大连续子段和即可。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int n;
int a[50005];
int maxsum(int a[], int n)
{
int start,end;
int tmp = a[0];
int max = a[0];
int i, tmpstart = 0, tmpend = 0;
start = 1;
end = 1;
for(i = ...
NENU 博士的化学元素发音问题
- 博客分类：
- dp
某天，博士突然对化学无比狂热，对化学的无比狂热使得他认为自己说的每一句话都应该由元素名称组成的，例如：“I Am CLaRa”（I是碘，Am是镅，C是碳，La镧，Ra是镭），“InTeRnAtIONAl”。但是有些词他是不能说的，例如“collegiate”, “programming” and “contest”。
现在给你一些单词，博士希望你确定这些单词是他是否能说，如果能输出YES，不能输出NO。
Input
第一行T表示数据组数。
下面T行每行一个字符串，表示博士询问的词语。长度不超过5W
附录
NENU 密码破译III
- 博客分类：
- 数论
Description
命案现场，死者用血写了Mersenne_prime(x)，这样一个式子，可是x这个整数已经难以识别了，只能分辨出应该是2~64的一个整数。
为了协助破案，柯南需要求出3~64的梅森数，并且要确定它们是不是梅森素数。
如果不是梅森素数，柯南还需要对他们进行质因数分解，以探求他们之间的规律。
Input
输入有多组，每组输入数据占一行，包含一个整数x，2<=x<=64。
Output
如果 y = 2x - 1 是一个梅森素数，则输出一行：“y is Mersenne prime.”，
否则输出两行，第一行输出：“y is NOT Mersen ...
NENU 怪盗基德的游戏
- 博客分类：
- 搜索
Description
Kid和新一开始玩一个有趣的游戏。游戏规则是这样的：在一个n*m棋盘中，某个位置有一颗棋子，并且有些位置是不能走的。现在两个人轮流操作，每次可以将棋子向上下左右的格子里走一格，不能走出边界。若一方不能行动，或者走到了已经走过的格子，则算失败。 现在给出棋盘的初始状态，柯南先行。请判断当双方均用最优策略时，柯南是否可以获胜。
Input
数据有多组。 第一行为两个数n, m (2 <= n, m <= 5)。代表棋盘有n行m列。 接下来有n行，每行m个字符，代表棋盘的初始状态。其中’.’代表可行区域，’x’代表不能走的区域，’S’代表棋子的初始位置 ...
NENU 雪莉的命运II
- 博客分类：
- 搜索
黑暗组织终究找到了雪莉的住址，雪莉只好躲在一个角落里。黑暗组织会在1~T秒的某些个时间点搜查这个角落，为了避免被黑暗组织抓到，雪莉配制了K(K <= 10)瓶隐身药剂，每瓶药剂有相应的持续时间ti。如果她在第t秒喝下药剂i，那么她会在[t, t+ti-1]时间段上保持隐身而避免被抓到。现在给出药剂的数量K以及每瓶药剂的持续时间，黑暗组织搜查雪莉藏身处的时间点，以及总时间T。如果雪莉使用了最好的喝药策略，她可以安全脱身么？
例如T = 10, K = 2, N = 5, ti={4, 2}，xi={3, 4, 6, 8, 9}时。雪莉可以在第3s喝下第一 ...
水题，水过。
模板：将一个数（可以是负数）反序。
int work(int n)
{
int flag=1;
if(n<0)
{
flag=0;
n=n*-1;
}
int k;
for(k=0;n>0;n/=10)
k=10*k+n%10;
if(!flag)
return -k;
return k;
}
#include <cstdio>
#include <iostream> ...
题目大意：求出第n行的符号要求的元素总数。
首先需要明确两个概念：
1.法里数列：n阶法里数列表示从0到1之间分母不大于n的最简分数集合。
同时对于法里数列的长度我们有如下计算公式
。
其中φ(n)表示欧拉函数。
2.欧拉函数：
欧拉函数表示小于或等于n的正整数中于n互质的数的个数，例如φ(8)= 4 ={1,3,5,7}；
求欧拉函数的模板如下：
long long eular(int n)
{
Eular[1]=1;
for(int i=2;i<=n;i++)
if(!Eular[i])
fo ...
hdu 4540 打地鼠
- 博客分类：
- dp
中文题，题意非常简单，这里不赘述了。
显然状态之间具有联系，考虑使用动归。
设dp[i][j]表示第i时刻敲第j个出来的地鼠的最小消耗能量。
则构建dp方程如下：
dp[i][j]=min(dp[i][j],dp[i-1][p=1...k]+abs(pos[i][j]-pos[i-1][p]));
代码如下：
#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
int n,k;
int pos[25][15];
int dp[2 ...
hdu 1421 搬寝室
- 博客分类：
- dp
题意非常简单，一道中文题。
首先将所有重量进行排序，我们容易证明，两个相邻的数的差平方一定比其他位置的差平方要小。
那么dp方程就好写了，设dp[i][j]表示从i个物品里选出j对最小的疲劳度。则dp方程如下：
dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+(weigh[i]-weigh[i-1])^2)
只考虑最后一个物品，如果他不能被选上，就相当于从前i-1个物品里面继续选j对，
否则如果这个物品被选上了，根据前面的证明，只有可能和他配对的是第i-1个，于是就相当于从前i-2个里面选j-1对，再加上新的那一对疲劳度。
#include ...
网络流算法 网络流算法用于解决从源点到汇点最大流的问题。 Edmonds-Karp算法 算法主要思想： 每次BFS找到一条从源点到汇点的最少路径数的可行路径，同时把这条路径塞满，这条路上的最小容量即为这条路径的流量。然后将这条路径的正向边删除，增加一条容量相同的反向边，当BFS无法进行下去的时候，则算法结束，最大流为每次BFS找到的可行路径的流量和。
Poj1273 Drainage Ditches
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <qu ...