先看看数据范围,1≤t≤104,1≤n≤2⋅105,1≤ai≤200注意到ai很小是吧?那么我们就可以dp[i][j]预处理它们的值i到当前j位子有多少个.然后暴力就没了..3个for 200n的复杂度 #include<bits/stdc++.h> #define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define pb push_back typedef long long ll; const ll inf=132913423200339; const ll mod=998244353676776; c...

因为本人很弱没学过dp,试图用dp写最短路,结果算法写出来复杂度应该大概有n^2,本人对算法复杂度又不是很敏感.所以就炸了,呜呜呜 void dfs1(ll x) { vis1[x]=1; // cout<<1<<endl; for(ll i=0;i<v1[x].size();i++) { ll so=v1[x][i].son; if(vis1[so]) continue; ll va=v1[x][i].val; dp1[so]=min(dp1[so],dp1[x]+va...

#include <stdio.h> #include <iostream> #include <algorithm> #include <string.h> #include <queue> #include <map> #include <math.h> #include <set> #include <vector> #define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define pb push_bac...

先给大家看看样例的图.思路:从最底下开始考虑,消耗了其价值肯定要走完,然后没消耗的就要保留到现在消耗1能造成的最大价值.下面的代码有注释.大家看看就懂了,不懂私聊~ #include<bits/stdc++.h> #define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define pb push_back #define inf 132913423039 typedef long long ll; const ll mod=1e9+7; const ll N=1e5+5; const ll M=10+5; ...

这个题还是好心的群友教我的...加群的好处..我不会一点图论知识,子树都不会求.群友给我讲的.其实思路我还是懂=-=就是不会写.下面先给大家看看两幅图:算下两幅图的满足题意边权,第一幅图边权是1+2+3,第二幅图的边权是1+3.我们很容易发现假如子树个数为奇数这条边就需要+,假如为偶数这条边就不用加.按着思路写下代码就好了. #include<bits/stdc++.h> #define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define pb push_back #define inf 132913423...

一个点连几条边就是度为几?所以度为1就是树最外边的那个点..还有题目并不要考虑删完后的情况.先插个图题目就是要让4 5 6 8 9这些点道不了1.让你删除一些边,使得删除的边权最小.那么怎么做呢..这个题目还是很简单的..设立dp[i]为底面的点都到不了i点的最小代价.那么dp[i]= min(vul[i][son[i]],dp[son[i]]);要么选联通它的子节点断开,要么继续往下搜..找更优的断开方法. #include<bits/stdc++.h> #define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)...

题目要求区间[l,r]的每个数的因数,然后计算每个因数最高的数是出现多少次？那咋写呢?考虑朴素算法..就是枚举[l,r]每个数的因子再对最高位进行统计..但是这样算法的复杂度就到了大于O(r-l)的级别.具体我也不会算.这样肯定不行,考虑优化.怎么优化呢?首先求[l,r]中区间每个因数最高的数是出现多少次,是不是就等同于 求[1,r]中每个因数最高的数出现多少次-求[1,l-1]中每个因数最高的数出现多少次?那么我们来枚举一个因式从而确定另外一个因式的多少,保证在因式的积在l~r的范围就好了吧?枚举因数肯定是枚举到根号x就好了...因为之前的都算过了. #include<bits/std...

树状数组的前置知识明天更新.下面讲如何利用板子解题,明天会解释树状数组的思想以及板子的由来.树状数组可以进行单点修改和区间查询,复杂度都是nlogn.先给大家讲讲树状数组求逆序对.假设现在有一个长度为5的数组是.a[5]={2,5,7,3,2}首先进行一次离散化.离散化我就不解释了(板子代码里有,ls()就没了).离散化后数组变成了a[5]={1,3,4,2,1}.那么我怎么求逆序对呢?总所周知,逆序对是i<j<k,a[i]>a[j]>a[k]这种形式的东西.那么假如这个数出现了一次,那我就在那个位子加1.我模拟一下这个数组(不要在意细节),首先是a[i],先出现了一次...

完成每日打卡了，应该+..要

之前航电有道不要62.这个是幸运数字.那么我们可以进行打表处理.打表用个dfs就好了.(1 <= l <= r <= 1000,000,000)说句实话..可能是数据水了.为啥那种r-l的算法能过..先贴一下r-l算法的代码: #include<bits/stdc++.h> #define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define pb push_back #define inf 132913423039 typedef long long ll; const ll mod=1e...

题目意思是用k个点把一个有n个节点的树染色,然后的地方必须联通,求有多少方案数?下面给大家介绍两种做法..做法1:切边表示染色用的颜色个数,比如我要用3种颜色染色,那么我就只要考虑切2条边,比如切2-4,和3和7这是一种方案,那么,考虑树,一共n个点,一共n-1条边,我可以用k种颜色染色,那么就是切k-1条边.也就是选k-1条边.那么答案就是:Cn-1 0+Cn-1 1+Cn-1 2+Cn-1 3+...+Cn-1 k-3+Cn-1 k-2+Cn-1 k-1的和..然后考虑染色,假如我现在切的是i条边,那么,我选颜色总数就是A(k,i+1). 代码如下: #include<bits/st...

出题人的题解还是讲的挺清晰的,emm,为了方便大家理解出题人的题解我解说一下..思路大概就是线性dp+差分,做这个题目的时候没有思路大概就是dp的魅力吧!下面讲讲怎么做?题目要求起点和终点同时不能出现两次,用差分思想就是分配括号，相同的括号不能出现两次在同一个地方出现两次,并且括号一定要合法..什么是合法呢?就是(的数量一定大于或者等于)的,不然肯定不行啊..出题人聚聚说的,我觉得它写的超级棒~对于每个每个点有4种放置:放置1:(放置2:)放置3:(、)放置4:什么都不放然后建立状态dp[i][j]表示到第i个位子,(比)多了j个,使得前i个都等于m?多了多少个(就相当于这个位子可以多少次+1...

大水题..先介绍下第一种做法dp观察数据易知..每个数大概就是0~100之间,然后最多100组,所以建立一个dp数组dp[i][j]表示到第i组,价值为j的数量是多少?然后转移就更简单了,思想就是桶,你这个转态肯定是有上一个转态+a[i][j]组成a[i][j]表示第i组位于j的价值..然后注意把第一组初始化为1..所以转移方程就是: dp[i][k+a[i][j]]+=dp[i-1][k];最后从1开始找到10000找k个数就好了..时间复杂度大概1e8吧..AC代码 #include<bits/stdc++.h> #define ios ios_base::sync_with_...