刚中考完那段时间比较无聊，报名了一个同步赛，报完名才发现成绩单是要挂到网上的,而且因为报的早给了一个很靠前的考号...那布星啊，赶紧学点东西，于是在一周内学了网络流，Treap以及一些数论。
Day1：
作为一个全国的信息学组织，官网竟然卡成这样，按理说OI选手应该学做网站也会简单一点吧...无法接受.jpg。终于还是在9点前拿到了题。浏览一遍题面感觉只有第一题比较可做，T2T3的暴力也不是很难打？
归程：https://www.luogu.org/problemnew/show/P4768
看到离线完全没有在意，写了一个最短路+BFS，50.本来还有10分可以写树剖，然而觉得写起来比较麻烦以至于没写。事实上离线的做法非常简单，最短路+并查集；关键是这个做法很有启发性，如果会写离线做法就离A题不远了。
T2写了next_permutation以及归并排序，期望得分8分，然而交错了题于是爆零。
T3写了4分的暴力，没有去重于是爆零。
于是Day1得分：50+0+0=50；
听有人说Cu线40，真是难以置信。
Day2：
因为Day1大爆炸，于是对Day2也没有什么希望。开题：XXX，XXX,多边形。emmmm多边形？计算几何吗？不过本来也没有打算做Day2T3于是愉快的开始看题啦。
第一眼感觉T1是个dp，T2网络流，T3...不知道是个什么...
仔细看T1，发现了一些奥妙重重的东西。“按照1-n的顺序”，顺序是固定的啊。“选择XXX的剑”，选剑也是固定的？必须一次把龙打死，不可以打好几个回合。那就不是dp了，好像没有什么决策之类的东西。使得x最小，二分！似乎并不满足单调性。
$$(a_i-atk_i*x)\%p_i=0$$
写出这个式子后仿佛发现了什么...看数据范围，“保证$p_i$是质数”，“lcm”，果然是个数论题目啊，感觉非常可做！
首先找一个set维护选哪些剑，然而set的各种操作非常不熟悉，调了好久决定手写一个Treap，此时大约10:00，还有三个半小时，难道连半道题都做不出来吗？
$$atk_i*x=a_i(\%p_i)$$
写了一个excrt(从网上抄的)解方程，然而似乎并不能解带系数的方程，难道是我把这道题想简单了吗？后来想到把$akt_i$的逆元乘过去就是普通的excrt啦。然而...P不是质数怎么办呢？一开始以为是无解，后来发现似乎并不是这样。可以把式子重新展开：
$$atk_i*x-a_i=p_i*y$$
可以把这里面的公因数全部除掉。看到这里你可能会觉得非常奇怪，因为除掉公因数的$p_i$有可能还是不是质数啊？逆元有两种求法，快速幂的方法肯定是不行了，但是扩欧还可以抢救一下。
Q:如果扩欧还是求不出逆元呢？A:这样就真的无解了。
再套用excrt，这道题就做完了。真的完成了吗，其实还没有。
这里面有几处乘法是爆longlong的，所以要用快速乘，另外也要注意只要是取模尽量往前提，和乘法合并在一起，比如说赛后改了一个小时的这个地方:
x=(a[i]-A)/d*x;
2 t=p[i]/d;
x=(x%t+t)%t;
如果这样写就会爆longlong，如果把第三行提到第一行边乘边取模就可以了。
顺便注意快速乘里面的左移应该写成这样：$a<<1LL$，每个常数都强转成longlong才保险。
其实还没有结束呢。对于任意的龙，我们还需要满足一个条件：$atk_i*x>=a_i$,不过这个地方还是比较简单的，因为这是个方程组，套用crt求最小整数的思想，任意解加减所有模数的最小公倍数后还是一个解，所以预处理一下把每条龙砍成非正数血的最小次数后取max，如果最终的答案小于这个值，就不停的加最小公倍数直到满足条件。
看起来好像不太难？然而我考试时提交的版本仅有35分，如果数组开到足够大可以有45分。这个AC思路我写了整整一天。也许，这个题对于NOI选手是个签到题？
// luogu-judger-enable-o2
# include <cstdio>
# include <iostream>
# include <cstdlib>
# define LL long long
# define inf (long long)(1e9) inline LL min (LL x,LL y) { if(x>y) return y; return x; }
inline LL max (LL x,LL y) { if(x>y) return x; return y; }
int T,n,m,num;
const int maxn=;
LL a[maxn],lcmm,minc,m1,m2,c1,c2;
LL p[maxn],ans;
LL g[maxn],x,exx,exy;
LL atk[maxn]; LL mu(LL a,LL b,LL p)
{
a=(a%p+p)%p;
b=(b%p+p)%p;
LL res=;
while(b)
{
if(b&1LL) res=(res+a)%p;
a=(a+a)%p;
b>>=1LL;
}
return res;
} struct node
{
node *ch[];
LL v;
int r,s,n;
int cmp(LL x)
{
if(x==v) return -;
if(x>v) return ;
return ;
}
void in(LL x)
{
v=x;
r=rand();
s=n=;
ch[]=ch[]=NULL;
}
void update()
{
s=n;
if(ch[]) s+=ch[]->s;
if(ch[]) s+=ch[]->s;
}
}*roo[],pol[maxn<<]; node *newnode()
{
static int cnt=;
return &pol[cnt++];
} void rotate(node *&n,int d)
{
node *k=n->ch[d^];
n->ch[d^]=k->ch[d];
k->ch[d]=n;
n->update();
k->update();
n=k;
} void insert(node *&n,LL x)
{
if(!n) n=newnode(),n->in(x);
else
{
int d=n->cmp(x);
if(d==-) ++n->n;
else
{
insert(n->ch[d],x);
if(n->ch[d]->r > n->r) rotate(n,d^);
}
n->update();
}
} LL lef(node *&n,LL x)
{
if(!n) return -inf;
if(n->v>x) return lef(n->ch[],x);
return max(n->v,lef(n->ch[],x));
} LL rig(node *&n,LL x)
{
if(!n) return inf;
if(n->v<=x) return rig(n->ch[],x);
return min(n->v,rig(n->ch[],x));
} void del(node *&n,LL x)
{
if(!n) return ;
int d=n->cmp(x);
if(d==-)
{
if(n->n>) n->n--;
else
{
if(!n->ch[]) n=n->ch[];
else if(!n->ch[]) n=n->ch[];
else
{
int f=(n->ch[]->r < n->ch[]->r?:);
rotate(n,f);
del(n->ch[f],x);
}
}
}
else del(n->ch[d],x);
if(n) n->update();
} LL gcd(LL a,LL b)
{
if (!b) return a;
else return gcd(b,a%b);
} void exgcd(LL a,LL b,LL &x,LL &y)
{
if (b==)
x=1LL,y=0LL;
else
exgcd(b,a%b,y,x),y-=x*(a/b);
} LL inv(LL v,LL p)
{
LL x,y,g;
exgcd(v,p,x,y);
g=gcd(x,y);
if (g>)
return -;
return (x%p+p)%p;
} LL lcm (LL a,LL b)
{
return a/gcd(a,b)*b;
} LL solve()
{
for (int i=;i<=n;i++)
{
LL g=gcd(a[i],gcd(atk[i],p[i]));
atk[i]/=g,p[i]/=g,a[i]/=g;
LL Inv=inv(atk[i],p[i]);
if (Inv<)
return -1LL;
a[i]=mu(a[i],Inv,p[i]);
}
LL M=p[],A=a[],t,d,x,y;
for(int i=;i<=n;++i)
{
d=gcd(M,p[i]);
exgcd(M,p[i],x,y);
if((a[i]-A)%d)
return -1LL;
t=p[i]/d;
x=mu((a[i]-A)/d,x,t);
x=(x%t+t)%t;
A=(A+mu(M,x,(LL)M/d*p[i]))%((LL)M/d*p[i]);
M=M/d*p[i];
}
A=(A%M+M)%M;
ans=A;
while (ans<minc) ans+=(LL)lcmm;
return ans;
} int main()
{
scanf("%d",&T);
for (num=;num<=T;num++)
{
minc=(LL)-;
scanf("%d%d",&n,&m);
for (int i=;i<=n;++i)
scanf("%lld",&a[i]);
for (int i=;i<=n;++i)
scanf("%lld",&p[i]);
for (int i=;i<=n;++i)
scanf("%lld",&g[i]);
for (int i=;i<=m;++i)
{
scanf("%lld",&x);
insert(roo[num],x);
}
if(n==) lcmm=p[];
if(n>=) lcmm=lcm(p[],p[]);
for (int i=;i<=n;++i)
lcmm=lcm(lcmm,p[i]);
for (int i=;i<=n;++i)
{
atk[i]=lef(roo[num],a[i]);
if(atk[i]<=) atk[i]=rig(roo[num],(LL)-);
del(roo[num],atk[i]);
if(a[i]%atk[i]==) minc=max(minc,a[i]/atk[i]);
else minc=max(minc,a[i]/atk[i]+(LL));
insert(roo[num],g[i]);
}
printf("%lld\n",solve());
}
return ;
}
屠龙勇士
这里强烈谴责T1的大样例，看起来非常庞大，检验性很强，然而我的35代码也可以过这个大样例。T2，T3其实弄点分不是很困难，但是T1写的太久了，最后就没开这两个题。
Day2得分：35+0+0=35；
于是这个比赛的得分：100(笔试)+50+35=185...Cu线199，于是就什么都没有啦。
实力不够是一个问题，但是还有一个问题就是考试的策略非常不合理。有5道题的正解确实是不会，但是唯一想到正解的题也没有写出高分来。
Day1的三道题都有不该丢的分，T1的65分离线其实想到了，但是因为已经写了一部分BFS舍不得扔掉就没写，5分的在线树剖其实也应该写一写(最后还剩很多时间),T2交错程序...,T3要是手出几组数据可能就想到判重的问题了。不过同步赛选手没有拿到大样例表示体验极差。T2有几个点其实相当于提答，但是也没有想到打打表。
Day2的T1挂到连暴力分都不如，首先数组只要开的下就尽量往大里开，如果不能保证正解能得分就写几个分段程序稳住分，n=1,m=1,p=1,p是质数的部分分其实都不难写吧。还有一些小一点的数据点其实可以枚举x。这样差不多就有70+了，T2T3连纯暴力都没写，听说2、30分的部分分也不是很难写。于是精神Cu。以后做题就有经验了，不要再犯这种错误啦，也要多学点东西。
---shzr
