闲扯下:A,E题解．．．写在最后,然后B....不会,不过好像大不了硬写一个搜索好像也能过,题都没咋读懂先写D题,C当时没有dp出来 D D题其实算是求割边数量的板子题,什么是割边呢?即比如我们把一个图中一条边去掉,就会变成两个图,但是如果我们要去掉的那条边在自环上,就不存在割边如果知道割边的数量,那么答案即总边数减去割边数,所以就是一个板子题.........然后这个割边咋求具体看代码时间复杂度: #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5 + 50;...

bitset,统计个数二分答案,三分答案,看到最后输出1个结果的都要试试看看能不能直接二分答案二分适用于答案符合单调函数三分适用于答案符合双调函数map映射关系,将key和value,主要统计key的个数 看到统计能有多少种情况的都要试试二进制,组合数学除外开到统计异或答案或者其他二进制答案,都要先将该数转换为二进制,然后看咋样能结合出1的情况如:0 xor 0 xor 1=1 mulitset 允许重复的set 一般对于k次方，你就可以把他转化成k个人玩这个游戏就比如这道题，是两次方，所以转化成2个人玩这个游戏就比如这道题，是两次方，所以转化成2个人玩这个游戏

题意:求s有多少种情况....题解:bitset,第一次认识这个东西我们先看暴力怎么做,每次输入一个区间,然后对于每一个位置的元素,与上一次的到的所有元素相加,然后去重比如输入[1,2],然后我们之前输入的区间一共可以得到[4,9,16];那么可以新的得到[5,10,17,8,13,20],然后新得到的会出现重复,具体的可以根据样例试一试然后如果一直输入的右区间都是100的话,输入100次最大可以得到100100100=1e6,然后区间长度100,100个区间.....1e10的时间复杂度,然后现在用bitset,现在有[4,9,16]这三个数可以改写成二进制00000001000000100...

A,B,C1比较简单没什么说的,C2........图都画不出来,就是再考画图.......画出图不就是一个三角函数 D 两种做法(1)树状数组 #include<iostream> using namespace std; int n; int a[1000005],c[1000005]; //对应原数组和树状数组 int lowbit(int x){ return x&(-x); } void updata(int i,int k){ //在i位置加上k while(i <= n){ c[i] += k; ...

题解:我以为求每个题目的通过概率.....果断看错题这个很多种做法,写一种最笨的做法,枚举比如17=000000010001嗯,然后就是0表示做不出来,1表示能做出来,相当于要枚举 个数,挺小的........然后对于每个枚举数里面出现的1的个数求一下数量,就是这种情况下过题的数量,再把这个枚举数求出来的概率加到相应的过题的那个概率上 #include<bits/stdc++.h> using namespace std; double a[13],b[13],c[13],d[13],e[13],res[13]; signed main() { for(int i=0; ...

A题意:1个单体技能,1个群体技能,然后单体技能消耗1,群体技能消耗x,然后问kill掉所有的怪,需要消耗多少题解:贪心,如果怪的数量小于x个是肯定不划算的,所以就是先排个序,然后对于倒数第x个,看看消耗多少,然后再加上前面的群体对于后面的怪攻击完剩余的血量用单体来打需要的消耗 #include<bits/stdc++.h> using namespace std; #define int long long int a[390000]; signed main() { int n,x; cin>>n>>x; int sum=0; ...

C题题意:给定 ABCD是范围,然后求xyz构成的合法三角形的个数题解:枚举 的值,然后可以直接算出 的范围和 的范围 #include<bits/stdc++.h> using namespace std; typedef long long ll; int main() { int a,b,c,d; cin>>a>>b>>c>>d; ll ans=0; for(int i=max(a+b,c+1);i<=b+c;i++)//2 3 6 10,此时x=2,y=3,z最小要取6,不合法 { int l=max(a,i-c...

我吐槽下这题,输入输出的问题,然后时间高了四五倍.........题意:求解无效轰炸有多少次,解释下什么叫有效轰炸,也就是在 区间内不存在1,就是有效轰炸题解:二维前缀和模板题(算是dp吧)如果对于每一位枚举,时间复杂度:(看题解他们有人说能过去,额,不知道咋说)现在我们优化这个参考链接:https://www.cnblogs.com/hulean/p/10824752.html先计算(1,1)到(i,j)这个大的矩形之内存在的1的数量套用下大佬的图计算方法, 因为对于(i-1,j)和(i,j-1)都有(i-1,j-1)这部分的面积,所以可以这两部分相加减去(i-1,j-1)然后下来求答案那还...

题意:给定i和i+1两点的距离,i点的货物数量,以及费用计算方法ans=x * dist( i , j ),dist(i,j)为两点间距离然后每次查询将区间(i,j)的货物全部转移到x点所需要的费用ans题解:前缀和(1)求1点到i点的距离前缀和a[]区间[1,i]点货物集中到1点,1点货物总和的前缀和b[]区间[1,i]点货物集中到1点,所需要的价值的前缀和c[](2)分情况讨论区间[L,R],点X如果X小于等于L,那么可以先把区间[L,R]所有的货物集中到1点的花费为c[R]-c[L],但是对于对于每个j点,j在[L,R],都多走了a[x],所以要减去(b[R]-b[L])*a[x]如果X...

题意:走迷宫,每次可以上下左右的走,花费为1s,或者当前位置有传送阵,花费为3s题解:搜索,对于每个点进行上下左右的压入搜索,然后对于每个点的传送阵进行压入的搜索......广搜裸题记得标记路径防止重复 #include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #include<iostream> #include<queue> #define ll long long #define N 405 using namespace std...

闲聊:这次的有点简单.....A题:看了一下感觉像汉诺塔问题....假设最开始n=0,也就是石墩数为0,此时荷叶数为m,那么可以过去 只青蛙,相信这个大家都知道现在n=1,我们可以由前一个状态得到,可以假设1号石墩为上一个的终点的石墩,那么除了1号石墩,剩下的状态为n=0的状态,此时可以跳过来m+1个,然后现在1号石墩上还剩余m+1个,把这m+1个每个荷叶和1号石墩上各一个,然后逐步累加到终点石墩上,此时答案为现在n=2,那么我们同理2号石墩等于n=1时终点石墩的状态,然后剩下的状态就为拿n=1时候的状态,那么为然后多写几个发现 #include<bits/stdc++.h> u...

题意:给定一个不知道树的情况的中序遍历,然后求左子树的值乘右子树的值再加上根节点的值,然后求这个的最大值题解:我知道这个咋说....树形dp还是记忆化搜索,好像都差不多,基本上都是发挥计算机,算的快的优越性的暴力........中序遍历结果:left表示左子树的区间,right表示右子树的区间,就是以root根节点来划分左右子树枚举每一个点为树的根节点,然后再以当前位置,枚举其左子树的最大值和右子树的最大值递归遍历,可以加上记忆化搜索减少次数然后每次对所求区间的最大值式子如下:第i个节点为划分左右子树节点,咦有点像区间dp时间复杂度:我瞎猜一个 .....这种递归的不咋会计算........逃...

题意:回合制游戏......齐齐先手,每次攻击完司机,然后司机打齐齐攻击司机的那一个物品,但是每次会有连锁反应.......真就是我打别人,然后极限一换一题解:搜索+贪心先求对于司机多少次连锁反应可以团灭再求对于齐齐多少次连锁反应可以团灭然后比较两个的次数如果齐齐的次数<司机的次数,输出-1否则,求齐齐用来极限一换一的连锁的那几个大炮,产生连锁反应,所损失的最小的大炮数,然后总数再减去损失数就是答案求连锁反应的可以用搜索,对于每次的求的时候要标记,防止重复,就是求每一次的连锁反应可以影响多少个大炮然后把求的连锁反应所影响的大炮的个数从小到大排序,取前司机团灭数个求和时间复杂度: 实际要高...

题意:给n个电影,一个时长L,然后问在时长L中最少看多少个电影,没个只能看一次,中间可以跳场题解:状态压缩dp,看了好多大佬写的,(刚看会) 枚举所有的观看的组合的可能,然后讲i转化为二进制,比如 ,第一,五,六场不看,第二,三,四场看然后我们对于每一种组合的情况进行处理对于第i种情况下的第j个电影我们放在最后进行观看,那么我们要在前面求出不看第j个电影的一个时间,设为 因为可以中间退出,所以求小于等于的最大第j个电影的开始时间的数,然后再加上第j个电影的播放时间然后对于每个如果大于L 求其中二进制的1的个数,即为答案时间复杂度: #include<cstdio> #includ...