Cwyy

分类

学习笔记(3) 比赛(1) 题解(24)

/ 注册

全部文章（共28篇）

题解 P4134 【[BJOI2012]连连看】

题解- P4134 连连看题目大意就是在区间中找出尽量多的数对,若两种情况下数对数相同使得若干对数对和尽量大。这道题目难点在于如何转换到熟悉的模型——最小费用最大流。但是题目要我们求数对和尽量大，所以我们只要把边权取反相当于求最小费用，最后答案再去一遍反即可。因为这样我们就可以用简单...

网络流

2020-01-20

1 673

题解 CF650D 【Zip-line】

题解- CF650D Zip-line 题目意思就是给你个序列以及多次操作，每次把换做求一遍（操作之间互不影响）显然每次修改暴力做是不可行的复杂度至少为。于是我们要思考每次修改会对答案形成怎样的影响。先对原序列每个点做一遍以他为结束的记为，以他作为起始的记为。易得原序列的就为。每次对...

树状数组 lis

2020-01-20

1 702

CSP 常用模板整理

并查集 #pragma GCC optimize(3) #include <bits/stdc++.h> #define For(i,a,b) for ( int i=(a);i<=(b);i++ ) #define Dow(i,a,b) for ( int i=(a);i>...

2019-11-14

1 892

题解 CF1082D Maximum Diameter Graph

题解-CF1082D Maximum Diameter Graph 题目大意就是让你构造一连通的无向图,使得每个点的度数并且要使得直径足够长。贪心：要让直径最长我们就要构造链，对于的点把他们加到链上去。然后把那些度为的点粘到链上去。最后一点也是最值得注意的是：我们还可以让链变得更加长...

构造贪心树的直径

2019-11-13

1 571

我可爱的珂朵莉树

我可爱的珂朵莉树珂朵莉树又名在数据随机的情况下极其优秀，会有些意想不到的结果思维简单暴力，操作简单粗暴实现原理就是现对于原数组相同颜色段推平然后一起处理。必然如果数据部随机一种颜色一格一定会有非常美妙的效果。实现方式初始化我们可以用一个三元组分别表示被推平后用来维护...

ODT

2019-11-07

2 582

题解 P3658 [USACO17FEB]【cdq模板题】

题解- P3658 Why Did the Cow Cross the Road III P 题目大意很小清新。就是给你两个排列使得两个排列中相同的数字两边相连。最后问你存在多少对数对满足有交叉且我们可以将题目转化的更加小清新。因为要有交显然满足以及为该元素在排列中的位置这样我们就可...

树状数组 cdq

2019-11-03

1 771

题解 P2824 [TJOI2016]排序

题解-P2824[HEOI2016/TJOI2016]排序题目意思就是给你一个排列，接下来有次操作每次将区间里的数降序或者升序排列，最后询问。这道题目主要是思想的转化，其他并无难点。对于这种思想的转化可以看戳这里。考虑离线。我们可以二分答案，对于每次二分的答案如果大于那么将变为否...

线段树二分转化

2019-10-28

2 758

题解-CF121E Lucky Array

题目大意就是有两种操作：把区间里面的数加上询问区间里有多少幸运数字由于最大值很小，直接预处理即可然后用树状数组维护区间这种数的个数。对于查询操作我们直接输出即可。对于修改操作我们可以暴力扫一遍对于原来是幸运数的数先再如果原数加上后为幸运数。时间复杂度： #include &l...

树状数组数论

2019-10-24

1 583

W round 1 题解

W round 1 题解比赛链接 https://www.luogu.org/contest/18397 .好题题目意思给一个巨大的杨辉三角，采用类似入门题(数字三角形)的方式求从顶点到指定点的最小累加和。输出样例，和样例中的第二组数据一样呀应该比较好写吧组合数问...

2019-10-16

2 706

题解 [USACO2004OPEN]洞穴里的牛之三

这道题目难度不是很大的，主要就是分类讨论。题目意思题目意思很简单，就是让你找出一对点对使得两点之间曼哈顿距离最大。暴力大法这道题目显然暴力不能过。正解这道题目难就难在分类讨论：我们已经知道原式为：我们先来考虑几种情况：当以及的时候，此时原式将会转换为：。然后移项可得：，要让这个柿子...

数论

2019-10-15

1 670