p1205 [usaco1.2] 方块转换 transformations
时间: 2023-04-26 08:01:22 浏览: 68
题目描述:
给定两个n x n的矩阵A和B,每个矩阵由1和组成。我们可以执行以下三种操作之一:
1.旋转:将A逆时针旋转90度。
2.反转:将A沿中心水平翻转。
3.组合:先执行任意数量的旋转和/或翻转操作,然后将结果与B进行比较。
请确定A是否可以通过执行这些操作之一而转换为B。
输入格式:
第一行包含整数n。
接下来n行,每行包含一个长度为n的字符串,表示矩阵A。
接下来n行,每行包含一个长度为n的字符串,表示矩阵B。
输出格式:
如果A可以通过执行这些操作之一而转换为B,则输出1,否则输出7。
样例输入:
3
@-@
---
@@-
---
@-@
@@-
样例输出:
1
提示:
1<=n<=10
相关问题
p1217 [usaco1.5]回文质数
题目描述:
给定一个序列,要求找出其中的最长的不下降子序列,输出该子序列的长度。
不下降子序列定义:一个序列中的一组数,如果这组数按照原来的顺序排列起来,无论如何也不会变小,则称其为不下降子序列。
输入格式:
第一行包含整数n。
第二行包含n个整数,表示完整序列。
输出格式:
输出一个整数,表示最长不下降子序列的长度。
数据范围:
1≤n≤1000
0≤序列中的数≤10000
样例
输入样例:
7
3 1 4 1 5 9 2
输出样例:
4
解题思路:
使用动态规划,设状态dp[i]表示以a[i]结尾的不下降子序列长度,初始值为1,因为最少也有一个数。
转移方程为:dp[i]=max(dp[j])+1,其中j<i且a[j]<=a[i],即在以a[j]结尾的不下降子序列的末尾加上a[i]得到以a[i]结尾的不下降子序列。
最终结果为dp数组中的最大值。
时间复杂度:O(n^2)
P4087 [USACO17DEC]Milk Measurement
这是一道USACO的题目,需要模拟题意并进行计算。题目大意是给定一组牛奶产量的记录,每条记录包含三个信息:日期、产奶的牛编号、产奶量。要求统计在某个日期时,产奶量最大的三头牛的编号,如果有多个牛的产奶量同时为第三大,则也要统计在内。
我们可以使用一个哈希表来存储每头牛在每个日期的产奶量,然后按照日期顺序依次处理每条记录,更新每头牛在该日期的产奶量,并统计出该日期产奶量最大的三头牛的编号。对于每个日期,如果产奶量最大的三头牛有变化,则更新计数器。
具体实现细节可以参考下面的代码: