博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
BZOJ2976:[POI2002]出圈游戏(exCRT)
阅读量:5824 次
发布时间:2019-06-18

本文共 1784 字,大约阅读时间需要 5 分钟。

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

Sample Output

5
 

Solution

exCRT比较裸的题了,注意特判一下答案为0的情况
应该会exCRT就会这个题了
还有我竟然因为爆int调了半天也可以说是很丢人了QAQ
我就知道应该直接用long long

Code

1 #include
2 #include
3 #include
4 #define N (1001) 5 using namespace std; 6 7 int n,x,q[N],m[N],a[N]; 8 bool vis[N]; 9 10 void exgcd(int a,int b,int &d,int &x,int &y)11 {12 if (!b){d=a; x=1; y=0; return;}13 exgcd(b,a%b,d,y,x); y-=x*(a/b);14 }15 16 int exCRT()17 {18 int M=m[1],A=a[1],d,x,y,t;19 for (int i=2; i<=n-1; ++i)20 {21 exgcd(M,m[i],d,x,y);22 if ((a[i]-A)%d) return -1;23 x*=(a[i]-A)/d; t=m[i]/d; x=(x%t+t)%t;24 A=M*x+A; M=M/d*m[i]; A%=M;25 }26 A=(A%M+M)%M;27 if (!A) A=M;28 return A;29 }30 31 int main()32 {33 scanf("%d",&n);34 for (int i=1; i<=n; ++i)35 {36 scanf("%d",&x);37 q[x]=i;38 }39 40 int now=1,cnt=1;41 for (int i=1; i<=n-1; ++i)42 {43 m[i]=n-i+1;44 while (1)45 {46 if (vis[now])47 {48 now=now%n+1;49 continue;50 }51 if (now==q[i])52 {53 a[i]=cnt;54 vis[q[i]]=true;55 cnt=1;56 break;57 }58 ++cnt;59 now=now%n+1;60 }61 }62 63 int ans=exCRT();64 if (ans==-1) printf("NIE");65 else printf("%d",ans);66 }

转载于:https://www.cnblogs.com/refun/p/9230208.html

你可能感兴趣的文章
Ubuntu设置python3为默认版本
查看>>
JsonCpp 的使用
查看>>
问题账户需求分析
查看>>
JavaSE-代码块
查看>>
爬取所有校园新闻
查看>>
32、SpringBoot-整合Dubbo
查看>>
python面向对象基础
查看>>
HDU 2044 一只小蜜蜂(递归)
查看>>
docker 下 安装rancher 笔记
查看>>
spring两大核心对象IOC和AOP(新手理解)
查看>>
数据分析相关
查看>>
Python LDAP中的时间戳转换为Linux下时间
查看>>
微信小程序蓝牙连接小票打印机
查看>>
环境错误2
查看>>
C++_了解虚函数的概念
查看>>
全新jmeter视频已经上架
查看>>
Windows 8下如何删除无线配置文件
查看>>
解决Windows 7中文件关联和打开方式
查看>>
oracle系列(五)高级DBA必知的Oracle的备份与恢复(全录收集)
查看>>
hp 服务器通过串口重定向功能的使用
查看>>