题目大意：12个题目，给定每个题目能做出来的概率，求总共做对 0-12 道题的概率.分析：一共12道题，我们可以二进制枚举做对题目的所有情况 ,然后每一种情况的算出做对题数的概率，然后累加输出即可. #include<bits/stdc++.h> using namespace std; const int maxn=2e5+10; double a[13][10]; double ans[13][10]; double res[13]; int main() { for( int i=1;i<=12;i++ ) cin>>a[i][0]; ...

题目大意:给定一个有 个元素序列,有四种操作和一种询问. 1 L R K 让区间 的元素加上 . 2 L R K 让区间 的元素乘上 . 3 L R K 让区间 的元素变为 . 4 L R K 在末尾位置添加一个元素值为 . 5 L R 询问区间 元素的值的和. 分析: 赛中分析，前四个操作都是线段树的操作，后面看到操作四，以为不能写线段树，直接码分块，后面T了三十发直接自闭. 赛后分析：显然我们可以直接建n+m大小的线段树，然后直接操作.(惊了推标记直接用两个mul 和add 维护乘法和加法,这种操作就是码板子. #include<bits/stdc++.h> #de...

题目大意: 的网格，，网格上有一些点不能行走，给定Q个传送门((x1,y1),(x2,y2)),表示点(x1,y1)到点(x2,y2)额外有一条路径耗时为3秒，给定起点与终点，问从起点走到终点的最短时间是多少。 分析:网格上点数为9e4,可以直接跑dij,网格加边和额外的Q条边.注意坐标化点:(x,y)---->点(x-1)*m+y . #include<bits/stdc++.h> using namespace std; #define ll long long #define inf 0x3f3f3f3f #define pr pair<int,int> i...

题目大意: 帕秋莉掌握了一种土属性魔法 这种魔法可以在一片k×k大小的一个正方形区域内产生地震 但是如果某片即将产生地震的区域内有建筑物，帕秋莉会停止施法 整个地图大小为n×m，其中一些地方有建筑 请问有多少种可能的情况，使得帕秋莉会停止施法. 分析：枚举 子矩阵，判断矩阵中是否有1.判断方法直接求子矩阵的元素和是否为0.----------求子矩阵元素和常规技巧表示从 到 所组成的矩阵元素的和。计算每 --(画图理解 如果要计算矩阵元素和计算公式为 .------(同上,画图理解 #include<bits/stdc++.h> using namespace std; ...

题目:一个数轴，每一个储物点会有一些东西，同时它们之间存在距离。每次给个区间 ,查询把这个区间内所有储物点的东西运到另外一个储物点的代价是多少？比如储物点 有 个东西，要运到储物点 ，代价为 就是储物点间的距离。 表示第i个储物点与第i+1个储物点的距离 表示每个储物点的东西个数 分析：对于区间的物品移动到第位置,显然是 .因为是多组询问显然是不可能直接暴力计算的.以为 是在变化的，我们可以预处理所有物品移动到指定的一个点的价值,我们指定移动到第一个物品的位置,根据位置先后维护移动代价的前缀和.那么移动位置从第物品的位置 变成了 物品的位置。 假如对于询问区间 , ,那么与我们预处理...

题目大意：给定 部电影,影片放映时间 ,对应 次影片放映的开始时间.求在 时间内可以连续观看电影的最少数量.(一部电影放映时可以切换另一部正在放映的电影)分析:状压dp 小于等于20，可以枚举所有选电影的方案. 表示 状态下连续放电影的结束时间. 考虑 的转移, 方案没有选的电影就是二进制位下为0的位置 ,因为 的放映时间是所以我们只要找到第 部电影放映时间在 之前即可.因为暴力枚举会TLE,而且给出放映时间的是单调递增,所以我们二分找即可. 答案就是所有符合 状态的下标 的二进制下 个数最小值. #include<bits/stdc++.h> using namespace...

题意:河宽 ，河中有 个石子，青蛙想要过河，青蛙每次可以跳 的距离,问青蛙过河至少要踩多少块石子。分析：经典的状态压缩dp. 我们先不考虑范围,先将所有石子的位置进行排序， 到第 的位置最少踩的石子数量.转移方程: 显然空间太大，那么考虑如何优化空间.其实很多 是没有意义的,假如 远大于 ,那么对于下标为 到下标为 的dp值 有很多部分并无实际转移价值。考虑压缩dp状态. 每次青蛙跳跃的距离是 ,那么 以后的距离是都能到达的，如果两个石子间的距离大于的话，我们将状态压缩为 .那么空间就优化完成了. 那么如何得到最终答案.我们并不知道终点在哪里，但是我们知道起点的位置。那么我们考虑从逆向dp...

题目大意：给定一棵树，每个结点上都有一个棋子，牛牛和牛妹两个人每次选择任意一个结点的棋子，将棋子移动到该节点子树下的节点位置。(不可以不移动)牛牛先手，牛妹后手。现在假设双方都采用最优策略，请问牛牛能否赢。如果牛牛（先手）能够赢，请问牛牛第一步有多少种不同的必胜策略。我们认为两个策略是不同的，当且仅当这两个策略一开始选择的棋子不同，或者移动的路径不同。 参考：Lskkkno1 大佬题解 (由于写的急,万分抱歉 https://blog.nowcoder.net/n/6650ed32a8d64f649dd0b370eb22edaa 分析: 前提知识： SG 函数定义与结论:(粗略解释)任何...

最近做的矩阵选数问题比较多，写一篇博客。 1.每个人戴不同帽子的方案数. https://leetcode-cn.com/problems/number-of-ways-to-wear-different-hats-to-each-other/ 题目大意:有n个人40顶帽子，每个人喜欢不同的帽子,求满足每人拿到喜欢帽子的方案数.(n<=10 )分析：看数据范围就是可以二进制暴力枚举,dp[i][j]表示前i顶帽子分分配方案为j ( j---二进制下 k位置为1 表示第k个人拿到喜欢的帽子 ) 的方案数.那么转移方程就是: class Solution { public: ...

https://ac.nowcoder.com/acm/contest/4912/C https://ac.nowcoder.com/acm/contest/5556/E 多重背包1 。 https://leetcode-cn.com/problems/form-largest-integer-with-digits-that-add-up-to-target/

分析:一个新的方法求任意区间小于等于k的个数.-------离散+树状数组.将询问按照 大小从小到大排序,并且将 也从小到大排序，然后根据询问从小到大插入到树状数组对应编号中,当大于时候更新询问答案.复杂度可以做到O(nlogn).十分优美的方法 #include<bits/stdc++.h> #define lowbit(x) x&(-x) using namespace std; const int maxn=1e5+10; int cnt,sum[maxn]; void add( int x,int c ){ while( x<=cnt ) sum[x]+=...

1.https://ac.nowcoder.com/acm/contest/5523/I 二分+整数分块 #include<bits/stdc++.h> using namespace std; typedef long long ll; ll n,m,q; int check( ll x ) { ll sum=0; for( int l=1,r;l<=x;l=r+1 ) { r=x/(x/l); sum+=1ll*min(x/l,m)*(r-l+1); } return sum; } int m...

题意：给定一棵树,第i个结点有 权值,删除一些结点的代价是删除结点的权值和,求满足树上任何一条链长度小于等于l的删除方案代价最小.(n<=5000, <=5000 )分析: 从n的范围可以知道复杂度可以是n^2,那么可以搞树形二维dp. 表示以第i个结点为根节点的子树满足最长链小于等于l. 那么我们考虑如何转移.对于当前节点x而言,我们定义 表示删除当前节点的子树满足最长链小于等于l-1的方案的最小值,显然 . 那么考虑 如何转移,都是保留x节点的方案，那么当前子树的最长链有可能是某两个子节点的最长链和当前节点合并产生---------(当前第一个子节点最长链那么另一个子节点就需...