- 博客(41)
- 收藏
- 关注
RSS订阅原创 微软面经 社招
微软面经 社招phone screen面一面二面三面四面AA面本人一年工作经验，面的是苏州微软sde。phone screen面一道场景题，给定一个字符串文本和一个list<string>，两者的信息量都非常大，要求从文本中检索出，存在于List中的字符串的位置。第一反应是字典树，但是好久都没有写过了，于是说了一个暴力匹配的方法，把List中的string都存储在map里。面试官让优化时间效率，我提出将List中所有string的子串（index从0开始）存在map里。面试官又让优化
2021-09-23 16:40:07
1982
1
原创 网易游戏研发岗笔试题
第三题对于一个只含大写字母的串，可以进行最多两次的修改字符的操作，问最长的连续的仅由N组成的子串长度为多少？思路：暴力，先贴代码，晚些再详述。#include<bits/stdc++.h>using namespace std;typedef struct node{ int l,r;}node;char s[50010];vector<node>...
2019-08-11 18:17:25
1698
原创 PAT L2-001 紧急救援(Dijkstra+路径记录)
L2-001紧急救援（25 分）作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。输入格式:输入第一行给出4个正整数N、M、S、D，其中N（2...
2019-03-09 14:47:51
420
原创 洛谷P1020导弹拦截(LIS nlogn)
传送门第一问让我们求一个最长不上升子序列。此题第二问要用到Dilworth定理：偏序集的最少反链划分数等于最长链的长度就是让我们求一个最长上升子序列。nlogn解法：#include<bits/stdc++.h>using namespace std;int arr[100010],ans1[100010],ans2[100010];int len1=1,...
2019-03-01 20:11:29
322
原创 南邮微机实验三 流光发生器的设计
实验目的和要求：完成相应的硬件电路连线并编写程序，使8254的三个计数器输出不同周期的方波信号，控制三个发光二极管，达到流光效果。.486CODE SEGMENT USE16 ASSUME CS:CODEBEG: JMP STARTCCONPORT EQU 213H ;控制口地址CCONBIT1 EQU 00110110B ; _0号计数器初始化控制字C...
2018-12-10 21:24:52
12693
原创 P1029 最大公约数和最小公倍数问题
传送门 分析：X0（最大公因数），（Y0）最小公倍数，Y0=X0*X1*X2P=X0*X1，Q=X0*X2，其中X1与X2互质，便符合题意。 #include<bits/stdc++.h>using namespace std;typedef long long ll;int gcd(int x,int y){ int k=x%y; whi...
2018-12-02 15:24:48
285
原创 洛谷P1032(字符串处理+BFS)
传送门分析：这道题WA点很多。。并且需要判重。弱鸡看了大佬题解才get了string类的replace()函数用法。str.replace(position,length,the other string);一个WA了好几次才意识到的地方 ：在主串中找到第一个与子串匹配的位置后，应该继续往下查找其他可匹配位置，直到主串结束。代码#include<bits/stdc++.h>...
2018-11-27 21:41:19
316
原创 洛谷P1162填涂颜色 (DFS入门好题)
传送门题目要求用BFS做，但在这里DFS明显更简洁。题意：在n*n的方格中，一个由 ‘1’ 构成的环，将整个方格划分成了两部分，即环内与环外。要求将环内格子的值均改为 2 。我们只要用DFS把所有环外的点标记出来就可以啦。先上代码#include<bits/stdc++.h>using namespace std;int n;int mp[35][35];int ro...
2018-11-22 20:02:15
445
原创 洛谷P1164 小A点菜(dp入门好题)
传送门dp[i][j]表示购买前i种物品恰好花费j元的方案数。该题为方案的叠加。代码#include<bits/stdc++.h>using namespace std;typedef long long ll;int dp[10005];int a[105];int N,M;int main(){ memset(dp,0,sizeof(dp)); ...
2018-11-21 21:53:50
232
原创 poj2420(模拟退火)
传送门模拟退火入门题代码#include<iostream>#include<cmath>#include<cstdio>#include<cstdlib>#define INF 0x7fffffffusing namespace std;int n;const double t=0.98;const double eps=1e...
2018-11-05 22:34:01
621
原创 Lyft Level 5 Challenge 2018 - Final Round (Open Div. 2) B. Taxi drivers and Lyft
题意：根据就近原则为taxi分配乘客（且乘客与两辆taxi距离相同时，选择坐标位置小的taxi。最后计算每辆taxi需要搭载的乘客总数。分析：按坐标位置从小到大遍历即可求出：每位乘客左边 （pos（taxi）< pos（people）） 距离最近的taxi的编号。同样地按坐标位置从大到小遍历即可求出：每位乘客右边距离最近的taxi的编号。代码#include<bits/stdc...
2018-11-05 21:31:15
469
原创 南邮微机实验二
实验要求：输入用户名和密码，输入密码时无回显，当输入用户名及密码与预设用户名、密码相同时，才显示欢迎页面。DATA SEGMENTINPUTID DB 'PLEASE INPUT YOUR ID: $'WRONGINPUT DB 'YOUR INPUT IS WRONG $'ID DB 'KELLY' ;your IDIDLEN EQU $-IDINPUTPASSWORD DB ...
2018-10-31 20:11:12
6950
4
原创 南邮微机实验一
（实验1.2）DATA SEGMENTSUM DB ?,?MESG DB '25+9=' DB 0,0,'$'N1 DB 9,0F0HN2 DW 25DATA ENDSCODE SEGMENT ASSUME CS:CODE,DS:DATABEG:MOV AX,DATA MOV DS,AX MOV BX,OFFSET SUM MOV A...
2018-10-30 21:58:25
8177
原创 hdu2089 (数位dp入门题)
不要62Problem Description杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。不吉利的数字为所有含有4或62的号码。例如：62315 73418 88914都属于不吉利号码。但是，61152虽然含有6和...
2018-10-27 22:25:57
254
原创 bzoj1012(单调队列)
分析：单调队列模板题，用来统计前k个或后k个数中的最大值。#include<bits/stdc++.h>using namespace std;int a[200005],ans[200005];char q[1];int main(){ char c; int M,D,cnt=0,lst=0,v; scanf("%d%d", &M, &D...
2018-10-24 21:46:04
184
原创 bzoj1003 （dp+Dijkstra）
分析：核心是要计算出任意x天不改变路线所需的花费，即此处的dis[i][j]，再用动态规划搞一下就可以了。#include<bits/stdc++.h>using namespace std;typedef long long ll;const ll mod = 1000000007;const int maxn = 105;const int INF = 1e9;ty...
2018-10-23 21:56:51
234
原创 hdu2586 (LCA-Tarjan+并查集)
How far away ？Problem DescriptionThere are n houses in the village and some bidirectional roads connecting them. Every day peole always like to ask like this “How far is it if I want to go from hous...
2018-10-16 22:51:20
210
原创 Codeforces Round #512 C - Vasya and Golden Ticket
Examplesinput573452outputYESinput41248outputNO水题= =算一下前缀和，根据总和sum[n]，从2->n枚举一下可以分成几段。假设分成k段，则遍历一下前缀和数组，若有k个sum[i]满足sum[i]%(sum[n]/k)==0，则改分割方法可行。还有就是要特判一下字符0的情况。#include<iostr...
2018-10-01 22:16:58
238
原创 Codeforces Round #510 (Div. 2) C. Array Product(暴力模拟)
C. Array ProductExamplesinput55 -2 0 1 -3output2 31 1 21 2 41 4 5input55 2 0 4 0output1 3 52 51 1 21 2 4input22 -1output2 2input40 -10 0 0output1 1 21 2 31 3 4in...
2018-09-17 22:13:25
187
原创 Codeforces Round #510 (Div. 2) B. Vitamins(暴力)
Examplesinput45 C6 B16 BAC4 Aoutput15input210 AB15 BAoutput-1input510 A9 BC11 CA4 A5 Boutput13input6100 A355 BCA150 BC160 AC180 B190 CAoutput250input25 BA...
2018-09-17 20:54:22
195
原创 ACM-ICPC 2018 焦作赛区网络预赛 K. Transport Ship (多重背包+方案记录)
K. Transport Ship传送门样例输入11 22 112样例输出01#include&amp;lt;stdio.h&amp;gt;#include&amp;lt;string.h&amp;gt;#include&amp;lt;iostream&amp;gt;#include&amp;lt;algorithm&
2018-09-17 19:09:56
336
原创 Codeforces Round #506 (Div. 3) C. Maximal Intersection
C. Maximal IntersectionExamples input41 32 60 43 3output1input52 61 30 41 200 4output2input34 51 29 20output0input23 101 5output7n个区间...
2018-09-14 21:54:38
215
1
原创 hdu2795 线段树
BillboardProblem Description At the entrance to the university, there is a huge rectangular billboard of size h*w (h is its height and w is its width). The board is the place where all possible ann...
2018-09-14 20:08:50
124
原创 hdu1394 线段树求逆序数
Minimum Inversion NumberProblem Description The inversion number of a given number sequence a1, a2, …, an is the number of pairs (ai, aj) that satisfy i &lt; j and ai &gt; aj.For a given sequence...
2018-09-13 22:11:02
212
原创 poj2777 线段树+二进制状态存储
Count ColorDescriptionChosen Problem Solving and Program design as an optional course, you are required to solve all kinds of problems. Here, we get a new problem. There is a very long board wit...
2018-09-13 21:57:30
401
原创 ACM-ICPC 2017 北京 Cats and Fish
E - Cats and FishThere are many homeless cats in PKU campus. They are all happy because the students in the cat club of PKU take good care of them. Li lei is one of the members of the cat club. He l...
2018-09-10 20:59:52
365
原创 poj3311 TSP问题 状态压缩dp
Hie with the PieDescriptionThe Pizazz Pizzeria prides itself in delivering pizzas to its customers as fast as possible. Unfortunately, due to cutbacks, they can afford to hire only one driver to d...
2018-09-02 20:11:17
270
原创 hdu1565 方格取数(状压dp入门)
方格取数(1)Problem Description 给你一个n*n的格子的棋盘，每个格子里面有一个非负数。 从中取出若干个数，使得任意的两个数所在的格子没有公共边，就是说所取的数所在的2个格子不能相邻，并且取出的数的和最大。Input 包括多个测试实例，每个测试实例包括一个整数n 和n*n个非负数(n<=20)Output 对于每个测试实例，输出可能取得的最大的和S...
2018-09-02 15:03:23
274
1
原创 阿牛的EOF牛肉串 (简单递推型dp)
HDU2047传送门阿牛的EOF牛肉串Problem Description今年的ACM暑期集训队一共有18人，分为6支队伍。其中有一个叫做EOF的队伍，由04级的阿牛、XC以及05级的COY组成。在共同的集训生活中，大家建立了深厚的友谊，阿牛准备做点什么来纪念这段激情燃烧的岁月，想了一想，阿牛从家里拿来了一块上等的牛肉干，准备在上面刻下一个长度为n的只由”E” “O” “F”...
2018-08-23 22:16:35
292
原创 ACM ICPC 2011–2012, Northeastern European Regional Contest Problem B. Binary Encoding
题意：对于一个数m，要用不同的01串（类似二进制编码）表示出0到m-1。 串的长度是n或n-1。（n为满足该表达式的最小整数：2^n>=m） 并且长度为n-1的串不可以是长度为n的串的前缀。分析：算出n，在数组中依次存下所有比特数为（n-1）的串。 如m=6，则n=3，在数组中存的串是：00011011这里只有4个串，而我们需要6个串，剩下的串的长度一定只能是...
2018-08-23 20:35:14
243
原创 Tarjan算法求割点 附裸题
无向图中割点的概念： 割点：一个结点称为割点（或者割顶）当且仅当去掉该节点及其相关的边之后的子图不连通。 判断一个结点是否为割点有如下两个条件： 条件一：若该结点u为根结点，它应有两个及两个以上的子结点。 条件二：若该结点u非根结点，它应有一个满足条件的子结点v：该子结点v及其后代没有反向边可以连回结点u的祖先。 在Tarjan算法中，有两个points非常重要： 1.dfn[i]表...
2018-08-22 14:59:33
517
原创 Educational Codeforces Round 49 (Rated for Div. 2) B. Numbers on the Chessboard
Examplesinput4 51 14 44 33 22 4output1816134input5 42 14 23 33 4output169720题意：有一个n*n的方格，先给行(i)、列(j)相加为偶数的格子依次填上编号，再给行列相加为奇数的格子填上编号。现要求某行某列的方格中填的数是多少。 ...
2018-08-20 15:02:11
193
原创 Codeforces Round #245 (Div. 1) B.Working out
B. Working outSummer is coming! It’s time for Iahub and Iahubina to work out, as they both want to look hot at the beach. The gym where they go is a matrix a with n lines and m columns. Let number a...
2018-08-16 22:31:06
155
原创 HDU2084 DP入门题
数塔Problem Description在讲述DP算法的时候，一个经典的例子就是数塔问题，它是这样描述的：有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？ 已经告诉你了，这是个DP的题目，你能AC吗?Input输入数据首先包括一个整数C,表示测试实例的个数，每个测试实例的第一行是一个整数N(1 &lt;= N ...
2018-08-16 20:40:01
259
原创 百练4103 踩方格 非常推荐的DFS入门题
4103:踩方格描述有一个方格矩阵，矩阵边界在无穷远处。我们做如下假设： a. 每走一步时，只能从当前方格移动一格，走到某个相邻的方格上； b. 走过的格子立即塌陷无法再走第二次； c. 只能向北、东、西三个方向走； 请问：如果允许在方格矩阵上走n步，共有多少种不同的方案。2种走法只要有一步不一样，即被认为是不同的方案。输入允许在方格上行走的步数n...
2018-08-15 21:55:02
354
原创 HDU1305 简单字典树
Immediate DecodabilityProblem DescriptionAn encoding of a set of symbols is said to be immediately decodable if no code for one symbol is the prefix of a code for another symbol. We will assume ...
2018-08-15 16:55:21
276
原创 HDU1251 统计难题 字典树
统计难题Problem DescriptionIgnatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).Input输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分...
2018-08-15 15:27:38
228
原创 poj2251 BFS
2251:Dungeon Master描述You are trapped in a 3D dungeon and need to find the quickest way out! The dungeon is composed of unit cubes which may or may not be filled with rock. It takes one minute to...
2018-08-14 16:23:54
139
原创 poj1321 简单DFS
1321:棋盘问题描述在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。输入输入含有多组测试数据。 每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n &lt...
2018-08-13 22:15:09
152
原创 poj2248 DFS+剪枝 or BFS
传送门2248:Addition Chains描述An addition chain for n is an integer sequence with the following four properties: a0 = 1 am = n a0 &amp;amp;lt; a1 &amp;amp;lt; a2 &amp;amp;lt; … &amp;amp;lt; am-1 &amp;amp;lt;
2018-08-13 16:07:56
263
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人