- 博客(873)
- 收藏
- 关注
RSS订阅
原创 常用ACM知识点清单（未完待续）
文章目录图论动态规划数论组合数学计算几何数据结构字符串其它图论拓扑排序强联通分量Tarjan算法双连通分量强连通分支及其缩点图的割边和割点最小割模型、网络流规约2-SAT问题欧拉回路哈密顿回路最小生成树：prim，Kruskal，次小，k小 最优比例生成树 最小树形图 最小度限制生成树 平面点的欧几里德最小生成树 平面点的曼哈顿最小生成树 最小平衡生成树最短路 dijkstra floyd spfa 次短路径 第k短路径 差分约束系统最大流
2020-07-21 18:24:23
3659
2
原创 2023CSPJ 旅游巴士 —— dijkstra
应当是一条最短路，在思考每条边的限定时间的时候会发现，假设这条边从a到b，边权为c。那么如果在d(d<c)的时刻到达a时，通不过，所以我们要么延迟k的倍数次从起点开始，使得到达a的时候是d+nk时刻,并且满足d+nk>=a且最小，要么就是绕个路再回到a点。你可以在k的倍数的时间点在起点开始，每条边的边长为1，同时，每条边有一个限定时间ai，表示你必须在大于等于ai的时间点才能走这条边。=d+nk，那么我思考至此发现，其实到达a的时候，总共只有k种情况，也就是：到达a位置的步长%k的不同情况。
2023-10-23 19:14:22
1087
原创 Poj2362 Square ——搜索+剪枝
首先是四条边我们只需要搜三条即可。那么我们想让搜的数量尽可能小的话，需要将值从大到小排序，这样如果第一条边需要的长度>1的时候，第四条边需要的长度>=2.并且如果有一个样例会让排序后第四条边的长度数量尽可能少的话，那么这个答案我们会在搜到中间的时候搜出来，而不会拖到最后。我们的思路是一条边一条边去组成，先搜第一条边，用过的长度标记一下，在回溯的时候给撤销。然后从大到小排序的另一个好处就是，对于当前这条边的组成的长度，前面搜过的就不会再搜了，我用了一个sta在参数里面就表示下一次枚举长度的时候从哪里开始。
2023-02-03 19:33:55
194
1
原创 洛谷P1028 [NOIP2001 普及组] 数的计算 —— 简单DP+双指针优化
从前往后也可以，我这里用的是从后往前的，也就是从小的数开始每次加变大的。我们知道每次至少*2，所以最多也就增大10次。那么dp[i][j]表示到了第i个数，值为j的情况数。它可以从dp[i-1][1:j/2]转移过来。我们从小往大枚举j的话，就可以用一个sum维护i-1位置上，值≤j/2的所有情况和。在搜索不确定时间复杂度的情况下，尽量避开。请你求出，一共有多少个合法的数列。不同当且仅当两数列长度不同或存在一个正整数。
2023-02-02 21:17:40
180
原创 洛谷P2089 烤鸡 —— 深搜
猪猪 Hanke 特别喜欢吃烤鸡（本是同畜牲，相煎何太急！）Hanke 吃鸡很特别，为什么特别呢？因为他有 10 种配料（芥末、孜然等），每种配料可以放 1到 3克，任意烤鸡的美味程度为所有配料质量之和。首先是模板搜索题，考虑简单的剪枝：假设后面未放的位置全是1，那么当前位置最大可以取到多少。假设后面未放的位置全是3，那么当前位置最小可以取到多少。同时对1和3取最大最小值即可。现在， Hanke 想要知道，如果给你一个美味程度 n ，请输出这 10 种配料的所有搭配方案。
2023-02-02 20:45:05
156
原创 Codeforces 1644 C. Increase Subarray Sums —— 二维DP
This way题意：给你一个长度为n的整型数组a，和一个整型x。你可以在数组a中的任意多个位置加x，然后取出a中的连续一段使得数值总和最大，问你位置数从0~n答案一次是多少？题解：又咕了一段时间…真舒服啊（不是）首先看到5e3当然想的就是暴力，但是发现暴力的话，要找左右端点，然后又要考虑数量，很容易就上N3N^3N3，然后不知道为什么就想到了DP。那么dp[i][j]表示位置i作为取的末尾，j个位置加x的时候的答案是多少。那么状态转移方程就是：dp[i][j]=max(dp[i-1][j]
2022-04-24 10:25:19
279
原创 Codeforces 1635 F. Closest Pair —— 树状数组，思维，有一丶丶东西
This way题意：给你长度为n的数组x（x[i]<x[i+1]）和w，对于一对i,j，定义他们的val为∣xi−xj∣∗(wi+wj)|x_i-x_j|*(w_i+w_j)∣xi−xj∣∗(wi+wj)。每次给你l,r，问你[l,r]中val最小为多少题解：第一次挑战28的题目，说实话还是不够难，感觉只有25左右难度。一开始我想到的是笛卡尔树，但是不太对劲，因为它并不是区间这种东西。接下来我想到的是斜率优化，然后我就开始写式子…然后就写不下去了。由于点i一定会找w比它小的
2022-03-10 10:05:21
1300
原创 Codeforces 1635 E. Cars —— 黑白染色+拓扑排序
This way题意：现在有n辆车在x轴上，每辆车都在不同的点，并且有一个朝向（左或右），它们会往朝向开。它们之间有这样的关系：1 x y表示x和y无论怎么样的速度往前开都不会相遇2 x y表示x和y无论怎样的速度往前开都会相遇问你这些车的可能起始位置和朝向题解对于1的情况，x和y是相反方向，且在左边的往左，在右边的往右。对于2的情况，x和y也是相反方向，且在左边的往右，在右边的往左。那么如果两个车有1或者2的关系，它们的方向就是相反的。那我们随便假设某个车的朝向，然后再对与它在一个连
2022-03-04 14:56:11
362
原创 Codeforces 1635 D. Infinite Set —— DP，斐波那契数列应用
This way题意：给你长度为n的数组a，然后构造一个集合，这个集合中的数存在这样的规律：x=ai for some 1≤i≤n.x=2y+1 and y is in S.x=4y and y is in S.并且x<=2p2^p2p，问你最终集合里有多少个数。题解：那么对于某个a[i]，在二进制下的情况来看，它到集合里的数可能是：a[i]a[i]1a[i]00a[i]100a[i]001…可以看得出来，每次要么最后加了1，要么最后加了两个0.dp[i]=dp[i-
2022-03-03 18:59:56
506
原创 Codeforces 1635 C. Differential Sorting —— emmm..
This way题意：给你一个长度为n的数组a，你每次可以选择三个位置x,y,z并且x<y<z。然后将a[x]=a[y]-a[z]你要在n步之内将这个数组变成非降序，问你最终的数组长成什么样。题解：非降序？而且x<y<z?那岂不是异常简单首先非降序的情况直接输出。然后对于最后两个位置，一定要是非降序的。接下来我们对于前面的n-2个数，不是只需要=a[n-1]-a[n]即可吗？#include<bits/stdc++.h>using namesp
2022-03-03 11:01:06
459
原创 Codeforces 1635 B. Avoid Local Maximums ——贪心
This way题意：给你一个长度为n的数组a，你可以改变某些位置的值，使得最终的数组没有峰。问你最少要改变的数量和最终的数组。题解：观察样例就可以知道，如果两个峰间隔只有一位的话，那么就可以使中间的这个值等于它们中的最大值，这样同时就可以消掉两个峰。#include<bits/stdc++.h>using namespace std;const int N=2e5+5;int a[N],top[N];int main(){ int t; scanf("%
2022-03-02 15:01:20
215
原创 Codeforces 1635 A. Min Or Sum —— 简单思维
This way题意：给你一个长度为n的数组a，你每次可以选择i,j两个位置，将a[i],a[j]变成x,y，要求满足x|y=a[i]|a[j]。问你最终要使得数组和最小是多少。题解：一眼看过去就知道是所有数的或之和因为我们要使得x|y=a[i]|a[j]且要x+y最小。那么我们就可以把二进制上重复的位消掉。如此反复，最终留下来的就是所有存在于数组a中的二进制位之和。#include<bits/stdc++.h>using namespace std;int main()
2022-03-02 14:48:05
569
原创 Codeforces 1638 E. Colorful Operations —— 线段树+暴力，有丶东西
This way题意：给你一个长度为n的数组a，一开始所有位置的颜色都为1，值都为0.每次有三种操作：Color l r x:把[l,r]中的所有位置颜色变成xAdd c:把颜色为c的所有位置的值加上cQuery i:问i位置的值是多少。题解：这个感觉还是有点绕的，我也是想了比较长的一段时间。最后在通过某位大佬的代码证实了我的想法之后才敲的，要不然我敲崩了又没有借鉴可以参考，非常难受。首先这种区间变换的题目，很容易就能想到是区间修改，但是有的时候也不一定，所以我在决定做法的时候还是犹豫了一
2022-03-02 10:54:30
517
原创 Codeforces 1638 D. Big Brush —— BFS
This way题意：给你个n*m的矩阵，你每次可以在矩阵内的某个2*2子矩阵写上某个相同的数，问你经过怎么样的操作得到最终的矩阵。题解：一眼就看出来是BFS，这种题目一般来说都是倒着找，首先找到某个完整的2*2子矩阵，然后消去它的影响，再检查它周围的这一圈是否有消去影响之后可能可以涂的，然后依次去做。#include<bits/stdc++.h>using namespace std;const int N=1e3+5;int a[N][N];int same(int x
2022-02-27 20:05:04
210
原创 Cdeforces 1638 C. Inversion Graph —— 简单思维
This way题意：给你一个长度为n的排列，i和j之间可以连边当且仅当i>j && p[i]<p[j]。问你这里有多少个连通块。题解：第一眼就是并查集，但是并不需要，不如说写了并查集反而比较笨。对于任意一道题目充分理解它，利用好其中的条件，这道题它既然是排列了，也就是说如果i不在前i个位置，那么它必然能够与前面相连。那么连到哪里呢？设mx是前mx个位置的p的最大值，如果mx在前面没有出现过，那么就不会新增一个连通块。否则就会新增一个连通块，就比如2 3 1 5
2022-02-27 19:07:12
234
原创 Codeforces 1638 B. Odd Swap Sort —— 树状数组，no，简单思维.
This way题意：给你一个长度为n的数组a，如果a[i]+a[i+1]是奇数，那么你可以交换a[i]和a[i+1]，问你是否最终能让数组a非降。题解：中午没睡…下午昏昏沉沉的，思路不清晰。我的想法是，先从小到大排序，每一个数都要到达排序好的位置，自然要让跟后面的比他小的所有数交换位置。因此就看每个数后面所有小于它的数是否与它同奇或者同偶。我的方法是，到了当前位置，查看这个位置上所有与它同级或者同偶的小于它的数是否被取完了。当然我这里就非常愚蠢了，为什么要看是否取完了呢？你直接看奇数序列和
2022-02-27 18:45:36
495
原创 Codeforces 1638 A. Reverse —— 简单思维
This way题意：给你一个排列，你可以将其中[l,r]区间翻转，问你字典序最小的答案是多少。题解：一开始没有看到排列这个信息，所以写着写着感觉不太对劲啊，不像是A题的难度，于是重新看了一遍题意。不过去掉排列这个点，倒是可以再出一道题目。那么我们肯定是贪心地找最小的值，然后翻转，但是这个最小值它指的不一定是1，比如第三个样例，它翻转的就是2，那我们要找的最小是不在1,2,3,4这种递增当中的最小即可。#include<bits/stdc++.h>using namespac
2022-02-27 14:46:25
228
原创 Codeforces 1637 F. Towers —— 思维，dfs
This way题意：给你一棵树，每个点都有一个值a[i]。你要在一些点上放值b[i]，使得对于任意一个点x，都有两个点u,v：x在u,v的路径上且min(b[u],b[v])>=a[x]。问你最少的b之和是多少。题解：我把ne写成了x，找了半个小时的bug。我们只需要将a最大的点当成根rt，然后对于任意一个x(x!=rt)，只需要它的子树中有一个b>=a[x]即可。因为在最后我们需要两个点的值>=a[rt]，那么对于任意一个x(x!=rt)来说，必然至少有一个点不在它的子
2022-02-26 21:28:34
191
原创 Codeforces 1637 E. Best Pair —— 思维
This way题意：给你n个数，cnt[i]表示i出现的次数。求出最大的(x+y)*(cnt[x]+cnt[y])x不等于y并且给你一些不能取的对数。题解：一开始想的是那种随着值增大出现次数单调递减的二分。但是这种不能取的情况一旦出现就导致可能不是最优的，那么二分怎么做我一下子就想不出来了。值想不出来换个思路，通过出现次数枚举，我们会发现不同种类的出现次数最多只有O(n)O(\sqrt{n})O(n)次。最坏情况应该是这样：出现1次的有1个，2次的有1个，3次的有1个…那情况数为(1+
2022-02-23 20:21:02
220
原创 codeblocks安装后出现问题的可能解决办法
昨天在写cf的时候遇到了一个问题，因为办公室这台电脑我是刚用，没有装过codeblocks之前。在用到花括号构造的时候报错，如图：不能直接用花括号了，这我能忍？按照以往的经验来说，是compiler出现了问题，于是设置了一下：看起来好像对了吧？运行一下还是错误。虽然强制转换类型能用，但是我接受不了不能直接使用花括号。于是去官网上重新下了20版的，依旧出现问题，问了问以前集训队的队友，他好像也不知道，于是我就要了他的安装包。安装之后还是不能用，猜测可能是我前面装的codeblocks没删除干净
2022-02-23 09:17:02
2790
2
原创 Codeforces 1637 D. Yet Another Minimization Problem —— 数学，dp
This way题意：给你一个长度为n的a数组和b数组，你每次可以选择一个位置i，交换a[i]，b[i]。最终要使得∑i=1n∑j=i+1n(a[i]+a[j])2+∑i=1n∑j=i+1n(b[i]+b[j])2\sum\limits_{i=1}^{n}\sum\limits_{j=i+1}^{n}(a[i]+a[j])^2+\sum\limits_{i=1}^{n}\sum\limits_{j=i+1}^{n}(b[i]+b[j])^2i=1∑nj=i+1∑n(a[i]+a[j])2+i=1∑n
2022-02-22 08:44:43
497
原创 Codeforces 1637 C. Andrew and Stones —— 简单思维
This way题意：给你n个石子堆，你每次可以选三个位置i,j,k(i<j<k)。并且当前j至少要有两个石子。将j中的一个石子放到i，一个石子放到j。问你最终想要所有石子都在位置1或者n上，问能否完成，步数最少是多少。题解：分类讨论，我们可以看出[2,n-1]的时候如果全为偶数的话总和/2就是答案。如果有奇数呢？那就需要另一个位置给它一个，然后再放到1或者n上，那就是一步变成两步。如果没有别的位置给它，那岂不就是完不成。所以可得：有多少奇数，步数就加多少。如果n=3或者[2,n-1
2022-02-15 20:10:58
566
原创 Codeforces 1637 B. MEX and Array —— 读题，暴力
This way题意：给你一个长度为n的数组a。问你它所有子段的价值和最大是多少。价值：将一个数组分成多个区间，每个区间的价值是区间长度+这个区间的MEX。数组的价值是所有区间的价值和。题解：这tnd我阅读题目就阅读了半天。既然需要我们求最大值，那我们就要看看是分成多个区间可能会好一点，还是让区间中的MEX更大好一点。举个例子：0 1 2 3 4这个看起来是不是变成一个区间的MEX最大所以可能最优呀？答案是区间数1+区间MEX5=6那如果一个区间只有一个数呢？那就是区间数5+区间MEX
2022-02-15 19:46:05
645
原创 Codeforces 1637 A. Sorting Parts ——简单思维
<a href=https://codeforces.com/contest/1637/problem/A">This way题意：给你一个长度为n的数组a，你可以选择一个数k(1<=k<=n)。将这个数组分别在前缀长度为k的地方和后缀长度为n-k的地方排序。问你是否不能将其变成非降序数组。题解：emmm…那么我们只需要找是否有一个位置i∈[1,n)，a[i]>a[i+1]。那么k只需要等于i，是不是就意味着a[i]和a[i+1]无论变到了哪里，都至少有一个地方是逆
2022-02-15 18:48:12
579
原创 Codeforces 1629 F2. Game on Sum (Hard Version) —— 杨辉三角，暴力，找规律
This way题意：你手上有一个数字，一开始是0，每次可以选择[0,k]中任意一个实数。然后由对手决定加还是减去这个数字。总共n轮，并且对手至少要有m轮加上你手中的数字。你希望数字尽可能大，对手希望数字尽可能小。如果你们双方都做出最优抉择，问数字最大是多少。题解：有了上题的基础就比较好做了。观察数据往往能给出思路，看到是1e6，就说明有暴力可能，否则不就给出1e9了吗。画一下图：假设下面红点是要求的值，我们将它所对应的关系画出来：看到这个右上斜的这里，1,3,6,10是否有点眼熟
2022-02-11 22:39:38
7766
原创 Codeforces 1629 F1. Game on Sum (Easy Version) —— DP，博弈，思维
This way题意：你手上有一个数字，一开始是0，每次可以选择[0,k]中任意一个实数。然后由对手决定加还是减去这个数字。总共n轮，并且对手至少要有m轮加上你手中的数字。你希望数字尽可能大，对手希望数字尽可能小。如果你们双方都做出最优抉择，问数字最大是多少。题解：博弈…我是真的菜。那个2000左右的博弈就能把我按在地上摩擦，还是得多练练我一开始还想顺着做，连样例都模不出来QAQ。那么设dp[n][m]为当前总共要拿n轮，对手至少要加m轮。拿拿了一轮以后，由于前面的决策并不影响后面的情况，所
2022-02-11 20:17:53
225
原创 Codeforces 1629 E. Grid Xor —— 简单思维
This way题意：给你一个二维数组b，b[i][j]=a[i][j+1]^a[i][j-1]^a[i+1][j]^a[i-1][j]。让你输出a的所有值的异或和。题解：我一开始没看到输出的是异或和，所以就直接够早了，可能它想的是从这里面找规律？等会找找看首先我是假设第一行全为0，怎么想到全为0呢，是因为需要一个入手点…具体就不过多介绍了。第一行全为0之后，第二行是不是全都知道了，然后第三行，第四行…全都可以推出来。一开始我以为到了最后一行会出错，所以画蛇添足了一下，但是似乎并不会出错？可能
2022-02-11 16:40:42
372
原创 Codeforces 1629 D. Peculiar Movie Preferences —— 简单思维，回文串
This way题意：给你n个字符串，每个字符串长度不超过3，问你能够选出一个子序列使得子序列构造的字符串为回文串。题解：可以知道如果有字符串本身是回文串的，那就能构造出来。剩下两种情况：1.长度为2时，假设字符串为ab。①找出后面是否有长度为2且字符串为ba。②找出后面长度为3的最后两个字符为ba。2.长度为3时，假设字符串为abc：①找出后面长度为2且字符串为ba②找出后面长度为3且字符串为cba。可以看到长度为2和3时候的差别在于第二个，那么我们可以用哈希来做这道题.map
2022-02-09 20:49:54
548
原创 Codeforces 1629 C. Meximum Array —— 简单贪心
This way题意：给你一个长度为n的数组a和一个空的数组b，你每次可以选择最前面k个，求出其中的MEX，塞到b的最后面。要使b的字典序最大，问答案是什么。题解：字典序有关的很多是贪心，那么这道题既然要字典序最大，那我们肯定前面取的时候要贪心地大呀，那就枚举每一个数是什么，然后看看现在a中是否能找得到，如果找不到了就是它。同时要注意维护a中还剩下的数。#include<bits/stdc++.h>using namespace std;const int N=2e5+5;
2022-02-09 20:06:37
221
原创 Codeforces 1629 B. GCD Arrays —— 简单思维
This way题意：给你一个区间[l,r]的所有数和你的最大操作次数k，你每次可以做这样一个操作：将你手上的数中拿出两个相乘之后放回去。问你最终是否能将手上的所有数的gcd变成不是1.题解：既然gcd不是1，那就要将所有数变成某个数的倍数。那肯定猜测是2的倍数啊，每两个变成一个显然是最优的，可以自己造例子验证以下。当然有一点：只有一个数的时候就不需要了。那么怎么变呢，每次拿一个奇数和一个偶数相乘即可。拿就相当于只需要看奇数的数量是否<=k。#include<bits/std
2022-02-09 18:17:51
131
原创 Codeforces 1629 A. Download More RAM —— 简单贪心
This way题意：告诉你一开始RAM的容量k。现在有n次运算，每次运算需要占用你a[i]容量的RAM，并且运算完之后会不占用，还会给你的RAM增加b[i]点容量。但每个只能用一次。问你你的RAM最后最大是多少。题解：那么一个显然的贪心，我们肯定是取a最小的先运算，然后拿过来b。#include<bits/stdc++.h>using namespace std;const int N=105;struct node{ int a,b; bool oper
2022-02-09 17:37:17
395
原创 Codeforces 1634 F. Fibonacci Additions —— 斐波那契数列加，想法
This way题意：给你长度为n的数组a和数组b，每次会有一个操作：x l r如果x是A表示在数组a上进行操作，否则是bl r表示将区间[l,r]的数一一对应加上斐波那契数列[1,r-l+1]的数。问你最后a和b是否相等。题解：斐波那契数列加的题目之前好像做到过？447E吧，那个是使用到了斐波那契的性质，有点忘了到时候回去再看看。这道题首先想到的就是把b减到a上，然后就只用在一个数组上，每次查看是否全为0即可了。然后该怎么办呢，用线段树该怎么做我想了一会想不太到，于是更改思路：设f
2022-02-09 16:09:30
545
原创 Codeforces 1634 E. Fair Share —— dfs
This way题意：给你m个数组，你要将每个数组的数字对半分到多重集合L和R中，并且最终L和R相同，问你对于每个数组的每个数字怎么分。题解：其实还是比较简单的题目…首先假设我们拿出了第一行第一列的数x放到左边，那么肯定要在所有数组中找到另一个x放到右边。如果这两个x在同一行那么就相当于这行就多了一组左右。如果不在同一行，假设L拿到的x是在行i，R拿到的x是在行j。那就没有办法保证每一行都是对半分啊？那我们在j行随便拎一个数y到L里面呗，再继续往下找另一个y放到R中。如此往复R一定能先回到i。
2022-02-09 13:36:03
347
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人