A 自相残杀：题目链接
题目大意：
在 \(n \times n\) 的棋盘上摆放 \(k\) 头恶龙，使得每头恶龙都能相互攻击到对方的方案数。
解题思路：
模拟，找规律。
-
当 \(k\gt 4\) 时，无论怎么摆放，方案数都是 \(0\) 种，直接输出 \(0\)
-
当 \(k \le 4\) 时，分类讨论：
-
\(o\) 表示摆放恶龙的位置，\(x\) 表示空白棋盘
-
\(k = 0\) ，\(0\) 种方案
-
\(k =1\) ，\(n \times n\) 种方案，每个棋盘的一个格子就是一种方案
-
\(k =2\) ，\(2\times (2n-1) \times(n - 1)\) 种方案，只有 \(4\) 种摆放方式
- \(\begin{matrix}o&x\\o&x\end{matrix}\)
- \(\begin{matrix}o&o\\x&x\end{matrix}\)
- \(\begin{matrix}o&x\\x&o\end{matrix}\)
- \(\begin{matrix}x&o\\o&x\end{matrix}\)
-
\(k=3\) ，\(4\times (n-1)\times(n-1)\) 种方案，只有 \(4\) 种摆放方式
- \(\begin{matrix}o&o\\o&x\end{matrix}\)
- \(\begin{matrix}o&o\\x&o\end{matrix}\)
- \(\begin{matrix}o&x\\o&o\end{matrix}\)
- \(\begin{matrix}x&o\\o&o\end{matrix}\)
-
\(k=4\) ，\((n-1)\times(n-1)\) 种方案，只有一种摆放方式
- \(\begin{matrix}o&o\\o&o\end{matrix}\)
-
B 暴躁兔兔：题目链接
题目大意：
将 \(C\) 只兔子放到 \(N\) 个兔笼里，使得每个兔子之间相隔的最近距离最大。
解题思路：
二分答案
首先数据不是有序的，先排序sort(a + 1, a + 1 + n)；
可以知道答案的左边界是：\(1\) ，答案的右边界是：\(a_n-a_1\)
接下来二分，\(check\) 函数
bool check(int x)
{
int cnt = 1, last = a[1]; // 上一次放兔子的位置
for (int i = 2; i <= n; i++)
{
if (a[i] - last >= x)
{
cnt++;
last = a[i];
}
}
return cnt >= m; // true -> l = mid + 1; false -> r = mid - 1;
}
...
while (l <= r)
{
int mid = (long long)(l + r) / 2;
if (check(mid)) l = mid + 1;
else r = mid - 1;
}
cout << r << endl;
C 灯火通明：题目链接
题目大意：
使得两列灯笼距离最小的交换相邻灯笼的次数。
解题思路：
贪心：首先想到一定是高度一一对应，小对小，大对大。
离散化：通过映射下标，使两列灯笼相关联， c[第一列灯笼的下标]=第二列灯笼的下标
-
举个例子：
-
4 1 3 4 2 -> 排序后：1 2 3 4，下标为：1 4 2 3 1 7 2 4 -> 排序后：1 2 4 7，下标为：1 3 4 2 接下来进行下标的关联 c[1] = 1 c[4] = 3 c[2] = 4 c[3] = 2 所以c数组为 [1,4,2,3] -
我们求的交换次数，就是 \(c\) 数组的逆序对的个数。
至此：问题转化为求 \(c\) 数组的逆序对的个数。
D 猜灯谜啦：题目链接
题目大意：
求区间 \([L,R]\) 内可以由 \(B\) 进制表示成有 \(K\) 个 \(1\) 的数的个数。
如：\((17)_{10}=(10001)_2\) \((18)_{10}=(10010)_2\) \((20)_{10}=(10100)_2\)
解题思路：
考虑 $1 $ ~ \(n\) 满足条件的数的个数 dp(n)
所以我们的所求为：dp(R) - dp(L-1)
组合数的初始化，使用递推公式即可。
考虑组合数，我们对这个数字转换成 \(B\) 进制后的每一位进行处理，假设分解后的位数为 \(n+1\) 位，\(last\) 为可取 \(1\) 的个数。
- 这一位是 \(0\) ，那么可以考虑从后面的所有位中选 \(K-last\) 个数的选法，\(C_i^{k-last}\)
- 这一位 \(\gt 1\) ，比如 \(4\) ，那么可以取 \(1,2,3,4\)
- 取 \(1\) 后，剩下的只能是后面所有的位中选 \(K-last-1\) 个数， \(C_i^{k-last-1}\)
- 为什么不考虑其他情况，因为本题是求 \(1\) 的个数
- 这一位 \(=1\) ，直接取 \(last\)++，为啥不能和上面的情况归到一类呢？因为我们要保证组合出来的数都要比 \(n\) 小，如果直接组合数的话，可能组合出来的就比 \(n\) 大了，所以我们要在下一位判断。
把上述的情况加起来，还要算上最后一种：取到最后一位，并且 \(last\) 为 \(K\) 了，答案加 \(1\)
核心代码：
const int N = 35;
int f[N][N]; // 存组合数
int X, Y, K, B;
void init() // 初始化组合数
{
for (int i = 0; i < N; i++)
for (int j = 0; j <= i; j++)
if (!j) f[i][j] = 1;
else f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
}
int dp(int n)
{
if (!n) return 0; // 边界判断，n为0
vector<int> nums; // 存B进制下分解后的每一位的数字
while (n) nums.pb(n % B), n /= B;
int res = 0;
int last = 0; // 取1的个数
for (int i = nums.size() - 1; i >= 0; i--)
{
int x = nums[i];
if (x) // x不为0
{
res += f[i][K - last]; // 当前取0
if (x > 1) // 当这一位 > 1 ，我们只能取 1
{
if (K - last - 1 >= 0) res += f[i][K - last - 1];
break; // 因为我们是从最高位依次判断的，所以我们可以直接算出来后面的方案数，因为那些方案组成的数字一定不会超过原来的数字。
}
else // 等于1的情况
{
last++;
if (last > K) break;
}
}
if (!i && last == K) res++; // 到了这里，说明原来的那个数n也是满足条件的，要加一个
}
return res;
}
E 龙登天梯：题目链接
题目大意：
求斐波那契数列的第 \(n\) 项
解题思路：
递推表达式，注意写高精度。f[i] = f[i - 1] + f[i - 2] 这里使用高精度加法。
标签：begin,last,matrix,int,end,times,2024,锦鲤,化龙 From： https://www.cnblogs.com/yhgm/p/18012173也可以使用 python 直接写斐波那契数列 hhh