题目描述

原题地址：COGS BZOJ

思路

合法的n是一个区间，可以分成两次求，二分n的范围。注意有一些关于long long和代码的细节，这个checker还是很好写的

题目描述

原题地址：COGS

思路

本来没有什么想法，搜了一下题解之后发现一个很妙的方法，将字符串正反各读一遍，然后求最长公共子序列的长度，最后再用总长度减一下就可以了

题目描述

题目地址：COGS

这题真是蛇，调一晚上。。码力太弱了qwq

思路

本来以为这跟HAOI2016的食物链一样，但是在WA了一次后注意到食物链计算的是经过某点的路径条数，而本题是经过某边的路径条数。

DP 方程

为了求出经过某一条边的的路径条数，可以这样：

设$f(u,v)$是经过边$u,v$的路径条数，$dp(u)$为从源点到$u$的路径条数，$rdp(v)$为从$v$到终点的路径条数，则有 $f(u,v)=dp(u)\times rdp(v)$ 最后的答案就是$\max{f(u,v)} u,v\in G$

A题

题目描述

原题地址：Codeforces

题意：判断回文时间。

解决方案

先搞出来一个判断回文的函数，然后枚举分钟。

题目描述

原题地址：COGS

一句话题意：二维的分组背包

DP方程

状态定义

令$f(i,j,k)$为在前$i$个箱子中取药，使得生命值为$j$，精神值为$k$ 。

令第$i$瓶药造成的生命值伤害是$pain(i)$，精神伤害是$san(i)$，痛苦值为$suff(i)$。

[COGS 131][USACO Mar08] 奶牛渡河

题目地址：COGS

DP方程

令$dp(i)$为前$i$头牛渡河的最短时间，$m(i)$为一次带$i$头牛过河所花费的时间，则有方程： $$ dp(i)=\min_{2\leq 2j\leq i}{dp(j)+dp(i-j)+m(0),m(i)} $$

对方程的解释

$2\leq 2j\leq i$等价于$1\leq j\leq i-j$ ，即枚举与前面的牛分成一组过河所需时间，然后取最小值

题目描述

问题：题目地址 ，中文版

思路

注意到$a,b\leq 60$，所以预处理出所有$x^a,y^b$存起来，然后两两求和，去重， 然后处理一下得到答案。

坑点

1. 开unsigned long long

2. while (num <= 1e18)
      num = num * x
   

   这样写是不符合基本法的，会溢出掉的

题目描述

问题：题目地址

Vladik often travels by trains. He remembered some of his trips especially well and I would like to tell you about one of these trips:

Vladik is at initial train station, and now n people (including Vladik) want to get on the train. They are already lined up in some order, and for each of them the city code $a_i$ is known (the code of the city in which they are going to).

什么是主席树

主席树：可持久化线段树，特点是每次修改都新建一颗新树，由于单点修改最多影响$\log n$个节点，因此只需要新建一条链，挂在原树上

问题：[COGS 2554][福利]可持久化线段树 RMQ问题的可持久化版本

这是一道板子题，但是此题没有体现主席树的经典应用，代码如下：