折纸

Description 现在有一个1×1的小格子分割的矩形纸片,每个小格子内包含一个整数. 现在你可以进行一系列的折叠,每次折叠的折痕必须是分隔两行或两列小格子的分割线. 折叠完之后所有重叠的小格子被看做一个单独的格子并且这个格子的价值为重点的小格子的价值和. 你想要知道在所有可能得到的新格子中格子价值的最大值是多少? Input 第一行有两个整数,n和m,分别表示初始的矩形的长和宽. 接下来的n行,每行有m个数字,表示初始的小格子内的整数. Output 输出一行表示所能得到的格子价值的最大值,对于100%的数据格子数字权值的绝对值不超过10000. Sample Input 2 2 1 -3 3 -1 Sample Output 4 Code #include <cstdio> #include <algorithm> using namespace std; const int maxn = 25; const int maxm…

20170116 AHSDFZ day3 NOI 模拟赛解题报告

graph 题目大意: 给出一个n个点m条边的无向图,边有边权。你要求一个含有点数最少的正环,输出该环长度。n<=300,保证无重边自环 考场上这道题弃疗了…我一想 环 就想简单环 然后就不会做了。。 赛后lt跟我讲一个非简单环一定不是答案,考虑一个非简单环 由至少两个子环构成 那么他们其中一个权值大于等于0,一个小于等于0,这样非常不好,我们干脆不要小于的那部分,剩下的还可以更优是不是。。 正解: 考虑动态规划 令dp[i][j][k]表示从i到j走了k步的最长路。求答案的时候枚举k 看看dp[i][i][k]是否大于0. 然后这样状态是n^3,转移n 总复杂度n^4爆炸。 我们发现一个一个转移k不妙,于是用倍增的思想来做。 dp[i][j][k]表示从i到j走了2^k步的最长路…

CodeForces 301 E. Yaroslav and Arrangements

E. Yaroslav and Arrangements Round 182 time limit per test 3 seconds memory limit per test 256 megabytes Yaroslav calls an array of r integers a1, a2, …, ar good, if it meets the following conditions: \(|a_1 - a_2| = 1, |a_2 - a_3| = 1, ……

优美的树 shu

Description 众所周知,树是 n 个节点 n-1 条边的结构,而所谓的优美的树需要满足如下条件: 这是一棵有根二叉树; 非叶节点需有两个儿子; 不可以变换为 k-左偏树。 所谓的 k-左偏树是指一棵有 k 个叶子的树,每个非叶节点的右儿子均为叶子且均有左儿子。 所谓的变换指的是经过若干次如下两种变换: 删去一个节点的两个儿子; 用一个节点的某个儿子替换该节点。 如下图,若 k=3 则这不是一棵优美的树。 现在给你 k 和 n,想要你求出叶子数为 1,2,3…n 的优美的树分别有多少。 Input 一行两个整数 k 和 n。 Output n 行第 i 行一个正整数表示叶子数为 i 时的答案。答案很大所以对 1,000,…

AHSDFZ 20170305 模拟赛题解 (land genes average)

1.一亩地 land Description 老 G 是个辛勤的码农,他用了一生的时间,默默种下了一片又一片的代码。现在,他有了一亩代码地。这亩代码可以用一个 n 个节点的树来描述,所有节点可以通过树边互相到达。节点从 0 开始编号。 老 G 渐渐的老去,所以他现在想把他的地传承给他的两个儿子。为了避免儿子产生冲突,他决定将整块地平均分给两个儿子,更具体地,他会将地里 n 个节点平均分给每个儿子。 分割代码地是需要代价的,更具体地,若用树边相连的两个节点最后分给了不同的儿子,则这条边就会产生一定的代价,每条边的代价不一定相等。老 G 想知道最优的分割方案,你能帮助他吗? Input 第一行一个整数 n,表示树有 n 个节点。保证 n 为偶数。接下来 n-1 行每行三个整数 ui,…

BZOJ 4767: 两双手

Description老W是个棋艺高超的棋手,他最喜欢的棋子是马,更具体地,他更加喜欢马所行走的方式。 老W下棋时觉得无聊,便决定加强马所行走的方式,更具体地,他有两双手,其中一双手能让马从$(u,v)$移动到$(u+A_x,v+A_y)$而另一双手能让马从$(u,v)$移动到$(u+B_x,v+B_y)$。小W看见老W的下棋方式,觉得非常有趣,他开始思考一个问题:假设棋盘是个无限大的二维平面,一开始马在原点$(0,0)$上,若用老W的两种方式进行移动,他有多少种不同的移动方法到达点$(E_x,E_y)$呢?两种移动方法不同当且仅当移动步数不同或某一步所到达的点不同。老W听了这个问题,觉得还不够有趣,他在平面上又设立了$n$个禁止点,表示马不能走到这些点上,…

「2017 山东一轮集训 Day1」Sum

题目大意 求有多少 n 位十进制数是 p 的倍数且每位之和小于等于 m (对0..mm都要求),允许前导 0 ,答案对 998244353 取模。 输入格式 三个数n, mm, p 输出格式 mm + 1个数 分别表示m = 0 .. mm的时候的答案 样例输入 2 3 3 样例输出 1 1 1 5 数据范围 对于测试点 1,1≤n≤1000,1≤p≤50.1≤m≤5; 对于测试点 2、3,1≤n≤…

BZOJ 4033: [HAOI2015]树上染色

Description 有一棵点数为N的树,树边有边权。给你一个在0~N之内的正整数K,你要在这棵树中选择K个点,将其染成黑色,并 将其他的N-K个点染成白色。将所有点染色后,你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。 问收益最大值是多少。 Input 第一行两个整数N,K。 接下来N-1行每行三个正整数fr,to,dis,表示该树中存在一条长度为dis的边(fr,to)。 输入保证所有点之间是联通的。 N<=2000,0<=K<=N Output 输出一个正整数,表示收益的最大值。 Sample Input 5 2 1 2 3 1 5 1 2 3 1 2 4 2 Sample…