- 博客(25)
- 资源 (13)
- 收藏
- 关注
RSS订阅原创 CF1634E Fair Share
题意：有 mmm 个数组，每个数组长度为 nin_ini。要在每组间恰好划分一半进可重集 LLL，剩下的进 RRR。要求判断能否找出一组划分方式，使 LLL 和 RRR 相同。思路：题目要求最终的 LLL，RRR 相同，考虑转化成数据中的一些互相对立的关系，从而想到建图后黑白染色。容易发现，只有所有数都出现了偶数次才有解，于是可以先把 No 给判掉。考虑按如下方式建图：定义“一组”表示一个数组中相邻两元素。在两个相邻的，值相同的数之间连边。在每一组之间连边。可知若两数之间有边，则
2022-03-13 21:05:28
111
原创 CF1648B Integral Array
题意:若一个数组长度为 nnn 的数组 aaa，对于它之中任意两个元素 xxx，yyy，在 aaa 中都存在 ⌊xy⌋\lfloor \frac{x}{y} \rfloor⌊yx⌋，则称 aaa 为一个 Integral Array。先给你一个元素都不超过 ccc 的数组，要判断它是否是 Integral Array。思路:发现这个 ccc 很小，只有 10610^6106，所以可以将每个元素是否出现都存起来。枚举倍数，若 ⌊ab⌋=k\lfloor \frac{a}{b} \rfloor =
2022-03-11 14:58:01
250
原创 CF1068E Multihedgehog
题意：定义 k−multihedgehogk-multihedgehogk−multihedgehog 为：对于 1−multihedgehog1-multihedgehog1−multihedgehog，其中一个点度数 ≥3\ge3≥3 ，其它点度数均为 111.k−multihedgehogk-multihedgehogk−multihedgehog 是在 (k−1)−multihedgehog(k-1)-multihedgehog(k−1)−multihedgehog 的基础上，把所有度为 11
2021-08-29 19:36:45
89
原创 [USACO20JAN]Loan Repayment S
首先我们想到的肯定是一个超时的暴力算法。但发现题目要求查找 xxx 的最大值，所以可以想到用二分去优化。每次判断当前 midmidmid 是否符合题目要求。二分模板：while(l<r){ mid=(l+r+1)/2; if(check(mid)) l=mid; else r=mid-1;}这里只需要将 checkcheckcheck 函数改一下即可。在 checkcheckcheck 函数中，我们需要统计当前需要求的 midmidmid 是否
2021-08-02 19:52:45
148
原创 [USACO17JAN]Hoof, Paper, Scissor S
这道题首先说明了有 333 个手势 PPP , HHH , SSS。我们可以开三个数组分别把他们记下来。定义 f[i][j][k]f[i][j][k]f[i][j][k] 为当前第 iii 轮，是否用了手势，当前是 PPP 或 HHH 或 SSS。转移方程：f[i][j][0]=max(f[i][j][0],max(f[i−1][j][0]+h[i],max(f[i−1][j−1][1]+h[i],f[i−1][j−1][2]+h[i])));f[i][j][0]=max(f[i][j][0]
2021-08-02 19:52:07
116
原创 UVA11059 【最大乘积 Maximum Product】
题意：确定一个 l,rl,rl,r ,使 ∏i=lrsi\prod_{i=l}^r s_i∏i=lrsi 最大。思路我们可以枚举每一个左节点和右节点，求这段区间的和，最后取 max\maxmax 即可。注意：ansansans 初始化为 111。输入到 EOFEOFEOF 为止。代码#include<bits/stdc++.h>using namespace std;int n,tot;long long ans,a[20];int main(){ while(s
2021-07-29 15:39:30
180
原创 UVA10364 【Square】
这道题我们可以用 dfsdfsdfs 的方式来做。可以先对 a[1...n]a[1...n]a[1...n] 取 max\maxmax, min\minmin 和 sumsumsum。若 sum mod 4sum \bmod 4summod4 不等于 000，那么直接输出 nonono。若 mx>sum/4mx > sum/4mx>sum/4 ，也输出 nonono。最后判断 dfs(1,0,a[1])dfs(1,0,a[1])dfs(1,0,a[1]) 是否为 truetr
2021-07-29 15:38:54
94
原创 CF1416B 【Make Them Equal】
这是一道数学题首先，我们可以发现只要求出任意一种方案即可。于是我们通过模拟样例得出，有一种保证只要 3∗(n−1)3*(n-1)3∗(n−1) 步求可以得出答案：先让 a[i]a[i]a[i] 能被 iii 整除。把 a[i]a[i]a[i] 转移到 a[1]a[1]a[1] 上。再把 a[1]a[1]a[1] 分成 nnn 组注意：当 $ \sum_{}a[i]$ 不能被 nnn 整除时，应该直接输出 −1-1−1。代码：#include<bits/stdc++.h>us
2021-07-29 15:38:19
126
原创 CF359B Permutation
题目：给出整数 nnn, kkk构造一个长度为 2×n2 \times n2×n 的序列 aaa满足:∑i=1n∣a2i−a2i−1∣−∣∑i=1na2i−a2i−1∣=2k\sum_{i=1}^n |a_{2i} -a_{2i-1}| -|\sum_{i=1}^n a_{2i}-a_{2i-1}| = 2ki=1∑n∣a2i−a2i−1∣−∣i=1∑na2i−a2i−1∣=2k1≤n≤500001≤n≤500001≤n≤50000 , 0≤2k≤n0≤2k≤n0≤2k≤n思路：首
2021-07-29 15:37:28
88
原创 CF630K 【Indivisibility】
首先，我们可以明显地发现这是一个容斥问题。在 2≤i≤102\leq i \leq 102≤i≤10 这 999 个数中，只有 2,3,5,72,3,5,72,3,5,7 需要枚举。于是这样我们就可以分成 444 个部分来做了。一个数 减去两个数 加上三个数 减去四个数 加上最后输出结果即可。代码：#include<bits/stdc++.h>using namespace std;#define int long long int sum,n;signed ma
2021-07-26 18:56:48
62
转载 CF1041F Ray in the tube
转自 https://www.luogu.com.cn/blog/MrHY43245/solution-cf1041f解题思路本题求解的是打到的传感器数量。首先可以发现，上下边缘的纵坐标，即 y1y_1y1 和 y2y_2y2 对答案是没有影响的。我们只需要关注传感器的横坐标即可。同样的，激光的发出点在上边缘还是下边缘对答案也没有影响，因此我们不妨设激光发出点总是在上边缘。而能够被激光打到的传感器横坐标的形式与等差数列有相似之处，即最终结果只与发出点的横坐标（首项 xxx），和每次从一个边缘到另
2021-07-21 19:11:53
63
原创 [USACO16DEC]Moocast S
首先我们从题目中得知，每头牛的对讲机的有效传输半径为一个圆心为 (x[i],y[i])\left(x[i],y[i]\right)(x[i],y[i]) 半径为 p[i]p[i]p[i] 的圆。这样我们就可以进行 BFSBFSBFS 去查找当前位置上的牛所能传出到的所有牛了。当然，也可以理解为这是一个 变种 的连通块，每次可以跳到一个与当前点的 欧几里得距离 $ \leq p[i]$ 的位置。执行 nnn 次，每次更新最大值即可。注意：每次操作前要清空队列和vis数组，还要将 sumsumsum 初
2021-07-21 19:01:40
120
原创 CF1413A 【Finding Sasuke】
首先，题目告诉我们如果有多种答案则输出任意一种即可于是，可以这么构造：让 b[i]=a[n−i+1]b[i]=a[n-i+1]b[i]=a[n−i+1] 且让 b[i]=a[n−i+1]b[i]=a[n-i+1]b[i]=a[n−i+1]这样所有 ∑a[i]∗b[i]\sum_{}a[i]*b[i]∑a[i]∗b[i] 为 000 了。当然，构造的方法还有许多，比如让 b[i]=a[i+1]b[i]=a[i+1]b[i]=a[i+1] , b[i+1]=a[i]b[i+1]=a[i]b[i+
2021-07-21 19:00:58
75
原创 UVA1292 【Strategic game】
题意：标记最少的点使所有的边都被包含。前置知识：树形DP状态：f[u][0/1]f[u][0/1]f[u][0/1] 表示 uuu 号点，选或不选。若当前点不选，那它的儿子选或不选都可以。若当前点要选，那它的儿子只能不选。转移：f[u][0]+=max(f[v][0],f[v][1])f[u][0]+=max(f[v][0],f[v][1])f[u][0]+=max(f[v][0],f[v][1])f[u][1]+=f[v][0]f[u][1]+=f[v][0]f[u][1]+=f[v][
2021-07-21 18:59:57
89
原创 Luogu P4894 【GodFly求解法向量】
解方程大法好！我们将题中 x∗x1+y∗y1+z∗z1=0x*x_1+y*y_1+z*z_1 = 0x∗x1+y∗y1+z∗z1=0 称为 ① 式，将 x∗x2+y∗y2+z∗z2=0x*x_2+y*y_2+z*z_2 = 0x∗x2+y∗y2+z∗z2=0 称为 ② 式。再将 ① 式乘上 x2x_2x2，将 ② 式乘上 x1x_1x1，得：{x∗x1∗x2+y∗y1∗x2+z∗z1∗x2=0x∗x2∗x1+y∗y2∗x1+z∗z2∗x1=0 \left\{\begin{align
2021-07-21 18:59:21
71
原创 CF1041E Tree Reconstruction
提供一种不是链的做法题意：给定 一棵树中每条边被删去后，形成的两个连通块中两个编号最大的点的编号，问 满足条件的树存不存在。若存在，输出 YES ，并给出方案，否则输出 NO 。思路：首先，我们可以很明显地看到，无论砍掉树上哪一条边，其中一个连通块内编号最大的树一定是 NNN。若不满足这一条件，可直接判无解。我们把最后答案里的树想象成一个类似菊花图的样子，如下图所示：而这棵树的根一定是n。然后，观察输入数据中每个数（除 NNN 外 ）的出现次数，将其分为以下两类：tot=0tot=0t
2021-07-21 18:57:31
35
原创 STL之next_permutation
std::next_permutationC++ 算法库定义于头文件 (1) template< class BidirIt >bool next_permutation( BidirIt first, BidirIt last );(C++20 前)template< class BidirIt >constexpr bool next_permutati...
2020-03-04 20:17:14
186
原创 最长公共子序列
最长公共子序列LIS：给定两个序列 S1 和 S2 ，求二者公共子序列 S3 的最长的长度。如：s1=abcfbc,s2=abfcab发现：状态转移方程!!!lcs[i][j]表示s1的前i个字符与s2的前j个字符的最长公共子序列的长度于是，代码就出来了：字符串版本：#include <iostream>#include <cstring>#...
2020-02-22 21:20:51
109
原创 正反约瑟夫问题
【问题描述】n只猴子围坐成一个圈，按顺时针方向从1到n编号。然后从1号猴子开始沿顺时针方向从1开始报数，报到m的猴子出局，再从刚出局猴子的逆时针方向下一个位置重新开始报数，报到m出列；再从出列的猴子的顺时针方向的猴子开始报数。如此重复，直至剩下一个猴子，它就是大王。输出依次出列的猴子的编号。输入两个整数n和m输出n行，每行一个整数，表示猴子的编号。样例输入4 3样例输出341...
2020-02-22 18:31:47
645
原创 对称二叉树(NOIP2018)
首先，我们将题目给定的对称二叉树的定义来梳理一遍：一棵有点权的有根树如果满足以下条件1.这是一棵二叉树2.将这棵树所有节点的左右子树交换，新树和原树对应位置的结构相同且点权相等。则这颗树就是一棵对称二叉树我们来看9~12的数据：这是一棵满二叉树所以，对于这一档数据，我们只要判断他们的权值是否相等就行了再看17~20的数据：这是一颗所有权值都为1的二叉树对于这一档数据，我们...
2020-02-21 21:10:55
563
原创 逆序对
题目描述对于一个包含N个非负整数的数组A[1…n]，如果有i < j，且A[ i ]>A[ j ]，则称(A[ i] ,A[ j] )为数组A中的一个逆序对。 例如，数组（3，1，4，5，2）的逆序对有(3,1),(3,2),(4,2),(5,2)，共4个。求n个数中的逆序对个数。输入第一行一个整数n(<=1,000,000)第二行n个整数，a[i]<=2^3...
2020-02-14 20:18:32
204
原创 Aut- The Bus
题目描述：Byte City 的街道形成了一个标准的棋盘网络 – 他们要么是北南走向要么就是西东走向. 北南走向的路口从 1 到 n编号, 西东走向的路从1 到 m编号. 每个路口用两个数(i, j) 表示(1 <= i <= n, 1 <= j <= m). Byte City里有一条公交线, 在某一些路口设置了公交站点. 公交车从 (1, 1) 发车, 在(n, m)...
2020-02-13 21:59:44
347
原创 关押罪犯（NOIP2010）
题目描述S 城现有两座监狱，一共关押着N 名罪犯，编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为c 的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为c 的冲突事件。每年年末，警察局会将本年内监狱中的所...
2020-02-13 21:42:01
444
原创 亲戚（并查集）
题目背景若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。题目描述规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。输入格式第一行：三个整数n,m,p，（n<=5000,m<=5000,p<=5000），分别表示有n个人，m个亲...
2020-02-11 22:50:48
1015
原创 花神游历各国（线段树区间开根）
题目描述输入样例输入41 100 5 551 1 22 1 21 1 22 2 31 1 4样例输出1011111一句话题意：维护一颗线段树，操作有区间开根，区间求和一开始看到这题以为可以使用延迟标记但是sqrt(a)+sqrt(b)!=sqrt(a+b)!!!（太可怕了）but1e9开5次根就不变了（计算机按出来的）那么，每次暴力修改到根节点，...
2020-02-11 22:12:03
237
1
背包九讲完整详解.pdf
2020-02-29
归并排序merge_sort模板
2020-02-29
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人