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

AtCoder ARC 103 D - Robot Arms

Problem Statement Snuke is introducing a robot arm with the following properties to his factory: The robot arm consists of m sections and m+1 joints. The sections are numbered 1, 2, …, m, and the joints are numbered 0, 1, …, m. Section i connects Joint i−1 and Joint i.…

BZOJ 3509 CodeChef-COUNTARI

Description 给定一个长度为N的数组A[],求有多少对i, j, k(1<=i<j<k<=N)满足A[k]-A[j]=A[j]-A[i]。 Input 第一行一个整数N(N<=10^5)。 接下来一行N个数A[i](A[i]<=30000)。 Output 一行一个整数。 Sample Input 10 3 5 3 6 3 4 10 4 5 2 Sample…