本周学习任务清单DP本周黄队详讲了DP有关知识的拓展，从本质到转移方式再到优化等。本质一般DP可以理解为DAG上推式子。特殊的可能需要解方程（直接解&高斯消元），以及图论（最短路，同余最短路）来解决。四大要素状态，最好是无后效性，把不能直接处理的&后面要用到的，都塞到状态里。

​哇你竟然看到了，恭喜<(￣︶￣)↗[GO!]本人水平有限，如有问题请各位大佬指出基础算法算法复杂度双指针模拟贪心递推二分三分排序递归枚举分治排序前缀和差分离散化STLsetmap基础数据结构链表队列栈二叉树哈夫曼树堆字符串后缀自动机,SAM字典树,Tri

[JOI2022Final]让我们赢得选举(Let'sWintheElection)/選挙で勝とう(Let'sWintheElection)首先由\[\min\left(\fracab,\fraccd\right)\le\frac{a+c}{b+d}\le\max\left(\fracab,\fraccd\right)\]得出，集中力量办大事，得到的支持者一定要和本人在同一州进行演讲。

CF传送门AT传送门两题主要Trick相同。CF的还多了一个小trick。给定一棵根节点为\(1\)的二叉树\(T\)，你需要先保留一个包含\(1\)号节点的连通块，然后给每个点确定一个权值\(a_i\)，使得对于每个点\(u\)都有其权值\(a_u\)大于等于其所有儿子的权值和\(\suma_v[(u,

有的时候在遇到问题时，不妨换一个角度，100%不会吃亏\[\begin{align*}&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&----LYJ\end{align*}\]有时，在想办法优化DP时，如果遇到了一些像\(A\)和

23集训测试题(10.8)密码锁这题数据量较小，可以直接暴力枚举所有密码情况并一一判断暴力代码#include<iostream>#include<cstring>#include<algorithm>usingnamespacestd;structL{intstate[6];booloperator<(constL&b)const{for(inti

题意分析给出一个矩阵，要求每行只能选一个节点，每列选的节点不能超过所有选的节点的一半，不能不选，给出每个节点的选择方案数，求总方案数考场思路考虑暴力枚举每一个点的选择情况，最后统计答案。对于行：但是因为有每一行只能选择一个的限制，所以考虑当前行选择一个后直接转跳到下一行

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=2010,M=1010,MAX=-1;inta[N];intdp[M][N];signedmain(){ intn,m; while(cin>>n>>m) { for(inti=1;i<=n;i++)cin>>a[i]; sort(a+1,

A点击查看代码#include<iostream>#include<algorithm>usingnamespacestd;constintN=105;#definelllonglongllt,shu[N],n;intmain(){cin>>t;shu[1]=1;shu[0]=1;for(inti=2;i<82;i++)shu[i]=s

对于一个x我们发现最多只有\(\log\)次有效取模，但没啥用。我们发现\(dp\)数组(函数)是一个分段一次函数(等差数列)，然后从第一个\(a_i\)开始考虑，发现每次只会多出一条线段(就是\(a_i-1\)这条)其他线段会翻折到下面，对于一条线段只会进行\(\loga\)次翻折，所以对线段的操作总次数

这个人很懒，一个月之后才写游记。考的挺差的，后来想想还是写篇游记吧。10.26初赛初赛前几天都在摆。结果考试当天在车上疯狂复习linux指令。然后就看到了pwd。开考，连蒙带猜，最后发现完善程序9个A？？出考场，小图灵测的97分。没什么好说的，只能说rp都叠初赛上了，有点慌。（事实上

一、徒步旅行中的补给问题问题描述小R正在计划一次从地点A到地点B的徒步旅行，总路程需要 N 天。为了在旅途中保持充足的能量，小R每天必须消耗1份食物。幸运的是，小R在路途中每天都会经过一个补给站，可以购买食物进行补充。然而，每个补给站的食物每份的价格可能不同，并且小R最多只

**[POI2004]PRZ****考察内容：二进制子集遍历，DP转移**#include<bits/stdc++.h>usingnamespacestd;intn,W;structdata1{ intt,w;}a[20];intdp[(1<<20)],tt[(1<<20)],ww[(1<<20)];intmain(){ scanf("%d%d",&W,&n); for(

ARC060C.TakandCards*1583简单题。考虑一个非常非常常见的Trick。把区间平均值为\(k\)转化为区间和为\(0\)只需要将每个数都减去\(k\)即可。然后就是一个朴素的背包求和为\(0\)方案数。注意处理负数下标就好了。#include<bits/stdc++.h>usingnamespacestd;typ

有些题其实都挺有价值的，搞得我都想每个都单独建随笔，但是这样还是太多太乱了，之前那个难度较低，部分题甚至可以直接删除，遂新开一个2记录更高质量的题目。[ABC379E]SumofAllSubstrings看到有思路但是想到要用高精度就头疼，但是这题并没有用到很复杂的高精度，相反甚至更像是一个

1.问题描述:你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的

本文于github博客同步更新。A：一个数可以被操作当且仅存在一列的顶部元素为它且存在一列的底部元素为它，初始扫一遍，将合法的元素以顶部所在列为关键字扔到小根堆里，每次找到最小的元素添加，然后检查将新露出来的元素是否存在匹配，若结束时未填完即为无解。B：要么在非环边上砍一刀，

看题前言:花了\(10\rm{min}\)把昨天的题调了一下,神经\(\rm{T1}\)艹,再一次缺失大样例神秘博弈放\(\rm{T1}\),大抵可做(主要原因是\(\rm{lhs}\)键盘敲得框框响)手玩几组数据大概能做,后面再认真看\(\rm{T2}\)看到树直接小命不保喵了个咪的,这我打鸡毛啊又

前言老登你也知道你又在出\(\rm{LIS}\)算法首先我们需要注意到,本质上和随机了一个\(1\simn\)的排列没有任何区别具体的,任意一个\(\rm{LIS}\)数列,都仅仅是由大小关系推过来的,并且可以证明,\(\rm{LIS}\)数列相同,当且仅当大小关系完全相同注意到这个之后(事

​ 其实赛前也没对具体的赛站有什么了解。是教练把我们分配到这个赛站的。学长在赛前就一直在给我们灌输铜牌对于现在的形式来说已经没什么用了，银牌才有点含金量。所以赛前其实是抱着要拿银牌的心态来打这场南京的。​ 提前说一下结果吧：银牌。​ 赛时很快就切出了两道签到，一道字

前言：无需多言，8:00~10:00\(4\)小时\(IOI\)，ABC198，264C、D、E\(6\)道题。以下顺序按照开题顺序：T1ABC198C-CompassWalking：一眼感觉非常的结论，开始分讨。\(10min\)后过样例了，交，似了；开\(longlong\)，交，似了\(2\)个点。（漫长的查错时间）。感觉是精度问题，换成\(double\)

继续来看动态规划中01背包的题目。题目：最后一块石头的重量II1049.最后一块石头的重量II-力扣（LeetCode）有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 

洛谷题面T1,T2,T4没什么价值，建议跳过，在此不提供T1,T2题解，套题T5,T7较为精彩，个人安利一下T3题面翻译给定 n个人做 m个题的时间分布情况，每题得一分，每题的完成时间是这道题的罚时，排名按照得分为第一关键字升序，罚时为第二关键字降序，计算在所有人都按最优顺序做题的情况下，第 1个

联考看到T1就知道一定是简单计数题然后发现\(O(n)\)可以过于是就大概写了写式子就开写。写的过程中犯了一些低级错误，代码重构了一次才过。耽误的时间比较久。然后开T2，一眼有一个\(O(n^2)\)的dp。然后考虑优化，但是记录下标必须再带一个信息所以无论怎么优化都不能到\(O(n

A当n>=30m一定<$2^n$所以直接输出即可B直接dfs统计即可C第一眼是个背包，但L太大发现有二进制，每一个容量正好在二进制上只有一位脑瘫想法是用每个数的二进制用其他数能表示的就表示，有个30的大常数其实输入就是有序的，直接让每一位都是最优的即可D额读错题，南坪选