pamhip level
获赞
133
粉丝
13
关注
14
看过 TA
237
男
华南理工大学
2023
C++
IP属地：美国
暂未填写个人简介
私信
关注
发布(148) 评论 刷题 收藏
2020-05-01 14:53
已编辑
华南理工大学 C++
cf 1182E Product Oriented Recurrence（欧拉定理 + 矩阵快速幂
description Let       f   x    =    c    2   x   −   6     ⋅    f    x   −   1     ⋅    f    x   −   2     ⋅    f    x   −   3      f_{x} = c^{2x-6} \cdot f_{x-1} \cdot f_{x-2} \cdot f_{x-3}   fx​=c2x−6⋅fx−1​⋅fx−2​⋅fx−3​ for      x   ≥   4    x \geq 4   x≥4 You have given integers      n    n   n,  ...
各种题解及学习笔记~
0 点赞 评论 收藏
分享
2020-05-01 14:52
已编辑
华南理工大学 C++
主席树详解——区间的权值线段树
为啥叫主席树？ 很多人一看到这名字觉得这肯定是个很厉害的数据结构，从而望而却步。 其实为啥这个数据结构叫主席树呢，emmmm…  这个数据结构是这位同学在考场上想出来的，而他的名字与某位主席缩写有一致的相似性QAQ  引入题（静态区间第k小) 题目描述 如题，给定      n    n   n 个整数构成的序列，将对于指定的闭区间查询其区间内的第      k    k   k 小值。 输入格式 第一行包含两个正整数      n   ,   m    n,m   n,m，分别表示序列的长度和查询的个数。 第二行包含      n    n   n 个整数，表示这个序列各项的数字。 接下来 ...
各种题解及学习笔记~
0 点赞 评论 收藏
分享
2020-05-01 14:51
华南理工大学 C++
CF1295E Permutation Separation
题意 给出一个排列       p   1    ,    p   2    ,   .   .   .    p   n     p_1,p_2,...p_n   p1​,p2​,...pn​ .初始时你需要选择一个位置把排列分成左右两个。然后在两个序列间移动元素使得左边序列的所有元素都比右边的所有元素小。给出每个元素       p   i     p_i   pi​ 从一个序列移动到另一个序列的代价       a   i     a_i   ai​。求总代价最小值。 分析 先看最后两个集合的性质，假设左边的集合最大值是      k    k   k，那么左边的集合为     [   ...
各种题解及学习笔记~
0 点赞 评论 收藏
分享
2020-05-01 14:51
已编辑
华南理工大学 C++
CF1278D Segment Tree（set乱搞
题意 有      n    n   n 个线段，如果两条线段严格相交，则两条线段之间有一条边。 问最终能否生成一棵树。 分析 设两条线段为      a   ,   b    a,b   a,b（设      a   .   l   <   b   .   l    a.l < b.l   a.l<b.l ）      a   ,   b    a,b   a,b 相交的条件是：      b   .   l   <   a   .   r   <   b   .   r    b.l < a.r < b.r   b.l<a.r<b.r ...
各种题解及学习笔记~
0 点赞 评论 收藏
分享
2020-05-01 14:51
华南理工大学 C++
【网络流24题】飞行员配对方案问题
题目描述 英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的2 名飞行员，其中1 名是英国飞行员，另1名是外籍飞行员。在众多的飞行员中，每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。如何选择配对飞行的飞行员才能使一次派出最多的飞机。对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。 对于给定的外籍飞行员与英国飞行员的配合情况，编程找出一个最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。 输入格式 第 1 行有 2 个正整数 m 和 n。n 是皇家空军的飞行员总...
各种题解及学习笔记~
0 点赞 评论 收藏
分享
2020-05-01 14:50
华南理工大学 C++
【网络流24题】 圆桌问题
题目描述 假设有来自m 个不同单位的代表参加一次国际会议。每个单位的代表数分别为ri (i =1,2,……,m)。 会议餐厅共有n 张餐桌，每张餐桌可容纳ci (i =1,2,……,n)个代表就餐。 为了使代表们充分交流，希望从同一个单位来的代表不在同一个餐桌就餐。试设计一个算法，给出满足要求的代表就餐方案。 对于给定的代表数和餐桌数以及餐桌容量，编程计算满足要求的代表就餐方案。 输入格式 第1 行有2 个正整数m 和n，m 表示单位数，n 表示餐桌数，1<=m<=150, 1<=n<=270。 第2 行有m 个正整数，分别表示每个单位的代表数。 第3 行有n 个正整数...
各种题解及学习笔记~
0 点赞 评论 收藏
分享
2020-05-01 14:50
华南理工大学 C++
【网络流24题】 最小路径覆盖问题
题目描述 给定有向图 G=(V,E) 。设 P 是 G 的一个简单路(顶点不相交)的集合。如果 V 中每个定点恰好在P的一条路上，则称 P 是 G 的一个路径覆盖。PP中路径可以从 V 的任何一个定点开始，长度也是任意的，特别地，可以为 0 。G 的最小路径覆盖是 G 所含路径条数最少的路径覆盖。设计一个有效算法求一个 GAP (有向无环图) G 的最小路径覆盖。 输入格式 第一行有 22 个正整数 n 和 m 。 n 是给定GAP(有向无环图) G 的顶点数， m 是 G 的边数。接下来的 m 行,每行有两个正整数 i 和 j 表示一条有向边 (i,j)。 输出格式 从第1 行开始，每行输出...
各种题解及学习笔记~
0 点赞 评论 收藏
分享
2020-05-01 14:50
华南理工大学 C++
【网络流24题】 最长不下降子序列问题
题意： 给定正整数序列      x   1    ,   .   .   .   ,    x   n     x_1,...,x_n   x1​,...,xn​ （1）计算其最长不下降子序列的长度      s    s   s。 （2）计算从给定的序列中最多可取出多少个长度为s的不下降子序列。 （3）如果允许在取出的序列中多次使用       x   1     x_1   x1​ 和       x   n     x_n   xn​，则从给定序列中最多可取出多少个长度为      s    s   s 的不下降子序列。 分析 第一问，普及组问题。 第二，三问，要用网络流解决。 第二问...
各种题解及学习笔记~
0 点赞 评论 收藏
分享
2020-05-01 14:49
华南理工大学 C++
【网络流24题】 方格取数问题
题目描述 在一个有 m*n 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意 2 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘，按照取数要求编程找出总和最大的数。 输入格式 第 1 行有 2 个正整数 m 和 n，分别表示棋盘的行数和列数。接下来的 m 行，每行有 n 个正整数，表示棋盘方格中的数。 输出格式 程序运行结束时，将取数的最大总和输出 输入输出样例 输入 #1 3 3 1 2 3 3 2 3 2 3 1 输出 #1 11 分析 如果将棋盘黑白染色，黑点放左边，白点放右边，每个黑点向相邻的白点连边，会形成一个二分图。 ...
各种题解及学习笔记~
0 点赞 评论 收藏
分享
2020-05-01 14:49
华南理工大学 C++
【网络流24题】 太空飞行计划问题
题面  分析 这类题叫最大权闭合图问题。 有向图的闭合图是指每个点的后驱节点都在图中。 这道题中，一些实验和它对应的仪器形成了个闭合二分图，一边点权是正，一边是负，总收益是权值和。 怎么最大化权值和呢？ 建超级源点      s    s   s 和超级汇点      t    t   t 从      s    s   s 到每个实验连边，边权为       a   i     a_i   ai​ 从 每个仪器到      t    t   t 连边，边权为       b   i     b_i   bi​ 的绝对值 每个实验向对应仪器连边，边权为      i   n   f    in...
各种题解及学习笔记~
0 点赞 评论 收藏
分享
2020-05-01 14:49
华南理工大学 C++
杜教筛学习笔记
前置知识 狄利克雷卷积 若     f   (   n   )   =  <munder>  ∑    i   ∣   n   </munder>  g   (   i   )   h   (    n   i    )    f(n) = \sum\limits_{i|n}g(i)h(\dfrac{n}{i})   f(n)=i∣n∑​g(i)h(in​) 则记      f   =   g   ∗   h    f = g*h   f=g∗h 杜教筛 假如要求某积性函数      f   (   n   )    f(n)   f(n) 的前缀和      (   ...
各种题解及学习笔记~
0 点赞 评论 收藏
分享
2020-05-01 14:48
已编辑
华南理工大学 C++
CQOI 2015 选数
题目描述 我们知道，从区间 [L,H]（L 和 H 为整数）中选取 N 个整数，总共有 (H-L+1)^N 种方案。小 z 很好奇这样选出的数的最大公约数的规律，他决定对每种方案选出的 N 个整数都求一次最大公约数，以便进一步研究。然而他很快发现工作量太大了，于是向你寻求帮助。你的任务很简单，小 z 会告诉你一个整数 K，你需要回答他最大公约数刚好为 KK 的选取方案有多少个。由于方案数较大，你只需要输出其除以 1000000007 的余数即可。 输入格式 输入一行，包含四个空格分开的正整数，依次为 N,K,L,H。 输出格式 输出一个整数，为所求方案数。 输入输出样例 输入 #1 2 2 2...
各种题解及学习笔记~
0 点赞 评论 收藏
分享
2020-05-01 14:48
华南理工大学 C++
CF617E XOR and Favorite Number（莫队算法）
题意 给你一个大小为n的序列，然后给你一个数字k，再给出m组询问，询问给出一个区间，问这个区间里面有多少个区间的异或结果为k。 分析 因为这题去学了莫队QAQ 首先记前缀异或和为       s   i     s_i   si​，区间异或和为      k    k   k的对数，等价于       s   r   <mtext>   </mtext>  x   o   r  <mtext>   </mtext>   s    l   −   1     =   k    s_r~xor~s_{l-1}=k   sr​ xor sl−1​=k ...
各种题解及学习笔记~
0 点赞 评论 收藏
分享

创作者周榜

更多
关注他的用户也关注了：
牛客网
牛客网在线编程
牛客网题解
牛客企业服务