Luogu – Tgotp-Blog

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-5a6336b772aea[……]

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-5a6336b773acc491[……]

Read more

T16635 树集

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

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

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

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

c++代码如下:
[crayon-5a633[……]

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

T15683 切

题目背景

2017/11/01 T1

题目描述

给出一棵有n个结点的树,将其中的一些边切掉,使得每个节点至少有k个结点与之相连(包括自己),求方案数对786433取模的结果。

输入输出格式

输入格式:

输入第一行,包含两个正整数n,k。

接下来的 n-1 行,每行包含两个正整数[……]

Read more

P3939 数颜色

因为交换只会交换相邻两数,所以交换很好写。

用vector存一下每个颜色出现的位置,然后对于查找的颜色在vector上二分。

c++代码如下: