Posted on | In

乡下人进城

今天是去华为参加面试的日子。
这大概是我第一次参加一个像样的面试，整个过程给我留下的印象很深，虽然整个过程难度不大，但是不管怎样我都觉得自己的收获不小。趁着睡觉之前记下来，记住这一次挺令人难忘的经历。

准备

其实我感觉个人的准备还是很不充分的。首先，在面试的两天前刚刚加班加点甩完了两个锅，累的不要不要的，面试前一天主要用来放松心情，没做什么过多的准备。不过我对于一些面经倒是看了不少，从一些技术问题看到面试礼仪，个人感觉至少不算特别的虚。身边的几个同学一直在复习一些基础知识，不知道为什么我好像有一种蜜汁自信，感觉这些问题我都能答得上来。。。总之就是抱着破罐子破摔实在不行就当是去见识见识的心态上的路。中午出发前才把连夜修改过的简历打印了一份，还发现面试要求带的学生证拉在了宿舍。。。不过还好，苏州地铁比百度地图想象的要给力的多，原本以为一个多小时的行程大概实际就花了四十几分钟，总算没有迟到。。。

体验

下了地铁本以为会看到高楼林立绿茵遍地的场面，实际上高楼林立是没错，不过总给人一种荒芜的感觉。道路十分宽阔，但是来往的车辆不多，人行道也挺宽，但是绿化做的并不好，都是些没啥用的小树苗。四下望去人也不是很多，空荡荡的高楼里也没什么人。路边打扫卫生的大叔在车里放着八九十年代的老歌，竟然有一种复古的感觉。。。
在保安大叔的指引下看到了属于华为的建筑群。或许是因为周日放假，基本看不到个人。一番摸索后来到了大厅，空荡荡的大厅当中坐着一个看上去瘦小的前台小哥。说明了来意后，他指引我们七绕八绕绕道了后面面试的那栋楼。刚一进门就闻到了一股扑鼻的香味，嗯，估计是什么香薰。前台的姐姐很热情，指引着我们登记，旁边有一些跟图书馆差不多的小桌子，上面坐着一些好像在讨论问题的人，给人一种很宁静的感觉。
来之前我看到知乎上有人说，判断一个公司怎么样其实可以去看一看它的卫生间搞得怎么样，我觉得此言甚是靠谱，于是就特意先去卫生间体验了一下。刚站到门口就闻到一股扑面而来的。。。。。。香味，就是刚进门的同款香薰。洗手池清理的很干净，边上还差了一束花，不过摸了摸是一个假花。。。烘干机、洗手液看上去也挺新的，卫生纸是那种一抽一大张的软软的正方形擦手纸，品质还不错。进去是小便池，怎么说呢，就是那种让人看了就有小便欲望的地方。除了有蹲着嗯嗯的地方，在旁边还有一个挺宽敞的房间，里面有独立的无障碍盥洗池，和无障碍坐便器，虽然没开灯，但是看上去也挺干净的，我觉得在这里玩王者荣耀还是雅的。。。
到处走了走发现总体的卫生工作做的挺不错，绿植挺多，也有专门的吸烟区，所谓吸烟区就是一个阳台，通风和环境都还不错。不过目测搞这行的吸烟的人不多，烟灰缸里没几只烟头。

候试

接着我们被hr大姐姐领进了候试区，先是用身份证刷卡签到。hr大姐姐挺可爱，还跟我抱怨我挂了她的电话（其实是没听见）。。候试区是一个挺大的类似会议室的地方，墙上贴了一些励志的名人名言。旁边的桌子上先是摆了各式各样的零食，新鲜的水果拼盘还有开水咖啡，然后就是一些关于华为产品的小广告，随手翻了翻基本是我看不懂的硬件疙瘩，不过另我耳目一新的是在宣传材料边上还有一些教你减压、养生之类的畅销书，以及一本名叫《为什么华为不会倒》的内部读物。我当然先是假模假样的看看书，然后hr大姐姐跟她的小姐妹一波一波的进来催我们吃水果拼盘。。。反正闲着也是闲着，那就吃呗。。。
不过也没光顾着吃，在我们前面也来了一些人，我们聊了聊发现很多都是西安交大研究院的研究生，还有苏大的研究生，基本上除了我们一路的大三狗之外就是研二党了，萌新表示瑟瑟发抖。不过看上去他们一起来的人不多，所以表现的比较拘谨。我们反正互相比较熟，大家都挺轻松的在吹牛。。。

一面

本来说是安排我两点半的面试，不过事实上是先来后到进行面试，到了没多久就轮到我了。一面大概就是传说中的技术面了，一对一，面试官是一个看上去挺年轻的大哥。上来先说让我做一个五分钟以内的自我介绍。哦不得不说我胆子挺大，简单的花了十几秒说了下个人信息就直接跟他说我不太擅长自我介绍。事实是我刚进来的时候不知道为什么突然有点紧张，脑子有点空白。。。他倒是不太介意，看了看我的简历，说：“你这个简历做的挺业余的么”，我赶快辩解说我习惯用markdown写东西，然后承认我不太懂这个。。。他翻了几页之后：“嗯，还挺有个性”。接着他对着我在简历里的项目经验一点一点的问，问的都是一些基础情况，只要项目是自己做的，基本都没什么难度。问完自己的项目经历，然后就开始问一些“例行”问题，诸如“你对类有什么理解”、“你对链表、树这类的数据结构有什么理解”。当然，这些问题没什么标准答案，回答之后他也不会再追问。然后他看到我再简历里写我最近都是用python，就问我“你觉得python相比c++这些语言有哪些优缺点”，开放性问题，他也不会过多纠缠于细节，一问一答基本就结束了。接着就问了我比较擅长的语言，以及期望的工作地。
整个话题基本是他来主导，但是他的思路都是从简历里来的，问起来也非常的自然，没有任何刁难的意思。感觉相比编码能力，他们应该挺看重生活和学习态度学习能力，以及将理论化为应用的能力。有一回我在回答一个项目问题的时候无意中说“这个项目是因为同学来找我解决问题，我就顺便在里做了一点研究”，他就表示这一点挺不错的。
问我愿不愿意接受挑战，我说愿意。。。
面试官也会看成绩单，似乎他们对数学类、数据结构、编译原理、操作系统这些课程成绩比较感兴趣，看到我的成绩还不错，小夸了几句。
不过在面试的最后，他也对我提出了一些建议：

  1. 他觉得我研究的东西比较多比较杂，可能需要一个特别突出的地方来彰显自己。不过看到我“才”大三，他表示这个不急。。。
  2. 他似乎抱怨我在对自己项目的技术细节描述的不多，我表示这玩意不太能说的清楚啊。。。

总体上来讲，虽然我感觉回答的并不太好，但是至少没有尴尬。整个气氛还是挺融洽的，感觉主要还是要放轻松，基本上只要表现的阳光一点，不需要表现出最优秀的一面，表现出最平常的一面就ok。我感觉面试官的难度也不小，他得在短时间里对你做多方面的评价，然后还要写成报告，主导对话，而我们只需要回答问题就好了。。。面试官本人也和nice，语速略快，不过调理很清楚，提意见的时候也能充分尊重个人的看法，语言也很亲和。

二面

二面就是传说中的boss面，没想到这么快就终面了。由于boss只来了一个，面起来比较慢。我先面的能够有幸1v1，后面的同学考虑到时间关系变成了2v1和3v1。。。也就是传说中的撕逼群面，虽然我没体验过，但据说有点蛋疼，好像是问一个问题两个人互相补充。
下面大概说说我的经历。
二面给我的感觉就是—-聊人生。boss很随和，没要做自我介绍，没有看我带过去的简历，看样子是先前的材料都汇总到他那里了。感觉boss的厉害之处在于他会在跟你聊天扯淡的不经意间问你对一些事情的看法，问题来相当的自然，以至于我都不太清楚这是在聊天还是在问问题。跟一面大哥一直忙个不停的在看材料跟码字不同，基本不会看任何的材料，记任何的东西，而是一心一意的跟你“聊天”。而且他特别擅长对别人说的话进行总结，对于一个问题，我可能零零散散的说了几点，他就能用一个词去抓住我说话的重点。
聊的过程中，我表示我这个人见识比较短，没去过什么洋气的地方，见到人呢比较害羞，boss却表示这ok啊，说明我的时间都花在了研究技术上。我还表示我不太擅长做演讲，他就认认真真的引导我去分析如何做一个好的演讲。
至于具体的问题，他先是让我聊一聊过来的感受，问我过来想要收获些什么，问我认为自己的优秀品质有哪些等等。然后聊了聊华为这个公司啊，以后要扩建了，楼会更加漂亮，人也会更多。接着就开始问我对于未来的规划。简而言之，他的建议就是你有这个能力在本科进华为你就不需要去读一个研究僧了，总结来说大概就是：

  1. 在华为工作学到的东西是都研究生远远学不到的
  2. 多上几年班，基本上就能混的不错，这时候新来的研究生或许成了你的下属
  3. 读研出来还不是要工作，但是我们华为已经是顶尖的公司了，你还想怎样？？
  4. 如果你是面试官，你遇到三年华为工作经历的本科生和没有经历的研究生你会选谁
  5. 在评价机制上，华为对本科生和研究生不会区别对待，一切靠能力

有一个小细节我觉得挺有趣，就是他在谈论所谓比华为更厉害的公司的时候，我以为他可能会说BAT之类的，结果他说的是Amazon。。。
接着我们探讨了关于华为的加班文化之类的事情，他表示两点：

  1. 几乎所有成功的公司，都会加班。当然，除了国家电网。。。
  2. 华为并不会让一个人变废，比如他自己还有前面一个面试官，哪里像废了的样子，还让我猜他本人的年龄。。。

然后我咨询了一下华为校招刷人奇怪的问题（感觉有点作死），他表示这是很正常的，还举了某著名互联网公司招一个人要考察半年的例子。
基本就是这样，然后他表示聊的时间太久了，还有很多人要面呢（我是愣了一会才知道它的意思是结束了。。。）。走的时候我问他什么时候会有通知，他说要我们一起等消息。

其他

总的来说华为的门槛并不高，基本上身边有志向有能力的同学都有很大的机会。不过不知道为什么，我们学校去面试的同学真的不多，倒是研究生去的不少，但是目测一面就被刷的也不在少数，似乎普通的研究生什么的的确没什么优势，相比面试水平相近的本科生反而会吃亏。个人觉得不管怎么样，最重要的首先是基础能力，然后就是要表现的阳光开朗，会就是会不会就是不会，没什么尴尬的，敢于表现出优点跟缺点并存的真实的一面。重点是一定要自信，一定要相信自己能够胜任这个工作，你才能让别人相信你能胜任这个工作。
总之就是个人感觉还行，最终面不面的上我其实也无所谓，能体验下这种环境我觉得对我的帮助还是很大的，开心就好喽。

Posted on | In

面向对象是相对于面向过程而言，过程其实就是函数，对象是将函数和属性进行了封装。
Java中的面向对象（Object Oriented）是一种新兴的程序设计方法，或者是一种新的程序设计规范(paradigm)，其基本思想是使用对象、类、继承、封装、多态等基本概念来进行程序设计。

Read more »

Posted on | In

这是Java教程的第一篇，梳理Java基础知识是学习其他专业知识的第一步阶梯；要想精通编程必须通过大量的编程训练，在实践中掌握编程知识，培养编程能力，并逐步理解和掌握程序设计的思想和方法。

Read more »

Posted on | In

前言

最近需要在网页上做一个对于文档的预览功能，但是这个预览功能基本只能对pdf格式的文件进行处理，而不能对doc、ppt之类的格式进行处理（毕竟微软爸爸）。因此为了能够方便的显示所有的文档，并且统一管理，我需要找到一个能将doc、ppt这些文件方便快捷的转成pdf的工具。当然，word、ppt这些软件本省有到出成pdf的功能，网络上这类转换工具很多，但是用起来也是不太方便，而且这当中垃圾软件也不少。
仔细想想，实现这个功能无非有两个途径，一是利用微软自己的api。不过这显然有点麻烦，还要自己写代码。另外一个途径就是用仿ms的开源软件，比如libreoffice、openoffice、wps这些比较成熟的工具提供的支持。搜索一番后发现，还是开源软件的力量大，这类的转换工具还特别的多，最终我选择了一个叫unoconv的文档格式转换工具。

安装使用

unoconv本身就在apt软件包里，sudo apt install unoconv就能安装。
unoconv不仅支持doc、ppt等格式转向pdf，他还能支持几乎所有libreoffice、openoffice支持的格式之间的互相转换，包括pdf、doc、docx、ppt、pptx、odt、csv、png、jpg、xsl、csv等等，用途很广。
基本用法如下：

1
unoconv -f pdf some-document.doc

这个命令会读取some-document.doc，转换成some-document.pdf文件。并且，输入文件支持通配符。比如：

1
unoconv -f pdf *.doc

这就能一次性转换所有的doc文件。

字体支持问题

在使用的过程中发现，在对文章进行转换的时候，经常会有乱码的现象。研究一下发现并不是字符集乱码，而是缺失字体文件，也就是windows里的很多字体在linux里面是没有的。因此我们只要将windows下的字体文件拷贝到linux下面就行了。具体步骤如下：

  1. 复制windows下的C://WINDOWS/Fonts/下的字体文件，拷贝到/usr/share/fonts文件夹下。
  2. 删除一些不支持的文件（比如以.fon后缀的文件）。
  3. 执行sudo mkfontscale、sudo mkfontdir 、sudo fc-cache，加载字体。

这样配置好基本就可以支持绝大部分的字体了。不过在使用的时候发现有一些特殊的符号还是不能正确加载，不过影响不大。

Posted on | In

前言

想想已经有一年多没有接触算法题了，忙活了一年多没什么用的东西，才陡然发现自己竟然就要毕业了，然而审视了下自己的水平估计还达不到大一的程度，甚是惊恐。于是下定决心开始刷一点题，打好基本功。正好有同学在做网易笔试题的时候来向我问问题，我看了看有12道，好像也不多，于是就顺便刷了刷。本以为会是一帆风顺的，可是事实是，我果然还是太菜了。。。

双核处理

题目

一种双核CPU的两个核能够同时的处理任务，现在有n个已知数据量的任务需要交给CPU处理，假设已知CPU的每个核1秒可以处理1kb，每个核同时只能处理一项任务。n个任务可以按照任意顺序放入CPU进行处理，现在需要设计一个方案让CPU处理完这批任务所需的时间最少，求这个最小的时间。

输入描述

输入包括两行：
第一行为整数n(1 ≤ n ≤ 50)
第二行为n个整数length[i](1024 ≤ length[i] ≤ 4194304)，表示每个任务的长度为length[i]kb，每个数均为1024的倍数。

输出描述
输出一个整数，表示最少需要处理的时间

输入例子
5
3072 3072 7168 3072 1024

输出例子
9216

分析

题意很清晰，就是给一个数组，要我们把他分成两份并分别求和，使得这两个和的最大值最小。
我下意识的想法是枚举出所有有可能的和，但是复杂度大概是$O(2^n)$，貌似会超时。可是仔细一看，$length[i]$的取值在$[1,4096]$之间，那么最多n个数的和的范围肯定在$[n,4096n]$之间。那么我们只要对能取到的和打个表，而且表的长度肯定不超过$4096*50=204800$，再加上总共遍历n遍，计算量大概是1e7的级别，可解。

我的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
int n;
int a[51];
set<int>s;
int sum=0;
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        int tmp;
        cin>>tmp;
        a[i]=tmp/1024;
        sum+=a[i];
    }
    s.insert(0);
    for(int i=0;i<n;i++){
        set<int>added;
        for(set<int>::iterator it=s.begin();it!=s.end();it++){
            added.insert(*it+a[i]);
        }
        s.insert(added.begin(),added.end());
    }
    int ans=sum;
    for(set<int>::iterator it=s.begin();it!=s.end();it++){
        ans=min(ans,max(*it,sum-*it));
    }
    cout<<ans*1024<<endl;
}

赶去公司

题目

终于到周末啦！小易走在市区的街道上准备找朋友聚会，突然服务器发来警报,小易需要立即回公司修复这个紧急bug。假设市区是一个无限大的区域，每条街道假设坐标是(X，Y)，小易当前在(0，0)街道，办公室在(gx,gy)街道上。小易周围有多个出租车打车点，小易赶去办公室有两种选择，一种就是走路去公司，另外一种就是走到一个出租车打车点，然后从打车点的位置坐出租车去公司。每次移动到相邻的街道(横向或者纵向)走路将会花费walkTime时间，打车将花费taxiTime时间。小易需要尽快赶到公司去，现在小易想知道他最快需要花费多少时间去公司。
输入描述:
输入数据包括五行:

第一行为周围出租车打车点的个数n(1 ≤ n ≤ 50)

第二行为每个出租车打车点的横坐标tX[i] (-10000 ≤ tX[i] ≤ 10000)

第三行为每个出租车打车点的纵坐标tY[i] (-10000 ≤ tY[i] ≤ 10000)

第四行为办公室坐标gx,gy(-10000 ≤ gx,gy ≤ 10000),以空格分隔

第五行为走路时间walkTime(1 ≤ walkTime ≤ 1000)和taxiTime(1 ≤ taxiTime ≤ 1000),以空格分隔

输出描述:
输出一个整数表示，小易最快能赶到办公室的时间

输入例子:
2
-2 -2
0 -2
-4 -2
15 3

输出例子:
42

分析

基础题，先算步行的时间，再枚举每个打车点算出打的时间，找到时间最短的即可。

我的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include<algorithm>
#define MAX 100000000
using namespace std;
int n;
int tx[51],ty[51];
int gx,gy;
int wt,dt;
int main(){
    cin>>n;
    int walkTime=MAX,driveTime=MAX;
    for(int i=0;i<n;i++){
        cin>>tx[i];
    }
    for(int i=0;i<n;i++){
        cin>>ty[i];
    }
    cin>>gx>>gy>>wt>>dt;
    walkTime=(abs(gx)+abs(gy))*wt;
    for(int i=0;i<n;i++){
        driveTime=min(driveTime,(abs(ty[i])+abs(tx[i]))*wt+(abs(ty[i]-gy)+abs(tx[i]-gx))*dt);
    }
    cout<<min(driveTime,walkTime)<<endl;
}

调整队形

题目

在幼儿园有n个小朋友排列为一个队伍，从左到右一个挨着一个编号为(0~n-1)。其中有一些是男生，有一些是女生，男生用’B’表示，女生用’G’表示。小朋友们都很顽皮，当一个男生挨着的是女生的时候就会发生矛盾。作为幼儿园的老师，你需要让男生挨着女生或者女生挨着男生的情况最少。你只能在原队形上进行调整，每次调整只能让相邻的两个小朋友交换位置，现在需要尽快完成队伍调整，你需要计算出最少需要调整多少次可以让上述情况最少。例如：
GGBBG -> GGBGB -> GGGBB
这样就使之前的两处男女相邻变为一处相邻，需要调整队形2次
输入描述:
输入数据包括一个长度为n且只包含G和B的字符串.n不超过50.

输出描述:
输出一个整数，表示最少需要的调整队伍的次数

输入例子:
GGBBG

输出例子:
2

分析

事实上，最终的结果只有两种可能，要么是GGG…BBB，要么是BBB…GGG。我们不妨考虑B，我们可以事先求出B全部在左边和全部在右边两种情况下的和。然后对当前每个B的下标求和，显然我们每进行一次有用的调整必然使当前的和+1或者-1。那么，我们只要计算出当前的和与最终结果的和的差就行了，由于最终结果有两种情况，我们取最小值即可。

我的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
#include<string>
using namespace std;
int main(){
    string s;
    cin>>s;
    int cntB=0;
    int valB=0;
    for(int i=0;i<s.length();i++){
        cntB+=s[i]=='B';
        valB+=s[i]=='B'?i:0;
    }
    int leftB=valB-cntB*(cntB-1)/2;
    int rightB=(2*s.length()-cntB-1)*cntB/2-valB;
    cout<<min(leftB,rightB)<<endl;
}

消除重复元素

题目

小易有一个长度为n序列，小易想移除掉里面的重复元素，但是小易想是对于每种元素保留最后出现的那个。小易遇到了困难,希望你来帮助他。
输入描述:
输入包括两行：
第一行为序列长度n(1 ≤ n ≤ 50)
第二行为n个数sequence[i](1 ≤ sequence[i] ≤ 1000)，以空格分隔

输出描述:
输出消除重复元素之后的序列，以空格分隔，行末无空格

输入例子:
9
100 100 100 99 99 99 100 100 100

输出例子:
99 100

分析

从后向前先判重后加入即可。

我的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;
int main(){
    int n;
    int a[1002]={0};
    vector<int>v;
    set<int>s;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=n-1;i>=0;i--){
        if(s.find(a[i])==s.end()){
            s.insert(a[i]);
            v.push_back(a[i]);
        }
    }
    cout<<v[v.size()-1];
    for(int i=v.size()-2;i>=0;i--){
        cout<<" "<<v[i];
    }
    cout<<endl;

魔力手环

题目

小易拥有一个拥有魔力的手环上面有n个数字(构成一个环),当这个魔力手环每次使用魔力的时候就会发生一种奇特的变化：每个数字会变成自己跟后面一个数字的和(最后一个数字的后面一个数字是第一个),一旦某个位置的数字大于等于100就马上对100取模(比如某个位置变为103,就会自动变为3).现在给出这个魔力手环的构成，请你计算出使用k次魔力之后魔力手环的状态。
输入描述:
输入数据包括两行：
第一行为两个整数n(2 ≤ n ≤ 50)和k(1 ≤ k ≤ 2000000000),以空格分隔
第二行为魔力手环初始的n个数，以空格分隔。范围都在0至99.

输出描述:
输出魔力手环使用k次之后的状态，以空格分隔，行末无空格。

输入例子:
3 2
1 2 3

输出例子:
8 9 7

分析

矩阵快速幂模板题。。。

我的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<iostream>
#include<cstring>
using namespace std;
#define MAX 52
#define MOD 100
struct Matrix{
    int n,m;
    int a[MAX][MAX];
    void clear(){
        n=m=0;
        memset(a,0,sizeof a);
    }
    Matrix operator +(const Matrix &b)const{
        Matrix tmp;
        tmp.n=n;
        tmp.m=m;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                tmp.a[i][j]=(a[i][j]+b.a[i][j])%MOD;
        return tmp;
    }
    Matrix operator *(const Matrix &b)const{
        Matrix tmp;
        tmp.clear();
        tmp.n=n;
        tmp.m=b.m;
        for(int i=0;i<n;i++)
            for(int j=0;j<b.m;j++)
                for(int k=0;k<m;k++)
                    tmp.a[i][j]=(tmp.a[i][j]+a[i][k]*b.a[k][j])%MOD;
        return tmp;
    }
    void print()const{
        for(int i=0;i<n;i++){
            for(int j=0;j<m-1;j++)
                cout<<a[i][j]<<" ";
            cout<<a[i][m-1]<<endl;
        }
    }
    Matrix operator ^(int k)const{
        Matrix tmp,mul;
        tmp.clear();
        mul.clear();
        mul.n=mul.m=tmp.m=tmp.n=n;
        mul=mul+(*this);
        for(int i=0;i<n;i++)
            tmp.a[i][i]=1;
        while(k>0){
            if(k&1){
                tmp=tmp*mul;
            }
            k>>=1;
            mul=mul*mul;
        }
        return tmp;
    }
    Matrix transpose(){
        Matrix tmp;
        tmp.n=m;
        tmp.m=n;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                tmp.a[j][i]=a[i][j];
        return tmp;
    }
};
int n,k;
int main(){
    Matrix arr;
    cin>>n>>k;
    arr.m=1;
    arr.n=n;
    for(int i=0;i<n;i++)
        cin>>arr.a[i][0];
    Matrix mul;
    mul.clear();
    mul.n=mul.m=n;
    for(int i=0;i<n;i++){
        mul.a[i][i]=1;
        mul.a[i][(i+1)%n]=1;
    }
    arr=(mul^k)*arr;
    arr.transpose().print();
}

工作安排

题目

现在有n位工程师和6项工作(编号为0至5)，现在给出每个人能够胜任的工作序号表(用一个字符串表示，比如：045，表示某位工程师能够胜任0号，4号，5号工作)。现在需要进行工作安排，每位工程师只能被安排到自己能够胜任的工作当中去，两位工程师不能安排到同一项工作当中去。如果两种工作安排中有一个人被安排在的工作序号不一样就被视为不同的工作安排，现在需要计算出有多少种不同工作安排计划。
输入描述:
输入数据有n+1行：
第一行为工程师人数n(1 ≤ n ≤ 6)
接下来的n行，每行一个字符串表示第i(1 ≤ i ≤ n)个人能够胜任的工作(字符串不一定等长的)

输出描述:
输出一个整数，表示有多少种不同的工作安排方案

输入例子:
6
012345
012345
012345
012345
012345
012345

输出例子:
720

分析

空间不大，直接dfs就行了。

我的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream>
#include<cstring>
using namespace std;
bool can[6][6];
bool vis[6];
int n;
int dfs(int now){
    int ans=0;
    for(int i=0;i<6;i++){
        if(can[now][i]&&!vis[i]){
            vis[i]=true;
            if(now==0)
                ans++;
            else
                ans+=dfs(now-1);
            vis[i]=false;
        }
    }
    return ans;
}
int main(){
    cin>>n;
    memset(can,0,sizeof can);
    memset(vis,0,sizeof vis);
    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        for(int j=0;j<s.length();j++)
            can[i][s[j]-'0']=true;
    }
    cout<<dfs(n-1)<<endl;
}

集合

题目

小易最近在数学课上学习到了集合的概念,集合有三个特征：1.确定性 2.互异性 3.无序性.
小易的老师给了小易这样一个集合：
S = { p/q | w ≤ p ≤ x, y ≤ q ≤ z }
需要根据给定的w，x，y，z,求出集合中一共有多少个元素。小易才学习了集合还解决不了这个复杂的问题,需要你来帮助他。
输入描述:
输入包括一行：
一共4个整数分别是w(1 ≤ w ≤ x)，x(1 ≤ x ≤ 100)，y(1 ≤ y ≤ z)，z(1 ≤ z ≤ 100).以空格分隔

输出描述:
输出集合中元素的个数

输入例子:
1 10 1 1

输出例子:
10

分析

题意就是给分数判重，显然我们不能直接算，因为浮点数是不精确的，建个结构体保存最简分数，然后丢进set里就好了。

我的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream>
#include<cstring>
#include<set>
using namespace std;
struct Frac{
    int p,q;
    bool operator<(const Frac &frac)const{
        if(p!=frac.p)
            return p<frac.p;
        if(q!=frac.q)
            return q<frac.q;
        return false;
    }
};
int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}
int main(){
    int w,x,y,z;
    set<Frac>s;
    cin>>w>>x>>y>>z;
    Frac f;
    for(int i=w;i<=x;i++){
        for(int j=y;j<=z;j++){
            int div=gcd(i,j);
            f.p=i/div;
            f.q=j/div;
            s.insert(f);
        }
    }
    cout<<s.size()<<endl;
}

奇怪的表达式求值

题目

常规的表达式求值，我们都会根据计算的优先级来计算。比如*/的优先级就高于+-。但是小易所生活的世界的表达式规则很简单，从左往右依次计算即可，而且小易所在的世界没有除法，意味着表达式中没有/，只有(+, - 和 *)。现在给出一个表达式，需要你帮忙计算出小易所在的世界这个表达式的值为多少
输入描述:
输入为一行字符串，即一个表达式。其中运算符只有-,+,*。参与计算的数字只有0~9.
保证表达式都是合法的，排列规则如样例所示。

输出描述:
输出一个数，即表达式的值

输入例子:
3+5*7

输出例子:
56

分析

小模拟。。。

我的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<iostream>
#include<string>
using namespace std;
bool isNumber(char c){
    return c>='0'&&c<='9';
}
int main(){
    string s;
    cin>>s;
    int num=0,ans=0;
    char op='+';
    for(int i=0;i<s.length();i++){
        if(isNumber(s[i])){
            num=num*10+s[i]-'0';  
        }else{
            if(op=='+'){
                ans=ans+num;
            }else if(op=='*'){
                ans=ans*num;
            }else{//op=='-'
                ans=ans-num;
            }
            op=s[i];
            num=0;
        }
    }
    if(op=='+'){
        ans=ans+num;
    }else if(op=='*'){
        ans=ans*num;
    }else{//op=='-'
        ans=ans-num;
    }
    cout<<ans<<endl;
}

涂棋盘

题目

小易有一块n*n的棋盘，棋盘的每一个格子都为黑色或者白色，小易现在要用他喜欢的红色去涂画棋盘。小易会找出棋盘中某一列中拥有相同颜色的最大的区域去涂画，帮助小易算算他会涂画多少个棋格。
输入描述:
输入数据包括n+1行：

第一行为一个整数n(1 ≤ n ≤ 50),即棋盘的大小

接下来的n行每行一个字符串表示第i行棋盘的颜色，’W’表示白色，’B’表示黑色

输出描述:
输出小易会涂画的区域大小

输入例子:
3
BWW
BBB
BWB

输出例子:
3

分析

小模拟，注意只能涂相邻连续的。。。

我的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include<string>
using namespace std;
string s[52];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>s[i];
    int maxCnt=0;
    for(int j=0;j<n;j++){
        int cnt=1;
        for(int i=1;i<n;i++){
            if(s[i][j]==s[i-1][j]){
                cnt++;
            }else{
                maxCnt=max(maxCnt,cnt);
                cnt=1;
            }
        }
        maxCnt=max(maxCnt,cnt);
    }
    cout<<maxCnt<<endl;
}

小易记单词

题目

小易参与了一个记单词的小游戏。游戏开始系统提供了m个不同的单词，小易记忆一段时间之后需要在纸上写出他记住的单词。小易一共写出了n个他能记住的单词，如果小易写出的单词是在系统提供的，将获得这个单词长度的平方的分数。注意小易写出的单词可能重复，但是对于每个正确的单词只能计分一次。
输入描述:
输入数据包括三行：

第一行为两个整数n(1 ≤ n ≤ 50)和m(1 ≤ m ≤ 50)。以空格分隔

第二行为n个字符串，表示小易能记住的单词，以空格分隔，每个单词的长度小于等于50。

第三行为m个字符串，系统提供的单词，以空格分隔，每个单词的长度小于等于50。

输出描述:
输出一个整数表示小易能获得的分数

输入例子:
3 4
apple orange strawberry
strawberry orange grapefruit watermelon

输出例子:
136

分析

把能记住的单词丢进set里，然后判断每一个是不是在系统提供的集合里即可。

我的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
#include<set>
using namespace std;
int main(){
    int n,m;
    set<string>s1,s2;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        s1.insert(s);
    }
    for(int i=0;i<m;i++){
        string s;
        cin>>s;
        s2.insert(s);
    }
    int ans=0;
    for(set<string>::iterator it=s1.begin();it!=s1.end();it++){
        if(s2.find(*it)!=s2.end()){
            ans+=it->length() * it->length();
        }
    }
    cout<<ans<<endl;
}

堆砖块

题目

小易有n块砖块，每一块砖块有一个高度。小易希望利用这些砖块堆砌两座相同高度的塔。为了让问题简单，砖块堆砌就是简单的高度相加，某一块砖只能使用在一座塔中一次。小易现在让能够堆砌出来的两座塔的高度尽量高，小易能否完成呢。
输入描述:
输入包括两行：
第一行为整数n(1 ≤ n ≤ 50)，即一共有n块砖块
第二行为n个整数，表示每一块砖块的高度height[i] (1 ≤ height[i] ≤ 500000)

输出描述:
如果小易能堆砌出两座高度相同的塔，输出最高能拼凑的高度，如果不能则输出-1.
保证答案不大于500000。

输入例子:
3
2 3 5

输出例子:
5

分析

不知道怎么搞，看到题目保证答案不大于500000，想想这不是在提示我们“暴力搞没问题，我数据不大”么。于是我就就暴力搜索，枚举两堆塔的高度，但是需要一些剪枝：

  1. 当其中一堆高度大于500000,可以剪掉;
  2. 当较低的堆+剩下的砖块<较高的堆时，可以剪掉;
  3. 当当前可能达到的最大高度小于已经发现最大高度时，可以剪掉;

我的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 500000
int height[52];
int sum[52];
int n;
int ans=0;
void dfs(int n,int sum1,int sum2){
    if(sum1==sum2)
        ans=max(ans,sum1);
    if(n==0)
        return;
    if(sum1>MAX)
        return;
    if(sum1+sum[n]<sum2)
        return;
    if((sum1+sum2+sum[n])<=ans*2)
        return;
    dfs(n-1,min(sum1+height[n],sum2),max(sum1+height[n],sum2));
    dfs(n-1,min(sum2+height[n],sum1),max(sum2+height[n],sum1));
    dfs(n-1,sum1,sum2);
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>height[i];
    sort(height+1,height+n+1);
    for(int i=1;i<=n;i++)
        sum[i]=sum[i-1]+height[i];
    dfs(n,0,0);
    cout<<(ans?ans:-1)<<endl;
}

分饼干

题目

易老师购买了一盒饼干，盒子中一共有k块饼干，但是数字k有些数位变得模糊了，看不清楚数字具体是多少了。易老师需要你帮忙把这k块饼干平分给n个小朋友，易老师保证这盒饼干能平分给n个小朋友。现在你需要计算出k有多少种可能的数值
输入描述:
输入包括两行：

第一行为盒子上的数值k，模糊的数位用X表示，长度小于18(可能有多个模糊的数位)

第二行为小朋友的人数n

输出描述:
输出k可能的数值种数，保证至少为1

输入例子:
9999999999999X
3

输出例子:
4

分析

显然数字太大我们不能直接计算模(超过long long)，而且也不能枚举X(否则空间可能有$10^{18}$)。不过我们考虑到模n应该不大（喂喂，怎么题目没有给n的范围啊～），因此可以考虑用动态规划的思想从这里入手。
用$mod[k]$表示当前所有情况下模n余k的数量。如果我们把前i位当成一个整体$s[0:i]$，而且知道了$mod[0:n]$的值，那么对于前i+1位而言，$mod[k]$的值会贡献到$mod[(k*10+s[i+1])mod\%n]$上。如果$s[i+1]$的值是X，那么我们只要将$s[i+1]$遍历10次。
总体上说，就是从前往后遍历，依次更新mod数组，最后的结果当然就是$mod[0]$了。
注意long long 。

我的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<iostream>
#include<cstring>
using namespace std;
#define MAXN 100000
void transform1(long long mod[],int n){
    long long tmpMod[MAXN]={0};
    for(int i=0;i<n;i++){
        for(int j=0;j<10;j++){
            tmpMod[(i*10+j)%n]+=mod[i];
        }
    }
    memcpy(mod,tmpMod,sizeof tmpMod);
}
void transform2(long long mod[],int k,int n){
    long long tmpMod[MAXN]={0};
    for(int i=0;i<n;i++){
        tmpMod[(i*10+k)%n]+=mod[i];
    }
    memcpy(mod,tmpMod,sizeof tmpMod);
}
int main(){
    long long mod[MAXN]={0};
    string s;
    int n;
    cin>>s>>n;
    mod[0]=1;
    for(int i=0;i<s.length();i++){
        if(s[i]=='X'){
            transform1(mod,n);
        }else{
            transform2(mod,s[i]-'0',n);
        }
    }
    cout<<mod[0]<<endl;
}

Posted on | In

简介

在平时使用Linux的时候，经常需要配置一些环境变量，这时候一般都是网上随便搜搜就有人介绍经验的。不过问题在于他们的方法各不相同，有人说配置在/etc/profile里，有人说配置在/etc/environment，有人说配置在~/.bash_profile里，有人说配置在~/.bashrc里，有人说配置在~/.bash_login里，还有人说配置在~/.profile里。。。这真是公说公有理。。。那么问题来了，Linux到底是怎么读取配置文件的呢，依据又是什么呢？

文档

我一向讨厌那种说结论不说出处的行为，这会给人一种“我凭什么相信你”的感觉。而且事实上没有出处就随便议论得出的结论也基本上是人云亦云的。事实上，与其去问别人，不如去问文档。
找了一会，发现关于环境变量配置的相关文档其实是在bash命令的man文档里，毕竟我们常用的就是这个shell。
在$man bash里，我发现了下面的一段文字：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
INVOCATION
       A login shell is one whose first character of argument zero is a -,  or
       one started with the --login option.

       An  interactive  shell  is one started without non-option arguments and
       without the -c option whose standard input and error are both connected
       to  terminals  (as determined by isatty(3)), or one started with the -i
       option.  PS1 is set and $- includes i if bash is interactive,  allowing
       a shell script or a startup file to test this state.

       The  following paragraphs describe how bash executes its startup files.
       If any of the files exist but cannot be read, bash  reports  an  error.
       Tildes  are expanded in filenames as described below under Tilde Expan‐
       sion in the EXPANSION section.

       When bash is invoked as an interactive login shell, or as a  non-inter‐
       active  shell with the --login option, it first reads and executes com‐
       mands from the file /etc/profile, if that file exists.   After  reading
       that file, it looks for ~/.bash_profile, ~/.bash_login, and ~/.profile,
       in that order, and reads and executes commands from the first one  that
       exists  and  is  readable.  The --noprofile option may be used when the
       shell is started to inhibit this behavior.

       When a login shell exits, bash reads and  executes  commands  from  the
       file ~/.bash_logout, if it exists.

       When  an  interactive  shell that is not a login shell is started, bash
       reads and executes commands from  /etc/bash.bashrc  and  ~/.bashrc,  if
       these  files  exist.  This may be inhibited by using the --norc option.
       The --rcfile file option will force bash to read and  execute  commands
       from file instead of /etc/bash.bashrc and ~/.bashrc.

       When  bash  is  started  non-interactively,  to run a shell script, for
       example, it looks for the variable BASH_ENV in the environment, expands
       its  value if it appears there, and uses the expanded value as the name
       of a file to read and execute.  Bash behaves as if the  following  com‐
       mand were executed:
              if [ -n "$BASH_ENV" ]; then . "$BASH_ENV"; fi
       but  the value of the PATH variable is not used to search for the file‐
       name.

通过这段文字，我们发现其实所谓的环境变量配置文件，就是在shell登陆的时候自动加载的那些文件。不过他所定义的登陆却分为两种：

  1. login shell登陆。
  2. interactive shell登陆。

login shell 登陆

所谓的login shell登陆，实际上就是指需要输入密码的登陆。具体的说，包括开机登陆、ssh登陆，或者是输入bash --login这种“假装自己输入密码登陆”的方式。
在这种登陆方式下，系统会先读取/etc/profile文件，然后，系统会依次搜索~/.bash_profile、~/.bash_login、~/.profile 这三个文件，并运行只其中第一个存在的文件。
尤其要注意到后三个文件的“逻辑或”的关系。很多情况下我们会发现，明明已经修改了~/.profile文件为什么重新登陆后配置不生效呢？这是因为我们的系统可能存在了前面两个文件中的一个，导致不会继续读取剩下的文件。
下面的三张图很好的说明了这个问题：



interactive shell 登陆

所谓的interactive shell登陆，其实就是相对于login shell登陆而言的。我们平时在登陆后右键打开终端、或者CTRL+ALT+T打开终端都是interactive shell登陆。
在这种登陆方式下，系统会依次读取/etc/bash.bashrc和~/.bashrc，并加以执行。
通常情况下，~/.bashrc文件里会默认记录一些常量和一些别名，尤其是$PS1变量，这个变量决定着bash提示符的格式、样式以及颜色等。

注意

需要注意的是，这两种登陆方式读取的是不同的配置文件，而且互相之间没有交集，因此当我们需要配置环境变量时，我们要根据自己的登陆方式将需要的变量配置到不同的文件里。
例如下面这个经典的问题。

典型问题

环境配置文件配置异常的例子是，当我用ssh登录服务器的时候，发现提示符是这样的：

1
bash-4.3$

没错，就像上面第三张图片里的那个bash一样，提示符非常奇怪，而且当输入ls时文件和文件夹的颜色也没有区分。
这个问题显然是由于$PS1这个环境变量没有配置，导致他用了默认值，虽然查看.bashrc文件时发现有$PS1这个变量的定义。，但是由于ssh属于login shell，因此他在登陆时读入的配置文件是/etc/profile一类的文件，并没有读入.bashrc。
导致这个问题的原因通常是我们误删除了/etc/profile里默认的配置文件，因此解决的办法也很简单。。。把.bashrc里的部分文件复制到/etc/profile里就行了。

这个问题给我们的启示是，当我们为服务器配置变量时，尽量配置到/etc/profile里或者~/.bash_profile里，因为用ssh登录服务器是基本上用不到.bashrc文件的；当我们给自己的电脑配置环境变量时，尽量配置到.bashrc里，因为这样我们只要打开终端就会读入这个文件，这样就可以不用注销就能应用配置了（只有注销重新登录才会应用/etc/profile一类的配置文件）。