- 博客(30)
- 收藏
- 关注
RSS订阅原创 CodeForces - 1051D Bicolorings（dp）
题意：给定一个2*n的矩形，有黑白两种颜色，定义两个小方格相邻如果他们的边界挨着并且颜色相同。求分成k个部分的方案数对998244353取模。思路：dp[i][j][2]代表第i列分成了j块，此时第i列的状态为0或1.0代表第i列颜色相同1代表第i列颜色不同这样先确定j=1时的情况。j=1时,dp[i][j][0] = 2;后面的状态转移方程就比较好推出来了j>...
2018-09-28 17:13:18
251
原创 hdu 6390 (欧拉函数+莫比乌斯反演)
给出一个表达式 求解首先，设p为a，b共同的质因数phi(n) = p^α = (p-1)*p^(α-1)phi(ab) = (p-1)*p^(α1+α2-1)phi(a) = (p-1)*p^(α1-1)phi(b) = (p-1)*p^(α2-1)phi(ab)/(phi(a)*phi(b)) = p-1/p;这样原式子就能转化为若p只为a或b的质因子，...
2018-08-14 11:11:58
1022
原创 Subsequences CodeForces - 597C (树状数组+dp)
题意：给定一个长度为n的序列，给定一个k，求上升序列长度为k+1的序列数思路：dp[i][j]表示到第i个数位置，上升序列长度为j的个数。dp[i][j] = sum(dp[k][j-1]) (k<i)直接三重循环复杂度肯定不够所以考虑用树状数组来优化#include<cstdio>#include<cstring>#include&l...
2018-08-13 10:05:47
342
原创 hdu 2256(矩阵快速幂)
思路：用double来计算显然精度是不够的，先把2放进去就变成了（5+sqrt(6)）^n。展开之后可以发现是an+bn*sqrt（6）的形式。同样的，我们有(5-sqrt(6))^n = an - bn*sqrt(6).(5+sqrt(6))^n + (5-sqrt(6))^n = 2*an,又因为0 < (5-sqrt(6))^n < 1,所以(5+sqrt(6...
2018-08-10 10:01:51
209
原创 hdu 6315(多校第二场)
题意：给出一个b序列，还有一个a序列初始全为0。对a有两种操作，一种是add操作，对【l,r】区间所有数加1.一种是查询，对【l,r】区间求sum ( floor(ai/bi)）.思路：用线段树来维护一个区间最小值，维护一个sum。首先将序列b插入到线段树中，每次add时对区间进行减1操作，当区间最小值减到0时，跟新sum，0重新变为b[i]。#include <iostream&...
2018-07-26 21:22:33
299
原创 hdu 6305(多校第一场)
题意：定义RMQ（A，l，r）为序列A满足A[i] = max(A[l],A[l+1],......,A[r])中最小的i。如果RMQ（A，l，r）= RMQ（B，l，r），则称他们相似。给出A序列，B序列中元素为0-1的实数，求出满足RMQ（A，l，r）= RMQ（B，l，r）的B序列所有元素和的期望。思路：找出所有与A同构的笛卡尔树。对于每一个节点，与A同构的概率为这个节点子树的大小（包括...
2018-07-26 10:48:19
289
原创 hdu 6299 (多校第一场)
题意：给出一些字符串，重新组合，使括号的匹配数量最多这道题场上没能出，当时看了一眼，关于括号的，以为是个dp，就没有再去做这道题。这道题事实上是个贪心，先把已经匹配好的括号数量统计出来。剩下的括号往两边堆，右括号往左边堆，左括号往右边堆。然后就是排序。左括号比右括号多的这种情况肯定要排在右括号比左括号多的前面。左括号都比右括号多时，就按照右括号少的在前面右括号都比左括号多时，就...
2018-07-24 11:01:53
347
原创 Lightoj 1124 (容斥+lucas)
题意：有k个区间【l,r】，从每个区间选一个数使他们和为n，问有多少种方法。思路：这个问题可以转化为k个【0，r-l】的区间 ，每个区间选一个数使他们和为n-sum（l）。令n = n-sum(l).这样通过隔板法，就能得到方案数位C（k+n-1,k-1）。但因为会有超出的情况，所以通过容斥去判断超出的情况。超出0个时候加，超出1个的时候减，超出2个的时候加，超出3个的时候减……最后二进制枚举子集...
2018-04-26 22:31:34
228
原创 POJ 1284 (原根)
题意：给一个奇素数，求它原根的数目。定理：如果p有原根，则他有phi(phi(p))个原根，p为素数是，phi(p) = p-1，原根数量就为phi(p-1)；下面给出原根的求法：对于数m，先求ϕ(m) 的素幂分解式，即 φ(m) = p1^e1*p2^e2*……*pk^ek;然后枚举g，若g满足g^(φ(m)/pi )!= 1 (mod m) ,i = 1,2,3…...
2018-04-17 10:19:24
205
原创 POJ 1150 (数论)
题意，求n！/(n-m)!末尾第一个非零的数是什么。思路：这题折腾了我一晚上，终于搞明白了。以10！为例，首先，要去除末尾的0，要把因子10去除，但10不是质数，所以就考虑2*5；去除所有的2，5；例如：1 2 3 4 5 6 7 8 9 10，去除了因子2和5之后，就变为了1 1 3 1 1 1 7 1 9 1；那么这就相当于一个子问题了，我们可以用递归来求解。这样，整个序列就只剩下1 3 7 ...
2018-04-16 22:52:20
273
原创 poj 1077 (康托展开+bfs)
这是一个八数码问题，正好学习了康托展开，就做了这题，和hdu1043很像。康托展开并不难理解，其实就是一种hash。先上模板方便以后自己看。康托展开：int Contor(int str[],int n){ int ans = 0; for(int i = 0; i < n; i++) { int cnt = 0; for(int j...
2018-04-13 23:07:56
217
原创 Fzu 2282 (错排 组合)
题意：给n个数字，求至少k个数字位置不变的排列数量。思路：求至少k个人位置不变只要用全排列的数量减掉0-k错排的数量即可错排公式：Dn = (n-1)*(Dn-2+Dn-1);错排的数量为C(n,i)*Dn;#include <iostream>#include <cstdio>#include <algorithm>#include <cstrin...
2018-04-10 12:09:54
221
原创 Light OJ 1079 (概率 01背包)
题意：harry要去抢银行，他要在被捕率低于p的情况下抢到最多的钱给出n个银行的钱和被捕的概率。思路：看出了是个01背包，不过概率的01背包还是第一次遇到。dp[j]为抢j的钱时不会被捕的概率dp[j] = max(dp[j],dp[j-m[i]]*(1-p[i]));#include <iostream>#include <algorithm>#include <...
2018-04-09 21:46:19
123
原创 Poj 3734（矩阵快速幂）
题意：给定N个方块排成一列，现在要用红，蓝，绿，黄，四种颜色的油漆给这些方块染色。求染成红色的方块数和染成绿色的方块数同时为偶数的染色方案的个数。输出对10007取膜；思路：我们试着从左往右染色，设染到第i块为止，红绿色都为偶数的方案数位ai，红绿色恰有一个为偶数的方案数为bi，红绿色全为奇数的方案数位ci；这样染到第i+1块，红绿色都为偶数的有如下两种方案：1.到第i为止红绿都是偶数，第i+1个...
2018-04-09 19:52:08
230
原创 Gym 101606F Flipping Coins(概率dp)
题意：给n枚硬币，初始全部反面向上，有k次机会挑选一枚硬币抛，求正面向上的最大数学期望。思路：求的是最大数学期望，所以只有两种情况。1.i<n时，挑选反面向上的硬币抛，朝上朝下的概率都为0.5；2.i==n时，这时全部都是反面朝上，挑选一枚硬币抛，朝上朝下的概率都为0.5；这样就可以得出dp方程；dp[i][j]表示第i次抛，有j枚硬币朝上。i<n时，dp[i+1][j] += dp[...
2018-04-09 17:44:40
204
原创 Gym 100623J Just To Lucky(数位dp)
题意：1-n中有多少个数满足本身能被各个数位的和整除；思路：n是10的12次方，很快就能想到是数位dp，当时没板子，忘了数位dp怎么敲了，后来看了下题解，还是挺裸的数位dp。dp[pos][sum][remain][mod];pos:代表当前数位sum:各数位之和remain:当前枚举的数mod:枚举的膜9*12=108，所以只要枚举1-108即可；#include <iostream>...
2018-04-09 16:46:10
356
原创 Zoj 3344 （第一类斯特林数）附第二类斯特林数和Bell数的总结
题意：有个游戏，两个人玩。有n个卡片，洗牌后放入编号为1到n的盒子里，然后两个人轮流做如下操作，拿出盒子中编号最小的卡片k，然后再去编号为k的盒子中拿出卡片，依次类推，直到没有卡片可拿为止。拿走最后一张卡片的玩家获胜。求先手能够在K次操作以内获胜的概率，（以分数形式输出）思路：就是一个第一类斯特林数，然而并不会斯特林数，学习了一波，先上代码，下面是对第一第二类斯特林数，还有Bell数的总结。这题要...
2018-04-02 11:30:25
324
原创 UVa 1218 (树形dp)
很久之前做的题，今天又做到了，顺手来补一下题解。。。题意：有n台电脑，互相以无根树的方式连接。现在将其中一些电脑作为服务器，且要求每台电脑有且必须连接一台服务器。（不包括本身是服务器的电脑），问需要多少台电脑作为服务器。思路：设u是父亲，v是u的孩子。d(u,0):u本身是服务器；d(u,1):u不是服务器，u的父亲是服务器。d(u,2):u不是服务器，u的父亲不是服务器，u的孩子必须有且只有一个...
2018-04-02 10:28:54
314
原创 hdu 4370（最短路）
题意：给了一个n*n的矩阵，我们需要构造另一个矩阵满足以下要求1.X 12+X 13+...X 1n=1 2.X 1n+X 2n+...X n-1n=1 3.for each i (1<i<n), satisfies ∑X ki (1<=k<=n)=∑X ij (1<=j<=n). For example, if n=4,we can get the follo...
2018-03-22 23:11:17
402
原创 poj 1502 (最短路)
题意：给n个点，边的关系呈一下下三角的形状给出，求第一个处理器到其他处理器最短的时间思路：裸的最短路，直接用Dijkstra即可#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <queue>using name...
2018-03-22 22:16:35
405
原创 POJ 2184 （01背包）
题意：给出了n头牛的智力值和幽默值，要求智力值和幽默值和的最大值；思路：这是一个01背包问题，要么选要么不选，但由于智力值和幽默值都存在负值，那么问题就是怎么处理负值。我们只需要把数组延长一倍即可。dp[i]代表智力为i时幽默值的最大值。dp[j] = max(dp[j],dp[j-a[i]]+b[i]);需要注意的是在处理负数的时候要从0开始循环；代码：#include <iostream...
2018-03-20 11:07:33
258
原创 POJ 1236 （Tarjan+缩点）
题意：对于一个DAG，至少要选多少个点才能从这个点到所有点，至少要添加多少条边才能从任意一点到所有点。思路：对于第一问，用Tarjan求出强联通分量，缩点后求出入度为0的点就是答案。对于第二问，在缩点后求出入度为0，初度为0的个数，取最大值就是所要添加边的条数。注意对强联通分量只有一个时的特判。#include <iostream>#include <cstring>#...
2018-03-15 22:23:50
187
原创 POJ 3180 (Tarjan)
题意：给n给点，m条边，求连通分量>=2的强联通分量数；思路：直接上模板即可scc_cnt为SCC的计数器，sccno[i]为i所在的SCC编号。#include <iostream>#include <algorithm>#include <cstring>#include <cstdio>#include <vector>...
2018-03-15 21:20:17
244
原创 POJ 2186 （Kosaraju）
题意：每头牛都想成为牛群中的红人，现在又N头牛和M个有序对（A，B）。（A，B）表示牛A认为牛B是红人。该关系具有传递性，所以如果A认为B是红人，B认为C是红人，则A认为C是红人。求被其他所有牛认为是红人的牛的总数。思路：假设有两头牛A和B都被其他所有牛认为是红人。那么显然，A被B认为是红人，B也被A认为是红人，即存在一个包含A，B两个顶点的圈，或者说A，B属于同一个强联通分量。反之，如果一头牛被...
2018-03-15 19:46:22
205
原创 POJ 3074（DLX）
同样是数独的题，不同于poj 2676和2918，这题给的空白格很多，直接用dfs会超时，需要进一步的优化。自己剪了半天的枝还是超时，搜了题解，发现了一种新的算法Dancing Link X（DLX），关于这个算法，推荐一篇博客https://www.cnblogs.com/grenet/p/3145800.html，这篇博客里写的很清楚了。这样，我们就能把求解数独转换为精确覆盖问题。关键在于如何...
2018-03-15 15:41:05
277
原创 POJ 2676 （dfs）
题意：给一个9*9的数独，其中已经填了一些数了，需要填上剩下的空，如有多解随意输出一解即可。思路：由于这题初始给的数很多，所以直接dfs不用剪枝也可以过。数独需要每一行每一列，9个3*3的区域内不能有重复的数字。对于每一行每一列的判断很容易，关键在于子网格的判断。参考了大佬的思路，设子网格的编号为0-8，设一个小格（i，j）（0<i<9,0<j<9）的编号为k则3*（i/3...
2018-03-14 22:53:13
302
原创 HDU4099（Trie）
题意：输入一个数，这个数是斐波那契数列的前缀，求满足这个前缀的最小的下标。给出的数不超过40位，若满足这个前缀的最小下标超过100000则输出-1。思路：将斐波那契的前缀放到字典树中，由于两数相加有可能会进位，我们把斐波那契的前60位放到字典树中，这样就不会因为进位而产生误差。#include <iostream>#include <cstring>#include &...
2018-03-13 17:37:18
200
原创 hdu 1247 (Trie)
题意：给一些单词，问哪些单词能有另外两个单词组成思路：先去找一个单词的前缀，去除前缀后再去找单词的后缀#include <iostream>#include <cstring>#include <cstdio>#include <algorithm>using namespace std;struct node{ int co...
2018-03-12 23:12:35
132
原创 hdu 1251
题目：Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀). Input输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串. 注意:...
2018-03-12 21:51:21
126
原创 UVA11732 (Trie)
题意：给n个字符串，让他们两两比较，求比较的次数。如strcmp("than","that"),strcmp("there","the")各需要7次比较。思路：简单的模拟肯定不行，所以建立字典树。val数组代表经过该节点的单词书。添加一个isEnd数组来处理两个单词相同时的情况。#include <iostream>#include <cstring>#include
2018-03-12 19:39:58
138
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人