- 博客(129)
- 收藏
- 关注
RSS订阅原创 字节跳动2018校招后端方向（第三批）编程题1
有一个推箱子的游戏, 一开始的情况如下图:上图中, '.' 表示可到达的位置, '#' 表示不可到达的位置，其中 S表示你起始的位置, 0表示初始箱子的位置, E表示预期箱子的位置，你可以走到箱子的上下左右任意一侧, 将箱子向另一侧推动。如下图将箱子向右推动一格;..S0.. -> ...S0.注意不能将箱子推动到'#'上, 也不能将箱子推出边界;现在, 给你游戏的初始...
2020-03-14 16:28:07
566
原创 Gym 101873F Plug It In（二分图匹配，匈牙利算法）
题目链接：Gym - 101873F Sample Input 1 3 6 81 11 21 32 32 43 43 53 6Sample Output 15Sample Input 2 4 5 111 11 21 32 12 22 33 13 23 34 44 5Sample Output 25Sample Input 3...
2018-10-06 19:17:57
312
原创 Gym 101864 A Criminal （约瑟夫环）
题目链接：Gym - 101864 A Criminal 题意：t个样例，m个人围成一圈，m的范围在l到n，一二报数，报数到二的人离开，直至剩下一个人，现在求编号为x的人留下的概率思路：约瑟夫环有递推公式，f[1] = 0；当一个人的时候，出队人员编号为0，这里编号从0开始，题目是从1开始，f[n] = (f[n-1] + m)%n ，m表示每次数到该数的人出列，n表示当前序列的总...
2018-10-06 18:49:23
304
原创 gym-101873B Buildings（polya计数）
题目链接：B - Buildings Sample Input 1 Sample Output 11 3 1 1Sample Input 2 Sample Output 22 5 2 209728题意：一个房子，正m边形，每一面墙n*n的格子，c个颜色可以选择，旋转重合算一个方案，问有几种涂色方案思路：一面墙的不同方案数为c^(n*n)，那么问题转化为，这些不同的方案...
2018-10-05 17:08:36
425
原创 Gym - 101879C C. Promenade by the lake（欧拉回路，dfs）
题目链接：Gym - 101879C C. Promenade by the lakeThe city of Porto will host the ICPC World Finals in 2019. One of the secret touristic spots in the city is the so-called "lake of the thousand bridges". M...
2018-09-27 18:51:54
357
原创 ACM/ICPC 2018亚洲区预选赛北京赛站网络赛 B. Tomb Raider（暴力枚举）
题目链接：hihoCoder #1829 : Tomb Raider时间限制:1000ms单点时限:1000ms内存限制:256MB描述Lara Croft, the fiercely independent daughter of a missing adventurer, must push herself beyond her limits when she discov...
2018-09-26 16:35:15
185
原创 ACM/ICPC 2018亚洲区预选赛北京赛站网络赛 A. Saving Tang Monk II（bfs+dp）
题目链接：hihoCoder #1828 : Saving Tang Monk II时间限制:1000ms单点时限:1000ms内存限制:256MB描述《Journey to the West》(also 《Monkey》) is one of the Four Great Classical Novels of Chinese literature. It was writt...
2018-09-25 20:13:52
597
原创 ACM/ICPC 2018亚洲区预选赛北京赛站网络赛 D.80 Days（水）
题目链接：https://hihocoder.com/problemset/problem/1831?sid=1389856时间限制:1000ms单点时限:1000ms内存限制:256MB描述80 Days is an interesting game based on Jules Verne's science fiction "Around the World in Eig...
2018-09-22 18:41:56
444
原创 洛谷 P4015 运输问题（最小费用最大流）
输入输出样例输入样例#1： 2 3220 280170 120 21077 39 105150 186 122输出样例#1： 4850069140题意：中文题不说了思路：注意，要求所有的货物都要运送到商店，用最小费用最大流，保证在最大流的前提下，得到最小的费用。源点到仓库，流量为仓库容量，费用0；商店到汇点，流量为商店容量，费用0；仓库到商店，流量inf，费...
2018-09-21 12:32:33
602
1
原创 ACM-ICPC 2018 焦作赛区网络预赛 B. Mathematical Curse（dp）
题目链接：https://nanti.jisuanke.com/t/31711 样例输入 32 1 52 3/3 2 11 2 3++4 4 51 2 3 4+-*/样例输出 263题意： n个数字，m个运算符（+-*/），从n个数字中选择m个数字，按原数组顺序与k进行运算，使得最后结果最大思路：dp[i][j]表示取到i这个数字，用了j个操作...
2018-09-15 18:35:44
179
原创 ACM-ICPC 2018 焦作赛区网络预赛 L. Poor God Water（杜教）
题目链接：https://nanti.jisuanke.com/t/31721样例输入 33415样例输出 2046435170题意：三种食物，肉、鱼、巧克力，每小时吃一种，要求不能存在三种情况：连续三小时吃同一种食物；连续三小时，吃三种不同食物，巧克力在中间吃；连续三小时，第一小时和第三小时吃巧克力。问有几种符合条件的吃法思路：卡了很久这题，最后抱着试一试的心态...
2018-09-15 18:29:18
309
原创 ACM-ICPC 2018 焦作赛区网络预赛 G. Give Candies（大数幂，欧拉降幂）
题目链接：https://nanti.jisuanke.com/t/31716样例输入 14样例输出 8题意：n个小朋友n个糖果，从第一个小朋友开始给糖果，至少给一颗糖果，直到糖果给完，问有几种分糖果的方法思路：很容易看出来答案是2^（n-1），问题是n很大，所以要用大数，并且用到欧拉降幂，因为取模的mod=1e9+7，是素数，所以欧拉值为mod-1，2^n=2^(mod...
2018-09-15 18:18:16
156
原创 ACM-ICPC 2018 焦作赛区网络预赛 I. Save the Room（水）
题目链接：https://nanti.jisuanke.com/t/31718样例输入 1 1 21 1 41 1 1样例输出 YesYesNo题意：a*b*c的立方体，问能不能用1*1*2的立方体不重叠的放满思路：胆子放大，猜完就交，abc三遍任意一边能被2整除，就可以做到不重叠放满#include<cstdio>#include<cst...
2018-09-15 18:01:06
312
2
原创 ACM-ICPC 2018 焦作赛区网络预赛 A. Magic Mirror（水）
题目链接：https://nanti.jisuanke.com/t/31710样例输入 2JessieJustin样例输出 Good guy!Dare you say that again?题意：jessie这个人问魔镜谁最美，魔镜说她的名字（不区分大小写），就输出Good guy！否则就输出Dare you say that again?思路：注意不区分大小写就好了...
2018-09-15 17:56:29
200
原创 ACM-ICPC 2018 徐州赛区网络预赛 J. Maze Designer（LCA，最大生成树）
题目链接：https://nanti.jisuanke.com/t/31462 样例输入 3 3D 1 R 9D 7 R 8D 4 X 0D 2 R 6D 12 R 5D 3 X 0X 0 R 10X 0 R 11X 0 X 031 1 3 31 2 3 22 2 3 1样例输出 422题意：n*m的矩阵，两点之间建墙需要一定的花费，现在需...
2018-09-14 16:11:45
227
原创 ACM-ICPC 2018 徐州赛区网络预赛 B. BE, GE or NE（博弈，记忆化搜索）
题目链接：https://nanti.jisuanke.com/t/31454 样例输入1 3 -8 5 -53 1 12 0 10 2 1样例输出1 Good Ending样例输入2 3 0 10 30 0 10 10 10 2 1样例输出2 Bad Ending题意：A,B玩游戏，n轮，A先手，给一个数字m，每一轮操作有a，b，c三个选择，a为0...
2018-09-13 17:38:24
438
原创 ACM-ICPC 2018 徐州赛区网络预赛 A. Hard to prepare（递归）
题目链接：https://nanti.jisuanke.com/t/31453 样例输入23 14 2样例输出284题意：n个人围成一圈坐，每人从2^k个编号为0~2^k-1的面具中挑选一个面具戴上，求，任意相邻两人的面具编号，i，j，满足~（i^j)不为零，的可能情况思路：第一个人有2^k个选择，第二个人除不能选择与第一个人面具编号取反的面具以外，都可以选择...
2018-09-12 16:20:17
190
原创 ACM-ICPC 2018 徐州赛区网络预赛 G. Trace（set，模拟）
题目链接：https://nanti.jisuanke.com/t/31459 样例输入 31 44 13 3样例输出 10题意：n个矩阵，不存在包含，矩阵左下角都在（0，0），给右上角坐标，后来的矩阵会覆盖前面的矩阵，求矩阵周长思路：set按照x从大到小排序，从后往前遍历，放入set，找到当前矩阵在set中的位置，当前矩阵的x或者y，与set中后一位矩阵的x...
2018-09-12 15:13:19
257
原创 ACM-ICPC 2018 徐州赛区网络预赛 F. Features Track（水，暴力模拟）
题目链接：https://nanti.jisuanke.com/t/31458样例输入 182 1 1 2 22 1 1 1 42 1 1 2 22 2 2 1 4001 1 11 1 1样例输出 3题意：t组样例，n帧，k个特征，每个特征是二维向量，求最长连续出现的特征的长度，<a,b><b,a>是不同的特征思路：题目理解了，就暴...
2018-09-11 18:42:54
152
原创 ACM-ICPC 2018 徐州赛区网络预赛 H. Ryuji doesn't want to study（线段树区间求和）
题目链接：https://nanti.jisuanke.com/t/31460 样例输入 5 31 2 3 4 51 1 32 5 01 4 5样例输出 108题意：n长的数列，q个询问，1操作表示输出l到r （r-l+1）*a[l]+(r-l)*a[l-1]+……+a[r]的和 ，2表示将a[l]更新为r思路：线段树原数组为a的前缀和数组，那么a[l]更新为...
2018-09-09 21:30:24
227
原创 ACM-ICPC 2018 徐州赛区网络预赛 I. Characters with Hash（签到，模拟）
题目链接：https://nanti.jisuanke.com/t/31461样例输入 23 zoMl6 YYJSNPI样例输出 610 题意：给一个长度为n的字符串s，再给一个字符c，将字符串每一个字符的ASCII码-c的ASCII码，保留前导零，使得数字为两位，然后去掉整串数字的前导零，输出数字的长度。思路：直接模拟就好，注意全是0的情况，输出1#i...
2018-09-09 19:49:57
265
原创 ACM-ICPC 2018 沈阳赛区网络预赛 K. Supreme Number（打表找规律）
题目链接：https://nanti.jisuanke.com/t/31452样例输入 26100样例输出 Case #1: 5Case #2: 73 题意：supreme number的定义是：一个数的任意子串都是素数或者1（不连续），求不超过N的最大的supreme number思路：一位数符合的有：1 2 3 5 7；两位数符合的有：11 13 17 23 31...
2018-09-08 20:08:05
448
原创 ACM-ICPC 2018 沈阳赛区网络预赛 I. Lattice's basics in digital electronics（trie树，模拟）
题目链接：https://nanti.jisuanke.com/t/31450 样例输入 215 932 010033 11100 1011101 0110104 1010108 00111 100114 0111119 0101A6Fd021171c562Fde18 349 000150 0100151 01114DB247226...
2018-09-08 19:54:26
355
原创 ACM-ICPC 2018 沈阳赛区网络预赛 D. Made In Heaven（A*，K短路）
题目链接：https://nanti.jisuanke.com/t/31445 样例输入 2 21 2 2 141 2 52 1 4样例输出 yareyaredawa题意：单向图，问K短路是否小于等于T思路：模板题，你只需要一个优秀的板子，我的板子不够优秀就T了，队友的板子够优秀，但是他居然Whitesnake！里的W没有大写wa了7发！！！！！！！！#...
2018-09-08 18:46:48
264
原创 ACM-ICPC 2018 沈阳赛区网络预赛 G. Spare Tire（容斥）
题目链接：https://nanti.jisuanke.com/t/31448样例输入 4 4样例输出 14题意：给出a的递推式，1到n中与m互质的数为i，求a[i]的和思路：得到a的通项公式为,Sn的通项为,与m不互质的数，是取m的素因子的乘积，那么将m分解质因数，通过容斥原理，就可以得到与m不互质的数，总和减去这些数对应的a的和就是答案了。在求这些不互质数对应a的总和的...
2018-09-08 18:12:03
862
原创 ACM-ICPC 2018 南京赛区网络预赛 E. AC Challenge（状压dp）
题目链接：https://nanti.jisuanke.com/t/30994样例输入1 55 6 04 5 1 13 4 1 22 3 1 31 2 1 4样例输出1 55样例输入2 1-100 0 0样例输出2 0题意：n个题目，做每一个题目的得分是t*ai+bi，做某一题前必须先做完规定的题，求最大的得分思路：n只有20，状压dp，dp[i]表...
2018-09-07 16:47:56
123
原创 ACM-ICPC 2018 南京赛区网络预赛 L. Magical Girl Haze（队列优化的dijkstra，dp）
题目链接： Magical Girl Haze样例输入 15 6 11 2 21 3 42 4 33 4 13 5 64 5 2样例输出 3题意：n个点，m条边，有重边，最多可以使得k条边权值为0，问从1到n的最短路思路：dist[i][j]代表走到i这个点，使得j条边权值为0的最短路，用队列优化的dijkstra模板，用num记录当前边权为0的边数，除了常规...
2018-09-01 20:20:57
210
原创 ACM-ICPC 2018 南京赛区网络预赛 J.Sum（线性筛选，分解质因数）
题目链接：Sum样例输入258样例输出814题意：定义f[i]函数代表i=a*b的对数，其中a和b都不能是平方数的倍数，a*b与b*a不相同，t组样例，给出n，求1~n的f[i]之和思路：一个数n分解质因数为 ，且有，容易得到这样的规律，遍历所有的e，当e=1时，f[i]=f[i]*2，当e=2时，f[i]不变，当e>2时，f[i]=0。如果直接一个一个分解质因...
2018-09-01 18:11:27
937
3
原创 2018中国大学生程序设计竞赛 - 网络选拔赛 1003 Dream（hdu 6440）（费马小定理）
题目链接hdu 6440 DreamSample Input12 Sample Output0 11 00 00 1题意：重新定义+和*运算，要求小于p的m和n，满足，p为素数 思路：题意比较难懂，但是如果想到了费马小定理，代码是很简单的#include<cstdio>#include<cstring>#include<...
2018-08-27 14:59:32
253
原创 FFT（模板）
#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<iostream>using namespace std;typedef long long ll;//typedef complex<double> C...
2018-08-24 16:23:23
139
原创 莫比乌斯反演（模板）
太难了！看了这个博客：莫比乌斯反演详解 构造是重点，现在看这题： 构造方法和上面的讲解中的构造是基本一致的#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<iostream>using namespac...
2018-08-24 15:51:23
513
原创 求原根（模板）
数论令人头秃，原理就看看别人博客吧：数论之原根#include<cstdio>#include<cstring>#include<cmath>#include<iostream>#include<algorithm>#include <sstream>#include <set>#include
2018-08-24 11:11:28
4103
原创 中国剩余定理（孙子定理）（模板）
中国剩余定理是求解一次同余式组的方法当a互质的时候：#include<iostream>#include<cstdio>#include<climits>#include<cstring>#include<algorithm>using namespace std;int n,m[105],a[105],lcm=...
2018-08-24 11:05:49
282
原创 2018 Multi-University Training Contest 10 1010 Problem J. CSGO（hdu6435）
题目链接：hdu 6435 Problem J. CSGOSample Input22 2 10 2330 6660 1230 4562 2 1100 0 1000 100 1000 100100 0 Sample Output5432000题意：n个主武器，m个副武器，每个武器有一个s值和k个属性，现在选一个主武器，一个副武器，要求两个武器的对应属性值的...
2018-08-22 21:00:43
361
原创 2018 Multi-University Training Contest 10 1012 Problem L.Videos（hdu 6437）（最小费用流）
题目链接：hdu 6437 Problem L.VideosSample Input210 3 1 101 5 1000 05 10 1000 13 9 10 010 3 1 101 5 1000 05 10 1000 03 9 10 0 Sample Output20001990题意：一天有n个小时，m个节目，k个人，以及W，每一个节目从s小时开始t小时...
2018-08-22 20:07:25
179
原创 2018 Multi-University Training Contest 9 1001 Rikka with Nash Equilibrium（hdu 6415）（dp）
题目链接：hdu 6415 Rikka with Nash EquilibriumSample Input23 3 1005 5 2333 Sample Output641170题意： n*m的矩阵，填入1~n*m的数字，若某个数字是这个数字所在行列的最大值，那么这个数字就被称为Nash Equilibrium，现在要求你构造的矩阵只存在一个Nash Equilibr...
2018-08-21 12:47:39
160
原创 牛客网暑期ACM多校训练营（第十场）D Rikka with Prefix Sum
链接：https://www.nowcoder.com/acm/contest/148/D来源：牛客网 题目描述Prefix Sum is a useful trick in data structure problems.For example, given an array A of length n and m queries. Each query gives an inte...
2018-08-19 19:34:35
665
原创 2018 Multi-University Training Contest 8 1010 Taotao Picks Apples（hdu 6406）（ST、dp、二分）
题目链接：hdu 6406 Taotao Picks ApplesSample Input15 31 2 3 4 41 55 52 3 Sample Output153HintFor the first query, the heights of the apples were 5, 2, 3, 4, 4, so Taotao would only pic...
2018-08-15 21:25:14
156
原创 2018 Multi-University Training Contest 8 1001 Character Encoding （hdu 6397）（容斥）
题目链接：hdu 6397 Character EncodingSample Input42 3 32 3 43 3 3128 3 340 Sample Output107903题意：给n，m，k，从0到n-1中取正好m个数字（可以重复取），求这m个数字之和为k的方案数 思路：假设没有0到n-1这个限制条件，那么问题就变成k分为m份有几种方案，这是经典的组...
2018-08-15 19:04:24
170
原创 2018 Multi-University Training Contest 8 1004 Parentheses Matrix（hdu 6400）
题目链接：hdu 6400 Parentheses MatrixSample Input31 12 22 3 Sample Output(())(((())) 题意：n*m的矩阵，由'（'或'）'组成，空字符串为平衡，若A平衡，则（A）也平衡，若A和B平衡，则AB平衡，输出平衡的行和平衡的列之和最大的情况。思路：首先明确奇数的情况下，不可能是平衡的，所以当...
2018-08-15 17:38:58
121
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人