人丑心更黑

分类

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

/ 注册

全部文章（共53篇）

牛客练习赛78 部分题题解

打了20分钟的时候突然被叫去干活了。。心急火燎的交了A题。然后在8.50的时候坐下来想B题，最后在回寝室的床上打完了。。赛后补了C题。这里只放了前三题的题解，第四题开始不会了。。 A CCA的词典可以证明，对两个单词进行排序，如果排序以后相同，那么就可以认为两个原单词是一样的。注意到单词长度...

2021-03-14

0 543

每日一题4月30日换个角度思考离线+树状数组 or 分块

一个比较裸的题目吧。题目大意：给n个数m次询问。每次询问一个区间[l,r]和一个数k，问区间[l,r]中小于等于k的数字个数。n,m<=10^5，a[i]<=10^5 思路：直接暴力查找肯定是不可行的。直接开桶的话，空间上也不允许。但是我们可以分块。把n个数分成n/sqrt(n)个块，...

2021-03-12

0 529

每日一题4月29日 Symmetric Matrix 数学+递推

数学也太难了QWQ 题目大意：给一个n*n的矩阵，对于矩阵的每个元素a[i]∈{0,1,2}其中每行的a[i]的和为2，a[i][i]=0a[i][j]=a[j][i]问满足条件的矩阵有多少个。n<=10^5 思路：看题目感觉是个递推，但是完全不知道怎么做。参考了题解：本题给出的矩阵我们可以联...

2021-03-10

0 749

牛客IOI周赛23-普及组题解

这场的前三题都挺水的，第4题骗分也有80，挺良心的。。 A 小L的作文算送分题，直接一个for循环计数一下就可以了。 B 小L的多项式根据题意，f(x)可以O(n)计算得到，求f(x1)...f(xm)的话，再for循环一遍就可以了。复杂度O(n*m)。由于n,m<=1000，所以可...

2021-03-09

0 513

4月28日每日一题美味菜肴贪心+01背包

我好像忘记背包怎么写了。。写二维居然挂掉了。。改了一维才过。题目大意：题目解释起来比较复杂，直接贴原文链接：https://ac.nowcoder.com/acm/problem/14704 思路：看题目就给人浓浓的背包的感觉。显然不可能直接背包。我们假设最后已经得到了答案，那么我们必然会选择其中...

2021-03-08

0 518

每日一题4月27日 Removal dp+思维

憋了一天，终于把这题做出来了。题目大意：给一个长度为n的序列，现在可以从中移除m个元素得到一个新序列，问一共可以得到多少个互不相同的新序列。n<=10^5，m<=10思路：dp还是比较容易想到的。令dp[i][j]表示前i个元素移除了j个以后的方案数。那么显然第i个元素可选可不选，我们...

2021-03-07

0 511

每日一题4月24日子序列线性dp

我觉得我的数学需要回炉重造。。题目大意：给一个n个元素构成序列，从中选取子序列使得选取的子序列能够满足i<j,a[i]^j<a[j]<i。问一共有多少种子序列选择方案。n<=100,a[i]<=100 思路：其实我一开始的就想当然的认为了如果i<j<k,若...

2021-03-04

0 481

每日一题 4月23日边的染色思维+并查集+dfs

这题对我来说有一点点点点点....难！看题解都理解了好久。题目大意：给一个n个点m条边的无向图，有些边上已经标记了边权0或者1，现在要给剩下的边标记0或1，使得图中任意的环上的边异或和为0。问一共有几种标记方案。思路：本题有一个很巧妙的转化，就是把边权转为点权。对于一条边w(u,v)，我们将边权...

2021-03-04

0 546

每日一题 4月22日 K-th Number 二分答案+尺取

居然是二分，真的是没想到。。。题目大意：给n个数字ai，从这n个数中取任意长度不小于k的区间，对每个区间都获得其中的第k大的数。将这些区间中获得的第k大的数都放入数组b中，问数组b中的第m大的数字是多少？n<=100000,0<=ai<=10^9 思路：枚举区间肯定不行。这里考虑...

2021-03-03

0 468

每日一题4月21日糖糖别胡说思维+区间修改

这道题想了很久，但是自己思路局限性太大了。题目大意：比较麻烦，就不解释了。原文贴一下：从前，有n只萌萌的糖糖，他们分成了两组一起玩游戏。他们会排成一排，第i只糖糖会随机得到一个能力值bi。从第i秒的时候，第i只糖糖就可以消灭掉所有排在他前面的和他不是同一组的且能力值小于他的糖糖。请在这里输入引...

2021-03-01

0 523