精神病科黄主任

分类

cf(33) dfs(3) dp（动态规划）(4) poj(1) 二分(7) 位运算(1) 双端队列(1) 娱乐(1) 并查集(3) 快速幂(1) 思维(1) 拓扑排序(1) 数学(11) 数论(2) 暴力(8) 最短路(1) 未归档(3) 栈(1) 预处理优化(3) 题解(119)

/ 注册

TA的专栏 60篇文章 0人订阅

56篇文章 1966人学习

4篇文章 1075人学习

全部文章（共204篇）

2019上海ICPC K.Color Graph

K.Color Graph 题意：给了n个点和m条无向边，让你删掉一些边，让剩余的边不存在自环和奇数环，求剩余的边的最大值。思路：这个考了一个二分图的性质，很遗憾当时确实不知道这个。就是说如果一个图不存在奇数环，那么一定是一个二分图那么问题就转化为，选择尽可能多的边使得该图是二分图那么我们对这n...

2020-05-01

5 777

Codeforces Round #634 (Div. 3) D - Anti-Sudoku

考虑到数独本身的独特性。即每行、每列、每个3 * 3块内的数字都是不重复的现在让改至少有一个重复，最多改九次。那我们直接考虑把每行的指定一个数改为另一个数即可比如把每行的1都换成2 #include<bits/stdc++.h> using namespace std; typ...

2020-05-01

0 497

Codeforces Round #635 (Div. 2)D. Xenia and Colorful Gems

考虑二分。枚举每个数组为x，然后去二分出来y的值，在二分第三个数组为z的值取最小即可。注意一下这里的二分，我们要二分出来第一个≥x的数为y，在二分出来第一个≥y的数为z 这样不一定最优，还要考虑比他小的第一个。假设y的位置为pos z的位置为pos1 那么组合的就是 b[pos] c[pos1]...

2020-05-01

0 612

C. Linova and Kingdom

n个点的树型结构，选择k个工业城市，其他都是旅游城市，问所有工业城市到1节点的幸福值总和最大多少。幸福值为经过的旅游城市的个数。优先的想法肯定是深度越大越好。但是考虑一下，对于一棵树的内部节点而言，一定要经过根u，如果根被选为工业城市，那么增加的幸福值就是dep[u]-siz[u] 什么意思呢？...

2020-05-01

0 597

C. Yet Another Counting Problem

Yet Another Counting Problem 题意很简单，求l到r之间有多少个数x满足 (x%a)%x!=(x%b)%a a和b的范围很小，很容易想到从a、b下手。考虑一下如果x=lcm(a,b) 那么一定满足 (x%a)%x==(x%b)%a 结果肯定是以周期性呈现出来的其实每lc...

2020-05-01

0 659

滑雪与时间胶囊来自专栏

求最多能经过的点，那其实就是从起点1开始看他后面能到多少个点。bfs或者dfs一下 O(n)复杂度即可处理出来结果对于第二个最少的距离，因为用胶囊回去的话，一条路只算一次长度，有点像最小生成树，但是因为题中的边是有方向的，不能够直接最小生成树，所以对高度降序，高度一样路径长度升序。因为高度降序，保证...

2020-04-30

0 703

牛客练习赛62

A根据Ramsey定理可知，n≥6的话，三边同色的三角形，直接输出yes否则就n^3暴力check #include<bits/stdc++.h> using namespace std; int a[15][15]; int main(){ int t;cin>>t...

2020-04-29

0 647

【每日一题】换个角度思考来自专栏

树状数组、询问离线排序我的想法是对询问离线，然后我们容易知道[l,r]的答案等于[1,r]的值减去[1,l-1]的值所以把每次询问的两个端点都拉出来，标记好是左端点还是右端点，将每个询问的[1,l-1]和[1,r]答案记录下来最后一次性输出差值即可。复杂度O( (n+m) * logn)貌似和大佬的...

2020-04-29

0 780

Interesting Matrix Problem

无语。。原来这是个水题。。当时看榜过的人并不多题目就没去看题意：给你一个n * m的矩阵，矩阵中a[i][j]=i * jq次询问，每次询问矩阵中第k小的元素是多大。很容易想到二分答案，因为答案具有单调性。那么对于每一行计算出有多少个≤二分的答案mid的个数，计算一下总个数和k比较即可。对于每一...

2020-04-28

0 536

【每日一题】美味佳肴来自专栏

01背包、排序很容易看出来这是一个01背包，但是因为价值跟所完成的时间有关(即跟选取顺序有关)，所以不能按照顺序直接背包，要先排序。考虑第i个和第j个两个菜，假设先完成第i个菜的价值更大，则有化简后得到按照上式排序后，01背包即可。注意答案可能为负，dp数组除dp[0]外应赋为无穷小 #includ...

2020-04-27

0 675