Deep_Dark_FAntasy♂

未归档

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

/ 注册

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

HDU 4734(数位dp之memset优化)

常规想：dp[pos][sum],这状态是基本的。a是题目给定的，f(a)最大也就4600的样子，如果用memset优化，需要加一维dp[pos][4600][4600]来存f(a)的不同值。这个数组显然不合法。这个时候就要用减法了，dp[pos][sum]是枚举到pos位，小于等于sum的个数，这...

2021-01-27

1 754

Brexit Negotiations(反向拓扑)

https://vjudge.net/contest/419200#problem/B拓扑序从后往前，每次选最少时间就行这里用一个优先队列就能搞，有模板来着模板：https://www.cnblogs.com/atmacmer/p/5178666.html(要分清输入的是谁是谁的前继以反向拓扑)模板...

拓扑贪心

2021-01-23

1 782

A Color Game(区间dp)

来源：The 2020 ICPC Asia Taipei-Hsinchu Site Programming Contest链接：https://codeforces.com/gym/102835/problem/E对这些颜色进行分块是比较显然的操作，dp[i][j][q]维护在[i,j]这段区间只剩...

区间dp

2021-01-22

1 821

1087.过河解题报告(没写完)

设f[n]表示青蛙到达n位置最少需要踩到的石子数。rock[n]=1(n位置有石子)，0(n位置无石子)f[n]=min{f[n-i]+rock[n]}(s<=i<=t)这个方程时间复杂度是O(n)，在本题的1e9极限数据是无法出解的。优化方法：压缩法结论：px+(p+1)y=Q若采用跳...

2021-01-21

1 542

Prince and Princess

南京签到二题，博弈/思维。https://vjudge.net/contest/412295#problem/H1.a、b、c是王子一开始知道的。2.只有能够准确确定出才行。把题目解读成出题人想让你理解的那样就会发现这题很简单。特判1 0 0直接输出0即可如果a<=b, b总可以指定一个假公主...

博弈

2020-12-09

0 608

Codeforces Round #683 (Div. 2, by Meet IT)

A.让所有的都到sum即可 #include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >>...

2020-12-08

1 549

Codeforces Global Round 12 [date:12.6]

反思：cf题目需要抓住问题的根来解题。A.发现为了不让trygub出现只需要对字符串排一下序即可。 #include<bits/stdc++.h> using namespace std; int main() { int t; cin >> t; w...

2020-12-07

1 595

牛牛的无向图

链接：https://ac.nowcoder.com/acm/contest/7079/C题解：可以和旅游那道题一起分类到最小生成树里面，都是基于最小生成树的思想d(u,v)定义为无向图中点 u 能到达点 v 的所有路径中权值最小的路径的权值。而路径的权值定义为为路径中权值最大值。L按从小到大排序，...

最小生成树离线

2020-11-27

2 566

旅行

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

构造贪心思维

2020-11-27

2 616

装备合成

链接：https://ac.nowcoder.com/acm/contest/4743/C换元后三分，这题三分是利用三分确定极值存在的一个区间，然后在这个区间上再求解。 #include <bits/stdc++.h> using namespace std; #define IO io...

三分确定极值区间

2020-11-26

3 563