[COGS 1517] 放国王

题目描述

原题地址：COGS

思路

对于此题，先考虑一个弱化版的题目：

• 在$n\times n$的棋盘上放国王，有多少种方法？

[COGS 1516] 棋盘上的车

题目描述

原题地址：COGS

思路一

乘法原理水过，计算$n!$即可，复杂度$O(n)$

思路二

DP方程

每次放置一枚棋子，一行一行放，可以用一个二进制数表示状态，如$(0010011)_2$表示第一、二、五列已放棋子。

设$f(n)$是放置$n$枚棋子的方案数，可以知道，$f((0010011)_2)=f((0000011)_2)+f((0010001)_2)+f((0010010)_2)$，类似地，我们可以推出方程：

题目描述

原题地址： COGS Codeforces

思路

Bob的移动策略有三种：

向根节点方向走

题目描述

原题地址：COGS 洛谷

思路

第一问很简单，最长下降子序列问题，第二问的统计方案数有点意思。

DP方程

题目描述

原题地址：Codeforces

思路

固定两个相邻的点，其中一个是顶点，然后枚举另一个点的位置，求角。

观察到所成角每次增加$\frac{\pi}{n}$，然后就递推一波。。

题目描述

原题地址：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)$。