AROY

分类

不会DP的羸弱(1) 每日一题(29) 补题变更强(8)

/ 注册

全部文章（共38篇）

【每日一题0414】异或前缀和

https://ac.nowcoder.com/acm/problem/14247给定一个长度为n的整数数组，问有多少对互不重叠的非空区间，使得两个区间内的数的异或和为0。异或前缀和序列[5,1,1]pre[1]=5 pre[2]=5^1 pre[3]=5^1^1区间[2,3]的异或则=p...

2020-04-20

1 609

【每日一题0413】树型dp+换根

201400 树学 n个点和n-1条边（树），选择一个点作为根节点使得所有点的深度和最小。用表示以i为根的时候的深度和，表示i子树含有的节点和；每个节点的深度；假设u是v的父亲；则 #include <bits/stdc++.h> using namespace std; #defi...

2020-04-19

0 519

【牛客小白月赛24】补题（离散化，树剖）TODO

这次比赛啥都不说了===心酸。这次小白赛难度其实不高，除了A之外我应该都能做出来才对===心酸FG很简单，不写题解了。A放弃了-- H 好朋友——并查集+离散化先把所有朋友关系合并到并查集里面；然后枚举敌人关系，只要两者在一个朋友集合里面就是矛盾的。当时只用了并查集没过，想着10^9数值的话tre...

2020-04-19

0 598

【牛客练习赛61】4月10日贪心/dfs/最短路

https://ac.nowcoder.com/acm/contest/5026 还是好菜=.=.=卡在B时间太长了，一直没找出自己思路哪里错误。。。以后比赛30分钟搞不出一道题直接跳过吧==== B 贪心设操作次数是ans，从减一操作上来讲，必然等于两个数中的较大者；所以这道题贪心是去想怎么使...

2020-04-10

0 654

【每日一题】树上dfs+贪心

https://ac.nowcoder.com/acm/problem/13249一棵n个点的有根树，1号点为根，相邻的两个节点之间的距离为1。树上每个节点i对应一个值k[i]。每个点都有一个颜色，初始的时候所有点都是白色的。你需要通过一系列操作使得最终每个点变成黑色。每次操作需要选择一个节点i，i...

2020-04-09

0 592

【每日一题】枚举优化数码待补题

https://ac.nowcoder.com/discuss/399522?type=101&order=0&pos=14&page=2 #include <bits/stdc++.h> using namespace std; #define int lon...

2020-04-09

0 580

【每日一题】转换思维/树上dfs

https://ac.nowcoder.com/acm/problem/13886 是我最喜欢的树上dfs~给你一棵 n 个节点的树（保证 n是偶数），你需要将 nn个节点分为 n/2 个点对，使得每个点对的两个点的距离的和最小。关键点：思维转换:选点两两配对求距离和--》转换成选边在最短的...

2020-04-09

0 527

【每日一题】dfs序/DP

https://ac.nowcoder.com/acm/problem/13611shy有一颗树，树有n个结点。有k种不同颜色的染料给树染色。一个染色方案是合法的，当且仅当对于所有相同颜色的点对(x,y)，x到y的路径上的所有点的颜色都要与x和y相同。请统计方案数。题目：给k个联通块染色学习到了...

2020-04-09

0 642

【牛客算法周周练1】题解A/C/E

https://ac.nowcoder.com/acm/contest/5086#question A 前缀和一个数移到左边所减少的量= 增加的量为总的减少量维护前缀和，枚举下标从k~n-1,找出最少的减少量delta即可 #include <bits/stdc++.h> using...

2020-04-07

0 573

【每日一题】树上DFS

树上DP https://ac.nowcoder.com/acm/problem/22598 题目：在以S为根的树上删掉权值和尽量小的一些边使得S和每一个叶子节点都不连通。关于树的题目真是丰富啊====树是最能体现递归的，递归是从顶向下的，转化成从底向上就变成了DP，所以“树上”的题目真是前变万...

2020-04-05

0 544