- 博客(33)
- 收藏
- 关注
RSS订阅
原创 我的ACM模板整理
动态规划DP最长不下降子序列#include<iostream> using namespace std;#define MAXN 10000int main(){ int n; int a[MAXN]; cin>>n; for(int i=1;i<=n;i++) scanf("%d",&a[i]); int now=1,ans=1;...
2020-03-18 22:07:54
598
2
原创 Codeforces Round #679 (Div. 2) C.Perform Easily 有两种不同方法的题解
题目地址http://codeforces.com/contest/1435/problem/C大致题意有一个长度为6的数组a，代表每根弦的初始值。有另外一个数组b，代表需要弹奏的每个音符。每根琴弦的琴格从1开始。（在弹吉他里应该叫x品吧）如果我要弹音符b_i,找到x满足b_i=x+a_j则可以按琴弦j的琴格x来弹出这个音。（j弦x品）问怎么弹所有音符可以让最大的x和最小的x之间的差值最少？题目思路方法1：二分方法来自大佬的博客：https://www.cnblogs.com/accep
2020-10-28 20:38:38
247
原创 Codeforces Grakn Forces 2020 题解(CDE)
C.Discrete Acceleration发现自己傻了，这题明明可以直接O(n)模拟，我却写了个二分，但其实我的这个二分还是O(n)的复杂度，因为之前O(n)处理了左右端点到每个点的时间。我的傻逼写法：#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<vector>#include<map>#include&
2020-10-04 20:11:05
194
原创 莫队算法学习笔记
看了AgOH大佬的视频https://www.bilibili.com/video/BV1C4411u7rK?from=search&seid=5854182600235483127然后写了视频里的洛谷板子题洛谷P2709 小B的询问https://www.luogu.com.cn/problem/P2709#include<iostream>#include<algorithm>#include<cmath>#include<cstring&
2020-09-30 21:32:29
131
原创 Codeforces Round #674 (Div. 3) F. Number of Subsequences (DP)题解
题目链接：http://codeforces.com/contest/1426/problem/F题目大意 ：给一串包含abc和?的字符串，？表示这里可以随便选。如果给你ac?b?c那么就会有[“acabac”, “acabbc”, “acabcc”, “acbbac”, “acbbbc”, “acbbcc”, “accbac”, “accbbc”, “accbcc”]问这些字符串中有几个abc子序列。题解不考虑？的情况下，建一个二维数组dp[MAXN][3]；分别记录子串“1”，“12”
2020-09-30 19:27:48
150
原创 HDOJ 6869 Slime and Stones(杭电多校2020第九场1003)(威佐夫博弈+二分)可能是比较无脑的做法
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6869题意：给a和b两堆石头和一个k，每次可以进行如下两种操作的其中之一1.在其中一堆中取任意数量个石头2.在一堆取x个，另一堆取y个，但是限制|x-y|<=k普通的威佐夫：（会的直接跳到题解部分就行了）普通的威佐夫博弈就是这个问题的简化版，即k=0的情况参考了这篇帖子：https://blog.csdn.net/NIV__/article/details/54587849定义奇异局势(必败
2020-08-19 15:32:27
433
原创 洛谷P3370 【模板】字符串哈希 题解（写了一个双哈希）
https://www.luogu.com.cn/problem/P3370看了一下这题的题解，发现好像直接用单哈希就可以写。。对每个字符串计算两个字符串哈希值，分别取不同的模数，做一对pair分别储存对两个模数的哈希值。之后只需要对这些pair进行排序，找有多少个不同的就可以了。#include<iostream>#include<algorithm> using namespace std;int cansel_sync=(ios::sync_with_stdio(
2020-08-17 17:52:19
366
原创 HDOJ 6798 Triangle Collision(杭电多校2020第三场1008)(二分)题解
http://acm.hdu.edu.cn/showproblem.php?pid=6798思路：画出等边三角形相接的网格。这条直线和网格的交点即在三角形中的每一次碰撞。从(x,y)出发的朝(vx,vy)方向的射线与网格交k次之后得到的长度即碰撞k次经过的总长。转化为射线与网格相交的问题。二分查找需要的结果t。每次将整个三角形、点、速度方向一起绕三角形中心旋转0度，120度，240度，每次旋转的时候只计算和底边（即网格中与x轴平行的边）加起来就是射线和网格的所有交点数量。看大于k还是小于k。代
2020-07-29 15:24:34
291
原创 HDOJ 6795 Little W and Contest(杭电多校2020第三场1005)(并查集) 一种比较无脑的做法
http://acm.hdu.edu.cn/showproblem.php?pid=6795思路：tot2和tot1记录所有人中有多少个1多少个2cnt1[x]和cnt2[x]记录以x为老大的这组人中有多少个1多少个2。先算出初始状态下所有人互不相认的种数：(tot2*(tot2-1)/2tot1选两个2，选一个1的情况tot2(tot2-1)*(tot2-2)/2/3) 选三个2的情况每次并查集进行合并的时候，计算出此时减少的种数：假如是对把y组并入x组合并前做的到而合并后做不到的组队方
2020-07-29 11:42:33
104
原创 HDOJ 6768 The Oculus (哈希) (杭电多校2020第二场1006) 题解
http://acm.hdu.edu.cn/showproblem.php?pid=6768思路：因为数据的范围1≤∣A∣,∣B∣≤1000000.1≤|A|,|B|≤1000000.1≤∣A∣,∣B∣≤1000000.2≤∣C∣≤∣A∣+∣B∣+1.2≤|C|≤|A|+|B|+1.2≤∣C∣≤∣A∣+∣B∣+1.∑∣A∣,∑∣B∣≤5000000.∑|A|,∑|B|≤5000000.∑∣A∣,∑∣B∣≤5000000.给的有点大，所以我们找一个模数,这个数应该满足，在fb(1)到f
2020-07-24 19:46:37
215
1
原创 HDOJ 6772 Lead of Wisdom (dfs) (杭电多校2020第二场1010) 题解
http://acm.hdu.edu.cn/showproblem.php?pid=6772题意：给n个装备，分别具有abcd四个属性装备一共有k种类型，每个类型只能选一个。求DMG=(100+∑i∈Sai)(100+∑i∈Sbi)(100+∑i∈Sci)(100+∑i∈Sdi) DMG=(100+∑i∈Sai)(100+∑i∈Sbi)(100+∑i∈Sci)(100+∑i∈Sdi) DMG=(100+∑i∈Sai)(100+∑i∈Sbi)(100+∑i∈Sci)(100+∑i∈Sdi)的最大
2020-07-24 16:59:47
204
原创 2020牛客暑期多校训练营（第三场）C.Operation Love(计算几何) 题解
题意：按顺时针或逆时针的顺序给出这样一只手上所有的点坐标给出的图形在大小长度上都是一样的，只是可能经过了旋转。要求判断是左手还是右手思路：找到最长的一条边a（长度为9）然后再找到一条长度为8的边b，两个向量做叉乘,如果bxa>0则为右手，否则为左手。代码：#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<vector&
2020-07-19 15:52:35
175
原创 2020牛客暑期多校训练营（第三场）A.Clam and Fish(贪心) 题解
大致题意：00型:这个阶段没有鱼和蛤蜊。类型11:这个阶段没有鱼，只有一只蛤蜊。22型:只有一条鱼，这个阶段没有蛤蜊。类型33:在这个阶段有一条鱼和一个蛤蜊。#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<vector>#include<map>#include<queue>#include&
2020-07-19 12:51:00
189
原创 2020牛客暑期多校训练营（第三场）F.Fraction Construction Problem(扩展欧几里得) 一个详细的题解
题目大意：给两个正整数a和b；要求找到四个正整数c,d,e,f，满足ab=cd+ef\frac{a}{b}=\frac{c}{d}+\frac{e}{f}ba=dc+fe#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<vector>#include<map>#include<queue>#i
2020-07-19 00:10:11
1939
2
原创 洛谷P4145 上帝造题的七分钟2 / 花神游历各国[ (线段树) 或 (树状数组+并查集) ]题解
题目：线段树思路：我是通过线段树来写的。通过线段树维护两个值：区间最大值maxx和区间和sum那么，该如何实现区间开方这个操作呢？答案是直接单点修改。听起来有点不可思议，但是这种方法的可行的原因，是因为数据范围中，10e12的数字，最多经过6次的开方，就能到1。又因为对于数字1，有sqrt(1)==1，所以对于到达1的数字，我们在区间修改中便可以跳过，只去修改其他的数字，根据这个结论，我们最坏的情况也只需要进行6*n次的修改。那么，我们怎么跳过全部为1的区间？通过维护区间最大值线段树，如果这
2020-07-16 19:28:52
171
原创 洛谷验板子 P1886 滑动窗口 /【模板】单调队列
关于单调队列，我是从这个帖子里学习的思路。https://blog.csdn.net/ljd201724114126/article/details/80663855题干：我是用deque来实现单调队列的。维护两个双端队列dq_max和dq_min#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<vector>#incl
2020-07-14 14:22:48
192
原创 洛谷验板子 P3384 【模板】轻重链剖分
今天有点好运，学了树剖之后敲的板子居然没出问题直接ac了OWO1.子树的维护和查询与最普通的树链剖分不同的是，需要子树的和。因为一颗子树的所有点在树剖序上面也是连续的一段区间，所以我们一样可以通过线段树来维护它。但是这边怎么找到线段树上的l和r？如果我们要查询以x为根节点的子树的和，只需要找dfn[x]—x点的树剖序下标到dfn[x]+si[x]-1这段区间上的和即可。(si[x]是以x为根子树的大小size代码：#include<iostream>#include<alg
2020-07-11 17:03:41
221
原创 Codeforces Round #639 (Div. 2) C. Hilbert's Hotel题解
(这题一开始是真的读不懂这题的题意大致就是:希尔伯特旅馆内本来已经放满了人，我们输入一个数组，按照这个数组的规则给整个旅馆洗牌。即对负无穷到正无穷的每一个数x，都把它移动到x+a~x mod n~这个新的位置问在经过这样一系列操作之后，整个旅馆是否还是一个人占用一个房间?思路:旅馆里的所有人是以n为周期地进行处理的。比如cf给的第一个样例"1 14"就是以1为周期的x+k*1(x∈[0,1))都往后移动14个，显然这样仍然能够满足"每个人占用一个房间且没有空房间"其实如果n=4，那我们只需要让
2020-05-09 10:50:10
228
原创 HDOJ 2874 Connections between cities (LCM)
我是用LCM的方法来做的。即通过倍增法找到两个点的最小公共祖先。在维护p数组的同时，一边维护一个记录边长的数组w#include<iostream>#include<algorithm>#include<cstring>#include<cstdio>#include<vector>#include<queue>...
2020-05-04 15:32:54
132
原创 Codeforces Round #635 (Div. 2) D. Xenia and Colorful Gems (贪心) 题解
题目地址：http://codeforces.com/contest/1337/problem/D思路：1.先把三个数组按从小到大排序2.用pr,pg,pb分别指向红色绿色蓝色数组的位置3.每次假设把三个指针分别往后移动一位，执行结果最小的那次移动，这样循环直到三个指针都到了最后的位置#include<iostream>#include<cstring>#in...
2020-04-30 16:43:35
124
原创 《Computer Architecture:A Quantitative Approach》读书笔记
第一章 - 计算机设计的基本原理简介部分告诉我们，本书的主要内容是线程级并行（TLP）或者数据级并行（DLP）。计算机可以大致分类为嵌入式计算机，桌面计算机。嵌入式应用的性能具有实时性，即每个程序段有一个确定的最大执行时间，并且还具有最小化储存器需求和最小化功耗需求的特性。=============================================指令集系统结构（ISA，in...
2020-04-28 01:45:04
4696
2
原创 Codeforces Round #633 (Div. 2)D. Edge Weight Assignment(树，DFS) 超详细题解
题意：给定一颗树，可以往树上的每条边添加一个权值(这个权值可以非常非常大，不限范围)，使得任意两个叶子节点之间的连线上的所有边权异或得到的结果都为0.问这棵树上最少出现多少种不同的边权，最多出现多少种不同的边权思路：最小解是好找的，先说结论，如果这张图上存在任意两个叶子的路径长度为奇数(因为题干给定n>=3因此不去考虑n=2仅存在一条边的情况)，则这张图的边权不能只通过一个数来实现。...
2020-04-13 15:37:28
270
原创 Codeforces Round #632 (Div. 2) D. Challenges in school №41(排序、贪心) 题解
题意：L表示向左看的人，R表示向右看的人，需要执行一定操作，使得没有面对面看着对方的人。如果有一对LR面对面站在一起，则可以花费一秒钟的时间让他们都转头变成RL。可以同时进行转头，比如RLRL可以经过一秒变成LRLR，但是从LRLR到LLRR需要额外再花费一秒。题目给定n个人和k秒，要求输出正好k秒完成的转头方式。思路：1.冒泡其实是类似冒泡排序的思路，当整条队列呈现LLLLLRRRRR...
2020-04-10 02:36:15
166
原创 Codeforces Global Round 6 D.Decreasing Debts(图,思维)超详细题解 和样例答案一模一样的写法
写出来之后和样例居然一摸一样，，我也是惊了思路：先说结论，最后剩下来的所有债务就是所有点的入度之和或者出度之和。为什么呢？题目给了两种化简方式：即：1.d(a,b)>0和d(c,d)>0的情况下，可以让d(a,b)和d(c,d)共同减去z，再给d(a,d)和d(c,b)共同加上z;2.如果d(a,a)这样出入两点都是自己的情况下，则这个可以直接消去先从样例给的这种情况...
2020-04-07 19:26:48
162
原创 算法导论学习笔记-动态规划-15.1 钢条切割
简介动态规划方法通常求解最优化问题，这类问题有很多可行的解，所以我们希望找到的是一个最优值，我们称这样的情况为一个最优解(an optimal solution)，而不是最优解(the optimal solution),因为这个问题可能有多个解都能达到最大值。一般按下面四个步骤来求解：1.刻画一个最优解的结构特征。2.递归地定义最优解的值。3.计算最优解的值，通常采用自底向上的方法。...
2020-03-12 16:58:26
271
原创 Codeforces CodeCraft-20 (Div. 2) D. Nash Matrix (DFS)
思路：1.用Node a[1010][1010]存储每个点的目标点坐标(tx,ty)2.用s[1010][1010]来存储地图，一开始全部标0。3.在读入Node a[1010][1010]的时候，找到那些目标点是自己的点，在s上标记为‘X’4.找到X的点，从X出发开始DFS，通过for循环枚举dir移动方向。【这里其实有一个小技巧，就是当目标点只有一个，而出发点有多个的情况下，从出发点...
2020-03-06 01:54:20
110
原创 Codeforces Ozon Tech Challenge 2020 C.Kuroni and Impossible Calculation 的两种方法
这里介绍两种方法：一、分m个桶，cnt[i]储存a[x]%m的数量，再用v[i]储存a[x]的原值。当n个数字都按照这样读入完毕之后，for循环遍历一遍cnt数组一旦∀ i∈[0,m] 使得 cnt[i]>1,则说明有至少两个数字ax,y%m=i，ax%m=i，ay%m=i；根据取模运算的规律，可得|ax-ay|%m=0,这样只需要扫过一次cnt数组，如果有cnt[i]>1...
2020-03-04 20:15:42
156
原创 Codeforces Round #625 (Div.2) C.Remove Adjacent(贪心)
思路：1.从大到小枚举字母c；2.从字符串string的开头访问到结尾，如果有删去字符，则需要从string开头重新开始访问(比如test10里面的“bbbbbbbbabbbb”这种情况)3.如果把字符串访问一便以后没有删去任何一个字符，则flag=0；退出while循环，继续枚举下一个字母c-1。==============================================...
2020-03-03 02:56:11
178
原创 算法导论学习笔记-基础图算法
一、图的表示两种形式：[1]邻接表：struct Edge{ int from,to,cap,flow;//以最大流问题的数据结构为例 //from起点u；to终点v；}vector<Edge>edges;//保存每条边的信息并编号int n,m;//n记录点数V，m记录边数量Evector<int> G[MAXN];//G[u][v]存放从u出发到v的边...
2020-03-03 01:55:27
170
原创 POJ 1990 MooFest(树状数组) [带详细注解
分析：1.先用结构体读入所有的牛的位置x和音量阈值v。2.根据音量阈值v升序排序，只要按照这个顺序处理牛，就可以省去牛之间两两比较阈值v大小的过程。（因为当前的第i只牛比之前的i-1头牛的阈值v都大）3.用两个数组，数组c记录当前位置x前面的牛的个数；数组s记录当前位置x前面的牛的坐标总和。4.挨个读入牛，把第i头牛（当前这头）之前的i-1头牛，根据位置在第i头牛的前面还是后面分成两组处理...
2020-02-22 16:03:04
128
原创 HDOJ 1507(二分匹配) Uncle Tom's Inherited Land
http://acm.hdu.edu.cn/showproblem.php?pid=1507思路如下：1.读入池塘点，用mapp数组记录（0为空地，1为池塘）2.当读入结束后，遍历所有的点，若为空地，则根据奇偶性将这些空地分别放入结构体数组ji和ou之中。（并用nj和no记录奇、偶点的数量），因为题干说了空地的数量小于等于50，所以数组不用开太大。3.双层循环，枚举奇数偶数点，判断奇数点i...
2020-02-18 17:08:37
152
原创 Codeforces Round #609 (Div. 2) D.Domino for Young
1.大致题意：给一个数字代表空位的列数再从从左往右输入每列的高度。如果骨牌的大小是1x2可以横着放也可以竖着放，给出最大可放置的骨牌数量。2.思路通过染色黑白相间地标出黑格和白格。然后这时候数黑白格子地数量，少一点的就是可以放置的骨牌数量即cout<<min(black,white);代码实现：#include<iostream>#include<...
2019-12-24 14:23:34
341
原创 Codeforces Round #609 (Div. 2) A,B,C题详细题解
这次CF感觉是一个上分特别好的机会，可惜我英语太屎了，看不懂AB两题。。最后只AC了C题居然也能上分，一 题 涨 分 传 说。A题：Equation1.大概题意：输入一个n，输出两个合数a,b使得a-b=n；2.思路：签到题，题目保证ab一定是存在的，而且只需要输出其中的一个特解即可。可以知道如果n是偶数或者0（即mod2后余数为0），那么它加上4之后一定是一个合数，同理如果n...
2019-12-22 21:17:43
210
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人