ZigZagK的博客
[扩展欧几里得]BZOJ1407(Noi2002)【Savage】题解
[扩展欧几里得]BZOJ1407(Noi2002)【Savage】题解
2018年7月9日 13:34
BZOJ
查看标签

题目概述

有 $n$ 个JZ在一个长度为 $m$ 的环上,第 $i$ 个JZ刚开始在 $c_i$ ,每天会顺时针走 $p_i$ 的路程到那里虐人,共虐 $l_i$ 天。如果一个人在同一天被多个JZ虐了就会疯掉,这是JZ不想看到的(否则没人虐了)。问 $m$ 至少为多大使得没有人疯掉。

解题报告

$m$ 不满足单调性,所以爆枚 $m$ ,然后 $n^2$ 验证是否有两个JZ会在停止之前走到一起:

$$ c_i+p_ix\equiv c_j+p_jx\ (mod\ m)\Leftrightarrow (p_j-p_i)x\equiv c_i-c_j\ (mod\ m) $$

解同余方程得出最小的 $x$ ,然后判断 $x>l_i\ or\ x>l_j$ 。

ps: $m​$ 至少要是 $max\{c_n\}​$ ,被坑惨。

示例程序

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
#include<cstdio> using namespace std; typedef long long LL; const int maxn=15; int n,ans,c[maxn+5],p[maxn+5],l[maxn+5]; int exgcd(int a,int b,LL &x,LL &y) {if (!b) return x=1,y=0,a;int r=exgcd(b,a%b,y,x);return y-=a/b*x,r;} inline bool check(int MOD){ for (int i=1;i<n;i++) for (int j=i+1;j<=n;j++){ int A=p[j]-p[i],C=c[i]-c[j],t;LL x,y;t=exgcd(A,MOD,x,y);if (C%t) continue; x=x*C/t%(MOD/t);if (x<0) x+=MOD/t;if (x<=l[i]&&x<=l[j]) return false; } return true; } int main(){ freopen("program.in","r",stdin); freopen("program.out","w",stdout); for (int i=(scanf("%d",&n),1);i<=n;i++) scanf("%d%d%d",&c[i],&p[i],&l[i]),ans=c[i]>ans?c[i]:ans; for (;ans<=1e6;ans++) if (check(ans)) break; return printf("%d\n",ans),0; }
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
本文写于 2460 天前,最后更新于 2282 天前。
部分信息可能已经过时,博主也可能已经无法对其内容进行解答。
OK
  1. 1 Skyscape Plum - Melodic Artist
  2. 2 ほしのおとしもの ああああ
  3. 3 感情の摩天楼 ~ Cosmic Mind 上海アリス幻樂団
  4. 4 秘匿されたフォーシーズンズ 上海アリス幻樂団
  5. 5 Ideal and the Real 小西利樹
  6. 6 Undertale Toby Fox
  7. 7 First Steps Lena Raine
  8. 8 Mirror Temple (Mirror Magic Mix) Lena Raine / 2 Mello
  9. 9 City of Tears Christopher Larkin
  10. 10 Tower Of Heaven (You Are Slaves) Feint
Skyscape - Plum - Melodic Artist
00:00 / 00:00
An audio error has occurred, player will skip forward in 2 seconds.

作曲 : Jeong Min Jae

纯音乐,请欣赏