标签归档:51nod

51nod 1461 稳定桌 & codeforces 577C. Arthur and Table(贪心+权值线段树)

题面自己看吧。。。面试JD的时候居然问了个这个题(你敢信?),但是码力有限差一点就调出来就被面试官小姐姐打断了,被吐槽写得太慢了QAQ。。。吓哭了。。。估计多半是凉了。
就是枚举每个长度作为最大值的情况,那么比他大的全部删除,比他小的中删除最小的k个。前面的可以后缀和一下,前面的权值线段树上二分就行了。
贴个面试代码。。。

51nod 1135 原根

设m是正整数,a是整数,若a模m的阶等于φ(m),则称a为模m的一个原根。(其中φ(m)表示m的欧拉函数)
给出1个质数P,找出P最小的原根。
Input
输入1个质数P(3 <= P <= 10^9) Output 输出P最小的原根。 Input示例 3 Output示例 2 原根定理:如果模m有原根,那么它一共有个\(\phi(\phi(m))\)个原根。 模m有原根的充分条件:m=2,4,p^a,2*p^a,p为一个奇素数。 求模p的原根方法:偶数先转换成\(phi(p)\),然后分解质因数,挨个试。

51nod 1326 遥远的旅途

一个国家有N个城市,这些城市被标为0,1,2,…N-1。这些城市间连有M条道路,每条道路连接两个不同的城市,且道路都是双向的。一个小鹿喜欢在城市间沿着道路自由的穿梭,初始时小鹿在城市0处,它最终的目的地是城市N-1处。小鹿每在一个城市,它会选择一条道路,并沿着这条路一直走到另一个城市,然后再重复上述过程。每条道路会花费小鹿不同的时间走完,在城市中小鹿不花时间逗留。路程中,小鹿可以经过一条路多次也可以经过一个城市多次。给定城市间道路的信息,问小鹿是否有一种走法,从城市0出发到达城市N-1时,恰好一共花费T个单位的时间。如果存在输出“Possible”,否则输出“Impossible”。
注意,小鹿在整个过程中可以多次经过城市N-1,只要最终小鹿停在城市N-1即可。
例如样例中小鹿的行程可以是0->1->2->0->2.
Input

Output

Input示例

Output示例

是不是非常像上一场多校的1005啊QAQ。。。。

这个题目要求从0到n-1,那么我们需要把N-1所连出去的边中最小的 那个当成一个环,也是我们需要模的数。然后还是按照dij一次更新各个点的每种同余类的最小满足的距离。然后只需要保证t所对应的这一类的最小的值小于等于t即可。因为dis[x]存在的话,那么dis[x]肯定可以通过加模数的方法得到。