expect2004

分类

Codeforces Round(2) Contests(11) review(2) 其他(1) 动态规划(19) 动态规划 - 区间DP(3) 动态规划 - 期望与概率DP(1) 动态规划 - 树形DP(4) 动态规划 - 状压DP(1) 动态规划 - 线性DP(1) 动态规划 - 背包(2) 图论 - Tarjan(4) 图论 - 二分图判定(2) 图论 - 拓扑排序(1) 图论 - 最短路(1) 图论 - 生成树(3) 字符串 - AC自动机(2) 字符串 - KMP(2) 字符串 - 后缀数组（SA）(3) 字符串 - 字典树（Trie）(1) 数学 - 其他(2) 数学 - 多项式(3) 数学 - 组合计数(1) 数学 - 莫比乌斯反演(2) 数学 - 高斯消元(2) 数据结构 - 分块(1) 数据结构 - 平衡树(1) 数据结构 - 树状数组(1) 数据结构 - 树链剖分(2) 数据结构 - 珂朵莉树(2) 数据结构 - 线段树(6) 数据结构 - 虚树(1) 未归档(6) 模板(5) 游记(3) 算法 - 2-SAT(2) 算法 - CDQ分治(1) 算法 - 搜索(2) 算法 - 树分治(2) 算法 - 矩阵树定理(1) 网络流(7) 网络流 - 二分图相关(1) 网络流 - 最大流(1) 网络流 - 最小割(6) 题解(22)

/ 注册

全部文章（共149篇）

【题解】Make Product Equal One

本题解同步发布于[本场总题解](https://www.luogu.org/blog/expect/CF580DIV2)，欢迎来踩 B - Make Product Equal One 要让个数乘积为，必须保证这个数列中只有或者，且的个数为偶数个。考虑贪心，设代表变为的代价，代表变为的代价，优先...

贪心

2019-08-30

0 531

【题解】XOR Guessing

这是一道交互题。一共有两次询问机会，第一次询问的100个数二进制后7位下全都为1，第二次询问的100个数二进制前7位都为1. 这样无论系统返回哪个的xor值，都可以推算出这范围内的数。 code： #include<bits/stdc++.h> using namespace std...

交互

2019-08-30

0 438

【题解】动态逆序对

本题可以使用分治完成。二维偏序根据偏序的定义，逆序对是一个二维偏序，但这个二维偏序比较特殊：以上两种情况都符合这个二维偏序。三维偏序但带修改二维偏序怎么做？我们将删除操作视为插入操作。则没有没删除的插入时间为，第个被删除的，插入时间为将插入时间作为第一维，数列位置为第...

CDQ分治

2019-08-30

0 551

【题解】教主的魔法

洛谷博客欢迎来踩。摘要分块，是一种优雅的暴力，它通过对数列分段，完成对数列一些区间操作和区间查询的操作，是一种根号算法。这篇学习笔记&题解是本萌新在学习分块过程中的一些感悟，希望能够帮助分块零基础的同学学会基础分块。 0 说明本文中，以下变量有特定的含义：：块的大小：被分...

分块暴力

2019-08-30

1 428

LG1393 动态逆序对

问题描述 LG1393 题解本题可以使用\(\mathrm{CDQ}\)分治完成。二维偏序根据偏序的定义，逆序对是一个二维偏序，但这个二维偏序比较特殊： \(i>j,a_i<a_j\) \(i<j,a_i>a_j\) 以上两种情况都符...

2019-08-20

0 498

LG3205/BZOJ1996 「HNOI2010」合唱队区间DP

区间DP 区间DP：显然是一个区间向左右拓展形成的下一个区间，具有包含关系，所以可以使用区间DP。状态设计：考虑和关路灯一样设计状态因为不知道当前这个区间是从哪个区间拓展而来，即不知道这个区间最后一个进来的人站在了哪里设\(f(i,j,0/1)\)代表区间\([i,j]...

2019-08-06

0 466

LG4170/BZOJ1260 「CQOI2007」涂***间DP

区间DP 发现可以转化为区间包含转移。考虑区间\([l,r]\)，分为两种情况。 \(col[l]=col[r]\) 此时相当于在涂\([l,r-1]\)或\([l+1,r]\)顺带着涂掉 \[f(i,j)=min[f(i+1,j),f(i,j-1)]\] 通常转移枚举转...

2019-08-06

0 472

NOIP2018普及组复赛游记

2018年11月10日，NOIP2018普及组复赛。这是我初中阶段最后一次复赛了。和往常一样，我们在预定的早上7点，没有出发。 10分钟之后，人终于到齐了，于是出发了，一路无话。到了南航，合照三张，在慧园食堂吃了午饭。赛前有听说是吉老师命题，非常紧张，几乎什么都没吃。总是在...

2018-11-10

0 569

UVA11374 Airport Express 正反两次最短路

问题描述洛谷（有翻译）吐槽一道坑题。如何对待商务票因为商务票只有一张，所以在\(k\)条边中只有一条边会被选中，很显然，最后这条边会被枚举。如何选择使用商务票的边假设我们正在枚举这条边，现在的边为\((u,v)\)，边权为\(w\)。那么现在的最小代价肯定...

2018-07-31

0 530