Deep_Dark_FAntasy♂

未归档

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

/ 注册

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

「一本通 1.2 例 3」曲线

三分，主要解决单峰问题（求单峰），不过递增或递减链接：https://loj.ac/p/10013画图可以看出F(x)是一个单峰函数，在函数定义域内使用三分法即可。 int a[N], b[N], c[N]; int t, n; inline double cal(double x) { d...

三分

2020-11-26

3 597

四个选项

链接：https://ac.nowcoder.com/acm/contest/5026/C先dfs一遍，求出每个连通块有多少个点，把这个东西作为一个连通块的体积，一个连通块就是一个物品,这样就是在求恰好装满这4个体积分别为na，nb，nc，nd的背包有多少种方案。dp[i][x1][x2][x3][...

2020-11-26

3 494

吃水果

链接：https://ac.nowcoder.com/acm/contest/5026/B贪心：如果x==y，直接输出x，假设x < y, x不断乘以2，直到x > y/2 && x<=y，可以想象，如果x，y同时减1，肯定会到y是x两倍的情况，这时候x*2即可，这...

2020-11-25

3 430

序列卷积之和

链接：https://ac.nowcoder.com/acm/contest/5633/C解法1：这题看到一个不停使用前缀和优化最后达成O(n)计算的方法，感觉很有趣他的分析过程是这样：首先暴力4重循环 for(int l=1; l<=n; l++){ for(int r=l; r&l...

2020-11-25

3 589

生涯回忆录

链接：https://ac.nowcoder.com/acm/contest/9033/C求a的所有子集的mex之和思路：虽然a[i]到1e9，但这n个数的任意子集的mex只会是1到n+1的一个数，因此从1到n+1枚举每个数作为mex的情况即可。一个数i作为mex，显然1~i-1的数都要每个至少选一...

排列组合

2020-11-25

4 508

J. 挑选队列

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

思维

2020-11-24

4 522

atcoder.Camels and Bridge

链接：https://atcoder.jp/contests/arc105/tasks/arc105_c?lang=en好题，一直打算写题解，鸽了好久。首先N<8,8!=40320,dfs暴力枚举全排列。然后看这个顺序过桥的从头到尾的最短距离是多少，我一开始构造的dp方程不对dp[i]=min...

dp困难题二分

2020-11-06

4 565

2017 China Collegiate Programming Contest

题目链接：http://acm.hdu.edu.cn/downloads/CCPC2018-Hangzhou-ProblemSet.pdf总结：上来是俩水题，然后接着看B，C题其实都是思维水题。B题不需要推公式，dfs可以直接卡过，C题手动模拟出结论？不过暴露出来了我对博弈的有点遗忘和数学公式推理薄...

题解

2020-11-06

4 529

C. The Delivery Dilemma

链接：https://codeforces.com/contest/1443/problem/C题意：对于每道菜i，点外卖的话花费a[i],自己去拿的话花费b[i],外卖的时间都是平行的。问最短多长时间获得所有外卖？思路：二分最后答案，维护一个sum为自己取外卖的时间，二分的时候贪心的去考虑,如果a...

二分贪心

2020-11-03

4 752

B. Reverse Binary Strings

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

构造贪心思维

2020-10-28

4 709