3 qq_38232157

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 7w+

UVA 1160 X-Plosives(算法竞赛训练指南,并查集)

并查集, 算法竞赛训练指南, 191页题目意思:所以的元素看做是顶点,每两点连线,如果图中存在环的话,就会爆炸本题要点:1、每次读入 a, b, 如果 a 和 b 在同一个集合,就舍弃这两点。#include <cstdio>#include <cstring>#include <iostream>using namespace std;const int MaxN = 100010;int a[MaxN], b[MaxN], fa[MaxN];in

2020-08-10 16:08:18

HOJ 1061 Rightmost Digit(快速幂,水题)

快速幂,水题本题要点:1、快速幂,mod = 10, 首先把 base 模 mod 一下。#include <cstdio>#include <cstring>#include <iostream>using namespace std;const int mod = 10;int T, n;int fastPow(){ int base = n % mod, res = 1; while(n) { if(n & 1) {

2020-08-10 09:55:44

HOJ 1686 Oulipo(KMP, 裸题)

KMP, 裸题题目意思:给出a, b 两个字符串,长度分别是 n, m, 求字符串a 在b 中出现的次数。本题要点:1、先求出 a 字符串的 next 数组2、然后在b 字符串 中匹配,指针i指向 b, 指针 j指向a, 当 j == n, j 回溯j = Next[j];#include <cstdio>#include <cstring>#include <iostream>using namespace std;const int MaxN

2020-08-09 14:29:24

HOJ 4135 Co-prime(容斥原理,素数)

容斥原理,素数题意:输入三个数a,b,n,求[a,b]之间与n互质的个数本题要点:1、转化:这题可以转化成求[1,b]内与n互质的个数减去[1,a]内与n互质的个数。而[1,x]内与n互质的数可以转化成x-[1,x]内不与n互质的数。接下来就是求[1,x]与n不互质的数2、素数打表:先找出n以内的质因数保存在数组a里,如果没有就将n保存在数组a里。然后用 n/a1 + n/a2 +.... 但有一个很明显的问题是会有重复的元素加进去,这就需要用到容斥定理了,将多余的给减掉。公式是

2020-08-09 12:26:27

HOJ 5776 sum(抽屉原理)

抽屉原理题目意思:有n个数,问存不存在连续子序列之和是m的倍数本题要点:1、抽屉原理有n+1件或n+1件以上的物品要放到n个抽屉中,那么至少有一个抽屉里有两个或两个以上物品。2、一个结论a1,a2,a3…am是正整数序列,至少存在整数k和r,1<=k<r<=m,使得ak+a(k+1)+…+a®是m的倍数。3、具体步骤用sum来记录数组a的前缀和,a) 如果某个 sum[i] % m == 0, 说明 sum[i] = a[1] + a[2] + … + a[i]是 m

2020-08-08 23:45:21

POJ 2356 Find a multiple(抽屉原理,前缀和)

抽屉原理题目意思:n个数任取若干个, 这些数的和是n的倍数, 输出其中的任意一种取法,输出元素的下标即可本题要点:1、抽屉原理有n+1件或n+1件以上的物品要放到n个抽屉中,那么至少有一个抽屉里有两个或两个以上物品。2、一个结论a1,a2,a3…am是正整数序列,至少存在整数k和r,1<=k<r<=m,使得ak+a(k+1)+…+a®是m的倍数。此题中,必定存在解。3、具体步骤用sum来记录数组a的前缀和,a) 如果某个 sum[i] % c == 0, 说明 sum

2020-08-08 20:04:40

POJ 3981字符串替换(string, 水题)

字符串,水题本题要点:1、使用 string 的 find 和 replace 函数,每次读取一行,对该 string 操作,然后输出即可#include <cstdio>#include <cstring>#include <iostream>#include <string>using namespace std;int main(){ string str; int pos; while(getline(cin, str))

2020-08-08 18:10:20

HOJ 1205 吃糖果(抽屉原理)

抽屉原理本题要点:1、先找出数量最多的一种糖果,假设有N个, 其他所有的糖果有 S个。把N种糖果看做是N块挡板,其他的S个 糖果放在挡板之间。2、如果 S < N - 1, 说明至少有两个挡板之间没有放 糖果,而这两个挡板是同一种糖果,所以无解3、如果 S >= N - 1, 肯定有解。把S个糖果排队,其中同种类的糖果是连续的。每次取N个糖果,按顺序一个一个放到N个空间,由于隔板的数量比每一种的糖果数量都多,因此不可能有两个同类的糖果放到同一个空间。#include <

2020-08-08 18:07:19

POJ 3370 Halloween treats(抽屉原理,前缀和)

抽屉原理题目意思:n个数任取若干个, 这些数的和是c的倍数, 输出其中的任意一种取法,输出元素的下标即可本题要点:1、抽屉原理有n+1件或n+1件以上的物品要放到n个抽屉中,那么至少有一个抽屉里有两个或两个以上物品。2、一个结论a1,a2,a3…am是正整数序列,至少存在整数k和r,1<=k<r<=m,使得ak+a(k+1)+…+a®是m的倍数。3、具体步骤用sum来记录数组a的前缀和,a) 如果某个 sum[i] % c == 0, 说明 sum[i] = a[1]

2020-08-08 16:42:27

HOJ 4825 Xor Sum(字典树,异或)

字典树本题要点:1、n个数字,按二进制展开,取32位,看做是 32位 的 01 字符串,每个数字对应一个字符串,n个字符串,建立一颗字典树。2、对于m次查询,每次查询的数字 x 按二进制展开,某个数字如果是 0, 那么在字典树上按相反方向走,并累加每一位是1 的值,最后得到的 查询值 query 是数字x 和字典树某个数y的异或值query = x ^ y, 因此,y = query ^ x = x ^ y ^ x = x。#include <cstdio>#include &l

2020-08-06 00:26:08

HOJ 2222 Keywords Search(AC自动机,模板题)

AC自动机,模板题, 参考:https://blog.csdn.net/bestsort/article/details/82947639题目意思:给出若干字符串,最后给出一个大的文本字符串,求前面的字符串,在文本字符串中一共出现了多少次本题要点:1、AC自动机用若干模式串,建立字典树,同时为每一个字典树的每一个节点,建立 fail 数组。2、查询文本串, 统计文本串中出现的模式串的次数。#include <cstdio>#include <cstring>#inc

2020-08-05 21:52:34

CodeForces 1137B Camp Schedule(KMP的next数组)

KMP的next数组, 参考:https://blog.csdn.net/weixin_42102584/article/details/88360361题目意思:给出两个0-1字符串s和t,问如何重排s可以使得产生的新字符串中包括最多的连续子串t,输出重排结果。本题要点:1、对字符串 t 计算 next 数组, next[lent] 就是字符串t的最长的前后缀, 假如 next[lent] == idx,坐标范围 [1, idx] 这部分字符串假设是 x坐标范围 [idx + 1, lent]

2020-08-05 20:54:07

HOJ 2087 剪花布条(KMP,裸题)

KMP,裸题本题要点:1、先求出a字符串的next数组2、再用b字符串和a数组来匹配,注意,每次匹配完成,就剪断对应的字符串,因此,当 f[i] == n, 把 j 置零#include <cstdio>#include <cstring>#include <iostream>using namespace std;const int MaxN = 1010;char a[MaxN], b[MaxN];int Next[MaxN], f[MaxN];

2020-08-05 10:57:27

HOJ 4632 Palindrome subsequence(回文串,区间DP)

回文串,区间DP题目意思:找一个字符串里有多少个回文子序列。本题要点:1、转态表示:dp[i][j] 表示从i到j有多少个回文子序列2、转态转移dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]如果 s[i] == s[j], dp[i][j] = dp[i][j] + dp[i + 1][j - 1] + 1#include <cstdio>#include <cstring>#include &

2020-08-03 20:33:59

POJ 3280 Cheapest Palindrome(回文串, 区间DP)

回文串题目意思:给出一个字符串,然后给出n个字符,删除该字符和插入该字符的花费。问:删除或插入若干字符,使得该字符串变为回文串,所需要的代价花费最少。注意到,删除某个字符和插入某个字符是等价的,用数组 w 存放某个字符 删除后插入的较小值即可。本题要点:1、状态表示:dp[i][j] 表示s的子区间 [i, j] 变为回文串的最小花费2、转态转移:dp[i][j] = dp[i + 1][j - 1], s[i] == s[j]dp[i][j] = min(dp[i + 1][j] +

2020-08-03 11:59:02

HOJ 1003 Max Sum(LIS,基础DP)

LIS,基础DP题目意思:找到连续的子段,使得其和是最大的。输出 最大的和, 起点,终点。本题要点:1、状态表示:dp[i] 表示以a[i] 为结尾的最大连续子段的总和2、状态转移:dp[i] = dp[i - 1] + a[i], 如果dp[i - 1] >= 0dp[i] = a[i], 如果dp[i - 1] < 0#include <cstdio>#include <cstring>#include <iostream>usi

2020-08-02 18:12:22

HOJ 1257 最少拦截系统(LIS, 裸题)

LIS题目的裸题序列的最长递增子序列的长度,就是最少需要的导弹拦截系统本题要点:1、转态表示dp[i] 表示以第i个数为结尾的最长递增子序列的长度2、转移方程dp[i] = max{0, dp[j]}, high[j] < high[i], 0 < j < i#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using na

2020-08-02 16:27:41

HOJ 5119 Happy Matt Friends(基础DP, 滚动数组)

基础DP, 滚动数组题目大意:给你N个数,问有多少个子集,满足子集内所有数的xor和大于等于M本题要点:1、状态表示:dp[i][j] 表示前i个数,xor和为j的情况有多少种.这里用滚动数组(来两行数组)来存, long long dp[2][MaxN]。2、状态转移:dp[i][j] = dp[i - 1][j] + dp[i - 1][j ^ a[i]]dp[i - 1][j] 表示不选 a[i] 这个数dp[i - 1][j ^ a[i]] 表示选择a[i] 这个数(注意到 j ^

2020-08-02 12:48:44

HOJ 1024 Max Sum Plus Plus(线性DP,滚动数组,经典)

题目意思:本题的大致意思为给定一个数组,求其分成m个不相交子段和最大值的问题参考:https://www.cnblogs.com/kuangbin/archive/2011/08/04/2127085.html状态dp[i][j]有前j个数,组成i组的和的最大值。决策: 第j个数,是在第包含在第i组里面,还是自己独立成组。方程 dp[i][j]=Max(dp[i][j-1]+a[j] , max( dp[i-1][k] ) + a[j] ) 0<k<j空间复杂度,m未知,n<

2020-08-02 11:15:36

HOJ 1425 sort(排序,快排)

排序,快排本题要点:1、利用快排,可以在 O(n) 的时间内,找出第k大的数。2、再用 sort 对 前 m 个数进行排序#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int MaxN = 1000010;int a[MaxN];int n, m;bool cmp(int a, in

2020-08-01 18:18:14

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。