UVA305 - Joseph(数论 + 打表)
2024-08-26 05:02:22
UVA305 - Joseph(数论 + 打表)
题目大意:约瑟夫环问题:n个人围成一圈,每次都淘汰第m个人,问最后一个幸存下来的人的编号。
这题的意思有点不一样,它规定前面的k个人是好人,后面的k个人是坏人(2
∗
k形成环)。问最小的m是多少,可以先把后面的k个坏人淘汰再淘汰好人。
解题思路:这题有个递推式:ai = (ai - 1 + m - 1) % (2
∗
k - (i - 1))
ai表示第i次淘汰的人的编号。后面取余的是剩下的人数。
注意这题的k仅仅可能有14种,可是測试的例子可能有非常多,所以要先将每种k的可能相应的值算出来保存下来。不然会超时。
代码:
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 20;A
int solve (int k) {
int n = 2 * k;
int m = k + 1;
int pre, cnt;
while (1) {
cnt = 1;
pre = (m % n) == 0 ? n : m % n;
while (cnt <= k) {
if (pre <= k)
break;
pre = (pre + m - 1) % (n - cnt) == 0 ? (n - cnt) : (pre + m - 1) % (n - cnt);
cnt++;
}
if (cnt == k + 1)
return m;
else {
if (m % n == 0)
m += k + 1;
else
m++;
}
}
}
int main () {
int k;
int ans[N];
for (int i = 1; i < 15; i++)
ans[i] = solve(i);
while (scanf ("%d", &k) && k) {
printf ("%d\n", ans[k]);
}
return 0;
}
最新文章
- h5面试题集合
- Android 实现QQ扩展listview(expandlistview)
- 用js加密你的重要信息
- #CSDN刷票门# 有没有人在恶意刷票?CSDN请告诉我!用24小时监控数据说话!
- web服务器之nginx与apache
- [Angularjs]ng-class,ng-class-even,ng-class-odd
- Linux创建线程
- JAVA类与对象(五)----对象的生成、使用
- ASP.NET 之 检测到在集成的托管管道模式下不适用的ASP.NET设置
- HDU 5965 Gym Class 贪心+toposort
- WebService-相关概念介绍
- hdu 4055 Number String(有点思维的DP)
- 【NOIP2014】Day1题解+代码
- 利用jackson-databind,复杂对象对象和json数据互转
- 【转】Shell执行MySql操作
- 【翻译】在Ext JS应用程序中构建可维护的控制器
- 结合FireBreath在Chrome/FireFox的多进程模式下崩溃一例
- 转:为什么要有Spring?
- 使用laravel搭建CURD后台页面
- 【Linux】SecureCRT连接Linux乱码