HDU 3622 Bomb Game

Problem Description   Robbie is playing an interesting computer game. The game field is an unbounded 2-dimensional region. There are N rounds in the game. At each round, the computer will give Robbie two places, and Robbie should choose one of them to put a bomb. The explosion area of the…

折纸

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…

湖南集训 Equation

Description 听着自己美妙的曲子,小 Z 进入了梦乡。在梦中,小 Z 仿佛又回到了自己纵横考场的年代。在梦中,小 Z 参加了一场考试,这场考试一共有 n 道题,每道题的最终得分都是一个大于等于 0 的整数。然而醒来后,小 Z 忘记了自己每道题的得分。他只记得自己计算过 m 次一些题目的分数和,每道题都被计算过,并且只被计算过一次。除此之外他还记得其中 t 道题的满分分别是多少(一道题的得分不会超过满分)。现在小 Z 想知道他这场考试有多少种得分情况(至少有一道题的得分不同就算不同的情况),因为这个答案可能很大,你只需要输出答案对 1,000,000,007 取模后的结果即可。 Input 第一行两个整数 n,m 表示题目个数与求和次数。 接下来 m…

CodeForces 754 D. Fedor and coupons

Description All our characters have hobbies. The same is true for Fedor. He enjoys shopping in the neighboring supermarket. The goods in the supermarket have unique integer ids. Also, for every integer there is a product with id equal to this integer. Fedor has n discount coupons, the i-th of…

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步的最长路…

后缀自动机 HihoCoder

描述 小Hi:今天我们来学习一个强大的字符串处理工具:后缀自动机(Suffix Automaton,简称SAM)。对于一个字符串S,它对应的后缀自动机是一个最小的确定有限状态自动机(DFA),接受且只接受S的后缀。 小Hi:比如对于字符串S="aabbabd",它的后缀自动机是: 其中红色状态是终结状态。你可以发现对于S的后缀,我们都可以从S出发沿着字符标示的路径(蓝色实线)转移,最终到达终结状态。例如"bd"对应的路径是S59,"abd"对应的路径是S189,"abbabd"对应的路径是S184679。而对于不是S后缀的字符串,你会发现从S出发,最后会到达非终结状态或者“无路可走”。特别的,对于S的子串,最终会到达一个合法状态。例如"abba"路径是S1846,"bbab&…

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, ……

覆盖的串 chuan

Description 我们称一个字符串 A 覆盖了一个字符串 B 当且仅当对于 B 中的每一个字符,都有一个包含它的和 A 相同的子串。例如,A={1,2,1}覆盖了 B={1,2,1,2,1,1,2,1}。 所谓的最短覆盖子串,指的是覆盖该串的最短子串。例如 B 的最短覆盖子串为 A,长度为 3。 最短覆盖前缀数组指的是对于一个串的每一个前缀,它们的最短覆盖子串长度按顺序组成的数组。例如 B 的最短覆盖前缀数组为{1,2,3,2,3,6,7,3}。 现在给你一个最短覆盖前缀数组,判断是否存在某个串符合条件,如果存在则给出一组解。…