Insertion Sort Gym - 101955C 思路+推公式
2024-09-27 14:53:18
题目:题目链接
题意:对长为n的1到n的数列的前k个数排序后数列的最长上升子序列长度不小于n-1的数列的种数,训练赛时怎么都读不明白这个题意,最后还是赛后问了旁队才算看懂,英语水平急需拯救55555
思路:明白题意后就很容易了,有一个坑点是k可能比n大,所以我们对k取min(k, n),我们先不考虑前k个数的顺序,比k大的数只能有一个出现在前k个数中,而且是要替换k这个位置的数字,并且最后这个数还要不计入最长上升子序列,可以理解为删掉,如果k + 1存在的话对于这个数要特殊处理,这样后面的那些数必须保证直接是有序的才可以满足题目要求,这种情况有n - k种,如果前k个数最大的数才是k,那么后面的数我们可以选一个不考虑这个数的顺序(最后删掉这个数),组成的种类为1 + (n - k)*(n - k - 1),其中1是每一个数都在排好序的位置上的情况,这里拿出来防止重复计数,对于我们刚刚提到的k + 1存在的情况下,这时我们可以选一个比k小的数来替换,因为最后可以不删掉k + 1而是删掉选定的那个比k小的数。最后,因为前k个数是会排序的,所以我们再乘一个k!就OK啦。
所以:ans = n - k + 1 + (n - k) * (n - k - 1),如果k + 1存在的话,ans += (k - 1) * (n - k)
AC代码(临近java考试先用java写一段时间代码了5555):
import java.util.Scanner; public class Main { public static void main(String[] args) {
Scanner in = new Scanner(System.in); long T, n, k, mod;
T = in.nextLong();
for(long t = 1; t <= T; ++t) {
n = in.nextLong();
k = in.nextLong();
mod = in.nextLong(); k = Math.min(n, k);
long ans = n - k + 1 + (n - k) * (n - k - 1);
if(k < n)
ans += (k - 1) * (n - k);
for(long i = 1; i <= k; ++i)
ans = ans * i % mod;
System.out.println("Case #" + t + ": " + ans);
} in.close();
}
}
最新文章
- windows命令——taskmgr 1
- Android性能优化方法(五)
- Esfog_UnityShader教程_漫反射DiffuseReflection
- Nagios Apache报Internal Server Error错误的解决方法
- 020自动化测试 PK 手动测试
- .NET下发送邮件遇到问题及解决方案
- JS--我发现,原来你是这样的JS:面向对象编程OOP[3]--(JS继承)
- 第五章:大数据 の HBase 进阶
- button点击切换,获取按钮ID
- 20175314 《Java程序设计》第八周学习总结
- free命令常用参数详解
- MySQL保存历史执行语句
- Ubuntu下安装JDK图文教程详解 jdk-java6-30 .bin 的处理方法
- Mock session,cookie,querystring in ASB.NET MVC
- PHP仿LED点阵,读取字库文字,并转化为二进制输出
- 多模块Maven项目如何使用javadoc插件生成文档
- Dubbo -- 系统学习 笔记 -- 示例 -- 结果缓存
- unity5 Text
- mybatis递归,一对多代码示例
- bzoj4753 最佳团体