- 博客(334)
- 收藏
- 关注
RSS订阅原创 Codeforces Round #791 (Div. 2)（A-D）
Codeforces Round #791 (Div. 2)（A-D）A. AvtoBus题意：给你 n, 问满足 4x+6y=n4x+6y=n4x+6y=n 的 x+yx+yx+y的最小值和最大值是多少？x,yx,yx,y 都是非负整数。题解：n如果是奇数，无解。如果是偶数，等式除以2，考虑 2x+3y=n2x+3y=n2x+3y=n 。要想使得x+yx+yx+y尽可能大，那么x要尽量多，就需要找最小的y满足n−3yn-3yn−3y是偶数，分别讨论摸3的各种情况。反之同理。#include
2022-05-19 19:44:24
9343
原创 【无标题】Educational Codeforces Round 120 (Rated for Div. 2)（A-C）
Educational Codeforces Round 120 (Rated for Div. 2)（A-C）知识点整理：题号知识点备注A无B贪心，排序C贪心，二分，三分，前缀和D组合数学，双指针E位运算F构造，数论，哈希A - Construct a Rectangle题意给你三根木棍，折断其中一根变成四根，边长均必须为整数，问可否构成矩形题解两种情况：最长的等于两个短的之和有两根相等，另一根是偶数
2021-12-28 17:40:02
1528
原创 【无标题】AtCoder Beginner Contest 224（A-F）
AtCoder Beginner Contest 224（A-F）知识点整理：题号知识点备注A无B无C图D基础DP矩阵最大路径和变种E状态机DPF状压DPG?H?A - QQ solver题意给你三个字符组成的乘法表达式, 求计算结果题解用scanf读入整数#include <bits/stdc++.h>using namespace std;int main() {
2021-12-21 21:49:49
1126
1
原创 1584D - Guess the Permutation & 交互题入门
1584D - Guess the Permutation & 交互题入门一、 交互题简介第一次做交互题,用了大概半天时间学习了交互题的概念和大致做法交互题跟一般题相反, 一般题目是系统给你输入数据, 让你输出答案, 系统判断答案是否正确而交互题则类似于电视节目中的猜数字, 你可以理解为后台有一些数据, 但是需要你去询问, 系统会根据你的询问给你答案, 需要你在规定的询问次数内得到答案并输出主要的思想是二分、三分、随机数,难点在于几乎无法本地自测交互题是special judge中的一种
2021-11-15 12:30:36
1577
原创 AtCoder Beginner Contest 227（A-F）
AtCoder Beginner Contest 227（A-F）知识点整理：题号知识点备注A模拟,数学B打表法C数学D二分,贪心E字符串,DP建议顺便做下leetcode 777FDP好题, 经典题的变形G数论Poj2992, 数据范围加大H图论,欧拉路,网络流本次比赛大概比之前的ABC难一个字母, C相当于D,D相当于E这样子.简单题A - Last CardN个人站成一圈, 从A号人开始依
2021-11-15 08:08:52
883
2
原创 AtCoder Beginner Contest 226 H - Random Kth Max
H - Random Kth Max题意：给你NNN个连续随机变量X1,X2...XnX_1,X_2...X_nX1,X2...Xn.其中XiX_iXi 在区间[Li,Ri][L_i,R_i][Li,Ri]内均匀分布，求第KKK大数的期望。题解：一、求解子问题先看这个子问题：NNN个连续随机变量X1,X2...XnX_1,X_2...X_nX1,X2...Xn都服从U(0,1)U(0, 1)U(0,1),求第kkk大的数的期望。我们在大学的**《概率论与数理统计》**学
2021-11-11 19:24:38
407
原创 AtCoder Beginner Contest 226（A-H）
AtCoder Beginner Contest 226（A-G）@TOC知识点整理：题号知识点备注A无B无CBFSD简单模拟、数学E图论好题，需要记住思路FDP较为复杂的DPG贪心ARC的一道类似题H概率期望，DP签到题、简单题A - Round decimals求浮点数的四舍五入#include <bits/stdc++.h>using namespace std;in
2021-11-11 10:45:57
335
原创 AtCoder Beginner Contest 226（A-G）
AtCoder Beginner Contest 226（A-G）知识点整理：题号知识点备注A无B无CBFSD简单模拟、数学E图论好题，需要记住思路FDP较为复杂的DPG贪心ARC的一道类似题H概率期望，DP签到题、简单题A - Round decimals求浮点数的四舍五入#include <bits/stdc++.h>using namespace std;int mai
2021-11-11 10:45:15
962
原创 Codeforces Round #751 (Div. 2)
Codeforces Round #751 (Div. 2)知识点整理：题号知识点难度备注A字符串800B构造1100C数学1300DBFS，DP1900E分治，贪心，线段树2300F排序，贪心2700A题题意：给你一个字符串s，把他拆成两个字符串，a和b，要求a的字典序最小。题解：找到s里最小的字符，单独把它拿出来，然后把剩下的构成一个新字符串。#include <bits/stdc++.h
2021-10-27 22:14:50
148
原创 AtCoder Beginner Contest 224题解 A-G
AtCoder Beginner Contest 224签到题、简单题A - Tires判断一个字符串是不是以er或ist结尾。直接做即可#include <bits/stdc++.h>using namespace std;int main() { string s; cin >> s; int n = s.size(); if (n >= 2 && s[n-1]=='r' && s[n-2]=
2021-10-24 10:34:23
3918
3
原创 codeforces 刷题指南
https://blog.csdn.net/qq_16964363/article/details/79224776主要参考这篇文章，侵删。近期cf上线了难度指数功能，将每道题的难度量化。那么我根据这篇博主的启发， 做了个爬虫来对每个分类的难度进行分析。先上爬虫代码：# -*- coding: utf-8 -*-import jsonimport urllib.requestfro...
2018-11-12 18:39:39
5524
原创 360春招笔试算法题题解
A. 跑步（水）题目描述小明同学喜欢体育锻炼，他常常去操场上跑步。跑道是一个圆形，在本题中，我们认为跑道是一个半径为R的圆形，设圆心的坐标为原点(0,0)。 小明跑步的起点坐标为(R,0)，他沿着圆形跑道跑步，而且一直沿着一个方向跑步。回到家后，他查看了自己的计步器，计步器显示他跑步的总路程为L。 小明想知道自己结束跑步时的坐标，但是他忘记自己是沿着顺时针方向还是逆时针方向跑的了。他想知道在这两
2017-03-19 18:40:02
3279
2
原创 面经总结
一、操作系统1. 介绍一下信号量和互斥锁信号量是非负数，只有两个操作wait,signal 互斥量是0,1，只能用于一个资源的互斥访问 互斥量用于线程的互斥，信号线用于线程的同步。 有人做过如下类比： Mutex是一把钥匙，一个人拿了就可进入一个房间，出来的时候把钥匙交给队列的第一个，一般的用法是用于串行化对临界区代码的访问，保证这段代码不会被并行的运行。 Semaphore是一件可以容纳
2017-03-06 10:38:33
5741
7
原创 Week Of Code 28
A.Boat Trips(水)题目大意：n条旅游线路，每条旅游线路 pip_i人。现在有m条船，每条船装c个人，问是否这些船能满足所有的旅游线路？题目分析：就是判断 mcmc是否全部小于pip_i.太水了#include <bits/stdc++.h>using namespace std;#define RE(x) freopen(x,"r",stdin)#define WR(x) freop
2017-01-26 08:29:47
2192
原创 101 Hack 44
A. Picking Numbers(水题)https://www.hackerrank.com/contests/101hack44/challenges/picking-numbers题目大意：给你个数组，问至多有几个数，其中两两相差不到1.题目分析：反正数组长度才100，O(n2)O(n^2)随便一搞即可。#include <bits/stdc++.h>using namespace std
2017-01-17 14:09:55
5921
原创 Week Of Code 27
这个比赛是编程马拉松风格的，参赛者需要在七天时间内完成七道题的挑战，每天解锁一题，难度递增。这次我做出来四道题，第五题Hard难度是一个超级大模拟，不爱写了A.Drawing Bookhttps://www.hackerrank.com/contests/w27/challenges/drawing-book题目大意：有一本书，有n页，第一页在右侧，你可以从头翻也可以从尾翻，一次翻一页，问你想看第p
2017-01-13 11:05:58
985
原创 hackerrank Hourrank16题解
hr上面有好多比赛，形式主要分为笔试型（1-2小时，3-5题）和编程马拉松型（3-7天，8题+）。hourrank就是一个不错的模拟企业笔试，要求1小时内完成3~4道算法题，目前已经举办了十几届。A.pile of candies(排序，水)https://www.hackerrank.com/contests/hourrank-16/challenges/pile-of-candies题目大意：有
2017-01-05 17:37:57
5238
原创 Equal （贪心，思维）
题目大意给你一个数组，每次操作是固定一个数，其他的数可以+1、+2、+5.问至少经过几次操作可以让整个数组的数字都一样？题目分析：其实这道题最难的点在问题的逆向转化：原操作变成全相等的次数等价于每次只变一个数，可以-1、-2、-5使得整个数组相等的次数。因为，新的操作与原操作相比，不改变数组元素的相对大小关系，只相当于在数轴上平移了1/2/5个单位。所以我们贪心的来做，首先，把一个数变小x需要的操作
2017-01-03 17:16:36
460
原创 两道二分图建模的题。感觉脑子已经被掏空
题目大意：定义螃蟹图是这样的无向图：有n+1个点，其中一个点(head)连接其他的n个点(foot)，另外n个点与head点相连。给你一个无向图和整数k，问其中至多有几个**不超过**k个feet的不相交的螃蟹图？题目分析：之前在hihocoder里面见过一个拆点构建网络流的题，这里又见到一道。不过还是没太挖掘出这类题目的共性。算法如下： 1. 把原图中每个点i拆成2i和2i+1两个点 2. 如
2017-01-02 18:14:41
648
原创 (HR2016.2.21 101 Hack 34) Minimum Penalty Path (状压dp）
https://www.hackerrank.com/challenges/beautiful-path题目大意：给你个无向图，N个点M个边，每条边有个权值c，一条路径的权值为边的权值的按位或。求点a到点b的路径中最短的权值是多少。题目分析：乍一看就是迪杰斯特拉算法，把加法变成或就OK了。但是那就错了。其实我也没举出什么好的反例，直觉上dijkstra是每次更新从集合出发距离最短的点，但相加值逐渐收
2016-12-28 11:45:16
632
原创 hr与lc的对比
hackerrank：优点： 1. 题目较多 分类明确 每道题都有难度分 2. 从main函数开始写 3. 有contest，一般是2h五道题，或者1h 两三道题 比较适合笔试风格 4. 错误点不给出用例，要用分数买，分数通过参加比赛和AC练习题获得 5. 除算法题外还有别的类型的练习题 缺点： 1. 因为是阿三的网站 出题人都是阿三 有时候里面的English表达有点奇怪 2. 传
2016-12-28 10:14:09
1203
原创 开源工程学习笔记之Fastjson（Part 1）
Part 1.反序列化部分还是从part0那个json串入手，看看Fastjson框架是怎么把他拆出来的。1.1 Fastjson中存取JSON对象的方法首先，Fastjson是用JSONObject和JSONArray这两个类分别描述json对象和json数组的。那么先把这两个类拆开来看看。1.1.1 JSONObject通过阅读json文档得知，一个object由若干个（可以是0个）键值对组成，
2016-12-08 16:36:42
8297
原创 开源工程学习笔记之Fastjson（Part 0）
Part 0.为啥要拆它？最近实验室任务量不大，故决定找一些不错的开源项目拆开看看，学习下设计模式和实现工程的细节。看一看一些优秀的工程都是怎么实现的。前几天刚帮同学拆了一个超轻量级的json框架cJSON，感觉不错，于是找了下Java的解决方案，比较有代表性的有谷歌的gson和阿里的fastjson。作为国人就先拆国产作品吧~~首先我们要知道这东西是什么，怎么用，再从入口点开始逐步剥皮。0.1 F
2016-12-08 13:51:11
732
原创 2016 acm/icpc 青岛站现场赛 3道题
5982.Relic Discovery(水题)http://acm.hdu.edu.cn/showproblem.php?pid=5982题目大意：输入2个数列a1...ana_1...a_n和b1...bnb_1...b_n,求a1b1+a2b2...+anbna_1b_1+a_2b_2...+a_nb_n题目分析：太水了，略。#include <bits/stdc++.h>using nam
2016-12-07 11:37:40
2108
转载 三国杀里面有哪些是和历史吻合的比较好的例子？
作者：史大哥 链接：https://www.zhihu.com/question/31556196/answer/52447849 来源：知乎 著作权归作者所有，转载请联系作者获得授权。1.曹丕小攻喜欢翻别人，曹植小受喜欢翻自己。 2.貂蝉离间必伤血啊，谁能斗过他老公啊 ？ 3.吴国太给自己女儿孙尚香换装备，嗯，一看就是亲生的。 4.曹丕你连曹仁这样的大叔都翻，你口味好重啊！ 5.刘备
2016-12-01 19:11:53
1254
原创 2016 acm/icpc 大连站现场赛（7道题）
5971.Wrestling Match(并查集，二分染色)http://acm.hdu.edu.cn/showproblem.php?pid=5971题目大意：（这道题的题意有点说的不太明白，我大体理解是这样的：）有n个玩家，m场比赛，其中有x个人是good，y个人是bad，每一场比赛都看做是一个good和一个bad的比赛，问是否所有人都能分成good和bad。题目分析：其实这题我一直有个疑问，就
2016-11-29 16:32:21
2904
原创 ccpc 2016 合肥站 （5道题）
5961.传递 (思维题)http://acm.hdu.edu.cn/showproblem.php?pid=5961题目大意：给你两个有向图，问你这两个图是否都是传递的。一个有向图是传递的，当且仅当图中任意三点a,b,c，若存在边a->b,b->c则必存在边a->c.题目分析：bfs图，若存在一个点的深度>=3，则不是。为什么呢？道理很简单，如果bfs序列中有c点的深度是3，设父亲是b，爷爷是a，
2016-11-25 16:36:11
738
转载 深度理解链式前向星
转自：http://blog.csdn.net/acdreamers/article/details/16902023我们首先来看一下什么是前向星.前向星是一种特殊的边集数组,我们把边集数组中的每一条边按照起点从小到大排序,如果起点相同就按照终点从小到大排序,并记录下以某个点为起点的所有边在数组中的起始位置和存储长度,那么前向星就构造好了.用len[i]来记录所有以i为起点的边在数组中的存储长
2016-11-24 13:16:35
500
原创 2016 acm/icpc 沈阳现场赛题解（5道题，更新ing）
5948.Thickest Burger(签到题)http://acm.hdu.edu.cn/showproblem.php?pid=5948题目大意：给你A和B，问2A+B和2B+A谁大？题目分析：略。#include <bits/stdc++.h>using namespace std;int T,a,b;int main() { scanf("%d",&T); while
2016-11-21 21:59:04
5306
原创 hdu5933-5942 ccpc杭州站题解（7道题）
5933.ArcSoft’s Office Rearrangement(签到题)http://acm.hdu.edu.cn/showproblem.php?pid=5933题目大意：Arcsoft公司有N个工作块排成一行，每个工作块里面有ai个人。现在要求把他们变成K个工作块，每个工作块里的人数相等，问至少操作几次？（如果不可能变成K个工作块，则输出-1）每次操作可以把一个工作块拆成两个，也可以把两
2016-11-17 15:39:01
2497
1
原创 2016 acm/icpc 青岛网络赛 题解（hdu 5878-5889，9道题）
5878.I Count Two Three传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5878题目大意：有一些数可以写成2a3b5c7d2^a3^b5^c7^d的形式，称之为”I count two three numbers”.输入一个数，问比他大的最小的”I count two three numbers”是什么？题目分析：打表预处理，发现1e9
2016-11-07 16:36:18
1920
原创 hdu5894 hannnnah_j’s Biological Test(2016 acm/icpc 沈阳网络赛，组合数学)
传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5894题目大意：有n张桌子围成一圈，坐m个人，任意相邻两人至少隔k个空位。 座位是各不相同的，m个人是相同的，问有多少种组合方法？题目分析：设第一个人和第二个人隔了a1a_1个空位，第三个人和第二个人隔了a2a_2个空位…………第m个人和第一个人隔了ama_m个空位，则有： a1+a2+...+am+m
2016-11-04 10:11:22
637
原创 hdu 5899 oasis in desert（acm/icpc 沈阳赛区网络赛，Floyd+二分图判定+最大匹配，好难啊）
传送门： http://acm.hdu.edu.cn/showproblem.php?pid=5899题目大意：沙漠中有N个绿洲，由M条路相连，每条路的长度为L。定义两个集合： （1）最大危险集：对于集合中任意两点，其最小距离大于k，满足此条件的集合有多个，取最大的那个。 （2）最小安全集：对于图中任意两点，只要他俩的距离≤k，那么最小安全集中至少包含这两个点中的一个。满足条件的集合有多个，取最
2016-11-01 14:14:22
1304
原创 hdu 5898 odd even number（acm/icpc沈阳赛区网络赛，数位DP）
传送门： http://acm.hdu.edu.cn/showproblem.php?pid=5898题目大意: 定义odd-even-number是一个数，其中连续奇数位的长度是偶数，连续偶数位的长度是奇数。 问[L,R]里有几个odd-even number?题目分析: 其实呢我知道数位DP是干什么用的，但是没见过相关的题，所以即使一眼就看出用数位dp做，但却看了一天题解才弄懂这道题。其实
2016-10-31 16:35:58
944
原创 hdu 5900 QSC and Master（acm/icpc沈阳网络赛，区间DP）
传送门： http://acm.hdu.edu.cn/showproblem.php?pid=5900题目大意： 给你一个数组，数组的每个元素是一个二元组，用<Key,Value>表示，你每次可以消掉相邻的两个数对，要求他们的key是互质的，你的得分是它们的value，消掉之后后面的会并过来，问你最多可以得到多少分?题目分析： 首先看到“最多”字样，八成又是dp或者贪心。。。这道题如果只考虑前i
2016-10-31 15:46:20
394
原创 Java并发学习笔记（1）——并发编程基础
线程的状态NEW：初始状态，线程被new 出来，但还没start()的状态 RUNNABLE：指的是调用了start()方法，但还在等着CPU资源的状态； RUNNING：一个线程获得了CPU资源，正在走的状态； TERMINATED：线程对象的run()方法走完了的状态 BLOCKED：线程被阻塞，即该线程把CPU资源让出来，等待其他操作再回来请求CPU的状态、2.线程通信：volati
2016-10-28 15:16:12
419
原创 hdu 5914 Triangle 2016中国大学生程序设计竞赛（长春）（脑洞题）
传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5914题意： 给你n根棍，长度分别为1~n，至少删掉几根棍使得剩下的棍子里任意三根拼不成三角形？分析： 初中时老师大大已经教过我们，三根棍，哦不，三个数能组成三角形的充要条件是最小的两边之和大于第三边。 啊啊啊，那怎么用到这道题里呢？既然任意三个数拼不成三角形，还要尽可能多的数，那就考虑下临界情况，也
2016-10-26 16:01:13
492
原创 hdu 5912 Fraction 2016中国大学生程序设计竞赛（长春） 水题
传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5912 题意：输入a1…an,b1…bn，化简这个东西 分析： n不超过8，an,bn不超过10，所以暴力搞搞就好啦~~~ 注意有可能爆int滴~每轮的迭代过程就这样：从an开始，取倒数，乘bn，加an-1，再取倒数……迭代n轮之后除以最大公约数化简。#include <bits/stdc++.h>
2016-10-26 14:38:43
620
原创 hdu 5929 Basic Data Structure 2016CCPC东北地区大学生程序设计竞赛
http://acm.hdu.edu.cn/showproblem.php?pid=5929题目大意：模拟一个栈，有四种操作： PUSH x：往栈里压入x POP：丢掉栈顶元素 REVERSE：把栈翻转过来 QUERY：从栈顶到栈底求nand(与非)其中0 nand 0=1,1 nand 0=1,0 nand 1=1,1 nand 1=0. 输出每次的query结果，如果栈是空的输出Inv
2016-10-24 15:56:04
510
原创 hdu 5927 Auxiliary Set 2016CCPC东北地区大学生程序设计竞赛 - 重现赛 F题（树状dp）
传送门： http://acm.hdu.edu.cn/showproblem.php?pid=5927题目大意： 有一个树，以1为根。其中某些点为重要点。 定义“重要点集”为符合如下条件的点：（1）重要点，（2）两个重要点的最近公共祖先。给出q次询问，每次询问给出非重要点的序号，求“重要点集”中有几个点。题目分析： 刚拿到这题的时候的dp思路有点问题，是进行了两次dfs，这样的时间复杂度就达到
2016-10-24 15:19:11
353
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人