题目描述 给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入，且保证每行一定为20个)。要求将此字母串分成k份(1< k< =40)，且每份中包含的单词个数加起来总数最大(每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串this中可包含this和is，选用this之后就不能包含th)。 单词在给出的一个不超过6个单词的字典中。要求输出最大的个数。 输入 第一行有二个正整数(p，k) p表示字串的行数; k表示分为k个部分。 接下来的p行，每行均有20个字符。 再接下来有一个正整数s，表示字典中单词个数。(1...

描述 小新经常陪小白去公园玩，也就是所谓的遛狗啦…在小新家附近有一条“公园路”，路的一边从南到北依次排着n个公园，小白早就看花了眼，自己也不清楚该去哪些公园玩了。 一开始，小白就根据公园的风景给每个公园打了分-.-。小新为了省事，每次遛狗的时候都会事先规定一个范围，小白只可以选择第a个和第b个公园之间（包括a、b两个公园）选择连续的一些公园玩。小白当然希望选出的公园的分数总和尽量高咯。同时，由于一些公园的景观会有所改变，所以，小白的打分也可能会有一些变化。 那么，就请你来帮小白选择公园吧。 格式 输入格式 第一行，两个整数N和M，分别表示表示公园的数量和操作（遛狗或者改变打分）总数。 接下来N...

题目描述 如题，给定一个范围N，你需要处理M个某数字是否为质数的询问（每个数字均在范围1-N内） 输入格式 第一行包含两个正整数N、M，分别表示查询的范围和查询的个数。 接下来M行每行包含一个不小于1且不大于N的整数，即询问该数是否为质数。 输出格式 输出包含M行，每行为Yes或No，即依次为每一个询问的结果。 输入输出样例 输入 #1 100 5 2 3 4 91 97 输出 #1 Yes Yes No No Yes 介绍 素数有很多种筛法，比较多见的是埃式筛法（复杂度是nloglogn）。 这里想讲的是线性筛素数。 首先任何一个数a, 一定由某个 最小素因子b * 另一个数c得来的，即  ...

为什么要用dij： 很多人也许学了spfa，觉得简单方便，然而呢，spfa的复杂度是O(玄学)，容易被出题人出数据卡，于是我们要学用优先队列优化的dij。 简介： 如果大家理解dij算法的核心，那么也会很容易理解为什么优先队列可以优化的。 没优化前的dij，我们每次松弛都要遍历     1   →   n    1 \to n   1→n，来找到     d   i   s   [   i   ]    dis[i]   dis[i]最小的点，而总共要松弛     n   −   1    n-1   n−1次，复杂度是     O   (    n   2    )    O(n^2)   ...

逆元简介： 已知     a   ,   b   (   g   c   d   (   a   ,   b   )   =   1   )    a, b(gcd(a, b) = 1)   a,b(gcd(a,b)=1)对于      a   ∗   x   ≡   1   (   m   o   d  <mtext>   </mtext>  b   )    a*x \equiv 1 (mod ~b)   a∗x≡1(mod b) 我们称      x    x   x 为      a    a   a 模      b    b   b 意义下的逆元， 记做  ...

发现以后发题目只需要截图就可以了hhh。 感觉这种题好难想啊。看看数据范围，复杂度应该是     O   (   n   )    O(n)   O(n)，这就要我们舍弃脑中各种奇奇怪怪的想法了（当然有大佬可以用强大的数据结构+卡常等特技）。     O   (   n   )    O(n)   O(n)，我们读入就已经     O   (   n   )    O(n)   O(n)了，这就要求我们单独考虑每一个数对答案的贡献了。 我们来看某一个数      a    a   a 的一边，如果左边那个数      b    b   b 比他小，那么      a    a   a 一定会被...

简介 欧拉回路就是给一个图，存在一条回路把所边经过且每条边只经过一次。  存在欧拉回路的条件   对于无向图：  存在欧拉回路的条件：每个点的度都为偶数； 存在欧拉路的条件：有且只有两个点的度为一，且这两个点分别为起点和终点；  对于有向图：  存在欧拉回路的条件：每个点出度等于入度； 存在欧拉路的条件：存在一个点出度比入度多一作为起点，存在一点入度比出度多一作为终点，其余点出度等于入度； 一句话就是：一笔画问题能成立的条件：有2个奇点或没有奇点（奇点指该点度数为奇数）  套圈法 判断是否存在欧拉回路很好判断，那怎么求欧拉回路呢？ 我们采用套圈法，dfs回溯的时候才把边倒着记录。为什么要这样呢...

分析 这道题的点是在二维平面上的，而数据范围是1e5，于是我们要用扫描线来降维。 我们扫描横坐标，纵坐标就转化成了这么一个问题： 一维平面上有多个点，每个点有个值，给一个长为      h    h   h 的区间，问区间内的点权和最大值是多少。（单点修改，区间查询） maya我从来没做过这种题，难道要枚举区间的端点？？复杂度还不爆炸！！ 于是查了题解（我太弱啦） 有一种典型的处理方法，是把单点修改变成区间修改，区间查询变为单点查询。 什么意思？看图。  这是平面内若干个点（红色），高度表示值。我们已知区间长为      h    h   h ，如果      i    i   i 处有一个点...

分析 一开始可以想到的dp是用     f   [   i   ]   [   j   ]    f[i][j]   f[i][j]表示取到剩区间     [   i   ,   j   ]    [i,j]   [i,j]时的最大得分，转移方程比较显然。 不过我采用了另一种做法，就是用     f   [   i   ]   [   j   ]    f[i][j]   f[i][j]表示取完了区间     [   i   ,   j   ]    [i,j]   [i,j]的最大得分，相当于反过来做把。 这样可以得到转移方程:      f   [   i   ]   [   j   ] ...

题目描述 某一村庄在一条路线上安装了n盏路灯，每盏灯的功率有大有小（即同一段时间内消耗的电量有多有少）。老张就住在这条路中间某一路灯旁，他有一项工作就是每天早上天亮时一盏一盏地关掉这些路灯。 为了给村里节省电费，老张记录下了每盏路灯的位置和功率，他每次关灯时也都是尽快地去关，但是老张不知道怎样去关灯才能够最节省电。他每天都是在天亮时首先关掉自己所处位置的路灯，然后可以向左也可以向右去关灯。开始他以为先算一下左边路灯的总功率再算一下右边路灯的总功率，然后选择先关掉功率大的一边，再回过头来关掉另一边的路灯，而事实并非如此，因为在关的过程中适当地调头有可能会更省一些。 现在已知老张走的速度为1m/s...

题目描述 2020年，人类在火星上建立了一个庞大的基地群，总共有n个基地。起初为了节约材料，人类只修建了n-1条道路来连接这些基地，并且每两个基地都能够通过道路到达，所以所有的基地形成了一个巨大的树状结构。如果基地A到基地B至少要经过d条道路的话，我们称基地A到基地B的距离为d。 由于火星上非常干燥，经常引发火灾，人类决定在火星上修建若干个消防局。消防局只能修建在基地里，每个消防局有能力扑灭与它距离不超过2的基地的火灾。 你的任务是计算至少要修建多少个消防局才能够确保火星上所有的基地在发生火灾时，消防队有能力及时扑灭火灾。 输入格式 输入文件名为input.txt。 输入文件的第一行为n （n...

题目描述 有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点） 这棵树共有N个结点（叶子点或者树枝分叉点），编号为1-N,树根编号一定是1。 我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝的树 2 5 \ / 3 4 \ / 1 现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。 给定需要保留的树枝数量，求出最多能留住多少苹果。 输入格式 第1行2个数，N和Q(1<=Q<= N,1<N<=100)。 N表示树的结点数，Q表示要保留的树枝数量。接下来N-1行描述树枝的信息。 每行3个整数，前两个是它连接的结点的编号...

简介 所谓悬线，就是用一条线尽可能向两边拓展形成一个矩形，这样一条线就会构成矩形的宽。（原谅我也很难说明白悬线的具体定义）  用途 解决给定矩阵中满足条件的最大子矩阵  正确性 悬线法的正确性怎么证明？我们考虑最优解所代表的矩形（即满足条件的最大矩形），它的宽      h    h   h 一定来自于某一条悬线。可以用反证法，假设它的宽不来自于任意一条悬线，即每条悬线都比宽      h    h   h 大，这样我们显然可以得到一个更大的解，与条件矛盾。所以悬线法不一定能覆盖所有矩形，但一定可以覆盖到最优解的。  悬线法的具体实现      f   [   i   ]   [   j   ...

题目描述 上午的训练结束了，THU ACM小组集体去吃午餐，他们一行N人来到了著名的十食堂。这里有两个打饭的窗口，每个窗口同一时刻只能给一个人打饭。由于每个人的口味（以及胃口）不同，所以他们要吃的菜各有不同，打饭所要花费的时间是因人而异的。另外每个人吃饭的速度也不尽相同，所以吃饭花费的时间也是可能有所不同的。 THU ACM小组的吃饭计划是这样的：先把所有的人分成两队，并安排好每队中各人的排列顺序，然后一号队伍到一号窗口去排队打饭，二号队伍到二号窗口去排队打饭。每个人打完饭后立刻开始吃，所有人都吃完饭后立刻集合去六教地下室进行下午的训练。 现在给定了每个人的打饭时间和吃饭时间，要求安排一种最佳...