欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
  • 洛谷P2184 贪婪大陆

    [TOC] 题目 "戳" 思路 修改区间时在开始位置$s+1$表示从则例开始埋一种雷,在结束位置$e+1$表示有一种雷埋到这里就结束了。 查询时输出$[1,r]$s的和减去$[1,l 1]$的e的和。用线段树来实现。 $Code$ cpp include include include includ ...

    程序员文章站2023-10-18
  • 洛谷P4245 【模板】MTT(任意模数NTT)

    题目背景 模板题,无背景 题目描述 给定 22 个多项式 F(x), G(x)F(x),G(x) ,请求出 F(x) * G(x)F(x)∗G(x) 。 系数对 pp 取模,且不保证 pp 可以分解成 p = a \cdot 2^k + 1p=a⋅2k+1 之形式。 输入输出格式 输入格式: 输入共 ...

    程序员文章站2023-10-08
  • 洛谷 P2756 飞行员配对方案问题

    全名:线性规划与网络流24题 按照题目难度顺序: 1.飞行员配对方案问题(求最大匹配数并且输出配对方案) 两种做法: 1)二分图匹配匈牙利算法,可以直接求出最大匹配数,并且数组中记录了最佳配对方案 2)最大流,超级源点S到A集合中每一个元素建边(容量为1),B集合中每一个点到汇点建边(容量为1),A ...

    程序员文章站2023-09-28
  • 洛谷P4926 [1007]倍杀测量者(差分约束)

    题意 "题目链接" Sol 题目中的两个限制条件xian $$A_i \geqslant (K_i T)B_i$$ $$A_i(K_i + T) \geq B_i$$ 我们需要让这两个至少有一个不满足 直接差分约束建边即可 这里要用到两个trick 1. 若某个变量有固定取值的时候我们可以构造两个等 ...

    程序员文章站2023-09-07
  • 洛谷P2572 [SCOI2010]序列操作(ODT)

    题解 题意 "题目链接" Sol ODT板子题..... cpp // luogu judger enable o2 include define LL long long define Fin(x) freopen( x".in", "r", stdin); define Fout(x) freo ...

    程序员文章站2023-09-07
  • 洛谷P2447 [SDOI2010]外星千足虫(异或方程组)

    题意 "题目链接" Sol 异或高斯消元的板子题。 bitset优化一下,复杂度$O(\frac{nm}{32})$ 找最优解可以考虑高斯消元的过程,因为异或的特殊性质,每次向下找的时候找到第一个1然后交换就行,这样显然是最优的 cpp include using namespace std; co ...

    程序员文章站2023-09-07
  • 洛谷P3193 [HNOI2008]GT考试(dp 矩阵乘法)

    题意 "题目链接" Sol 设$f[i][j]$表示枚举到位置串的第i位,当前与未知串的第j位匹配,那么我们只要保证在转移的时候永远不会匹配即可 预处理出已知串的每个位置加上某个字符后能转移到的位置,矩阵快速幂优化一下 复杂度$O(M^3 \log n)$ cpp include using nam ...

    程序员文章站2023-09-07
  • 洛谷P4165 [SCOI2007]组队(排序 堆)

    题意 "题目链接" Sol 跟我一起大喊:n方过百万,暴力踩标算! 一个很显然的思路是枚举$H, S$的最小值算,复杂度$O(n^3)$ 我们可以把式子整理一下,变成 $$A H_i + B S_i \leqslant C + AminH + BminS$$ 首先按$H$排序 考虑去从大到小枚举$A ...

    程序员文章站2023-09-05
  • 洛谷P3248 [HNOI2016]树(主席树 倍增 )

    题意 "题目链接" Sol 从上午九点淦到现在qwq 思路比较简单,就是把每次加入的一坨点看成一个,然后直接倍增搞。。 然后慢慢调就可以了。。。 最后数量级会到达$10^{10}$,所以应该开long long cpp include define Pair pair define MP make_ ...

    程序员文章站2023-09-01
  • 洛谷P2085——最小函数值

    题目描述 有n个函数,分别为$F_1,F_2,...,F_n$。定义$F_i(x)=A_i x^2+B_i x+C_i (x∈N )$。给定这些$A_i、B_i和C_i$,请求出所有函数的所有函数值中最小的m个(如有重复的要输出多个)。 输入格式 输入数据:第一行输入两个正整数n和m。以下n行每行三 ...

    程序员文章站2023-08-31
  • 【洛谷】P1308 统计单词数-全AC题解(易理解

    弟弟的混乱代码(易理解 大概 思路: 循环b(被找的字符串),遇空格比较两空格间的长度是否与a(需要查找的字符)相等;不相等继续循环;相等比较内容是否相同(倒数比较,不一样直接退出 ,直到比较到第一个都相等时 num++)。 ...

    程序员文章站2023-08-30
  • 洛谷P1397 [NOI2013]矩阵游戏(十进制矩阵快速幂)

    题意 题目链接 Sol 感觉做这题只要对矩阵乘法理解的稍微一点就能做出来对于每一行构造一个矩阵A = a 1 0 b列与列之间的矩阵为B = c 1 0 d最终答案为$A^{n - 1}B A^{n - 1}B \dots $把$A^{n-1}B$看成一项进行快速幂即可 maya把数据范围看漏了1e ...

    程序员文章站2023-08-21
  • 洛谷P1600 天天爱跑步(差分 LCA 桶)

    题意 "题目链接" Sol 一步一步的来考虑 $25 \%$:直接$O(nm)$的暴力 链的情况:维护两个差分数组,分别表示从左向右和从右向左的贡献, $S_i = 1$:统计每个点的子树内有多少起点即可 $T_i = 1$:同样还是差分的思想,由于每个点 能对其产生的点的深度是相同的(假设为$x$ ...

    程序员文章站2023-08-11
  • 洛谷P2762 太空飞行计划问题(最大权闭合图)

    题意 有$m$个实验,$n$中器材,每个实验需要使用一些器材 每个实验有收入,每个器材有花费 最大化收入 - 花费 Sol 最大权闭合图的经典应用 从$S$向每个实验连流量为该实验收入的边 从每个器材箱$T$连流量为花费的边 每个实验向其需要其器材连边权为$INF$的边 答案为:总收入 - 最小割 ...

    程序员文章站2023-04-08
  • 洛谷P2763 试题库问题(最大流)

    题意 $n$道试题,每道题有多种类别属性 抽取$m$道题组成试卷,要求包含指定的类型 输出方案 Sol 又是一道zz网络流 我的构图长这样,$k_i$表示第$i$道试题需要的数量 ...

    程序员文章站2023-04-08
  • 洛谷P2764 最小路径覆盖问题(二分图)

    题意 给出一张有向无环图,求出用最少的路径覆盖整张图,要求路径在定点处不相交 输出方案 Sol 定理:路径覆盖 = 定点数 - 二分图最大匹配数 直接上匈牙利 输出方案的话就不断的从一个点跳匹配边 ...

    程序员文章站2023-04-08
  • 洛谷P1251 餐巾计划问题(最小费用最大流)

    题意 一家餐厅,第$i$天需要$r_i$块餐巾,每天获取餐巾有三种途径 1、以$p$的费用买 2、以$f$的费用送到快洗部,并在$m$天后取出 3、以$s$的费用送到慢洗部,并在$n$天后取出 问满足要求时的最小费用 Sol 一道非常不错的网络流,应该不难看出是费用流。 首先进行拆点,把每个点早上和 ...

    程序员文章站2023-04-08
  • 洛谷P3366 【模板】最小生成树(Boruvka算法)

    题意 "题目链接" Sol 自己yy着写了一下Boruvka算法。 算法思想很简单,就是每次贪心的用两个联通块之间最小的边去合并。 复杂度$O(n \log n)$,然鹅没有Kruskal跑的快,但是好像在一类生成树问题上很有用 cpp include define Pair pair define ...

    程序员文章站2023-04-05
  • 【解题报告】洛谷 P2571 [SCOI2010]传送带

    【解题报告】洛谷 P2571 [SCOI2010]传送带今天无聊,很久没有做过题目了,但是又不想做什么太难的题目,所以就用洛谷随机跳题,跳到了一道题目,感觉好像不是太难。 [CSDN链接](https://blog.csdn.net/Liang_Si_FFF/article/details/8457 ...

    程序员文章站2023-04-05
  • 洛谷P1107 & BZOJ1270 [BJWC2008]雷涛的小猫

    一道DP。 给你一个矩阵里面有很多数,你需要从上往下找到一种跳跃方法使得经过的点的价值之和最大。 具体题面见链接 洛谷P1107 BZOJ1270 很明显是一个二维的DP。 混搭码风,求谅解。 ...

    程序员文章站2023-04-05