Luogu – Tgotp-Blog

P3396 哈希冲突

一开始看着题目毫无思路...
只有一个暴力才能维持的了10分的样子...
想着打开时的标签:分块....
死活不会统计...
然后弃疗...
换了一个方向思考,,,
首先如果查询x > y肯定都不用管..直接输出0
考虑模数在n范围以内,那么对于模数特别大的情况,[......]

Read more

2018年4月17日 0 / /
Tag:  No Tags

P3806 【模板】点分治1

既然已经说了是模板,那么考虑怎么套用点分治。
容易想到记录到所有值的方案数,但是发现瓶颈在于每次结束以后去枚举答案。
因为k在1kw,显然单次统计都会有1kw的复杂度,考虑优化,发现实际上只有不到1w个取值,
那么在每次新增一个取值的时候去更新即可,然后现在又有一个问题在于每次新查找的时候数组[......]

Read more

P2858 [USACO06FEB]奶牛零食Treats for the Cows

令f[i][j]表示正向选到第i个,倒向选到第j个点,

那么 f[i][j] = max(f[i - 1][j] + a[i] * (i + j),f[i][j - 1] + a[n - j + 1] * (i + j));

c++代码如下:
[crayon-5bf0969d094b3[......]

Read more

Permutation

permutation.cpp/in/out
Time limit: 1s
Memory limit: 512MB

定义一个长度为 n 的排列 p 的生成图为一个 n 个点 n 条边的有向图,且该有向图的第 i 条边
为 i 指向 pi 的有向边
由于排列的定义,该图每个点的入度与出度[......]

Read more

2018年1月10日 0 / /
Tag:  No Tags

送你一个 DAG

Description
送你一个 n 个点 m 条边的 DAG 和参数 k, 定义一条经过 l 条边的路径的权值为 l
k
.
对于 i = 1...n, 求出所有 1 到 i 的路径的权值之和, 对 998244353 取模.
1.2 Input Format
第一行三个整数 n, m[......]

Read more

送你一棵圣诞树

求一遍dfs序,然后对于两个同种相邻颜色的lca的id[x]-=1,

然后用树套树维护,用树状数组维护颜色,线段树维护区间权值和。

然后还要用一个set记录颜色的位置。

具体看代码、

(可读性“极佳”

c++代码如下:
[crayon-5bf0969d09eb1990[......]

Read more

T16635 树集

考试中沙茶的没写出来TAT。

其实很水辣,考虑选出的区间最小与区间最大不能超过d/

固定区间最小,o(n)寻求答案,加起来就好了。

上午卡死在相同权值两点如何去重上面,其实就加一个判断,编号小的才能去统计编号大的的答案就ok了。

c++代码如下:
[crayon-5bf09[......]

Read more

P2258 子矩阵

暴力枚举选行的情况,然后dp求选列的最优情况。

f[i][j]表示选了i行,最后一次选的是j列的情况。。。

c++代码如下:

 

T16110 小象涂色

题目描述

小象喜欢为箱子涂色。小象现在有 c 种颜色,编号为 0~c-1;还有 n 个箱子,编号

为 1~n,最开始每个箱子的颜色为 1。小象涂色时喜欢遵循灵感:它将箱子按编号排成

一排,每次涂色时,它随机选择[L,R]这个区间里的一些箱子(不选看做选 0 个),为

之涂上随机一[......]

Read more

T15832 有趣的拖拉机

题目背景

回忆当年lyc,与xd,cyh,zjc三巨牛玩拖拉机的场景还历历在目。其中有一局 zjc和我打A,摸牌时都没人亮牌。刚摸完牌时,zjc突然说:“我手上有个A”。此时cyh开始嘀咕了,可能zjc不止有一个A吧。可是仍然没有人亮牌。就在要翻底牌的时候,zjc将手中的黑桃A亮了出来,此时xd大[......]

Read more