HDU 5668 Circle
2024-10-21 14:26:19
中国剩余定理。
可以手动模拟一下每一次开始的人的编号和结束的人的编号。
每次删掉一个人,对剩下的人重新编号。
这样一次模拟下来,可以得到n个方程
形如:(u[i]+k)%(n-i+1)=v[i]
化简一下就是:k%(n-i+1)=v[i]-u[i]%(n-i+1)
接下来就是求解最小的k,满足所有式子
中国剩余定理板子一套就AC了......
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std; typedef long long LL;
const int maxn = ;
int n, T;
int s[maxn], flag[maxn], tmp[maxn]; int u[], v[];
LL a[maxn], b[maxn]; void ls()
{
int cnt = ;
for (int i = ; i <= n; i++)
{
if (flag[i] == )
tmp[cnt++] = i;
}
} int Find(int a)
{
for (int i = a; i <= n; i++)
if (flag[i] == ) return i;
for (int i = ; i <= a; i++)
if (flag[i] == ) return i;
} int f2(int a)
{
for (int i = ;; i++)
if (tmp[i] == a) return i;
} void egcd(LL a, LL b, LL&d, LL&x, LL&y)
{
if (!b) { d = a, x = , y = ; }
else
{
egcd(b, a%b, d, y, x);
y -= x*(a / b);
}
} LL lmes() {
LL M = a[], R = b[], x, y, d;
for (int i = ; i <= n; i++) {
egcd(M, a[i], d, x, y);
if ((b[i] - R) % d) return -;
x = (b[i] - R) / d*x % (a[i] / d);
R += x*M;
M = M / d*a[i];
R %= M;
}
return (R + M) % M ? (R + M) % M : M;
} void exgcd(LL a, LL b, LL &d, LL &x, LL &y)
{
if (b == )
d = a, x = , y = ;
else
{
exgcd(b, a%b, d, y, x);
y -= x * (a / b);
}
} LL china(LL n, LL m[], LL a[])
{
LL aa = a[];
LL mm = m[];
for (int i = ; i<n; i++)
{
LL sub = (a[i] - aa);
LL d, x, y;
exgcd(mm, m[i], d, x, y);
if (sub % d) return -; LL new_m = m[i] / d;
new_m = (sub / d*x%new_m + new_m) % new_m;
aa = mm*new_m + aa;
mm = mm*m[i] / d;
}
aa = (aa + mm) % mm;
return aa ? aa : mm;
} int main()
{
scanf("%d", &T);
while (T--)
{
scanf("%d", &n);
for (int i = ; i <= n; i++)
{
int ai; scanf("%d", &ai);
s[ai] = i;
}
memset(flag, , sizeof flag); u[] = , v[] = s[];
if (v[] == n) v[] = ; flag[s[]] = ; for (int i = ; i <= n; i++)
{
int st, en;
ls();
st = Find(s[i - ]), st = f2(st), st = st - ;
if (st == -) st = n - i;
en = f2(s[i]), u[i] = st;
v[i] = en; if (v[i] == n - i+) v[i] = ;
flag[s[i]] = ;
}
/*
for (int i = 1; i <= n; i++)
printf("%d %d\n", u[i], v[i]);
*/ //接下来就是求解最小的k,满足所有式子
//k%(n-i+1)=v[i]-u[i]%(n-i+1) for (int i = ; i <= n; i++)
{
a[i] = (LL)(n - i + );
b[i] = (LL)(v[i] - u[i] % (n - i + ));
}
LL k = china(n, a + , b + );
if (k == -) printf("Creation August is a SB!\n");
else printf("%lld\n", k);
}
return ;
}
最新文章
- [bzoj3673][可持久化并查集 by zky] (rope(可持久化数组)+并查集=可持久化并查集)
- chrome浏览器调试typescript
- php复习第一章—1.1php 简介
- fir.im Weekly - Stanford 的 Swift 课程来了
- z/os上的tar和gzip
- 使用mongo-java-driver3.0.2.jar和mongodb3.0在java代码中的用户验证4
- git(4)如何在windows上安装git
- 文件和目录之设置用户ID和设置组ID
- AndroidUI组件之ActionBar--基于下拉的导航方式
- 《Programming WPF》翻译 第7章 5.可视化层编程
- 【Unity3d】【项目学习心得】从资源server下载资源(一)
- bug:翻页
- MkDocs项目文档生成器
- teachable-machine:探索机器学习如何工作,浏览器中实时浏览
- 从壹开始前后端分离 [ Vue2.0+.NET Core2.1] 十四 ║ VUE 计划书 &; 我的前后端开发简史
- Groovy语言学习--语法基础(2)
- Ansible系列(四):playbook应用和roles自动化批量安装示例
- Java基础再复习(继承、多态、方法内部类**、HashMap用法**、参数传递**)
- Alberta family&#39;s QR code is world&#39;s largest corn maze
- 【JAVAWEB学习笔记】19_事务概述、操作、特性和隔离级别