ThinkofBlank

题解

未归档(4) 论文(10) 题单(1)

/ 注册

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

[SCOI2009]粉刷匠题解

一.闲话五一收假了，qwq好气哦二.题解终于做到原题了（雾）这次就是一个比较简单的dp，只是状态的复杂度。。。（请参考传纸条）我们设dp[i][j][k][0/1]表示已刷完i-1个木块，第i个木块我们刷了前j个格子，第j个格子是否刷成符合我们需求的颜色,我们一共刷了k次所能获得的不难发...

题解动态规划

2020-05-02

0 698

换个角度思考题解

看样子，应该有比较好的做法，不过，这道题，肯定要上主席树辣！！如果打算用主席树做这道题的话，这道题就是一个主席树的纯板子问题了。。。相当于查询区间l-r中1-x的数字的个数代码： #include<bits/stdc++.h> using namespace std; const ...

题解主席树数据结构

2020-04-29

0 652

牛客算法周周练4 题解

木有闲话qwq A.[SDOI2016]齿轮看到名字，发现是2016省选题，于是先放着打后面去了，然而，后来发现贼简单？？？只需要判断下各个边给出的约束条件是否有矛盾就行。我们可以考虑下稍微简化的版本: 给出m个约束条件，每个条件是u比v小x，求是否有矛盾。对于这个题，我们可以直接令一个点为0...

题解

2020-04-29

1 882

Symmetric Matrix 题解

太菜了，直接上OEIS 然后发现递推式: 于是。。。完了/x #include<bits/stdc++.h> using namespace std; const int N=1e5+1; int n,m; int a[N]; int main(){ while(~scanf(...

题解数论

2020-04-28

2 1056

美味菜肴题解

一.闲谈好吧，又是个套路题。。。我对题面已无力吐槽。。。“第3-n+2行”明明应该是“第3-m+2行”，害我debug好久qwq 二.题解首先，明显这是一个01背包问题（一开始看到食材无限时，以为是完全背包，结果被样例2卡了，样例出的不错。。。）当然，我们直接打01背包是会错的，为什么？因为...

排序题解动态规划

2020-04-27

1 799

“Shopee杯” e起来编程暨武汉大学2020年大学生程序设计大赛决赛（重现赛）部分题题解

一.闲话由于我太菜了，打不动了就来写题解了 A.A Simple Problem about election 贪心即可先给自己票数加1，多余的尽量给票数增加后对自己排名无影响的人如果还有剩，则排名=现在排名+剩下的票数(每给剩余人一票一定会使得自身排名+1) 代码: #include<...

题解

2020-04-26

1 1042

Removal 题解

update:添加了个优化又是一道简单dp,qwq 我们读题，发现k和m的范围都很小，所以我们考虑从这里入手我们设dp[i][j]表示选了i个数，最后一个是j的方案数，那么就有：那么，我们想下转移。首先，我们枚举新增了一个数a[i] 那么，分为两种情况: 一.a[i]被剔除了这个情况下，...

题解动态规划

2020-04-24

4 928

子序列题解

update:新方法，树状数组优化dp，复杂度一道很简单的dp+数论题。。。我们设dp[i]表示以i结尾的子序列中成立的方案数那么，就有转移：答案就很显然了: 于是这题就基本做完了，不过，麻烦的是，你需要做这个式子如果我们直接算，最大的情况就可能搞出个,然后爆炸(当然，你要打个高精也没...

数论题解动态规划

2020-04-23

5 1154

边的染色题解

一.闲话今天这题着实有点难想啊。。。（也许我太菜了?qwq）字数警告二.题解首先，我们先考虑答案为0的情况——存在一个所以边的边权都确定的环，其中的边权异或和为1 考虑到做这个，边权未定的边并无任何影响，所以，我们先把这些边放到一边，先把边权确定的边全部连上，然后就开始做这道题了。首先，我...

图论题解研究

2020-04-22

8 1080

K-th Number 题解

Update:添加了一种常数小的做法一.闲话看了下大佬们的题解，然后。。。二分+尺取？？？我：。。。二.题解题目简意: 数组b的元素是，数组a中所有区间长度大于等于k的区间的第k大数(有点绕？) 求数组b中第m大的数要做这题，首先我们需要明白一个简单的性质，对于一个序列，我们如果添加进一...

优化题解数据结构

2020-04-21

10 1363