|
今天做了以下几题：
洛谷：
1.P2419 [USACO08JAN]Cow Contest S
2.P7228 [COCI2015-2016#3] MOLEKULE
3.P6591 [YsOI2020]植树
4.P1037 [NOIP2002 普及组] 产生数
解题思路
1.假设现在你所在的班级成绩发布，你想知道自己的排名，如果你知道前面有多少人比你高，后面有多少人比你低，那么就可以得到你自己的排名。因此，此题首先采用floyd算法求出其中存在的大于和小于关系，统计每个节点的入度和出度，如果入度+出度==N-1，N为牛的数量，那么这个牛的排名就可以确定了。
2.先根据这些信息建立一颗树，要想得到代价最小，假设现在有祖父节点，父亲节点，孙子节点，那么方向祖父节点指向父亲节点，孙子节点也指向父亲节点这样的代价是1。根据此，得出奇数层有当前节点指向下一层，偶数层有下一层指向当前节点。
3.根据题意要计算每个节点的子节点数量，因此使用dfs遍历1号节点（任意都行），然后再枚举每一个节点，如果这个节点只有一条边，或者每条边的子节点数都相同，那么就能够作为答案。这里我之前做的时候用异或运算判断子节点数是否相同，其实是不行的，存在某些特殊的数组，使得最后答案为0但是不是相等的。
4.这个题用floyd算法计算每个数字有可能变到哪些数字 例如1 2 2 3，那么1 3也是成立的。然后统计字符串的每个位置都能有哪些变化，最后将每个位置的情况连乘就行了，特别要注意这里会超出long long范围，需要用到高精度的乘法。
ACWing
1.3661. 重置数列
2.3627. 最大差值
3.3578. 最大中位数
4. 字符串归类
5.4303. 链表
6.数字重构
其中
3.此题用到了二分去判断某一个数是否满足要求，有点类似二分答案
6.这个题解题的思想用到了贪心，具体看代码，要注意类似的解题技巧
4.这个题用到了并查集，但是不是把某个字符串作为代表，而是把字母,a,b,c,d…这种作为一类的代表，这个思想我只能说太妙了。
|