wxyww

未归档

精品(28) 题解(65)

/ 注册

全部文章 / 未归档（共302篇）

[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

[luogu3197][越狱]

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

组合

2018-10-11

0 410

[luogu1655][小朋友的球]

luogu1665 思路一道第二类斯特兰数的模板题。只不过需要写个高精。 f[i][j]表示前i个球放到j个盒子里的方案数。第i个球可以单独一个盒子，所以f[i][j]+=f[i-1][j-1]。还可以与前面的放到同一个盒子里，所以f[i][j]+=f[i-1][j]*j 代码 #inc...

组合

2018-10-11

0 378

[luogu1655][小朋友的球]

luogu1665 思路一道第二类斯特兰数的模板题。只不过需要写个高精。 f[i][j]表示前i个球放到j个盒子里的方案数。第i个球可以单独一个盒子，所以f[i][j]+=f[i-1][j-1]。还可以与前面的放到同一个盒子里，所以f[i][j]+=f[i-1][j]*j 代码 #inc...

组合

2018-10-11

0 534