人丑心更黑

分类

读书笔记(1) 题解(52)

/ 注册

全部文章（共53篇）

牛客练习赛77部分题目题解

蒟蒻勉强打了3题，第4题开始不会了。。这里放了前4题的代码和题解。 A 小G的sum 显然对于任意一个数i，最大的约数为i，最小的约数为1.因此答案就是n+(1+2+3...n)=n+(1+n)*n/2注意开long long 代码： #include<bits/stdc++.h> ...

2021-02-28

0 448

每日一题4月17日华华给月月准备礼物二分答案

这题算是水题。。题目大意：给N根长度不一样的木棍，现在可以对木棍进行剪裁，问经过剪裁以后能否得到K根长度一样的木棍。多出来的可以不用。问最长可以剪裁成多少长度相同的K根木棍。N<=200000 思路：二分长度。然后每次判断当前二分的长度能不能组成K根木棍。代码： #include<b...

2021-02-26

0 495

4月16日逆序对数学公式题+快速幂

算是个水题。虽然我打表以后直接去了oeis.. 题目大意：给定一个长度为n，问长度为n的01串中有多少个逆序对。这里的逆序对为对于i<j,a[i]=1,a[j]=0n<=1e18 思路：数据范围很大，递推肯定是不行的。那么显然本题是一个公式题，或者需要矩阵优化的递推。暴力打表很简单，可以...

2021-02-26

0 506

每日一题4月14日 Treepath 树形dp or 思维

感觉树的题目做多了，每题都会往树形dp想。题目大意：给定一棵n个点的树，问其中有多少条长度为偶数的路径。路径的长度为经过的边的条数。x到y与y到x被视为同一条路径。路径的起点与终点不能相同。思路：第一反应是使用dfs计算每个点下面的奇数路径和偶数路径的数量。令f[i][0/1]表示从i出发到子...

2021-02-25

0 565

每日一题4月14日 Xorto 枚举+桶

给自己跪了，这道题居然没做出来o(╥﹏╥)o 题目大意：给定一个长度为n的整数数组，问有多少对互不重叠的非空区间，使得两个区间内的数的异或和为0。n<=1000,数组中的数字<100000 思路：一开始想的是枚举中间点，然后开一个f[i][k]数组表示到i点异或和为k的数量，然后从左算一...

2021-02-25

1 489

每日一题4月13日Accumulation Degree+201400 树学树形dp

原谅我前面一题每日一题没做。数学啊数学，太难了啊。。来看这里的每日一题，看到题目以为是网络流，直接点开了题解。发现推荐做201400树学。好的，那么先来看树学。链接：https://ac.nowcoder.com/acm/problem/201400题目大意：给一棵树，可以找一个点作为根，然后计算...

2021-02-25

0 434

每日一题4月9日 Running Median 堆 Or 优先队列

比较经典的一道题，以前在洛谷上做到过。题意：（原题是英文）给出n个数字，n为奇数。依次读入这些数字，读入奇数个数的时候，输出当前已输入的数字中的中位数。注意题目有多组数据。思路：算是套路题吧。我们可以利用两个堆来维护中位数，具体的操作是这样的：维护一个大顶堆一个小顶堆，接着我们每次维护当前的中位...

2021-02-10

0 552

每日一题4月8日黑白树树形dp

好久没做题了，之前放假稍微出去玩了一下。家里休息惰性又上来了，还是得抓一下自己！这题其实开了好久了，一直想不出来。后来去看了题解，其实基本的情况都考虑到了，但是不知道怎么解决。题意：给一颗n个节点的树，以1为根节点。一开始树是白色的，现在每次可以选择一个点进行染黑。每个点上有一个值k[i]。每次操...

2021-02-09

0 506

每日一题4月7日树乘法原理+思维

我太弱了。。看了本题的题解，给大佬们跪下了。题意：有一颗树，树有n个结点。有k种不同颜色的染料给树染色。一个染色方案是合法的，当且仅当对于所有相同颜色的点对(x,y)，x到y的路径上的所有点的颜色都要与x和y相同。请统计方案数。思路：如果要在树上解决这个问题，实在是太难处理了。参考了题解。首先...

2021-02-02

0 509

每日一题4月6日数码枚举优化、分块

本题对我这种蒟蒻来说还是太难了啊。。。首先想到的其实是分块打表，但是1e9的数据我连暴力都跑不出。题意：给定两个整数 l 和 r ，对于所有满足1 ≤ l ≤ x ≤ r ≤ 10^9 的 x ，把 x 的所有约数全部写下来。对于每个写下来的数，只保留最高位的那个数码。求1～9每个数码出现的次数...

2021-02-02

0 520