2020.5.18测试总结

· · 个人记录

这次考试几乎爆0了......

T1 Rsa

考试的时候被这个题面迷惑住了，然后就去求了φ(N)......

T飞了

其实正解现在想来很简单，知道了m^{e1}=c1(mod \ N)并且m^{e2}=c2(mod \ N)，如果要求m的最小正整数之，只需要找到满足e1·x+e2·y=1的x,y就行了。因为e1,e2互质，所以这个方程肯定是有解的，然后答案就是m^{e1·x} × m^{e2·y}，因为e2·y是个负数，所以答案就是m^{e1·x} × inv_{m^{-e2·y}}

注意得用龟速乘，不然会long \ long溢出

T2 小凸与矩阵

考试最后开的这题，写了个100%错的贪心，结果就这题得了40pts......

考完JF有人喊这题是个二分图，一下就懂了。

先二分答案，然后对于每一次二分到的答案，将矩阵中小于等于它的数的行和列对应的点连上一条边，求二分图最大匹配s，如果s>n-k说明比它大的数的个数小于k，这个答案就可行。

T3 小凸解密码

打了个暴力，最后还WA了四个点......得了0pt

考试后认真想了下这个题，发现这是个线段树。

先把区间倍长。

对于每次修改pos，考虑到修改的b只会有pos,pos+1,pos+n,pos+n+1，最多就4次，单点修改即可

对于每次询问，我们二分答案，如果区间[pos+mid,pos+n-mid]是一个被两个非0数隔断的区间，那么答案可行。

对于线段树每个节点，维护4个东西：左端点的值，右端点的值，区间的非0数个数，区间的连续为0段的个数

重载+号：

inline node operator + (node x,node y) {
    node z;
    z.lval=x.lval,z.rval=y.rval,z.num=x.num+y.num,z.cnt=x.cnt+y.cnt;
    if(x.num&&y.num&&(!x.rval||!y.lval)) ++z.cnt;
    return z; 
}

惨