Deep_Dark_FAntasy♂

未归档

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

/ 注册

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

Intelligent Robot

链接：https://ac.nowcoder.com/acm/contest/7501/B思路：只考虑特殊点即墙的端点，起点和终点。对于每个点都与另外的所有点尝试建边，建边的条件是这个边不会穿过墙。那么最后跑个最短路即可。代码： #pragma GCC optimize(2) #pragma GCC...

dij 计算几何建图

2020-10-27

4 573

Zero Remainder Sum

#include<bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f int mp[75][75]; int dp[75][75][75][75]; //dp[i][j][k][r]定义为：当前行选了k个，和能够余r的最...

dp

2020-10-23

3 543

Camels and Bridge

链接：https://vjudge.net/contest/401586#problem/C题意：有n个骆驼过桥，骆驼的重量为w1,w2,...,wn，桥由M段连成，每段的长度为li,承重为wi,可以调整骆驼的先后顺序，问骆驼能通过桥首尾的最短距离为多少？思路：n很小，那么可以暴力出n的全排列。令d...

dp 二分

2020-10-22

4 566

E. Carrots for Rabbits

链接：https://codeforces.com/contest/1428/problem/E题目：有n个数，把n个数分成k份，使得这k个数的平方和最小思路：首先发现一个数分的越多，那么这个平方和越小设函数fi(x)表示将a[i]分成y份的平方和，我们发现一开始都是fi(1)，这样我就分了n个数了...

贪心函数

2020-10-20

4 669

cf(div1+div2)构造题：D. Bouncing Boomerangs

链接：https://codeforces.com/contest/1428/problem/D(每列最多放2个，注意读题~)从右边向左考虑，先说结论：a[i]=0, 不放a[i]=1,放在(i,i)a[i]=2,(i,i)放一个点，然后后面找一个a[j]=1(j>i)的点(且之前没被其他a[...

构造

2020-10-19

3 619

Function

链接：https://vjudge.net/contest/402242#problem/C思路：因为x都是正整数，所以一开始x都为1，由f(x+1)-f(x)=2aix+ai+bi，每次找到最小的f(x+1)-f(x)，然后这个函数的x+1，维护一下这个增长率。代码： #include<bi...

函数思想离散

2020-10-18

3 576

Biorhythms

链接：http://poj.org/problem?id=1006思路：中国剩余定理水题贴一个中国剩余定理：逆元不能用快速幂，而要用exgcd来求，之前没有注意，快速幂求逆元是费马小定理要求模数是质数的时候才可以。代码： #include <iostream> #include &l...

中国剩余定理

2020-10-18

2 572

Let's Play Nim

链接：https://vjudge.net/contest/401586#problem/D这道题显而易见仅与怎么进入nim游戏有关。这种题跟转化基本博弈模型或是算sg函数没有关系，属于自己想种策略把自己说服。如果n为奇数，后手进入nim游戏的时候成为先手，她希望nim和不等于0，我们站在她的角度思...

博弈水题

2020-10-16

4 651

MAX-=min

链接：https://vjudge.net/contest/401586#problem/B辗转相减法：https://www.cnblogs.com/HuangWj/p/11261870.html这样去想：假设最后答案为T，也就是所有数都为T。那么一开始任何一个数X都可以写成TTTT...的形式，...

辗转相减法 gcd

2020-10-16

2 484

I - Strength

链接：https://vjudge.net/contest/400607#problem/I思路：思路还是很简单的，要么把所有的防卫都打掉，要么留下所有的防卫。剩下就是些细节问题啦代码： #include<bits/stdc++.h> #define int long long usin...

贪心

2020-10-13

2 491