- 博客(84)
- 收藏
- 关注
RSS订阅原创 阿里一面凉经
面试十分的突然。一切源于我加了同学发的招聘信息里的答疑群，然后内推人就加了我。我才刚开始准备春招，还没复习，就收到了内推人的消息，问我要投什么岗位，在一番交流之后，我的简历就被推上去了，很快就安排了面试ORZ。着实过于迅速，没复习慌得一批。因为我简历上写的是熟悉c++语言，然后投的java岗，就问了以下几个问题，个人觉得真的很简单啊，但是由于没有准备直接GG了。1、自我介绍2、tcp是怎样...
2021-03-06 11:16:00
43
原创 牛客题霸题解
题目：字符串距离计算题解：这个题暴力就好了，三层循环枚举哪个字符转换成哪个字符，然后将第一个串中的所有该字符替换，再比较两个串中不同的字符有多少个，每次更新最小值就好了。代码： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
2020-11-03 20:41:45
269
原创 POJ - 1696 Space Ant
传送门：Space Ant题意给出n个点，有一个小人，他每次只能往左边拐，并且不能走以前走过的路，走的路线也不能相交，问他怎么走可以走的路程最大。题解可以想到肯定是所有的点都走到路径会最大，然后就很容易想到这不就可以一直凸包了吗！！每次形成凸包的点删掉再继续凸包，然后每次把点的编号加入队列中，直到没有点没被走过。我用的是graham算法的凸包，先找到纵坐标最小的点，第一次按照极角排序是判...
2020-09-28 15:35:00
44
原创 2018 ccpc吉林 The Tower
传送门：HDU - 6559题意在一个三维空间，给定一个点和他的三维速度，给定一个圆锥，问这个点最早什么时候能撞上圆锥。题解本来一直想着怎么求圆锥的方程，然后....队友：这不是二分吗！然后问题就转换成了要怎么求当前时间是不是已经穿过了圆锥了....然后就gg了。正解就是联立:① r ' = (h-z)/h*r② x=x0+vx*t; y=y0+vy*t; z=z0+vz*t;③...
2020-09-27 17:57:00
34
原创 POJ - 1066 Treasure Hunt
传送门：Treasure Hunt题意有一个左下角为(0,0)，右上角为(100,100)的正方形，给出n条线段，线段的起点和终点都在正方形上，给定一个宝藏的坐标，问从正方形外走到宝藏至少要经过多少条线段。每次只能走线段的中点，也就是每两个交点的中点。题解因为肯定是从正方形的边开始走，所以枚举每条边上的相邻两个点的中点，连接宝藏所在的点，看这条线段和几条线段有交点，并更新最小值。(为什...
2020-09-27 17:21:00
20
原创 [HAOI2008]排名系统
传送门：https://ac.nowcoder.com/acm/problem/19971先记录下来，以后再学。神奇操作题解用到了C++ pb_ds库，真是一个神奇的库啊....#include <ext/pb_ds/assoc_containe.hpp>#include <ext/pb_ds/tree_policy.hpp>using namespace __...
2020-08-24 21:29:00
29
原创 回文树(回文自动机PAM)小结
回文树学习博客：lwfcgz poursoul边写边更新，大概会把回文树总结在一个博客里吧...回文树的功能假设我们有一个串S，S下标从0开始，则回文树能做到如下几点：1.求串S前缀0~i内本质不同回文串的个数(两个串长度不同或者长度相同且至少有一个字符不同便是本质不同)2.求串S内每一个本质不同回文串出现的次数3.求串S内回文串的个数(其实就是1和2结合起来)4.求以下标i...
2020-08-19 11:56:00
32
原创 [USACO12FEB]Symmetry
传送门：https://www.luogu.com.cn/problem/P3046https://ac.nowcoder.com/acm/contest/6306/G题意给定n个不同的点，求这个点集有多少条对称轴题解对于一个点只有两种情况，一种是和另一个点关于这条线对称，一种是在对称轴上。第一种情况：随机选择一个点p，枚举其他的点和他形成的对称轴，然后再判断这个对称轴是不是点集的...
2020-08-14 12:03:00
23
原创 Codeforces Round #664 (Div. 2) D. Boboniu Chats with Du
传送门：cf1395D题意给定一个长度为n的数组a[i]为当天说话的有趣值，如果a[i]>m，那么在 i 之后有d天不能说话。否则可以每天都说话。找到一个排列使得n天有趣值总和最大，问有趣值总和的最大值是多少。题解很明显用贪心。先取>m的有趣值直到取不下。根据样例1的解释可以看出将一个大于m的值放在最后，前边放<m的会更优，所以此时有两种情况，如果取了的p个大于m的值p...
2020-08-13 10:15:00
27
原创 Codeforces Round #664 (Div. 2) C. Boboniu and Bit Operations
传送门：cf1395C题意c[i]=a[i]&b[j]，b[j]是b数组中任意一个，求c[1] | c[2] | ... | c[n]最小值。题解经典的二进制枚举答案，因为a和b的最大值<29，所以最后的结果最大是9个位置全1，不会超过210 ，故只要枚举0到210-1即可。每次答案和a[i]&b[j]的值相与，如果有一个 j 可以使相与后答案不变，那么当前a[i...
2020-08-13 09:51:00
20
原创 2020牛客暑期多校训练营（第十场）
传送门：https://ac.nowcoder.com/acm/contest/5675AEIJA. Permutation题意给定一个质数p，找到一个1~p-1的排列，使得xi+1≡2xi(modp)或者xi+1≡ 3xi(modp)。题解打表找规律，可以发现2xi(modp) 会形成若干个环，3xi(modp)也会形成若干个环。如果在x*2中的某个...
2020-08-11 22:02:00
25
原创 2020牛客暑期多校训练营（第九场）
AEFIKA. Groundhog and 2-Power Representation题意一个数可以由2x1+2x2+2x3+.....组成，例如1315=210+28+25+2+1=2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0).现在给出一个由2的次幂组成的表达式，输出这个数是多少。题解不得不说py真的强，看到不到2分钟就有人a了，...
2020-08-09 17:53:00
30
原创 牛客网暑期ACM多校训练营（第二场）message
传送门：https://ac.nowcoder.com/acm/problem/16631题意对于直线y=ax+b，给出n个的a[i]和b[i]。m次询问，每次询问给出直线y=cx+d的c[i]和d[i]，如果和给出的n个直线交点的最大横坐标>0，则输出横坐标，否则输出No cross。题解y=ax+b ①y=cx+d ②联立①②得：x = - (b-d) / (...
2020-08-07 20:58:00
18
原创 牛客算法周周练18 画个圈圈诅咒你
有被诅咒到.......传送门：画个圈圈诅咒你题意主要是画线的这两个条件。题解这个题的关键在于，还记得高中的正弦定理和三角函数的运算。博主早就将知识还给老师了，幸好有学霸旁友指点。推导过程看图本来题解就写到了这里，但是我敲代码的过程中发现我的三角函数也白学了T^T，觉得应该不止我一个人会计算错，所以又写了计算角的过程(ಥ_ಥ)。代码 1 #include<...
2020-08-05 01:35:00
23
原创 2020牛客暑期多校训练营（第八场）Game SET
传送门：Game SET题意一套牌有四种属性，每种属性都有三种特征，shapes (one, two, or three), shape (diamond, squiggle, or oval), shading (solid, striped, or open), color (red, green, or purple)，如果是*，可以选任意一种。给出n套牌，每套牌给出[<num...
2020-08-03 23:19:00
25
原创 2020牛客暑期多校训练营（第八场） Kabaleo Lite
传送门：Kabaleo Lite题意有n道菜，1≤n≤105，a[i]是每道菜可以赚的钱，−109≤ ai≤109，b[i]是这道菜的个数，1≤bi≤105，你每次只能选从1开始连续的菜，然后问最多有多少顾客，并且顾客最多的前提下赚的钱最多是多少。题解这个题的重点在于会用__int128，我都没见过，好菜呜呜。从数据可以看出，爆long long了，一开始没发现，和队友疯狂wa，...
2020-08-03 18:30:00
24
原创 2020牛客暑期多校训练营（第八场）Interesting Computer Game
传送门：Interesting Computer Game题意给出n对数，你可以操作n次，每次操作只能在下面三种中选择一种，问最多可以选多少个不同的数字。什么都不做如果a[i]以前没选过，那么可以选择a[i]如果b[i]以前没选过，那么可以选择b[i]题解想法很简单，就是一个并查集。如果a[i]和b[i]的父亲一样，那么用一个数组记录一下这个父亲，说明这个堆里有环，否则把...
2020-08-03 18:24:00
26
原创 牛客15334 Easygoing Single Tune Circulation（后缀自动机+字典树）
传送门：Easygoing Single Tune Circulation题意给定n个字符串 s[i]，再给出m个查询的字符串 t[i]，问 t[i] 是否为某个 s[i] 循环无限次的子串。题解分成两种情况① t[i] 比 s[j] 短， 这个时候可以用后缀自动机，把每个 s[j] 重复一次，然后放到SAM中，这样直接每次直接查询就好了。当然，因为是有t(t<=1e5)组数据，...
2020-08-01 01:16:00
30
原创 牛客NC15879 A Simple Problem
传送门：A Simple Problem题意给定两个序列s1和s2，同样的数字可以用相同的别的数字代替(并且也可以是出现过的数字)，问s2在s1中出现了几次。题解首先预处理一下这两个序列，因为数字的位置是不会变得，所以把每个数字用当前位置和前一次出现的位置的差表示，如果是第一次出现，用-1表示，这里为什么是-1呢，不能比-1更大，但可以更小，不然如果匹配的时候 j=0，那么如果 s[i]...
2020-07-29 22:04:00
24
原创 牛客网暑期ACM多校训练营（第二场）carpet
传送门：carpet题意有一个n*m的地毯，aij表示地毯每格的元素，bij表示地毯每格的价格，要求选取一块价格最大值最小的地毯，并且这块地毯无限铺开之后，原地毯是其子矩阵。题解先找到这个矩阵的最小循环节子矩阵，求一下每行的循环节长度用map记录，取出现次数为m并且循环节长度最小的；每列也求一下循环节长度用map记录，取出现次数为m并且循环节长度最小的；这样就得到了最小的循环节子矩阵。然...
2020-07-29 09:07:00
28
原创 2020牛客暑期多校训练营（第六场）
BCEGKB. Binary Vector题意大概是说有一个A={0,1}，每天可以在An(n维空间) 中生成一个新的二进制向量，n天中生成的向量线性无关的概率是fn，求f1⊕f2⊕...⊕fn。题解由于这N个向量线性无关,则这N个向量张成的空间秩为N,考虑将每次随机的向量加入之前向量的空间，那么最后N个向量秩为N当且仅当每次加入的向量都不属于之前的空间。线性无关的意思是...
2020-07-28 11:49:00
10
原创 2020牛客暑期多校训练营（第五场）
DEFID. Drop Voicing题意：给你一个数列，你可以进行两种操作。Drop-2: 将n-1位置的数移到第一个位置，变成pn−1,p1,p2,…,pn−3,pn−2,pn。Invert: 将第一个数移动到最后一个位置，变成p2,…,pn−3,pn−2,pn−1,pn,p1。每次操作可以选择一种不限次数的移动，问Drop-2操作最少几次。...
2020-07-27 20:59:00
128
原创 2020牛客暑期多校训练营（第四场）
BCFHps：c还没写，明天起来再肝B. Basic God Problem题意给出c和n，求fc（n）。题解递归到最后 fc 函数肯定等于1，那么就变成了求c被乘了几次，只要找到 x 最多能被分解成多少个数相乘就好了。预处理用线性筛求出每个数最多能被分解成多少个数相乘，快速幂求出解。代码 1 #include<bits/stdc++.h> 2 #d...
2020-07-21 00:44:00
330
原创 2020牛客暑期多校训练营（第三场） Operation Love
传送门：Operation Love题意：t组测试，每次测试按顺时针或逆时针给20个点，是一个手的形状，问是左手还是右手。题解：这个题可以用凸包解，板子求出凸包的所有点记录下来，然后求一下长度为6的边（即大拇指）的下一条边是不是底下长度为9的边。是的话就是右手，否则为左手。但是，这个题他卡精度，两个边长相等判断的时候要用fabs(d1,d2)<1e-5，比1e-5更大一些也可以...
2020-07-18 17:43:00
232
原创 2020牛客暑期多校训练营（第二场） Boundary
传送门：Boundary题意：给你n个点的坐标，问最多有多少个点可以在同一个圆上，（0,0）必须在这个圆上。题解：三个点确定一个圆，所以暴力枚举两个点和（0,0）组成的圆，如果三个点不共线的话，用圆心公式求出圆心，然后用map记录以当前点为圆心的点圆的个数，边记录边判断有多少个圆圆心是同一个点，取最大值就好了。 1 #include<bits/stdc++.h>...
2020-07-15 16:09:00
345
原创 2020牛客暑期多校训练营（第一场）Easy Integration
传送门：J. Easy Integration题意：给你n，求这个积分，最后的结果分子是记为p，分母记为q。求（p*q-1）mod998244353。题解：比赛完看到巨巨说这是贝塔函数，我一搜还真是。贝塔函数的递推公式：但是菜鸡只会打表找规律。那么说说怎么找到的规律吧。先把所有的分子分母都找到，这个要用到（x-1）^n=C(n,0)x^n(-1)^0+C(n,1)x^(n...
2020-07-15 10:06:00
213
1
原创 2020牛客暑期多校训练营（第二场）All with Pairs
传送门：All with Pairs题意：给你n个字符串，求出，f(si,sj)的意思是字符串 si的前缀和字符串 sj后缀最长相等部分。题解：先对所有的字符串后缀hash，用map记录每个hash值（后缀）有多少个一样的。这个地方后缀的 hash 值可以将字符串倒过来求，每次乘以base^ i ，这和字符串正着求每次 t=t *base + s 是一样的，可以想象一下，前后...
2020-07-14 21:54:00
369
原创 2020牛客暑期多校训练营（第二场） Fake Maxpooling
传送门：Fake Maxpooling题意：给出矩阵的行数n和列数m，矩阵 Aij = lcm( i , j ) ,求每个大小为k*k的子矩阵的最大值的和。题解：如果暴力求解肯定会t，所以要智取。前几天刷蓝书的时候看到这种求区间最值的可以用单调队列，这个题就是用单调队列求解。先横着算一下每个长度为k的区间的最大值记录下来，然后再把记录下来的数组竖着同样算一下，最后求和。求最小公倍数...
2020-07-13 19:49:00
294
原创 匹配统计
传送门：https://www.acwing.com/problem/content/162/（acwing有视频讲解，题解，数据之类的）题意：给你两个字符串a和b，有q次询问，每次询问输出a的所有后缀和b恰好匹配长度为x的后缀个数。题解：这个题好微妙啊，我换了两种思路都不太对。然后看了一下大雪菜老师的视频和（传送门）这个题解，豁然开朗。先求出 b 串的 next 数组，然后a和b...
2020-07-11 17:57:00
237
原创 2019ICPC南昌邀请赛 Sequence
题意：给出n个点的权值，m次操作，操作为1时为询问，每次询问给出 l 和 r ，求 f(l,r)。操作为0时为修改权值。f(l,r)=f(l,l)⊕f(l,l+1)⊕⋯⊕f(l,r)⊕f(l+1,l+1)⊕⋯f(l+1,r)⊕⋯⊕f(r,r)F(l,r)=f(l,l)⊕f(l,l+1)⊕⋯⊕f(l,r)⊕f(l+1,l+1)⊕⋯f(l+1,r)⊕⋯⊕f(r,r)。题解：首先多写算几个 ...
2020-07-09 11:48:00
125
原创 WIN7使用msg命令发送消息心得
昨天搞了一下午+一晚上，终于捣鼓出了一些奇奇怪怪的操作，成功发送了消息。应实验要求，博主有幸在家里搞到了两台win7，其他的系统是不是这么操作就不太清楚了。一开始实验指导书上是用net send发消息，然后查了一下发现win7已经没有这个功能了，可以用msg发送。 命令是msg /server:对方IP地址 * "消息" （*的前后都要有空格）然后你就会惊奇的发现 “ 获取会话...
2020-06-07 16:06:00
4153
2
原创 Codeforces 1355 E. Restorer Distance（三分）
传送门：E - Restorer Distance题意：给出四个数N,A,R,M ，然后给出一个长度为N的序列。让一个数+1花费A，-1花费R，从一个大的数向一个小的数移动1花费M。问让所有数一样大的最小花费。题解：三分，每次找到可以移动的最大数量*M，再加上剩下比当前数小的*A，比当前数大的*R。 1 #include<bits/stdc++.h> 2 ...
2020-05-16 22:58:00
133
原创 Codeforces 1355 D. Game With Array
传送门：D - Game With Array题意：让你构造一个长度为n的序列，并且n个数的和为S，问能不能找到一个1~n的数k，使得数组里找不出一个子序列的和为k或者n-k；题解：最简单的想法肯定是让k=1，然后数组只要不出现1和n-1就好了，只要 s /n >= 2，也就是由n-1个2和一个 s-(n-1)*2 != 1 构成就可以。 1 #include<bit...
2020-05-16 21:56:00
112
原创 Codeforces 1355 C. Count Triangles
传送门：C - Count Triangles题意：给你四个数A，B，C，D，求有多少个三边为x，y，z （A≤x≤B≤y≤C≤z≤D）的三角形。题解：枚举 x=A~B，然后计算当z的值大于等于C时，y为最小值B可以有多少个三角形，y为最大值C有多少个三角形。想想就可以发现 y=B~C时 其实就是一个差值为1的等差数列。然后要算出 y=B 和 y=C 时 z...
2020-05-16 21:47:00
145
原创 Codeforces Round #641 (Div. 2)
只写了A~DA - Orac and Factors题意：f(n)就是n的第二小因数，问执行k次 n=f(n)+n 后的结果。题解：如果一直找第二小的因子的话,1e9肯定得t。看下边样例解释就会惊奇的发现，执行次数多了，n一定会变成2的倍数，然后就可以剪枝了。如果n不是2的倍数，那么就执行n=f(n)+n，k-- 直到n是2的倍数（当然k得>0），最后再加上k*2。 1...
2020-05-12 23:14:00
128
原创 Codeforces 1345 D - Monopole Magnets
传送门：D. Monopole Magnets这一场也是很神奇了，先是推迟三天，后是评测鸡崩了，unrated...题意：每一行，每一列必须都要至少有一个s，n要可以到所有的黑格，n的上下左右如果有一个s，他就可以往那个方向移动一格，n最后不能在白格，求n最少的个数。题解：1、每一行每一列如果有#，#必须是连续的，否则输出-12、如果有一行没有#，那么至少有一列要没有#，s就可...
2020-05-08 01:16:00
109
原创 SPOJ - SUBLEX Lexicographical Substring Search
感觉后缀自动机好难啊，比后缀数组难多了...看了好几天勉强懂了一丢丢学习博客：洛谷某大佬HihoCoder题目传送门：https://www.spoj.com/problems/SUBLEX/en/题意：给你一个字符串，然后是q次查询，每次输出第i小的字符串。题解：先构造出后缀自动机，然后对每个节点预处理出从这个节点可以到达多少个不同的子串，然后沿着SAM一路查找下去并更新。...
2020-04-28 23:07:00
106
原创 2020年4月 第十一届蓝桥杯大赛个人赛(软件类)省级模拟赛
感觉我的答案应该都是对的吧（逃1.问题描述 一个包含有2019个结点的无向连通图，最少包含多少条边？答案：2018题解：无向图最少边是一个树的结构，边数为结点数-1。2.问题描述 在计算机存储中，12.5MB是多少字节？答案：13107200题解：12.5*1024*10243.问题描述 由1对括号，可以组成一种合法括号序列：()。 由2对括号，可以组成...
2020-04-22 22:40:00
723
1
原创 Codeforces Round #634 (Div. 3)
D题想复杂了，花了好多时间，感觉也没时间看F了，就来写个题解蹭蹭访问量把^_^传送门：1335 A. Candies and Two Sisters题意：你要把n个糖果分给两个人，两个人的糖果数不能相等，问你有几种分法。题解：就是（n-1）/2 1 #include<bits/stdc++.h> 2 #define ll long long 3 using...
2020-04-14 01:02:00
72
原创 POJ - 1226 Substrings (后缀数组)
传送门：POJ - 1226这个题跟POJ - 3294和POJ - 3450都是一样的思路，一种题型。POJ - 3294的题解可以见：https://www.cnblogs.com/lilibuxiangtle/p/12649853.html题意：给你n个字符串，求最长子串的长度，要求子串或子串的翻转串在n个字符串中都出现。题解：把每个字符串和字符串的翻转串连接起来，中...
2020-04-13 15:15:00
122
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人