anthony1314

ACM题目和算法

acm(40) C++(1) codeforces(1) DP(1) hdu(1) Java(4) Linux(2) Maven(1) MySQL(1) OJ----codeforces(6) OJ----hdu(4) OJ----POJ(1) OJ----牛客(1) poj(1) Python(2) Web(3) 二分算法(1) 动态规划(1) 数据库(1) 数据结构----树状数组(1) 未归档(55) 比赛----2019暑假hdu多校(1) 牛客(1) 软件工程(1) 随笔(1)

/ 注册

全部文章 / ACM题目和算法（共130篇）

杜教BM板子线性递推

导入8个以上基本稳 #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <st...

2019-03-20

0 475

矩阵快速幂之矩阵构造的基本思想

矩阵与DP a[i]=a[i-1]+b[i-1]+1,b[i]=2*a[i-1]-5 ;a[1]=1,b[1]=1,问a[x]=?,b[x]=? 很简单的递推，一步步推即可，但是，如果x是10^9，如何推？思维：递推式可以化为矩阵乘积那么，矩阵A[i]=A[i-1]*B; A[i+...

2019-03-18

0 440

poj1328 Radar Installation 【贪心】

题意：有n个小岛，在x轴上方，有一种雷达，覆盖范围为d，现在你可以在x轴以及x轴下方建立雷达，请问最少建立多个雷达可以覆盖所有的小岛题解：这是一道很经典的贪心入门题目，从看到题意我们就知道雷达建在x轴上是最优的，那么应该如何对这些小岛进行处理呢，我们可以将每一个小岛的坐标信息来推...

2019-03-14

0 410

poj2965 - The Pilots Brothers' refrigerator 【枚举 + 思维】

题意：给你一个 4* 4的表格分别为 + 和 - 现在你可以将一个“+”翻转成“-”，那么必然会把对应的行和列上的所有点翻转一次求将所有位置都变为 - 最少要翻转多少个一开始以为要暴力dfs 但其实不用只要开一个 2维数组对加号的位置进行标记 AC_code: /* ...

2019-03-14

0 420

poj1753 Flip Game 【dfs + 暴力枚举】

题意：给你一个只有黑白棋的4*4的棋盘你有一种操作你可以对其中某一个位置的棋子进行翻转使其变换颜色，而且该棋子上下左右都会进行翻转请问最少进行几次操作可以使得棋盘颜色一致如没有就打印“Impossible” 题解：因为该棋盘只有16个格子，且每个格子无论翻转多少次，都只有...

2019-03-13

0 540

hdu4707 Sum 【整数和拆分 + 快速幂 + 费马小定理降幂】

题意：给你一个很大的n，要你求n的拆分有几种方式，答案模1000000007. 把n进行拆分，可以看出n个1进行隔板，答案就是 2 ^(n - 1) 由于n的数字较大，用费马小定理进行降幂 a^n % p== a^(n - (p-1) - ....- (p-1)) % p...

2019-03-10

0 571

hdu3591 The trouble of Xiaoqian [多重背包 + 完全背包 + 01背包]

题意：消费者有n种硬币，每种硬币的价值为v[i]，数量为c[i]，而超市有消费者拥有的每一种硬币，且每种有无限个，每次去买东西，如果要找钱的话，超市会给你最少的硬币数，给你一个数t，要你求出，最少需要用到的硬币数量在本次交易中（消费者需要携带的硬币数量 + 超市找钱给的硬币数量）。（t&...

2019-03-10

0 642

hdu5119 Happy Matt Friends [01背包 + 异或和]

题意：给你n个数字，和m，让你求从这n个数字里面抽取若干个数字，其异或和不小于m的方案数。题解： m的取值范围不超过 1000000 建一个二维的dp数组，通过滚动来进行dp 状态转移方程式为：dp[i%2][j] = dp[(i-1)%2][j] + dp[(i-1)%2][j^...

2019-03-10

0 1126

HDU2639 ( Bone Collector II )【01背包 + 第K优解】

题目：学过01背包都知道有道入门题目叫 Bone Collector（hdu2606）, 给你n个石头，每个石头占背包的v[i] 容量，价值为w[i]，给你背包的容量，要你求出所能得到的最大价值，也就是最优解，这道题的升级版就是要你求第k优解。思路：我们找到01背包的原理就是通过状态...

2019-03-10

0 422

hdu2433 Travel bfs+最短路树（预处理）

给你n个点，m条双向边，每条边的长度都为1，求删去第i条边后，每个点到其他点的最短路的距离之和. //题意很不清晰网上有最短路spfa 和djskra 的做法，而且代码可以ac，但是代码是错的，只是刚好卡着时间过了由于每条边的长度都一样，而且根据答案我们可以得出，每一个点到其他...

2019-03-09

0 353