wxyww

分类

未归档(12) 精品(28) 题解(65)

/ 注册

全部文章（共395篇）

[20181016上午][模拟赛]

题目思路全都是位运算，考虑按照二进制拆分进行dp。f[i][j]表示前i个数，二进制的第j位为1的概率。对于为0的概率，直接用(1-f[i][j])即可。然后就是转移，其实这个题转移蛮好想的，只要一点一点慢慢推就可以了。竟然用cin读入了100000个double。。。t飞了 ...

2018-10-16

0 376

[生成树计数]

prufer序列每个prufer序列对应一棵唯一的树。生成：得到一棵树的prufer序列的方法是依次去掉编号最小的叶子节点(也就是度数为1的点)，然后将这个点的父亲加入队列。直到剩下最后两个点。这样就可以得到一个长度为n的prufer序列。根据prufer序列的生成方式可以得到：每个节点会在...

2018-10-15

0 504

[生成树计数]

prufer序列每个prufer序列对应一棵唯一的树。生成：得到一棵树的prufer序列的方法是依次去掉编号最小的叶子节点(也就是度数为1的点)，然后将这个点的父亲加入队列。直到剩下最后两个点。这样就可以得到一个长度为n的prufer序列。根据prufer序列的生成方式可以得到：每个节点会在...

2018-10-15

0 426

[luogu1341][无序字母对]

luogu1341 思路欧拉回路和欧拉路的裸题，首先判断是否存在欧拉路或者欧拉回路。当且仅当途中每个点的度数都为偶数时，存在欧拉回路。当且仅当图中度数为奇数的点的个数为2时，存在欧拉路。如果存在欧拉回路，就可以找一个最小的点开始dfs。如果存在欧拉路，那就只能从度数为奇数的两个点中更小的那个开...

2018-10-14

0 396

[luogu1341][无序字母对]

luogu1341 思路欧拉回路和欧拉路的裸题，首先判断是否存在欧拉路或者欧拉回路。当且仅当途中每个点的度数都为偶数时，存在欧拉回路。当且仅当图中度数为奇数的点的个数为2时，存在欧拉路。如果存在欧拉回路，就可以找一个最小的点开始dfs。如果存在欧拉路，那就只能从度数为奇数的两个点中更小的那个开...

2018-10-14

0 362

[hdu5215][Cycle]

题目链接思路首先可以通过二分图染色找到奇环和一部分偶环。这个比较简单但是还有一种偶环容易忽略。如图(别问我为啥没节点4) 第一次可以找到1-2-3-1)这个奇环，第二次可以找到(3-5-6-3)这个奇环。但是(1-2-3-5-6-3-1)这个偶数环就被忽略了。再一种情况 ...

2018-10-13

0 445

[hdu5215][Cycle]

题目链接思路首先可以通过二分图染色找到奇环和一部分偶环。这个比较简单但是还有一种偶环容易忽略。如图(别问我为啥没节点4) 第一次可以找到1-2-3-1)这个奇环，第二次可以找到(3-5-6-3)这个奇环。但是(1-2-3-5-6-3-1)这个偶数环就被忽略了。再一种情况 ...

2018-10-13

0 409

[bzoj1563][诗人小g]

bzoj1563 思路首先考虑\(n^2\)的暴力dp，用sum[i]表示前i句话的长度总和。f[i]表示前i句话最小的不协调度之和。转移的时候考虑枚举前面的每个点，找到转移的最优秀的那个点。然后优化这个暴力。用一个队列存下当前个点之后的点中，哪个区间是从当前点转移更优秀(称为这个点的控制...

动态规划dp 决策单调性

2018-10-12

0 483

[bzoj1563][诗人小g]

bzoj1563 思路首先考虑\(n^2\)的暴力dp，用sum[i]表示前i句话的长度总和。f[i]表示前i句话最小的不协调度之和。转移的时候考虑枚举前面的每个点，找到转移的最优秀的那个点。然后优化这个暴力。用一个队列存下当前个点之后的点中，哪个区间是从当前点转移更优秀(称为这个点的控制...

动态规划dp 决策单调性

2018-10-12

0 396

[luogu3197][越狱]

luogu3197 思路看了很久没思路，看了题解发现自己好zz。用全部的情况减去不合法的情况就行了。全部的情况就是每个人随便选，总共有\(m^n\)种情况，然后考虑不合法的情况，也就是任意相邻的两个人不能信仰同一宗教，第一个人有m个宗教可以选，后面的每个人因为都不能和前面那个人相同，所以后面...

组合

2018-10-11

0 422