武汉大学新生寒假集训测试---Day4题解

C. Make It Equal

预处理出每个高度有多少个块,然后从上往下查看能不能在这切,如果不能就在它上面切一刀

C. Sequence Transformation

挺不好想……
题意是求1-n所有数的gcd,每次删去一个数再求一次gcd并输出,直到只剩一个,求输出内容的最大字典序
最开始gcd是1,下一个一定是2,那么希望2出现得越早越好,所以先删去所有的奇数。剩下的是2,4,6,8,10……
根据gcd(a*c,b*c)=gcd(a,b)*c,可以知道2,4,6,8,10……的gcd就是1,2,3……的二倍,因此同理不断删去此时奇数的二倍就可以了。
会变成4,8,12……也是1,2,3的四倍,同理。不断删去直到只剩一个。
有一种特殊情况(如样例1):最后剩下三个元素,比如1*x,2*x,3*x,那么应该先删去1*x和2*x。

B. Vasya and Isolated Vertices

给点数n边数m,求最小和最大的孤立点个数
最小很好想,让一条边只用来连接两个孤立的点就可以
最大就是尽可能构造一个最大的稠密图:可以直接模拟,每次把一个点加进来,和现有的所有的点连边,如果能连则孤立点数目-1

B. Forgery

看这个位置是否四周都是#,如果都是则在新图的这个地方按一下,最后比较新图和原图,一模一样就是yes,否则no
推论:其实不管这个印章是否对称长什么样都可以这么做(

A. Cashier

注意期间可以休息,第一个客人来之前可以休息,最后一个客人走之后也可以休息

A. Vasya and Chocolate

(这比新生赛那个买奶茶的题友好多了)

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注