我知道的大数据



      随着科技的发展,信息的收集也越来越容易,再加上摩尔定律,大的数据量处理也成为了可能。

什么是大数据,也许你有几千个人的基本信息、也许你有数百条购物记录,但这都不不是大数据,大数据至少在千万的数据量上。

     大数据有什么作用?其实数据中是包含各种规律的,互联网时代的数据以不在那么直观,再加上超大的数据量,人工已经很难从中找到规律或者关联了,但这并不意味着这些规律联系永远无法被发掘出来,事实上,计算机的飞速发展和机器学习数据挖掘相关理论的发展为挖掘其规律带来了可能,建立适当的模型,我们就可以发掘出其中一部分关联规律,但我相信并不是所有的,可能任何数据中都有其隐藏的深层规律。理论在逐步完善,科技也在飞速发展,我相信未来这些问题都会被一一解决的。

       也许很多人对大数据的作用没有直观的了解,举几个简单的例子。看过《大数据时代》的人可能都知道这个例子,如果你有超市所有的购物记录的话,你可能会发现,很多人在买尿布时都会买啤酒,你将这两者摆在一起,很容易提升其销量。另外,还有好多类似的例子,这里我再说一下推荐系统,如果你常在当当或者亚马逊买书的话,你会看到网站会推荐一些书,很多时候,你要买的下一本书就在其中,这并不是网站猜的准,其实是根据大量的数据进行分析得来的。比如1万个买了《机器学习》的用户中有1000个又买了《机器学习导论》,这要比买其它书的比例高的多,那么如果你买了《机器学习》,系统就会认为你非常有可能会买《机器学习导论》,这时候就把这本书推荐给你。
这只是根据用户购买行为进行分析的推荐方法,还有对商品类别进行分析的推荐方法,可能准确率会更高些。事实上,亚马逊有三分之一的订单来着于它的推荐系统。

       我感觉,大数据会变革非常多的行业,实际上已经变革了很多行业了。

       传统的交通行业首先应当被变革。你应该注意到街上的红绿灯了,每天每个时段间隔时间都是一样的,但事实上,每天不同手段过往的车流量并不是一样的,适当改变红绿间隔时间,也许会大大降低汽车尾气的排放量并节省能源。这并不是很难实现,只要在现有红绿灯上加装传感器统计不同时段的车流量即可。统计所有易发交通事故的地方,然后在那些易发地适当的做些措施,可能会挽救很多人的生命。听说智能交通已经有人在做了。 另外,大数据也可以用来做基础设施的选址的依据,可节约很多成本,甚至规划公交路线,这也不是不可能。

       现在人们所能收集的数据只占所有数据中非常小的一部分,能发掘的信息也是少部分,以后可能随着传感器的大量应用,我们会获取的前所未有的数据,这些数据将帮助我们过上更优的生活,甚至解决一些人类目前没有解决的问题,我感觉以后就是人工智能和大数据的天下了。

14年7月总结


       从搬完宿舍以来,过的一天不如一天,甚至每天早上6点钟自然醒的能力都开始慢慢丧失了,而且白天还比较嗜睡,一躺下没两个小时肯定不够。这两天也基本上没学什么东西,浪费了好多时间,感觉心里老是毛毛的,也有一丝的愧疚。就以这个状态,怎么去参加秋招。。。


       再回想前一段时间,复习操作系统那一周最充实了,不光只看了操作系统,还看了《饥饿游戏》三部曲,另外,开始看Andrew
Ng机器学习公开课,初次尝试使用 番茄土豆这个时间管理软件,每天45分钟的番茄至少有7个。虽然操作系统上课从来也没听过,但一周的复习还是很有效果的,感觉考挺好的,虽然只考了63分,不过考的轻松加愉快。

       考完操作系统,离开了我住了三年的宿舍,搬到9公寓暗无天日的地方,开始很不爽,首先搬宿舍那么累,再来环境比原来差多了。可后来想想,宿舍对我而言已经沦落到只是一个睡觉的地方了,何必在意呢!
况且,要老是为一些小事而影响到自己的心情,那我们活着还有什么乐趣。搬宿舍并不仅意味着坏处,任何事都有对立的一面,搬过来也离同级其他人比较近了。一直以来,与其说计算机学院把11级大部分人孤立了,倒不如说是11级大部分人把我们孤立了,搬过去倒结束了这格局。

      考完操作系统,以放松的心态,开始了这一段时间最浑浑噩噩的状态了,就是一种不正常的心态。再来就是操作系统课设了,找了一个很靠谱的搭档,果然省事的多,结对编程,两天搞定课设,报告就是他的事了,表示课设做的很是轻松愉快。

       三件事打乱了我原有的生活状态,搬宿舍、操作系统课设,再加上搬教室。课设让我本该自己学习的时间大多数都变成了和别人扯淡,搬教室让我没了网,严重影响到学习,以至于我机器学习的课程落下了一周,直到上周六才补交了coursera上week
2的编程练习(还是参考别人代码),这两天才在做week 1和week 2的review question,因为晚做,让我损失了20%的分数,说来这应该“得益于”我不定期的拖延。

      再来就是自学的有关机器学习的课程了。之前就买了《机器学习》《机器学习实战》两本书,也看过一部分Andrew Ng coursera上的视频,但收获甚微。一来就是自己没认真看认真记,二来就是没有任何练习。上个月《机器学习》又开课了,强迫自己跟着看,并把后面的习题做了。越来越觉得有些事,只要认真去做了,有时候很简单。对于我来说,学习机器学习的路还很漫长,需要脚踏实地一步步来。另外,我想,我也该尝试把刚学完的线性回归这一部分总结出来了,一来是看我的理解程度,二来希望对其他人有所帮助。


      这段时间也并不是整天无所事事,也看了几本书,其中不乏非常好的书。
     重读吴军的《数学之美》,如果加上浏览的一遍,这应该已经是第四遍了,又理解了不少的东西,再次加深了好书经得起多次读印象。再来就是
唐纳德的《研究之美》,大师的手笔,如果读懂想必收获颇丰
。可惜,一堆无聊了符号,加上难懂的推理定义,让我失去兴趣,只能硬着头皮看过一遍。还有一本比较难懂的《图灵的秘密》,其实开始还行,一些有趣的推论证明,比如读此书我知道了任何证明√2是无理数……,但后来,再次出现了对我来说晦涩难懂的定理推论什么的,至此此书被搁置一旁,然后才了解自己的数学有多弱。(一共搁置了三本书了《图灵的秘密》《时间简史》《暗淡蓝点:展望人类的太空家园》
      加上自己在学机器学习的课程,开始慢慢感觉到数学的重要性,程序只是实现工具,其本质还是数学。高中和大学的课程让我丧失了对数学的兴趣,所以我数学比较差,势必今后要花大量的时间精力去恶补数学。现在才体会到数学这东西,学再好都不为过。我觉得,对于计算机专业的学生来说,数学应该是必备的技能,可惜学校没让我们了解到数学在计算机学科中的重要性,更没培养我们对于数学的兴趣。所以我在这推荐看一下吴军的《数学之美》。
      除了这两本难懂的书外,也看了两本小说。 《饥饿游戏》,这本书给我的现实意义就是让我决心放弃唯一看的一类型的电影——科幻片。加上之前看了《云图》及电影,《安德的游戏》及电影。对比电影和小说,电影删减了好多东西,甚至修改了原剧情,表示开始有点反感小说改编电影了。不过倒是可以理解,那么长的小说压缩两个小时,不改改也不大可能。至此,不再看电视剧,不再看综艺节目,不再看电影,不再看动漫。
        一本《达芬奇密码》,差点一改我对基督教的看法,果然一家之言不可信,任何事都得有理有据才能相信,艺术是艺术,现实是现实,如果有人在看这本书,最好区分小说和现实。
       《岛》,我感觉是这两个月来看过最好的一本小说了,有非常吸引人的情节,与《达芬奇密码》单纯给人的好奇感相比,《岛》给我更人性化的吸引力。

        今天看完了《生命中不能承受只轻》,其实书名吸引我看了这本书,我就想知道生命中不能承受之轻是什么,不过我没找到答案。豆瓣书评说,米兰•昆德拉的书不是一遍就能懂的,但我没打算最近在看一遍该书。其他人的感悟,生命中总会有挫折、困难、压力压着我们,倒让我们更现实,如果有一天,这些都不见了,生命却给你一种飘飘然的感觉,却也变得无趣了。压力、挫折、困难就是生命之重,而解脱是生命之轻,这种轻却常让我们难以承受。

       关于我看过的更多的书,请戳这 here

      其实动手写之前,感觉没什么要写的,写完了才觉得自己什么都没写,加上去年对区预赛的总结,和对13年的总结,这只是我的第三篇总结。看过一些博客,才觉得自己应该慢慢学着去总结,一点点的积累进步,最终都会有成果的,刘未鹏写了8年博客,至少每月一篇,将所有博客一总结,就是《暗时间》了。



Stanford 机器学习练习 Part 1 Linear Regression



warmUpExercise.m

function A = warmUpExercise()
%WARMUPEXERCISE Example function in octave
%   A = WARMUPEXERCISE() is an example function that returns the 5x5 identity matrix
    A = [];

% ============= YOUR CODE HERE ==============
% Instructions: Return the 5x5 identity matrix 
%               In octave, we return values by defining which variables
%               represent the return values (at the top of the file)
%               and then set them accordingly. 
    A = eye(5);
% ===========================================
end

computeCost.m

function J = computeCost(X, y, theta)
%COMPUTECOST Compute cost for linear regression
%   J = COMPUTECOST(X, y, theta) computes the cost of using theta as the
%   parameter for linear regression to fit the data points in X and y
% Initialize some useful values
m = length(y); % number of training examples
% You need to return the following variables correctly 
J = 0;
% ====================== YOUR CODE HERE ======================
% Instructions: Compute the cost of a particular choice of theta
%               You should set J to the cost.
J = sum((X*theta - y).^2) / (2*m);
% =========================================================================
end

plotData.m

function plotData(x, y)
%PLOTDATA Plots the data points x and y into a new figure 
%   PLOTDATA(x,y) plots the data points and gives the figure axes labels of
%   population and profit.
% ====================== YOUR CODE HERE ======================
% Instructions: Plot the training data into a figure using the 
%               "figure" and "plot" commands. Set the axes labels using
%               the "xlabel" and "ylabel" commands. Assume the 
%               population and revenue data have been passed in
%               as the x and y arguments of this function.
%
% Hint: You can use the 'rx' option with plot to have the markers
%       appear as red crosses. Furthermore, you can make the
%       markers larger by using plot(..., 'rx', 'MarkerSize', 10);

figure; % open a new figure window
plot(x, y, 'rx', 'MarkerSize', 5);
xlabel("x");
ylabel("y");
% ============================================================
end

gradientDescent.m

function [theta, J_history] = gradientDescent(X, y, theta, alpha, num_iters)
%GRADIENTDESCENT Performs gradient descent to learn theta
%   theta = GRADIENTDESENT(X, y, theta, alpha, num_iters) updates theta by 
%   taking num_iters gradient steps with learning rate alpha
% Initialize some useful values
m = length(y); % number of training examples
J_history = zeros(num_iters, 1);

for iter = 1:num_iters
    % ====================== YOUR CODE HERE ======================
    % Instructions: Perform a single gradient step on the parameter vector
    %               theta. 
    %
    % Hint: While debugging, it can be useful to print out the values
    %       of the cost function (computeCost) and gradient here.
    %
    temp = 0;
    temp = temp + alpha/m * X' * (y - X * theta);
    theta = theta + temp;
    % ============================================================
    % Save the cost J in every iteration    
    J_history(iter) = computeCost(X, y, theta);
end
end

ex1.m

%% Machine Learning Online Class - Exercise 1: Linear Regression

%  Instructions
%  ------------
% 
%  This file contains code that helps you get started on the
%  linear exercise. You will need to complete the following functions 
%  in this exericse:
%
%     warmUpExercise.m
%     plotData.m
%     gradientDescent.m
%     computeCost.m
%     gradientDescentMulti.m
%     computeCostMulti.m
%     featureNormalize.m
%     normalEqn.m
%
%  For this exercise, you will not need to change any code in this file,
%  or any other files other than those mentioned above.
%
% x refers to the population size in 10,000s
% y refers to the profit in $10,000s
%

%% Initialization
clear ; close all; clc

%% ==================== Part 1: Basic Function ====================
% Complete warmUpExercise.m 
fprintf('Running warmUpExercise ... \n');
fprintf('5x5 Identity Matrix: \n');
warmUpExercise()

fprintf('Program paused. Press enter to continue.\n');
pause;


%% ======================= Part 2: Plotting =======================
fprintf('Plotting Data ...\n')
data = load('ex1data1.txt');
X = data(:, 1); y = data(:, 2);
m = length(y); % number of training examples

% Plot Data
% Note: You have to complete the code in plotData.m
plotData(X, y);

fprintf('Program paused. Press enter to continue.\n');
pause;

%% =================== Part 3: Gradient descent ===================
fprintf('Running Gradient Descent ...\n')

X = [ones(m, 1), data(:,1)]; % Add a column of ones to x
theta = zeros(2, 1); % initialize fitting parameters

% Some gradient descent settings
iterations = 1500;
alpha = 0.01;

% compute and display initial cost
computeCost(X, y, theta)

% run gradient descent
theta = gradientDescent(X, y, theta, alpha, iterations);

% print theta to screen
fprintf('Theta found by gradient descent: ');
fprintf('%f %f \n', theta(1), theta(2));

% Plot the linear fit
hold on; % keep previous plot visible
plot(X(:,2), X*theta, '-')
legend('Training data', 'Linear regression')
hold off % don't overlay any more plots on this figure

% Predict values for population sizes of 35,000 and 70,000
predict1 = [1, 3.5] *theta;
fprintf('For population = 35,000, we predict a profit of %f\n',...
    predict1*10000);
predict2 = [1, 7] * theta;
fprintf('For population = 70,000, we predict a profit of %f\n',...
    predict2*10000);

fprintf('Program paused. Press enter to continue.\n');
pause;

%% ============= Part 4: Visualizing J(theta_0, theta_1) =============
fprintf('Visualizing J(theta_0, theta_1) ...\n')

% Grid over which we will calculate J
theta0_vals = linspace(-10, 10, 100);
theta1_vals = linspace(-1, 4, 100);

% initialize J_vals to a matrix of 0's
J_vals = zeros(length(theta0_vals), length(theta1_vals));

% Fill out J_vals
for i = 1:length(theta0_vals)
    for j = 1:length(theta1_vals)
      t = [theta0_vals(i); theta1_vals(j)];    
      J_vals(i,j) = computeCost(X, y, t);
    end
end


% Because of the way meshgrids work in the surf command, we need to 
% transpose J_vals before calling surf, or else the axes will be flipped
J_vals = J_vals';
% Surface plot
figure;
surf(theta0_vals, theta1_vals, J_vals)
xlabel('\theta_0'); ylabel('\theta_1');

% Contour plot
figure;
% Plot J_vals as 15 contours spaced logarithmically between 0.01 and 100
contour(theta0_vals, theta1_vals, J_vals, logspace(-2, 3, 20))
xlabel('\theta_0'); ylabel('\theta_1');
hold on;
plot(theta(1), theta(2), 'rx', 'MarkerSize', 10, 'LineWidth', 2);


featureNormalize.m

function [X_norm, mu, sigma] = featureNormalize(X)
%FEATURENORMALIZE Normalizes the features in X 
%   FEATURENORMALIZE(X) returns a normalized version of X where
%   the mean value of each feature is 0 and the standard deviation
%   is 1. This is often a good preprocessing step to do when
%   working with learning algorithms.

% You need to set these values correctly
X_norm = X;
m = size(X, 2);
mu = zeros(1, size(X, 2));
mu = mean(X);
sigma = std(X);
for i = 1:m
    X_norm(:,i) = (X(:,i).-mu(i))./sigma(i);
end
% ====================== YOUR CODE HERE ======================
% Instructions: First, for each feature dimension, compute the mean
%               of the feature and subtract it from the dataset,
%               storing the mean value in mu. Next, compute the 
%               standard deviation of each feature and divide
%               each feature by it's standard deviation, storing
%               the standard deviation in sigma. 
%
%               Note that X is a matrix where each column is a 
%               feature and each row is an example. You need 
%               to perform the normalization separately for 
%               each feature. 
%
% Hint: You might find the 'mean' and 'std' functions useful.
%       









% ============================================================

end

computeCostMulti.m

function J = computeCostMulti(X, y, theta)
%COMPUTECOSTMULTI Compute cost for linear regression with multiple variables
%   J = COMPUTECOSTMULTI(X, y, theta) computes the cost of using theta as the
%   parameter for linear regression to fit the data points in X and y
% Initialize some useful values
m = length(y); % number of training examples
% You need to return the following variables correctly 
J = 0;
% ====================== YOUR CODE HERE ======================
% Instructions: Compute the cost of a particular choice of theta
%               You should set J to the cost.
J = 1/(2*m) * ( X * theta - y)' * (X*theta - y);
% =========================================================================
end


gradientDescentMulti.m

function [theta, J_history] = gradientDescentMulti(X, y, theta, alpha, num_iters)
%GRADIENTDESCENTMULTI Performs gradient descent to learn theta
%   theta = GRADIENTDESCENTMULTI(x, y, theta, alpha, num_iters) updates theta by
%   taking num_iters gradient steps with learning rate alpha

% Initialize some useful values
m = length(y); % number of training examples
J_history = zeros(num_iters, 1);

temp = zeros(feature_number,1); 

for iter = 1:num_iters
    temp = alpha/m * X' * (y - X*theta);
    theta = theta + temp;
    J_history(iter) = computeCostMulti(X, y, theta); 
    % ====================== YOUR CODE HERE ======================
    % Instructions: Perform a single gradient step on the parameter vector
    %               theta. 
    %
    % Hint: While debugging, it can be useful to print out the values
    %       of the cost function (computeCostMulti) and gradient here.
    %
    % ============================================================
    % Save the cost J in every iteration    
    J_history(iter) = computeCostMulti(X, y, theta);

end

end

normalEqn.m

function [theta] = normalEqn(X, y)
%NORMALEQN Computes the closed-form solution to linear regression 
%   NORMALEQN(X,y) computes the closed-form solution to linear 
%   regression using the normal equations.

theta = zeros(size(X, 2), 1);

% ====================== YOUR CODE HERE ======================
% Instructions: Complete the code to compute the closed form solution
%               to linear regression and put the result in theta.
%
% ---------------------- Sample Solution ----------------------
theta = pinv(X' * X) * X' * y;
% -------------------------------------------------------------
% ============================================================

end

ex1_multi.m

%% Machine Learning Online Class
%  Exercise 1: Linear regression with multiple variables
%
%  Instructions
%  ------------
% 
%  This file contains code that helps you get started on the
%  linear regression exercise. 
%
%  You will need to complete the following functions in this 
%  exericse:
%
%     warmUpExercise.m
%     plotData.m
%     gradientDescent.m
%     computeCost.m
%     gradientDescentMulti.m
%     computeCostMulti.m
%     featureNormalize.m
%     normalEqn.m
%
%  For this part of the exercise, you will need to change some
%  parts of the code below for various experiments (e.g., changing
%  learning rates).
%

%% Initialization

%% ================ Part 1: Feature Normalization ================

%% Clear and Close Figures
clear ; close all; clc

fprintf('Loading data ...\n');

%% Load Data
data = load('ex1data2.txt');
X = data(:, 1:2);
y = data(:, 3);
m = length(y);

% Print out some data points
fprintf('First 10 examples from the dataset: \n');
fprintf(' x = [%.0f %.0f], y = %.0f \n', [X(1:10,:) y(1:10,:)]');

fprintf('Program paused. Press enter to continue.\n');
pause;

% Scale features and set them to zero mean
fprintf('Normalizing Features ...\n');

[X mu sigma] = featureNormalize(X);

% Add intercept term to X
X = [ones(m, 1) X];


%% ================ Part 2: Gradient Descent ================

% ====================== YOUR CODE HERE ======================
% Instructions: We have provided you with the following starter
%               code that runs gradient descent with a particular
%               learning rate (alpha). 
%
%               Your task is to first make sure that your functions - 
%               computeCost and gradientDescent already work with 
%               this starter code and support multiple variables.
%
%               After that, try running gradient descent with 
%               different values of alpha and see which one gives
%               you the best result.
%
%               Finally, you should complete the code at the end
%               to predict the price of a 1650 sq-ft, 3 br house.
%
% Hint: By using the 'hold on' command, you can plot multiple
%       graphs on the same figure.
%
% Hint: At prediction, make sure you do the same feature normalization.
%

fprintf('Running gradient descent ...\n');

% Choose some alpha value
alpha = 0.01;
num_iters = 400;

% Init Theta and Run Gradient Descent 
theta = zeros(3, 1);
[theta, J_history] = gradientDescentMulti(X, y, theta, alpha, num_iters);

% Plot the convergence graph
figure;
plot(1:numel(J_history), J_history, '-b', 'LineWidth', 2);
xlabel('Number of iterations');
ylabel('Cost J');

% Display gradient descent's result
fprintf('Theta computed from gradient descent: \n');
fprintf(' %f \n', theta);
fprintf('\n');

% Estimate the price of a 1650 sq-ft, 3 br house
% ====================== YOUR CODE HERE ======================
% Recall that the first column of X is all-ones. Thus, it does
% not need to be normalized.
price = 0; % You should change this


% ============================================================

fprintf(['Predicted price of a 1650 sq-ft, 3 br house ' ...
         '(using gradient descent):\n $%f\n'], price);

fprintf('Program paused. Press enter to continue.\n');
pause;

%% ================ Part 3: Normal Equations ================

fprintf('Solving with normal equations...\n');

% ====================== YOUR CODE HERE ======================
% Instructions: The following code computes the closed form 
%               solution for linear regression using the normal
%               equations. You should complete the code in 
%               normalEqn.m
%
%               After doing so, you should complete this code 
%               to predict the price of a 1650 sq-ft, 3 br house.
%

%% Load Data
data = csvread('ex1data2.txt');
X = data(:, 1:2);
y = data(:, 3);
m = length(y);

% Add intercept term to X
X = [ones(m, 1) X];

% Calculate the parameters from the normal equation
theta = normalEqn(X, y);

% Display normal equation's result
fprintf('Theta computed from the normal equations: \n');
fprintf(' %f \n', theta);
fprintf('\n');


% Estimate the price of a 1650 sq-ft, 3 br house
% ====================== YOUR CODE HERE ======================
price = 0; % You should change this


% ============================================================

fprintf(['Predicted price of a 1650 sq-ft, 3 br house ' ...
         '(using normal equations):\n $%f\n'], price);


http://regex.alf.nu/ 非标准答案


网站链接

这是一个练正则表达式的好文章,有几个题目都比较意思,以下是参考答案,如果有得分更高的答案请告诉我,大家交流一下。

  1. Plain strings (207)                             foo
  2. Anchors (206)                                     ick$
  3. Ranges (202)                                     [a-f]{4}
  4. Backrefs (201)                                   (…).*\1
  5. Abba (190)                                          ^((?!(.)(.)\3\2).)+$
  6. A man, a plan (176)                          ^(.)(.).*\2\1$
  7. Prime (286)                                        ^(?!(xx+)\1+$)
  8. Four (199)                                           (.)(.\1){3}
  9. Order (199)                                         ^.{5}[^e]?$
  10. Triples (574)                                       ^(([147]4|40|3[269]|9[05]|[378]1).+|0[369]*|[81][257])*$ 或 00($|3|6|9|12|15)|4.2|.1.+4|55|.17
     
    关于第10条,可参考 http://www.zhihu.com/question/24824487
  11. Glob (384)                                           (rr|ll|[lbr]o|en|ta|y|cr|eat|up).*\1
  12. Balance (287)                                    ^(<(<(<(<(<(<.*)*>)*>)*>)*>)*>)*$
  13. Powers (80)                                       ^(((x|x{8}|x{128})\3?)\2?)\1?$
  14. Long count (239)                              ((..)00 \2+01 \2+10 \2+11 ?){4}
  15. Long count v2 (239)                         ((..)00 \2+01 \2+10 \2+11 ?){4}
  16. Alphabetical (0)


http://jimliu.net/2014/01/04/regex-golf/

Ubuntu下python安装mysqldb(驱动)


最近在学习Django框架,需要使用到数据库,我使用的是mysql,跟java一样,需要安装驱动,这是驱动的下载网址http://sourceforge.net/projects/mysql-python/  要注意的是此网址已被墙,需要翻墙过去。

下载到压缩包后解压,然后执行安装命令

先跳转的该目录下,然后执行 sudo python setup.py install

然后就是各种问题,需要配置这个那个的。

其实

在终端中输入:sudo apt-get install python-mysqldb

然后一切OK,可以测试以下。

import MySQLdb


无报错就成功了

南京区域赛总结



    赛前就知道自己很难拿牌,从网络赛就可以看的出来,水平还远达不到拿奖的高度,连现场赛名额都是申请下来了。赛前两周,接到申请到名额的通知,就和晨晨一起推掉之前张老师让参加的一个山东省的竞赛。感觉的出来,这是一个很难得的机会,很多人都想参加,但最后综合各个方面,选了我和宁宁还有晨晨参加,就这样,Pioneer就组建起来了(这个队名是我起的,中文意思开拓者,先驱的意思,见文知意,就是希望能开拓出理工大acm的一片新天地)。其实我和晨晨算老搭档了,省赛的时候就一个队的,虽说和宁宁是第一次组队,其实我很相信他的能力的。
    两周的时间准备确实是有点匆忙,再加上其他乱七八糟的事,真正准备的时间少之又少,只能回顾一下以前学过的那些算法(其实到现在我也没学到很多算法),然后总结一下模板,时间很快就过去了,都没做过训练。。。  反正还是自己太水,我相信真正的大神都不需要做什么训练。
    周五晚上到达南京,差点就露宿街头了,果然周末晚上宾馆酒店都是爆满了。通过这件事我了解到再充足的准备都有可能是不充足的,尤其是在陌生的地方。周六早上其实最大的收获就是终于见到了传说中的黄金雄和周维民,虽然距离比较远,在加上近视,看不清脸,不过还是靠借的相机拍下来了,这东西比我眼睛好用多了。 
    说说热身赛吧,三道题,因为是热身赛,要求不严格,题目就直接摆桌上,赛前就开始看了,第一题水题,我花5分钟敲完交了,过了,全场第25个提交的。然后就是被虐的节奏了,第二题一个简单的记忆搜索,晨晨用普通搜索tle,然后我改记忆化搜索wa,然后看到题目有个64位整数的字样,int换long
long 继续wa,突然看见是可能超64位,然后我又换JAVA大数类,发现java准备也不是很充分,还好最后三个人把代码凑出来了,继续wa,他们两个都放弃这题攻第三题了,我就一直在考虑有什么陷阱没。这时候陆陆续续很多人AK了,右上角是google队,左上角南京理工,右后方北大,左边右边具体哪个学校忘记了,反正都是实力比较强的队,只有对面一个弱队,确实比我们还弱,也是第一次参加区域赛的学校,热身赛和正式赛都成为我自我安慰的依据(还有队伍比我们弱),这点很不好,很多时候我们应该向前看而不不能向后看,眼光放长远一些,就如同我们常把目光局限在校内,自我感觉还良好,放青岛市,也不算最差,再稍微往外,一下子被虐成渣,切记人外有人,山外有山。还有,多被虐虐还是好的,至少让你认清自己现在的水平。回到热身赛,正当我们纠结b题时,惊现陈立杰,他出现在北大吴铮凯队伍旁边,几个人有说有笑的,一定是AK了闲的没事。然后我就在那仰望了他们好长时间,看他们调戏裁判。。。。最终B题最终发现重边的陷阱,不过还是wa一次,原因是改代码没改全。。
然后我就可耻的溜了,拉着同学去玩了,剩下他们两个继续C题,不过晚上我回去问最终还是没做出来。热身赛从头到尾都没看board,没敢看,无数人ak的时候我们还纠结第二题。。。。


    然后就是更坑的正式赛了,因为太紧张,开机密码一直输错,只能让他们输了。 拿到题目第一眼看到A题是水题,又是题目没看完整就敲了,幸好样例没过,不然就贡献一次wa了,最终19分钟1A,还是有点慢了,全场第90多个A的。然后刷榜看那道题简单,最后锁定一道题,他们俩就那讨论了,我继续看其他题目,期间周围队伍气球一个接一个的挂,越看越着急。第二题还是1A,时间已经过去很久了,排名100左右,后来因为一道题也没A出来,排名一直掉,其实到现在我都没看最终榜,不忍心看。后来我们又尝试做另外一道题,全场做出最多的三道题(前两题已经过了),他们俩毫无思路,就我一个人一直想这个,本来略有思路,最后半个小时,极度的紧张,效率极其低,不过最终证明自己的思路完全是错的。。 
就这样结束了,打了酱油了,正好江游宣传海报也是我们一起打酱油吧!  恩   跟你们一起了。


    参加完江游的宣讲会,然后就是颁奖典礼了,南京理工准备的节目很精彩,尤其是舞龙那个,很好看。上交好厉害,10题,加上6个first blood,陈立杰都认怂了,话说他们9题也很厉害。谷歌的两个队(据说全是wf队员,有个和刘汝佳02年拿银牌的)8题,其他的记不住了。还有上交的一个女队也让人印象深刻,开幕式的讲话和最终的成绩。山科海洋石油大学都比我们好多了,我们弱爆了。


    这两天看见陈立杰好几次,然后一直思考,同样是ACMer,为什么人家可以做到那个高度,为什么我们不能,也没看见他比我们有什么地方长的特殊,从codeforces上的记录就可以看出,人家在初三就可以虐我们了。不光是陈立杰,还有很多其他的大牛,我想他们搞acm的时间也比我们长不了多长时间,我们弱的原因肯定是我们花的功夫不够。前段时间看了3xian(他是国内少有的大学接触acm还进wf的人)的一篇博客,他指出了国内好多acmer的通病,很多时候不愿意自己独立思考,盲目追求题量,不注重质量,而且还静不下心了,这成了大多数人无法突破瓶颈的主要原因,我也差不多。还有,看他的经历,也曾经经历过挂科,差不多也是大一下学期开始acm生涯的,然后就进wf了,一样的经历,不一样的结果,一个原因,自己下的功夫比不过他,什么智商是硬伤就是为自己的不努力找借口,我承认这个世界上有天才,但并不是人人都是天才,绝大多数时候智商还是差不多的。
    其实这次的成绩远没达到我的期望值,上一届的把希望寄托在我们身上,我们却只能又把希望寄托在下一届的身上。不过看现在大家的水平,这依旧是一个漫长的过程。

codeforces 347A – Difference Row


给你一个序列,让你求(x1 - x2) + (x2 - x3) + … + (xn - 1 - xn).值最大的一个序列,我们化简一下公式就会发现(x1 - x2) + (x2 - x3) + … + (xn - 1 - xn).
= x1 – xn, 也就是说只有第一个和最后一个是确定的,其他的随便了!  也不是了, 还要让你按字典序最小的排列,也就是说其他的是按飞递减序排列的,简单的一次排序就OK了。

//2013-09-21-09.07
#include <stdio.h>
#include <algorithm>

using namespace std;

int a[120];

bool cmp(int x, int y)
{
    return x < y;
}

int main()
{
    int n;
    while (scanf("%d", &n) != EOF)
    {
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i]);
        }
        sort(a+1, a+n+1, cmp);
        swap(a[1], a[n]);
        for (int i = 1; i < n; i++)
            printf("%d ", a[i]);
        printf("%d\n", a[n]);
    }
    return 0;
}



codeforces 344B – Simple Molecules


       题意就是给出3个原子的化学价,然后组成一个分子,要保证这个分子是稳定的,如果你还记得高中化学知识的话这个很容易理解,然后让你求出1-2  2-3 1-3 号原子之间有几条键, 这里我分别用ta tb tc 表示, 用数学的方法表示出来的话就是a = tc + tb; b = ta+tc; c = ta + tb;可能有多种情况,只要输出一种即可。

      我们随便找其中一个原子,然后从0开始枚举它到b原子有多少键,根据上面的式子,可以计算出到c原子的键,然后就可以知另外两个原子间的键值,做一次判断即可,无需判断a = tc + tb; b = ta+tc; c = ta + tb; 因为计算工程中就用到了其中两个等式,保证其一定成立。 还有就是无法组成分子的情况,我们只要没找到满足条件的三个值就输出”Impossible”。

//cf 334B
//2013-09-19-15.57
#include <iostream>
#include <stdio.h>

using namespace std;

int main()
{
    int a, b, c;
    while (scanf("%d %d %d", &a, &b, &c) != EOF)
    {
        int flag = 1;
        for (int i = 0; i <= a; i++)
        {
            int tb = i, tc = a-i;
            if (tb > c)
                continue;
            int ta = c - tb;
            if (b == ta + tc)
            {
                printf("%d %d %d\n", tc, ta, tb);
                flag = 0;
                break;
            }
        }
        if (flag)
            puts("Impossible");
    }
    return 0;
}


hdoj 4712 Hamming Distance(靠人品过的)


我先解释一下汉明距离  以下来自百度百科

在信息论中,两个等长字符串之间的汉明距离是两个字符串对应位置的字符不同的个数。换句话说,它就是将 一个字符串变换成另外一个字符串所需要替换的字符个数。 例如:

* 1 与 0 之间的汉明距离是 1。

* 214 与 214 之间的汉明距离是 0。

* “abcd” 与 “aacd” 之间的汉明距离是 1。

汉明重量是字符串相对于同样长度的零字符串的汉明距离,也就是说,它是字符串中非零的元素个数:对于二进制字符串来说,就是 1 的个数,所以 11101 的汉明重量是 4。


汉明距离在信息论、密码学等方向有很重要的应用。

这个题是让你求n个数两两之间最小的汉明距离,而且规定了每个数是长度为5的16进制数,可以想到求出最大的值为20,最小为10。 没想到什么好的算法,看了人家的解题报告,依靠RP,随机找1000000对点求最小值,不过还是过了。

#include<algorithm>
#include<stdio.h>
#include <stdlib.h>
#define inf 1000000007

using namespace std;

int M[100005];
int count(int x,int y)
{
    int sum=0,p=x^y;
    while (p)
        sum+=p%2,p>>=1;
    return sum;
}

int main()
{
    int T,y,n,d,i,j,x;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d",&n);
        for (i=1;i<=n;i++)
        {
            scanf("%X", &M[i]);
        }
        int ans=inf;
        for (i=1;i<=1000000;i++)
        {
            x=rand()%n+1;
            y=rand()%n+1;
            if (x==y) continue;
            ans=min(ans,count(M[x],M[y]));
        }
        printf("%d\n",ans);
    }
    return 0;
}

hdoj 4706 Children’s Day


题目意思就是用a-z组成一个N,然后到z后又跳回a,输出宽从3到10的N。

#include <stdio.h>
#include <string.h>
char s[14][15];

int main()
{
    int cnt = 0;
    for (int kase = 3; kase <= 10; kase++)
    {
        memset(s, ' ', sizeof(s));
        for (int i = 1; i <= kase; i++)
        {
            for (int j = 1; j <= kase; j++)
            {
                cnt %= 26;
                if (i == 1 || i == kase)
                {
                    cnt %= 26;
                    s[j][i] = 'a'+cnt;
                    cnt++;
                }
                else
                {
                    if (i == j)
                    {
                        cnt %= 26;
                        s[kase-j+1][i] = 'a'+cnt;
                        cnt++;
                        break;
                    }
                }
            }
        }
        for (int i = 1; i <= kase; i++)
        {
            for (int j = 1; j <= kase; j++)
            {
                printf("%c", s[i][j]);
            }
            puts("");
        }
    }
    return 0;
}

hdoj 4715 Difference Between Primes 素数筛选+二分查找


#include <string.h>
#include <stdio.h>
const int maxn = 1000006;
bool vis[1000006];
int pr[1000005];
int cnt = 1;

int bs(int l, int r, int v)
{
    int mid=(l+r)>>1;
    while(l < r)
    {
        if(pr[mid] < v)
            l = mid+1;
        else
            r = mid;
        mid= (l+r) >> 1;
    }
    return l;
}

void getpr()
{
    int i,j;
    for(i=2;i*i<maxn;i++) if(!vis[i])
    {
        pr[cnt++]=i;
        for(j=i*i;j<maxn;j+=i) vis[j]=1;
    }
    for(;i<maxn;i++)if(!vis[i])
    {
        pr[cnt++]=i;
    }
}

int main()
{
    memset(vis, 0, sizeof(vis));
    getpr();
    int n, t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &n);
        int ans1 = 0;
        int ans2 = 0;
        for (int i = 1; i <= cnt; i++)
        {
            if (pr[i] <= n)
                continue;
            int x = bs(1, cnt-1, pr[i]-n);
            if (pr[i] - n == pr[x])
            {
                ans1 = pr[i];
                ans2 = pr[x];
                break;
            }
        }
        if (ans1)
            printf("%d %d\n",ans1, ans2);
        else
            puts("FAIL");
    }
    return 0;
}

poj 1503 高精度加法


把输入的数加起来,输入0表示结束。

先看我Java代码,用BigINteger类很多东西都不需要考虑,比如前导0什么的,很方便。不过java效率低点,平均用时600ms,C/C++可以0ms过。

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        BigInteger sum = BigInteger.valueOf(0);
        BigInteger a;
        a = cin.nextBigInteger();
        while (true) {
            sum = sum.add(a);
            if (a.compareTo(BigInteger.valueOf(0)) == 0)
                break;
            a = cin.nextBigInteger();
        }
        System.out.println(sum);
        cin.close();
    }
}

下面是我从网上找的C++代码,无外乎就是用数组模拟实现大数的加法。

#include<stdio.h>
#include<string.h>

#define N 20000

int ans[N],f,max;

void hadd(char a[])
{
    f=0;
    int n=strlen(a);
    for(int i=n-1;i>=0;i--)
    {
        a[i]-='0';
        ans[f]+=a[i];
        ans[f+1]+=ans[f]/10;
        ans[f]%=10;
        f++;
        if(max<f) max=f;
    }
}

int main()
{
    memset(ans,0,sizeof(ans));
    while(1)
    {
        char s[N];
        scanf("%s",s);
        if(strlen(s)==1&&s[0]=='0') break;
        hadd(s);
    }
    int flag=0;
    for(int i=N-1;i>=0;i--)
    {
        if((!flag&&ans[i]!=0)||flag||(!flag&&i==0))
        {printf("%d",ans[i]);flag|=1;}
    }
    puts("");
    return 0;
}

网协简介之——网协名人堂






   网协自成立以来,涌现出大批优秀的学生,在学校,考研考入名校的是我们网协人,获得优秀就业岗位的是我们网协人,拿到高薪资的也是我们网协人。




   说到网协,自然要问,网协是谁建立起来的呢? 这就不能不谈到我们网协的创始人之一————姜金男学长!他也是著名的“理工之窗”网站的创始人和现任站长(相信大家都有访问过http://www.qdlg.cn/),至今仍在运作,为理工广大师生提供服务。协会另一创始人杨长升学长在大一时就已经参加过程序竞赛,并且在抗击甲流期间,连熬夜几晚,为学生处开发了隔离学生信息系统,大大减轻了老师的工作量。这两位学长,在历建刚的带领下,建立了咱们现在庞大的网协!可谓是功不可没啊!


   另一位不得不提的人物!也就是网协的第二任会长!计算082的赵聪学长,更是我们学院的骄傲!曾多次在全国的软件比赛中获得奖项!不仅技术牛,学习成绩也很牛,他在13年1月份,顺利考入中国科学技术大学! 据说在面试的时候排名第一!后来又获得了微软亚洲研究院的offer,在那里有一段时间的实习!那可不是谁都能进去(迄今为止学校唯一一个进入NSRA的)!现在著名外企摩根实习。


   另外08级的李鑫学长,也是当年网协中的佼佼者,他靠着个人努力,以及蓝桥杯全国三等奖的竞赛成绩,在12年的时候拿到了北京大学的保研资格!也是咱学校为数不多获得北大保研资格!后又被评为理工十大杰出人物。 在北大期间,一年多读完所有硕士学科,现已赴美留学。

  

   08级的范鹤鹤学长,技术牛,学习也牛,也是12年的1月份,顺利考入华东科技大学。崔连超学姐保送山大研究生,他们都是08级里面网协的骄傲!

  09级里,也有好多厉害的大牛出没!


   09级李兴涛,就曾经在11年的全国软件设计大赛的省赛中,获得了山东省第一的宝座。

  

   09级徐浩鹏,也在12年的全国软件设计大赛决赛中,拿到了一等奖,并且在山东省的排名中,位列第一,曾在小米就职一年,现就职于搜狐畅游。

  

   09级王爱玲,凭借着大学四年优异的成绩,获得学校的保研名额,保研到中科院!

  

   09级王鹏,以优异的成绩考入了中科院,他们也都是咱们网协的骄傲!


   09级万力,计算机学院自主创业的先驱,尽管创业失败了。后成功考入的成都电子科技大学。


  网协的优秀是代代传承,从未间断的。


   10级中,第三任网协会长刘起耀,12年获得全国软件大赛C/C++全国二等奖,在今年7月份又获得了全国软件大赛Java全国一等奖,山东排名第一,现就职北京某初创公司。

 

   10级杜晓阳,在校多次参与程序设计竞赛,后自学机器学习算法,14年成功入职京东商城,现他所在的团队负责京东商城的推荐系统。

    

   10级李兆华,最短的时间,最好的成绩考入了成都电子科技大学。


   虽然说钱是很庸俗的东西,但钱有时候是衡量一个人能力最直接的东西,网协的学长学姐们,但凡找到工作的,他们的薪资绝对是学校所有同届学生中的薪资最高的。


   直到如今,网协人已经成为我们理工大学计算机学院的一个骄傲!网协的名人堂,也将由后来者一点点的充实。


hdoj 1715 大菲波数


先java代码:

import java.util.Scanner;
import java.math.*;

public class Main {
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		BigInteger fb[] = new BigInteger [1005];
		fb[1] = BigInteger.valueOf(1);
		fb[2] = BigInteger.valueOf(1);
		for (int i = 3; i < 1005; i++)
			fb[i] = fb[i-1].add(fb[i-2]);
		int t = cin.nextInt();
		while (t != 0) {
			t--;
			int n = cin.nextInt();
			System.out.println(fb[n]);
		}
		cin.close();
	}
}


然后是C++代码:

#include<stdio.h>
int fb[1001][100];
void add(int *s1,int *s2,int *s3)
{
    int t=0;
    for(int i=0;i<100;i++)
    {
        s3[i]=(s1[i]+s2[i])%10000+t;
        t=(s1[i]+s2[i])/10000;
    }
}
void print(int *s)
{
    for(int i=99;i>=0;i--)
        if(s[i]!=0)
            break;
    printf("%d",s[i--]);
    for(;i>=0;i--)
        printf("%04d",s[i]);
    puts("");
}
int main()
{
    int t,n;
    scanf("%d",&t);
    fb[1][0]=1;
    fb[2][0]=1;
    for(int i=3;i<=1000;i++)
        add(fb[i-1],fb[i-2],fb[i]);
    while(t--)
    {
        scanf("%d",&n);
        print(fb[n]);
    }
    return 0;
}

hdoj 1753 (Java)


刚刚开始用Java,代码难免不够简洁。

import java.math.BigDecimal;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while (cin.hasNext()) {
			BigDecimal a = cin.nextBigDecimal();
			BigDecimal b = cin.nextBigDecimal();
			a = a.add(b);
			if (a.compareTo(BigDecimal.valueOf(0.0)) == 0) {
				System.out.println(0);
				continue;
			}
			String out = new String(a.toPlainString());
			int l = out.length();
			boolean flag = false;
			for (int i = 0; i < l; i++)
				if (out.charAt(i) == '.')
					flag = true;
			int q = l - 1;
			while (out.charAt(q) == '0')
				q--;
			if (out.charAt(q) == '.')
				q--;
			if (flag == false && out.charAt(q) != '.')
				q = l-1;
			int p = 0;
			while (out.charAt(p) == '0')
				p++;
			if (out.charAt(p) == '.')
				System.out.print(0);
			for (int i = p; i <= q; i++)
				System.out.print(out.charAt(i));
			System.out.println();
		}
		cin.close();
	}
}

poj 1131 Octal Fractions(高精度小数进制转换) Java


虽然题目那么长其实就是把8进制的浮点数转换成10进制,为了练习Java Biginteger 类 我这里用的是Java,也可以用数组模拟。

import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		String str, ors;
		BigDecimal x, y, z;
		while (cin.hasNext()) {
			ors = cin.next();
			str = ors.substring(ors.indexOf(".")+1, ors.length());
			z = new BigDecimal(0);
			y = new BigDecimal(1);
			for (int i = 0; i < str.length(); i++) {
				x = new BigDecimal(str.charAt(i) - '0');
				y = y.multiply(new BigDecimal(8));
				x = x.divide(y, str.length()*3, RoundingMode.HALF_UP);
				z = z.add(x);
			}
			System.out.println(ors + " [8] = " + z + " [10]");
		}
		cin.close();
	}
}


ubuntu 下常用的mysql 命令



一、mysql服务操作 
0、查看数据库版本 sql-> status; 
1、net start mysql //启动mysql服务 
2、net stop mysql //停止mysql服务  
3、mysql -h主机地址 -u用户名 -p用户密码 //进入mysql数据库 
4、quit //退出mysql操作 
5、mysqladmin -u用户名 -p旧密码 password 新密码 //更改密码 
6、grant select on 数据库.* to 用户名@登录主机 identified by “密码” //增加新用户 
exemple: 
例2、增加一个用户test2密码为abc,让他只可以在localhost上登录,并可以对数据库mydb进行查询、插入、修改、删除的操作 (localhost指本地主机,即MYSQL数据库所在的那台主机),这样用户即使用知道test2的密码,他也无法从internet上直接访问数据
库,只能通过MYSQL主机上的web页来访问了。 

grant select,insert,update,delete on mydb.* to test2@localhost identified by “abc”; 
如果你不想test2有密码,可以再打一个命令将密码消掉。 
grant select,insert,update,delete on mydb.* to test2@localhost identified by “”; 

二、数据库操作 
1、show databases; //列出数据库 
2、use database_name //使用database_name数据库 
3、create database data_name //创建名为data_name的数据库 
4、drop database data_name //删除一个名为data_name的数据库 

三、表操作 
1、show databases;//列出所有数据库 

use 数据库名; //到达某一数据库 

show tables //列出所有表 
create table tab_name( 
id int(10) not null auto_increment primary key, 
name varchar(40), 
pwd varchar(40) 
) charset=gb2312; 创建一个名为tab_name的新表 
2、drop table tab_name 删除名为tab_name的数据表 
3、describe tab_name //显示名为tab_name的表的数据结构 
4、show columns from tab_name //同上 
5、delete from tab_name //将表tab_name中的记录清空 
6、select * from tab_name //显示表tab_name中的记录 
7、mysqldump -uUSER -pPASSWORD –no-data DATABASE TABLE > table.sql //复制表结构 

四、修改表结构 
1、 ALTER TABLE tab_name ADD PRIMARY KEY (col_name) 
说明:更改表得的定义把某个栏位设为主键。 
2、ALTER TABLE tab_name DROP PRIMARY KEY (col_name) 
说明:把主键的定义删除 
3、 alter table tab_name add col_name varchar(20); //在tab_name表中增加一个名为col_name的字段且类型为varchar(20) 
4、alter table tab_name drop col_name //在tab_name中将col_name字段删除 
5、alter table tab_name modify col_name varchar(40) not null //修改字段属性,注若加上not null则要求原字段下没有数据 
SQL Server200下的写法是:Alter Table table_name Alter Column col_name varchar(30) not null; 
6、如何修改表名:alter table tab_name rename to new_tab_name 
7、如何修改字段名:alter table tab_name change old_col new_col varchar(40); //必须为当前字段指定数据类型等属性,否则不能修改 
8、create table new_tab_name like old_tab_name //用一个已存在的表来建新表,但不包含旧表的数据 

五、数据的备份与恢复 
导入外部数据文本: 
1.执行外部的sql脚本 
当前数据库上执行:mysql < input.sql 
指定数据库上执行:mysql [表名] < input.sql 
2.数据传入命令 load data local infile “[文件名]” into table [表名]; 
备份数据库:(dos下) 
mysqldump –opt school>school.bbb 
mysqldump -u [user] -p [password] databasename > filename (备份) 
mysql -u [user] -p [password] databasename < filename (恢复) 

六、卸载 
卸载mysql:sudo apt-get remove mysql-server mysql-client 
sudo apt-get autoremove

poj 1205 :Water Treatment Plants (DP+高精度)



题意:有n个城市,它们由一个污水处理系统连接着,每个城市可以选择

1、将左边城市过来的污水和右边城市过来的污水连同本身的污水排到河里  >V<

2、将左边来的污水连同自己的污水排到右边  >>

3、将右边来的污水连同自己的污水排到左边  <<


问总共有多少种处理情况,即不同又符合实际的><V组合。


 


思路:DP+高精度。DP部分,易得最右边城市的状态只可能用3种:>V, V, <。故分三种状态讨论,设dp[i][0]为第i个城市的状态为:> V ,dp[i][1]为:V ,dp[i][2]为:<。由实际流动的可能性可以得到状态转移方程:


dp[i][0] = dp[i-1][0] + dp[i-1][1];


dp[i][1] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2];


dp[i][2] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2];


然后可以整理为:dp[i] = 3 * dp[i-1] + dp[i-2]。然后用java的BigInteger预处理就OK了。


以下是java代码:

import java.util.Scanner;
import java.math.*;

public class Main {
	public static void main(String[] args) {
		int n;
		Scanner cin = new Scanner(System.in);
		BigInteger[] a = new BigInteger[110];
		a[1] = BigInteger.valueOf(1);
		a[2] = BigInteger.valueOf(3);
		for (int i = 3; i <= 100; i++) {
			a[i] = a[i-1].multiply(BigInteger.valueOf(3)).subtract(a[i-2]);
		}
		while (cin.hasNextInt()) {
			n = cin.nextInt();
			System.out.println(a[n]);
		}
		cin.close();
	}
}

Qtech 暑假未讲到的算法(不完全)





一、数据结构:

   优先队列、堆、RMQ问题(区间最值问题,可以用线段树解决,还有一个Sparse-Table算法)、排序二叉树、划分树、归并树…..

  字符串处理:

   KMP、字典树、后缀树、后缀数组(两种求后缀数组的方法 倍增和DC3算法)

  包括C++ STL 里面一些东西 比如sort vector map set stack queue mulitmap mulitmap proptity_queue…….

   还有快排、归并、堆、冒泡、选择、插入、希尔、基数、计数、地精等排序算法最好了解一下,还有基于快排的区间第K值的快速查找法


二、图论算法:

   二分匹配、网络流、几种最短路径算法、差分约束、强or弱连通图…….


三、DP 动态规划

   各种背包、数位DP、树形DP、状态压缩DP、概率DP、平行四边型法则,单调队列….

四、数论&计算几何&博弈论

   这个就涉及的多了,包括各种数学定理、微积分、概率论、线性代数等等数学知识,有很多很难的问题,不过一些基础的数论还是要知道的,比如gcd….

五、搜索

   假期讲了dfs和bfs的原理,它们的应用很广,还有一些衍生出来的算法,比如双向广搜、A-star搜索、跳点搜索。。。