DAY2 B组
T1
2676. 调整 (Standard IO)
Time Limits: 1000 ms Memory Limits: 131072 KB Detailed Limits
Goto ProblemSet一看到题我想到的是求最短路,然后记录路径从大到小排序,从最大的开始删,用计数器记录次数,然而很快就被旁桌推翻了。(旁桌说这可能是dp,我说T1就dp不可能,后文打脸)
想法如下:
如图,若求最短路结果是从1—〉2,2—〉3,长度为6,若要将最短路改为1,答案是2,但可以直接从1—〉3,答案为1。
最后还是硬着头皮交,就过了一个点。
dalao说是dp(真香)。然而也没听懂。等懂了回来补代码。
看一下今天高分(lh)的题解(我是真的写不出来)
第一遍看完有点感觉了,但是不会实现。
T2
2677. 树A (Standard IO)
Time Limits: 2000 ms Memory Limits: 131072 KB Detailed Limits
Goto ProblemSet(0706)
因为有更改权值和问讯,第一个想到的是树状数组。然而想了想感觉不会这么难(其实不会打)就放弃了。打了一个简单的搜索,人生第一次加上了记忆化和小剪枝,过了样例觉得50左右,然而出来以后只有9.1。
仍然是dalao讲题(hin迷)讲到重儿子,重边,马上baidu。
仍然不会,等研究出来补码。
(0707老师又讲了一遍才清楚,早上来写题解qwq)
注意这道题存图时要用邻接链表,(若用邻接矩阵空间太大,并且记录dfs序的时候也会方便很多)
int x,y; for(int i=1;i<n;i++){ cin>>x>>y; lb[x].push_back(y); lb[y].push_back(x); }
询问
询问中要用到的知识点:前缀和,LCA(最近公共祖先)
设一个树上前缀和数组,表示节点到根的所有点的权值和。(如h[2]=1+2=3),先判断被询问的两个点是否直接是一条直链(如询问1—>2)。
若为直链,输出它们前缀和的差,若不为一条直链,找出它们的lca,根据容斥原理,求出它们的权值和。如图,4到5的权值和=sum[4]+sum[5]-2*sum[2]。
更改
更改中要用到的知识点:DFS序,树状数组
具体还不太明白...
T3
2678. 树B (Standard IO)
Time Limits: 2000 ms Memory Limits: 131072 KB Detailed Limits
Goto ProblemSetT4
2679. 跨时代 (Standard IO)
Time Limits: 1000 ms Memory Limits: 131072 KB Detailed Limits
Goto ProblemSet