dujvet-CSDN博客

原创 codeforces基础题——#161(div2) E

#161(div2) E题目大意：(这题我TM读了好久)有一个n * m(1 <= n, m <= 1000)的棋盘，第i行第j列的点有一个非负权值aij，现在给你一个整数k，你需要找到一个位置(x, y)满足 k <= x<= n - k + 1, k <= y <= m - k + 1且使得的值最大题解：暴力解法，正解下篇再说。我们把这个式子分析一下，把它代表的值画到图里假设k

2016-09-16 22:42:37 261

原创 codeforces基础题——#356(div2) D

#356(div2) D题目大意：你有一些边长为正整数的立方体，边长为i的立方体体积为i * i * i，现在有人要用这些正方体搭塔，每种边长的正方体都有无限多个，如果现在给定体积正方体的总体积k，那么它会采用一种贪心的方法，每次选用可选的体积中最大的来搭塔，问所有正方体体积和小于m(1 <= m<= 1e15)是最多有多少个正法体组成，如果有多组解则输出体积最大的举个例子，当m =

2016-09-15 23:50:51 251

原创 codeforces基础题——#356(div2) C

题目大意：交互题有一个2到100之间的整数，每次你可以询问它是不是一个值的倍数，有20次询问机会，最后输出他是质数还是合数题解：这题本来不想说的，但人家好不容易出了道交互题，还是说一下吧。如果询问的话我们一定会询问质数，但小于100的质数有二十多个，很容易就会被卡，但我们发现如果这个数是一个大于50的质数的倍数，那么这个数一定就是这个质数，因为他小于100，不可能在含有别

2016-09-15 23:25:35 237

原创 codeforces基础题——#357(div2) D

#357(div2) D题目大意：有一颗n(0 <= n <= 100000)个节点的树，每个节点要给他的一个祖先(它到根的路径上所有的点，包括他自己)送礼物。现在已知每个点要给那个祖先送礼，求一个序列，使得如果x要给祖先y送礼，那么在序列中y必须出现在x的所有其他祖先之前，即x会给序列中出现的第一个祖先送礼。题解： (这题题意理解了好半天…)我们发现，如果y是x的一个儿子， y的祖先

2016-09-15 00:17:53 163

原创 codeforcse基础题——#357(div2)C

#357(div2)C题目大意：有一个小根堆，支持插入，查询堆顶，删除堆顶三个操作，现在给你长度为n(n <= 100000)一个不完整的操作序列，让你在其中加入最少的操作使其合法，输出最小操作数及方案。题解：直接模拟即可，依次读入操作，只有查询堆顶时可能有不合法的情况，这时只要一直将堆顶弹出，直到堆顶大于查询的值，在将查询的值插入，就能使操作合法。（写的时候注意一些细

2016-09-15 00:02:23 260

原创 codeforces基础题——#358（div2）D

#358（div2）D题目大意：给你长度分别为n, m(1 <= n, m <= 1000)的两个只含小写字母的字符串s, t和一个整数k(1 <= k <= 10)，现在我们知道有一个字符串p，能将p分城k个子串使得这k个子串分别在s和t中连续出现，问p串可能长度的最大值。可能不太清楚，我们看一组样例9 12 4 bbaaababb

2016-09-09 22:24:28 296

原创 codeforces基础题——#358（div2）C

#358（div2）C题目大意：给你有一棵n(1 <= n <= 100000)个节点，以节点1为根的树，每个节点有一个权值ai，如果节点v的子树里存在一点u, 使得v到u的路径上所有点的权值和 > au，那么称v为不高兴的点，问至少删除树上的多少个点能使树上不存在不高兴的点。题解：首先我们注意删只能删叶子节点，所以如果节点x使它的祖先中的一个不高兴，那么只能把以它为根的

2016-09-08 20:51:01 380

原创 codeforces基础题——#361（div2）D

#361（Div 2） D题目大意：给你a, b两个长度为n的整数序列（1 <= n <= 200000）, 问有多少个（l, r)（1 <= l, r <= n )使得a中区间（l, r）的最大值与b中区间（l, r）的最小值一样题解：一开始在想神奇的树状数组瞎搞做法，其实可以做，但要维护各种树状数组和各种二分，离散化和预处理也很麻烦，于是写到一半太累（懒）了，就没再写……

2016-09-08 20:15:10 377

原创 codeforces基础题——#362（div2）D

#362（Div 2） D题目大意：给你一棵n个节点的树(1 <= n <= 100000)，根结点为1，跑一遍dfs，但每次dfs一个点的儿子时顺序是随机的，然后问每个点在dfs序中出现位置的期望。我们举个栗子：可能的dfs序有： 1 2 3 4 5， 1 2 3 5 4， 1 3 4 5 2， 1 3 5 4 2所以他们出现位置的期望分别是： ( 1 + 1 + 1

2016-09-08 20:11:38 377

原创 codeforces基础题——#362（div2）C

#362（Div 2） C题目大意：有一颗无穷大的二叉树，以编号1为的点根，编号为i的点的儿子分别为i * 2， i * 2 + 1，有q（1 <= q <= 1000）次操作: 1. 将点u到v的路径上所有边的权值加w； 2. 查询u到v路径上边的权值和；1 <= u, v <= 1018, w <= 109题解这题作为C题感觉有些水，

2016-09-05 21:25:46 332

dujvet的博客