CantSayAWord-CSDN博客

原创 HDU 6194 string string string

题目链接：string string string 题意：问一个给定字符串中有多少个正好出现k次的子串题解：考虑k=1k=1和k≠1k\neq 1的情况，k≠1k\neq 1的时候直接用后缀数组，然后用单调栈维护一个长度为k−1k-1窗口的最小值（因为height数组代表的是两个后缀之间的关系），出栈的时候更新答案。k=1k=1的时候考虑当前后缀sa[i]sa[i]与sa[i−1]sa[i-1

2017-09-10 18:00:49 301

原创 Codeforces Round #430 (Div. 2) D. Vitya and Strange Lesson

题目链接：Vitya and Strange Lesson 题意：给出一个序列，询问每次xor一个数以后的序列的mex（mex是集合中最小的没有出现的自然数）题解：由于每一次询问以后序列都会改变，我们可以把每一个询问看成从最开始询问的数的前缀异或和，这样我们每一次操作的对象就是同一个序列了。考虑把原序列建立一棵Trie，那么显然，我们可以知道，二进制表示具有某一个特定前缀的数有多少个（即Tri

2017-08-30 11:52:37 503

原创 POJ 2912 Rochambeau

题目链接：Rochambeau 题意：一群孩子分成三组玩石头剪刀布，在某一组中的孩子只能出和其组对应的手势，其中有一个人是裁判，裁判可以任意出，问能否在给定的游戏场景中找到裁判并输出对应的信息。题解：由于NN很小，所以直接枚举裁判，和裁判有关的场次直接忽略，那么就成了一个权值并查集。最后如果只有一个人满足条件，输出能排除其他情况的最小场次。#include <stdio.h>#include

2017-08-28 20:32:20 393

原创 HDU 6155 Subsequence Count

题目链接：Subsequence Count 题意：给出一个0101字符串，有两种操作：1.1.将区间内的00变成11，11变成00；2.2.询问区间内有多少个不相同的连续子串。题解：先考虑如何算出一个01字符串有多少个不相同的子串，很容易得到一个dpdp转移方程dp[i][0/1]=dp[i−1][0]+dp[i−1][1]+1dp[i][0/1]=dp[i-1][0]+dp[i-1][1]

2017-08-21 09:00:47 374

原创 HDU 6068 Classic Quotation(2017 Multi-University Training Contest 4)

题目链接：Classic Quotation 题意：给定两个字符串S和T，然后给出k个询问，每次询问输入L,R，输出S的1,i和j,n拼接成的字符串中出现字符串T的期望次数。题解：记A_i表示字符串S的[1,i]能匹配多少个T，prei=∑ij=1Aipre_i=\sum_{j=1}^{i}A_i，B_(i,j)表示T匹配完S中[1,i]的字符后kmp指针指向的位置。cnti,j=∑ik=1B

2017-08-19 22:02:14 378

原创 HDU 6139 Galaxy at War(2017 Multi-University Training Contest 8)

题目链接：Galaxy at War 题意：在一个给定的n∗mn*m的棋盘内的若干个位置(xi,yi)(x_i,y_i)有wiw_i个水晶，同时有t个冥想球和ss个污染源，每一次可以选定一个位置(u,v)(u,v)，将tt个水晶移动到(u+1,v)(u+1,v)或者(u,v+1)(u,v+1)，如果这个位置有冥想球，那么可以在(u+1,v)(u+1,v)和(u,v+1)(u,v+1)处制造tt个水

2017-08-18 15:22:32 647

原创 HDU 6133 Army Formations(2017 Multi-University Training Contest 8)

题目链接：Army Formations 题意：一棵二叉树，每一个节点有一个信息aia_i，每发送一个信息需要的时间是当前时间tt加上这个信息的权值aia_i，问从每一个节点出发，发送完以这个节点作为根节点的子树中的所有信息所需要的最小时间。题解：显然，如果我们把一个权值大的放在前面，所有在这个信息后面的信息所需要的时间都会增加，于是我们贪心的发送，即按照权值从小到大发送就是最优方法。那么问题

2017-08-18 12:57:17 546

原创 HDU 6138 Fleet of the Eternal Throne(2017 Multi-University Training Contest 8)

题目链接：Fleet of the Eternal Throne 题意：给出nn个字符串，mm次询问，每一次询问一个(x,y)(x,y)，问第xx和第yy个字符串的最长公共部分使得这个部分是某一个字符串的前缀。题解：注意到如果两个字符串同时匹配到了某一个前缀，那么这个前缀的长度就可以用来更新答案，所以我们可以直接根据前缀建立AC自动机，然后对于每次询问在AC自动机上匹配，用setset判断是否

2017-08-17 17:17:32 691

原创 HDU 6086 Rikka with String(2017 Multi-University Training Contest 3)

题目链接：Rikka with String 题意：给定nn个0101字符串和一个长度LL，问所有长度为2∗L2*L的反对称字符串（s[i]≠s[|s|−i+1],i∈[1,|s|]s[i]≠s[|s|−i+1],i∈[1,|s|]）中出现所有给定字符串的种类数。题解：我们先考虑一个简化版的问题：所有长度为LL的字符串中出现所有给定字符串的种类数。这就是一个基本的AC自动机上dpdp的问题，记

2017-08-16 21:23:01 398

原创 HDU 6096 String(2017 Multi-University Training Contest 6)

题目链接：String 题意：给定NN字符串以及QQ个询问，每一个询问包括一个前缀和一个后缀，在前后缀不重叠的情况下，有多少个字符串有这个前缀和后缀。题解：把每一个询问以“后缀+‘｛’+前缀”形式连接起来组成新的字符串，并用这些字符串构成AC自动机，同时记录原询问的长度，最后把原来的NN个字符串在AC自动机中跑一遍记录长度满足条件的就能得到答案。由于可能有相同的询问，所以可以利用map或者并查

2017-08-16 14:33:36 325

原创 POJ 2482 Stars in Your Window

题目链接：Stars in Your Window 题意：你有一个W∗HW*H大小的矩形，每一颗星星有一个亮度属性，给出nn颗星星的坐标，问能看到星星的亮度和最大为多少（恰好在边上的不算）题解：经典的线段树+扫描线问题。先不考虑边界，如果我们把每一颗星星作为这个矩形的中心，那么当矩形中心位于这个矩形中的任意一点的时候，这颗星星是在矩形内的。那么当矩形中心被多个矩形覆盖的时候，这个矩形就包括了这

2017-08-16 14:15:13 315

原创 ZOJ 3525 Disappearance

题目链接：Disappearance 题意：每一个物品有B,W,H,SB,W,H,S四种属性，问能否选出一个物品的集合，使得前三种属性的极值小于给定值，且SS属性的和最小，如果答案不为负数，输出给定的字符串。解法：注意到NN只有10001000，所以我们可以直接枚举第一维，接下来的做法就和POJ 2482 一样了，线段树+扫描线即可。#include <bits/stdc++.h>using

2017-08-16 14:00:53 403

原创 HDU 6059 Kanade's trio(2017 Multi-University Training Contest 3)

题目链接：Kanade’s trio 题意：给出一个序列A，问存在多少个不同的三元组满足Ai xor Aj<Aj xor Ak (i<j<k)A_i\ xor \ A_j <A_j\ xor \ A_k\ (i<j<k) 题解：对于每一个数，我们把它转化成30位的二进制形式，并按照序列顺序依次插入到0/1字典树中，插入过程中，我们把当前插入的数作为AkA_k，每次计算其贡献加起来即为答案。我

2017-08-02 13:05:24 400

原创浅谈AC自动机（Aho-Corasick automaton算法）

前置技能KMP&&TrieAC自动机简介AC自动机全称Aho-Corasick automaton算法，是1975由贝尔实验室发明的一种多模式匹配的算法。常用于给定多个模式串并要求匹配的一类问题中。算法介绍我们先由一个问题开始：给出m个字符串，再给出一个字符串S，问，S中出现了多少次前面给出的字符串？根据我们以往的做法，除了暴力，一个比较容易想到的做法就是先把m个字符串插入到一棵Trie中，然后

2017-07-31 18:01:18 877

原创浅谈整体二分

整体二分这一算法出自许昊然同学的2013年信息学国家队论文《浅谈数据结构题的几个非经典算法》。其优点在于简短的代码量，可以在较低的代价下，简化很多需要使用复杂数据结构的问题。不同于传统的数据结构题的解题方法，整体二分是将所有操作进行二分，然后采用分治的思想来解决问题。问题能使用整体二分的前提：1.满足修改操作对询问的贡献独立，修改操作之间互不影响结果。 2.题目没有强制在线。那么前提1是什

2017-07-28 21:19:58 392

原创 HDU 6039 Gear Up(2017 Multi-University Training Contest 1)

题目链接：Here题意：给你一些齿轮以及齿轮之间的关系，然后每次有两种操作：1.把第x个齿轮的半径更改为y;2.给第x个齿轮一个大小为y的角速度，问所有齿轮中最大的角速度的自然对数是多少。解法：根据齿轮之间的连接关系（共角速度或者共线速度）建图，我们就得到了一片森林。每一棵树任取一个点作为参照点，然后对于操作对象所在的树单独考虑。先讨论操作1，如果被修改的节点的父节点和该节点是共角速度的，

2017-07-26 16:23:33 510

原创 Educational Codeforces Round 1 Tutorial

题目传送门：http://codeforces.com/contest/598A. Tricky Sum题意：问小于等于n的所有自然数与其系数乘积的和，其中所有2的次幂（包括0次幂）的系数为-1，其他数字系数为1。解法：直接根据公式求出自然数前n项和，然后枚举2的幂减去两倍即可。#include using namespace std;long long tt[33];

2017-07-21 14:43:16 382

CantSayAWord的博客