熠丶

题解

未归档(32)

/ 注册

做想做的事，见想见的人

全部文章 / 题解（共156篇）

[HNOI2012]矿场搭建来自专栏

题意给定一个无向图，问最少在几个点上设置出口，可以使得不管哪个点坍塌，其余所有点都可以与某个出口连通。求设置出口的数量及方案数。做法：Tarjan，割点前置芝士：割点思路：目前可公开情报：1.孤点：数量+1，方案数不变2.连通块无割点：数量+2，方案数3.连通块存在一个割点，数量+1...

2021-01-26

0 637

[HAOI2006]均分数据来自专栏

做法：随机+贪心思路：是个定值,可以先用tmp存下来只需求即可我们可以用random_shuffle()用来对原数据进行重新排序，然后利用贪心的思想（每次把数加在最小的组里），即可满足均方差最小。用while ((double)clock()/CLOCKS_PER_SEC<...

2021-01-25

1 639

质数与合数来自专栏

做法：贪心思路先判断FFF和GGG谁能赢再特判下第一轮能不能进行如果FFF能赢，那么按照贪心的想法，FFF一定要取自己能取最多的数量，GGG一定要取自己能取最少的数量即FFF拿走后剩下不小于n-k的最小的质数，GGG拿1个。如果FFF拿完后剩下1，2，3的数，GGG不能拿，游戏结束。如果...

2021-01-24

1 692

NC103反转字符串

做法：从后往前遍历字符串时间复杂度：代码 class Solution { public: /** * 反转字符串 * @param str string字符串 * @return string字符串 */ string solve(s...

2021-01-24

3 688

合并两个有序的数组

做法先确定合并数组后数组的大小从后往前赋值，依次比较A和B数组较大的值赋值过去如果A、B数组中其中一个数组已经全部赋值过去，那么另一个数组剩余值从后往前依次赋值即可时间复杂度代码 class Solution { public: void merge(int A[], int m...

2021-01-14

3 779

[HAOI2006]旅行COMF 来自专栏

做法：类最小生成树思路： 1.先将边从大到小排 2.枚举最大边，然后进行连边 3.每次连边，如果连玩次边后发现s和t联通，那么最小边就是该边，并退出Kruskal 4.依次比较ans与最大边与最小边的比值 5.如果最大边枚举到不存在最小边s和t联通，那么退出枚举最小边代码 #include ...

2021-01-14

1 786

最长树链来自专栏

因为我太菜了，于是乎就找了份代码，理解了一下思路（把坑填完才能好好复习zz 思路： 1.先用筛求质数表,表长大约是sqrt(1e9) 2.建树 3.对权值进行质因数分解，并把对应的权值下标与素数对应起来存下来 4.然后树形dp求符合条件的最长链代码 #include<bits/stdc+...

2021-01-12

1 903

Mike and distribution 来自专栏

题意给两个长度为的数列A,B，要求至多选择个下标，使得A数组中选出的数的和的两倍大于sumA，B数组中选出的数的和的两倍大于sumB 做法：贪心思路： 1.先从大到小排序，第一关键字为a,第二关键字为b2.因为是选的数，我们可以先选取第一个数，之后在两个数中选一个b大的因为是选的数要越大越好，...

2021-01-11

0 736

小M和天平来自专栏

做法:dp 思路： 1.因为能测范围最大是，所以大于10000的范围必定测不出 2.考虑每一层状态转移，如果上一层存在，那么这一层分类讨论1）两边都不放石头,即2）放在多的那一侧,即3）放在少的那一侧,即代码 // Problem: 小M和天平 // Contest: NowCoder //...

2021-01-09

1 933

Beautiful Subarrays 来自专栏

做法：01Trie 思路我们可以先求异或前缀和然后套上字典树在执行find时如果 k 的这一位是 1 ，那么必须往 1 那一边走。如果 k 的这一位是 0 ，那么分情况讨论如果往 1 走，那么整个子树内所有的叶子结点都要计算。如果往 0 走，那么继续循环下去最后不要忘记等于k的个数代码 #inc...

2021-01-07

0 632