Deep_Dark_FAntasy♂

未归档

Codeforces(3) 博弈论(3) 基本数论、组合数学（排列组合，容斥等）(14) 并查集(2) 数据结构(2) 深度优先搜索、广度优先搜索、搜索剪枝(8) 线性dp、背包问题、区间dp(15) 题解(12)

/ 注册

全部文章 / 未归档（共17篇）

旅行

链接：https://ac.nowcoder.com/acm/contest/7329/C题解：在选择排列的时候，从边权最大的递减构造，那么这条边就是当前待选择边权中的最大值了。因此构造一个最大生成树即可。 #include <bits/stdc++.h> using namespace...

构造贪心思维

2020-11-27

2 607

J. 挑选队列

题目链接：http://www.acmicpc.sdnu.edu.cn/problem/show/1637看了题解，出题人把1-n的数转化为图上的点去考虑的。如果两个数互质就连一条边，这样我实际上就在求两两都连边或者两两都不连边的三元组有多少个？直接求麻烦，考虑容斥，用所有情况的三元组减去不符合条件...

思维

2020-11-24

4 522

B. Reverse Binary Strings

链接:https://codeforces.com/contest/1437/problem/B一看题便知道这题存在什么规律(别马后炮行不行啊喂....)引入：意识到只有连续的1或者连续的0的时候才会去进行操作，如何消去连续的1呢？去找以0为端点，以当前1为端点的段，然后找个段调个头。同理对于0。为...

构造贪心思维

2020-10-28

4 709

D - Squares

链接：https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_d思路：分为x轴和y轴来进行组合考虑1.如果x轴A,B不相交，y轴随便的话假设A在左，B在右，我们考虑AB在x轴上有哪些情况，怎么算呢？b现在在最右边，a向右移动有n-a-b+1种方式，b向...

思维组合数学

2020-10-12

5 453

E-Game 来自专栏

题目链接：https://ac.nowcoder.com/acm/contest/5675/E题意：从右向左将木块推动，直到不能再推木块，求所有列的max的最小值。思路：比较直观的是二分答案M，然后从高度M，从右往左推，模拟。等价于求前缀平均值的最大。实际上从左往右先把所有能推到左边的都尽量平分到到...

二分模拟思维

2020-08-10

2 565

完全平方数的尾巴

题目链接：https://ac.nowcoder.com/acm/contest/6488/B题目大意：给一个数判断是否个完全平方数对1000取模得到的。解题思路：若x是由(kk)%1000得到的即x=(k%1000 * k%1000) % 1000只要取遍0-999的全部数就可知道可以所有取到的x...

取模思维

2020-07-30

1 424

I-Hard Math Problem 来自专栏

题目链接：https://ac.nowcoder.com/acm/contest/5670/I题目大意：大本营(H)必须与一个gold miner(G)和一个elixir collector(E)相邻，f(n,m)表示在nm的方格中能最多放多少个H。问n->∞， m-> ∞时，f(n,m...

思维无限贡献

2020-07-29

1 606

C-Combination of Physics and Maths(思维、等比定理) 来自专栏

题目链接：https://ac.nowcoder.com/acm/contest/5671/C题目大意：挑一些行和列，其交叉元素组成了一个矩阵，把矩阵的总数看作是力，把矩阵的最后一行之和看作是面积，问压强最大是多少。解题思路：先上结论：等比定理最大答案一定是在两个子列之中选的。可以证明：（结论证明放...

思维等比定理

2020-07-27

1 598

E-Easy Construction(构造，思维) 来自专栏

题目链接：https://ac.nowcoder.com/acm/contest/5671/E题目大意：给出n，k，问有没有一个1-n的排列，使得子串长度从1~n，总存在子串的和模n等于k。解题思路：1-n的和是(n+1)n/2能模n余k，则打表可知，奇数的时候k必须为0(别忘了为0的时候不输出k，...

构造打表思维

2020-07-27

1 604

Harder Gcd Problem 来自专栏

题目链接：https://ac.nowcoder.com/acm/contest/5669/H题目描述：把1~N的数选尽量多的组，使得每组gcd大于1.输出任意一种方案。做法：看到匹配gcd大于1的，我们很容易想到质数，质数和除其倍数的数的gcd都是等于1的。考虑哪些数字是不可能在匹配里的。首先1不...

贪心质数思维

2020-07-24

1 541