T1
题目描述
猫猫是丛林里很多动物心中的天使，她为此十分自豪。猫猫最爱吃鱼了，她每天都要去池塘钓鱼吃。猫猫经常吃鱼脑，数学特别强，然而，小女生的性格决定了她的贪玩。
一天，猫猫钓到了很多条鱼。她并不想马上就把可怜的鱼儿吃掉，而是先折磨够之后再吃（有句话叫什么来着，最毒不过猫猫心）。
猫猫将这很多很多（数不过来）条鱼按照外观的漂亮程度排序，每个鱼的编号依次为 \(1、2、3 \dots \dots N\)，第 \(i\) 条鱼的美观程度为 \(3^{i-1}\)。
猫猫要把这些鱼放到桶里去。她每次拿的鱼的数目是任意的。中的鱼的“总美观程度”为各条鱼美观程度之和。例如：猫猫这一次拿了第一条鱼和第三条鱼，那么美观程度为 \(1 + 9 = 10\)。
猫猫想知道，她可以获得的第 \(k\) 小的“总美观程度”是多少。
输入格式
数据包含 \(n + 1\) 行，第一行读入 \(n\)。以下 \(n\) 行每行包含一个 \(k\)。
输出格式
输出包含 \(n\) 行，每行输出一个对应的结果。
输入样例
1
7
输出样例
13
样例解释
猫猫能够拿到的美观程度从小到大为 \(1、3、4、9、10、12、13 \dots \dots\)，所以第 \(7\) 大的美观程度是 \(13\)。
数据规模
对于 \(50\%\) 的数据，\(k \leq 5000\)。
对于 \(100\%\) 的数据，\(n \leq 100, k \leq 2^{31 }- 1\)。
题解
我们将每条鱼的美观程度转化为三进制，那他们的美观程度就分别是 \(001, 010, 100, \dots\)，可以发现它们的 \(1\) 都在不同位上，因此若干条鱼的美观程度加起来在三进制下每一位上只会出现 \(0\) 或 \(1\)，因此满足这个性质的数都可以被凑出来。
考虑如何快速找到第 \(k\) 小的数。将可以凑出的所有数转化成三进制，再按从小到大列出来：\(001, 010, 011, 100, 101, 110, \dots\)，可以发现将这些数转化成二进制后，就是 \(1, 2, 3, 4, 5, 6, \dots\).
于是，可以将 \(k\) 先转化成二进制，再把它当成一个三进制数，将它转化为十进制，就可以得出答案。
完整代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, k;
signed main(){
freopen("catfish.in", "r", stdin);
freopen("catfish.out", "w", stdout);
scanf("%lld", &n);
while(n--){
scanf("%lld", &k);
int len = log2(k) + 1, ans = 0, mi = 1;
for(int i = len; i >= 1; i--){
ans += mi * (k % 2);
k /= 2;
mi *= 3;
}
printf("%lld\n", ans);
}
return 0;
}
T2
题目描述
回到家中的猫猫把三桶鱼全部转移到了她那长方形大池子中，然后开始思考：到底要以何种方法吃鱼呢（猫猫就是这么可爱，吃鱼也要想好吃法^_*）。她发现，把大池子视为 \(01\) 矩阵（\(0\) 表示对应位置无鱼，\(1\) 表示对应位置有鱼）有助于决定吃鱼策略。
在代表池子的 \(01\) 矩阵中，有很多的正方形子矩阵，如果某个正方形子矩阵的某条对角线上都有鱼，且此正方形子矩阵的其他地方无鱼，猫猫就可以从这个正方形子矩阵“对角线的一端”下口，只一吸，就能把对角线上的那一队鲜鱼吸入口中。
猫猫是个贪婪的家伙，所以她想一口吃掉尽量多的鱼。请你帮猫猫计算一下，她一口下去，最多可以吃掉多少条鱼？
输入格式
有多组输入数据。
每组数据：
第一行有两个正整数 \(n\) 和 \(m\)，描述池塘规模。接下来的 \(n\) 行，每行有 \(m\) 个数字（非 \(0\) 即 \(1\)）。
每两个数字之间用空格隔开。
输出格式
只有一个整数——猫猫一口下去可以吃掉的鱼的数量，占一行，行末有回车。
输入样例
4 6
0 1 0 1 0 0
0 0 1 0 1 0
1 1 0 0 0 1
0 1 1 0 1 0
输出样例
3
数据规模
对于 \(30\%\) 的数据，\(n, m \leq 100\)。
对于 \(60\%\) 的数据，\(n, m \leq 1000\)。
对于 \(100\%\) 的数据，\(n, m \leq 2500\)。
题解
一眼 DP。设 \(f_{i, j}\) 表示以 \((i, j)\) 为右下角的最大的只有左上到右下为 \(1\) 的正方形的边长，\(g_{i, j}\) 表示最大的只有右上到左下为 \(1\) 的正方形的边长。
那么答案就是 \(\max_{1 \leq i \leq n, 1 \leq j \leq n}\{f_{i, j}, g_{i, j}\}\)
考虑如何转移，以 \(f_{i, j}\) 为例，首先发现当前 \(f_{i, j}\) 的可能最大值一定是 \(f_{i - 1, j - 1} + 1\)，就像这样：
\[\begin{bmatrix} \dots & \dots & \dots & \dots & \dots\\ \vdots & 1 & 0 & 0 & \vdots\\ \vdots & 0 & 1 & 0 & \vdots\\ \vdots & 0 & 0 & 1 & \vdots\\ \dots & \dots & \dots & \dots & 1\\ \end{bmatrix} \]但我们发现，假设在 \(j\) 到 \(j - f_{i - 1, j - 1}\) 之间有 \(1\)，或在 \(i\) 到 \(i - f_{i - 1, j - 1}\) 之间有 \(1\) 都无法全部转移。
设 \((i, j)\) 位置往左第一个 \(1\) 的位置是 \((i, k)\)，往上第一个 \(1\) 的位置是 \((k, j)\)，那么左上角的这个最大正方形只有 \(i > k\) 且 \(j > l\) 的部分可以转移过来。
设 \(s1_{i, j}\) 表示 \((i, j)\) 左边 (包含 \((i, j)\)) 最多有多少个 \(0\)，\(s2_{i, j}\) 表示 \((i, j)\) 右边 (包含 \((i, j)\)) 最多有多少个 \(0\)，\(s1_{i, j}\) 表示 \((i, j)\) 上边 (包含 \((i, j)\)) 最多有多少个 \(0\)。
那么就可以列出转移方程 \(f_{i, j} = \min(f_{i - 1, j - 1}, s1_{i, j - 1}, s3_{i - 1, j}) + 1\)
同理可得：\(g_{i, j} = \min(f_{i - 1, j - 1}, s2_{i, j + 1}, s3_{i - 1, j}) + 1\)
状态个数 \(O(n^2)\)，转移复杂度 \(O(1)\)，总复杂度 \(O(n^2)\)，可以通过此题。
但这题空间大小只有 \(32\) MB，因此只能将 \(f\) 和 \(g\) 先当做辅助数组，再当做 DP 数组。
完整代码
#include <bits/stdc++.h>
using namespace std;
#define int short
const int N = 2.5e3 + 5;
int dp[N][N], n, m;
bool a[N][N];
int max(int x, int y){
if(x > y)
return x;
else
return y;
}
int min(int x, int y){
if(x > y)
return y;
else
return x;
}
signed main(){
freopen("meal.in", "r", stdin);
freopen("meal.out", "w", stdout);
while(scanf("%hd", &n) != EOF){
scanf("%hd", &m);
memset(dp, 0x3f, sizeof(dp));
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
scanf("%hd", &a[i][j]);
for(int i = 1; i <= n; i++){
int now = 0;
for(int j = 1; j <= m; j++){
dp[i][j] = now;
if(!a[i][j])
now++;
else
now = 0;
}
}
for(int j = 1; j <= m; j++){
int now = 0;
for(int i = 1; i <= n; i++){
dp[i][j] = min(dp[i][j], now);
if(!a[i][j])
now++;
else
now = 0;
}
}
int ans = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
if(a[i][j]){
dp[i][j] = min(dp[i - 1][j - 1], dp[i][j]) + 1;
ans = max(ans, dp[i][j]);
}
else
dp[i][j] = 0;
memset(dp, 0x3f, sizeof(dp));
for(int i = 1; i <= n; i++){
int now = 0;
for(int j = m; j >= 1; j--){
dp[i][j] = now;
if(!a[i][j])
now++;
else
now = 0;
}
}
for(int j = 1; j <= m; j++){
int now = 0;
for(int i = 1; i <= n; i++){
dp[i][j] = min(dp[i][j], now);
if(!a[i][j])
now++;
else
now = 0;
}
}
for(int i = 1; i <= n; i++)
for(int j = m; j >= 1; j--)
if(a[i][j]){
dp[i][j] = min(dp[i - 1][j + 1], dp[i][j]) + 1;
ans = max(ans, dp[i][j]);
} else
dp[i][j] = 0;
printf("%hd\n", ans);
}
return 0;
}
T3
题目描述
猫猫把嘴伸进池子里，正准备“吸”鱼吃，却听到门铃响了。猫猫擦了擦脸上的水，打开门一看，那人正是她的好朋友——川川。
川川手里拿着一辆玩具汽车，对猫猫说：“这是我的新汽车！”接着，伴随一阵塑料叩击声，玩具汽车的车门竟开了，一只蜗牛慢慢吞吞爬了出来。
“哇！这么大的蜗牛……”猫猫惊讶道。
“这是我的宠物蜗牛，他叫点点。”川川介绍道。
“把他送给我好吗？”猫猫央求道。
“可以让他陪你几天，但是不能送给你……”
点点沿着川川的身体，爬到了地上，又移到了猫猫的池子旁边，只听见猫猫向川川介绍她的“创意吃鱼法”，心里不禁起了一丝凉意：“这个女生太毒了……吃鱼前还要玩鱼……”转眼一看，池中的鱼依旧畅快地游来游去。
“或许这些鱼听不懂猫语吧……好在我会一点儿猫语，也会一点鱼语……阿弥陀佛，善哉善哉。我还是救救这些鱼吧……”点点自言自语，一边费力地移动着身躯。他认识到——单凭自己的力量，把猫猫的阴谋告诉每一条鱼，似乎不太可能——自己底盘太低，走不快，看来只得想其他办法来传达信息。一翻认真思考之后，点点想到，如果把猫猫的计划告诉其中一条鱼，再让鱼们互相传达消息，那么在相对较短的时间内，每条鱼都会得知猫猫的计划。
鱼们的社会等级森严，除了国王菜鱼之外，每条鱼均有且只有一个直接上级，菜鱼则没有上级。如果 A 是 B 的上级，B 是 C 的上级，那么 A 就是 C 的上级。
绝对不会出现这样两条鱼 A、B：A 是 B 的上级，B 也是 A 的上级。
最开始的时刻是 0，点点要做的，就只是用 1 单位的时间把猫猫的阴谋告诉某一条“信息源鱼”，让鱼们自行散布消息。在任意一个时间单位中，任何一条已经接到通知的鱼，都可以把消息告诉他的一个直接上级或者直接下属。现在，点点想知道：
-
到底需要多长时间，消息才能传遍池子里的鱼？
-
使消息传递过程消耗的时间最短，可供选择的“信息源鱼”有那些？
输入格式
有多组输入数据，每组数据：
第一行有一个数 \(n\)，表示池中的鱼数，池鱼按照 \(1\) 到 \(n\) 编上了号码，国王菜鱼的标号是 \(1\)。
第 \(2\) 行到第 \(n\) 行（共 \(n - 1\) 行），每一行一个数，第 \(i\) 行的数表示鱼 \(i\) 的直接上级的标号。
输出格式
对于每组输入数据：
第一行有一个数，表示最后一条鱼接到通知的最早时间。
第二行有若干个数，表示可供选择的鱼“信息源鱼”的标号，按照标号从小到大的顺序输出，中间用空格分开。
输入样例
8
1
1
3
4
4
4
3
输出样例
5
3 4 5 6 7
数据规模
对于 \(100\%\) 的数据，\(n \leq 1000\)。
T4
题目描述
猫猫送走了客人，留住了蜗牛点点，晃晃悠悠走到池子边，又打起了鱼的主意。俯瞰池子，猫猫发现鱼阵明显乱了。“难道鱼们故意让我无法下嘴？”猫猫看到正在池边散步的点点，心想：“一定是他告的密……”猫猫愤怒地抓起点点，把他关进了抽屉里。
猫猫想：“好啊，鱼儿啊，你们不就是会传递信息吗？有什么了不起？用挡板把你们隔离开，看你们还怎么交流！”猫猫随即从后花园里拿来若干挡板，打算用这些挡板在水中设立“隔离室”，把鱼们分开。
池塘已经被猫猫抽象成了 \(n\) 行 \(m\) 列小方格，每个小方格中或有鱼，或无鱼。挡板必须沿着小方格的边缘放置。猫猫需要用挡板围出若干个“隔离室”，使得每个隔离室中有且只有一条鱼，而且，每个“隔离室”都必须为矩形（包括正方形）。那么，将鱼们隔离开来，猫猫最少需要多少个长度单位的木板呢？
输入格式
第一行有两个整数 \(n\) 和 \(m\)，描述池塘规模。接下来的 \(n\) 行，每行有 \(m\) 个数字（非 \(0\) 即 \(1\)）。每两个数字之间用空格隔开。
输出格式
对于每组输入数据，输出一行：一个数字，猫猫所需挡板的最短总长度。
输入样例
4 3
0 1 0
0 0 0
1 0 1
0 0 0
输出样例
5
样例解释
可以这么分：
\(\blue{0} \,\, \blue{1} \,\, \blue{0}\)
\(\blue{0} \,\, \blue{0} \,\, \blue{0}\)
\(\pink{1} \,\, \pink{0} \,\, \textcolor{cyan}1\)
\(\pink{0} \,\, \pink{0} \,\, \textcolor{cyan}0\)
由于池塘边框不需要放置挡板，所以这个分割方案所需的挡板总长度为 \(5\)。
数据规模
对于 \(20\%\) 的数据，\(1 \leq n,m \leq 10\)。
对于 \(40\%\) 的数据，\(1 \leq n,m \leq 16\)。
对于 \(70\%\) 的数据，\(1 \leq n,m \leq 24\)。
对于 \(100\%\) 的数据，\(1 \leq n,m \leq 32\)。
标签：dots,leq,猫猫,2024.9,校测,样例,int,dp From： https://www.cnblogs.com/JPGOJCZX/p/18422881