BZOJ2976:[POI2002]出圈游戏(exCRT)
2024-08-29 10:09:08
Description
有编号从1到n的n个小朋友在玩一种出圈的游戏,编号为i+1的小朋友站在编号为i小朋友左边。编号为1的小朋友站在编号为n的小朋友左边。首先编号为1的小朋友开始报数,接着站在左边的小朋友顺序报数,直到数到某个数字K时就出圈。直到所有的小朋友都出圈,则游戏完毕。游戏过程如下图所示。
Input
第一行有一个正整数n, 2 <= n <= 20,第二行有n 个整数其中第i个整数表示编号为i 的小朋友第i个出圈。
Output
求最小的K,如果不存在,则输出一个单词“NIE”
Sample Input
4
1 4 2 3
1 4 2 3
Sample Output
5
Solution
exCRT比较裸的题了,注意特判一下答案为0的情况
应该会exCRT就会这个题了
应该会exCRT就会这个题了
还有我竟然因为爆int调了半天也可以说是很丢人了QAQ
我就知道应该直接用long long
Code
#include<iostream>
#include<cstring>
#include<cstdio>
#define N (1001)
using namespace std; int n,x,q[N],m[N],a[N];
bool vis[N]; void exgcd(int a,int b,int &d,int &x,int &y)
{
if (!b){d=a; x=; y=; return;}
exgcd(b,a%b,d,y,x); y-=x*(a/b);
} int exCRT()
{
int M=m[],A=a[],d,x,y,t;
for (int i=; i<=n-; ++i)
{
exgcd(M,m[i],d,x,y);
if ((a[i]-A)%d) return -;
x*=(a[i]-A)/d; t=m[i]/d; x=(x%t+t)%t;
A=M*x+A; M=M/d*m[i]; A%=M;
}
A=(A%M+M)%M;
if (!A) A=M;
return A;
} int main()
{
scanf("%d",&n);
for (int i=; i<=n; ++i)
{
scanf("%d",&x);
q[x]=i;
} int now=,cnt=;
for (int i=; i<=n-; ++i)
{
m[i]=n-i+;
while ()
{
if (vis[now])
{
now=now%n+;
continue;
}
if (now==q[i])
{
a[i]=cnt;
vis[q[i]]=true;
cnt=;
break;
}
++cnt;
now=now%n+;
}
} int ans=exCRT();
if (ans==-) printf("NIE");
else printf("%d",ans);
}
最新文章
- Eclipse 快捷键 (应用中自己总结)
- java中值类型和引用类型的区别
- Zookeeper笔记(四)Zookeeper在Dubbo中的应用
- python之else总结
- iOS开发——语法篇&;swift经典语法总结
- 《APUE》第五章练习1
- 6个可以隐藏运行bat,浏览器等程序的方法
- Fedora14下首次搭建Samba服务器遇到的一些问题
- mvc vs iis默认页面
- @Html.CheckBoxFor为何输出两种控件
- cURL的运用,文字替换
- ACM HDU 1081 To The Max
- Python3使用PyQt5制作简单的画板/手写板
- [物理学与PDEs]第5章习题4 广义 Hookean 定律的张量的对称性
- Js中的提升
- jmeter压测
- easyui 回车搜索
- openSUSE搭建OpenVPN
- Unknown parameter datatype UNKNOW send from server.
- Windows内核编程之:分页内存与非分页内存