n0000000000o's Blog

Mol,que je pense, je suis

学习内容 Day_3

P1314 聪明的质监员分析：对于每一个 $Y_i$ ，有 \(Y_i = \sum\limits _{j} \times \sum\limits_jv_j , j \in [L_i, R_i] 且 w_j \geq W ，j为矿石编号\) 即区间 $[L_i ,R_i]$ 中所有 $w_j\geq W$ 的石块都选，在区间 $[L_i ,R_i]$ 内 $Y_i = ...

Posted by n0000000000o on July 20, 2018

学习内容 Day_1

POJ1753 Flip Game 题意简述： $4×4$ 的棋盘，只有黑白两种颜色的方块，翻动一个棋子后，其周围四个方块也会翻动（四连通）。现给定一个初始状态，求到达全黑或全白的最少翻动次数分析：棋盘 $4×4$ ,可以暴力枚举+状态压缩，强行枚举每翻转一次的状态，暴力宽搜求解。总共 $2^{16}(=65536)$ 种情况,每次要考虑 $16$ 种可能性，总的复杂度为 $O( 2^{...

Posted by n0000000000o on July 17, 2018

[模板]欧拉回路

题目 P1341 在纯无向图中直接考虑每个点的度数（旁边所连的边的条数），在图连通的情况下只有两种情况存在“一笔画” 所有点的度数都为偶数，此时以任意点为起点，必然存在“欧拉回路”，且会回到该点有且只有两点的度数为奇数，其他点度数都为偶数。此时从任意奇数点出发必然存在“欧拉道路”，且终点为另一奇数点（以上结论请自行证明，提示：从点的入度出度成对入手）在纯有向图中 ...

Posted by n0000000000o on June 28, 2018

[模板]最小生成树

题目 P3366 直接上代码，~ ~ #include <iostream> #include <algorithm> using namespace std; int n, m; const int Inf = 0x3f3f3f3f, maxn = 5000 + 5, maxm = 400000 + 5; int pre[maxn], paths[maxm];//...

Posted by n0000000000o on June 27, 2018

[模板]ST表

题目 P3865 直接上代码，~ ~ // ST表 #include <iostream> #include <cmath> #include <algorithm> #include <cstdio> using namespace std; int f[31][100005];//f用来记录区间最大值：从 j 开始长度为 2^i 的...

Posted by n0000000000o on June 27, 2018

题解P3367 [模板]并查集

题目 P3367 什么是并查集（百度：你就这么直接复制吗？，，）在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使...

Posted by n0000000000o on May 13, 2018

html学习记录

表示建网站真是一件难事。。。还要为此去学习html（不过学了肯定是有帮助的）懒得开印象笔记了 html 的基本格式网上抄的 <html> <head> <title>我的第一个 HTML 页面</title> </head> <body> <p>body 元素的内容会显示在浏览器中。<...

Posted by n0000000000o on April 21, 2018

题解UVA12657 Boxes in a Line

题目 UVA12657 关于这题的坑点，我已经不能再说什么了。。首先，对于数据上的坑点（也就是调试时要注意的）大家要注意这么几个我就简而言之了：对于初始化n为6的队列，要注意的操作 3 3 4 3 4 3 2 1 6 2 6 1 如果能把这几组数据过了，想必就没有问题了但其实，对于我这个小白来说，最坑的是。。。。最初判断时用的是 while(1) { ...

Posted by n0000000000o on April 18, 2018

题解P1887 乘积最大3

题目 P1887 只要仔细分析，我们就可以发现这是一道很简单的数学题（最开始以为是模拟，，后来看标签发现是数论）首先从最简单的问题开始分析，假设m为2，就是分为两组使之和最大，那么有一个结论已知x+y=k（k为常数），S=x*y，当x=y时，有S的最大值。（证明）由此可以类推，当一个数n被分为m份时，当每份数量相等，这m个数的乘积最大因而我们只需要使这m个数都相等就行了...

Posted by n0000000000o on April 18, 2018

题解P2907 农场周围的道路Roads Around The Farm

题目 P2907 分析题意，只要分后两群奶牛的差为k 这群奶牛就可以分假设总数q能被分为两部分，相差为k，那么设其中一部分为x，则这两群奶牛x1,x2可分别表示为 x1=x x2=x+k -> x+k + x=q –> x=(q-k)/2 有为了满足实际条件，x1，x2都要为整数（不可能有半只奶牛吧。。。）这便是主要思路。。在此附上代码： #in...

Posted by n0000000000o on April 18, 2018