「已注销」-CSDN博客

原创「日常训练」 Longest Run on a Snowboard （UVA-10285）

题意其实就一条二维的LIS，但是还是做的一愣一愣的，多努力。考虑dp[i][j]dp[i][j]dp[i][j]为从(i,j)出发的二维LIS的最大值，那么dp[i][j]=max{dp[i−di[k]][j−dj[k]]+1}dp[i][j]=max{dp[i−di[k]][j−dj[k]]+1}dp[i][j]=max\{dp[i-d_i[k]][j-d_j[k]]+1\}，取dp值时...

2018-08-14 11:02:33 206

原创「日常训练」COMMON 约数研究（HYSBZ-1968）

题意与分析感谢https://www.cnblogs.com/Leohh/p/7512960.html的题解。这题话说原来不在我的训练范围，正好有个同学问我，我就拿来做做。数学果然不是我擅长的啊，这么简单我都不会。。。简单说下自己的理解。从原题出发容易得到的朴素算法容易超时，所以要想到转化问题。原题要求1~n的因数之和，反过来说，就是求1~n中有几个数分别是1、2、…、n的倍数。这个弯...

2018-08-13 18:34:24 222

原创「暑期训练」「基础DP」免费馅饼（HDU-1176）

题意与分析中文题就不讲题意了。我是真的菜，菜出声。不妨思考一下，限制了我们决策的有哪些因素？一，所在的位置；二，所在的时间。还有吗？没有了，所以设dp[i][j]dp[i][j]dp[i][j]为第i秒在j处的最大馅饼数，有：dp[i][j]=dp[i][j]=max(dp[i−1][j−1],dp[i−1][j],dp[i−1][j+1])+f[i][j]dp[i][j]=dp[i][j...

2018-08-13 18:02:16 177

原创「暑期训练」「基础DP」FATE（HDU-2159）

题意与分析学习本题的时候遇到了一定的困难。看了题解才知道这是二重背包。本题的实质是二重完全背包。二维费用的背包问题是指：对于每件物品，具有两种不同的费用，选择这件物品必须同时付出这两种代价：对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。设第i件物品的两种代价分别为aiaia_i和bjbjb_j，两种代价可付出的最大值（两种背包容量）分别为VVV和UU...

2018-08-13 08:36:08 151

原创「暑期训练」「基础DP」 Monkey and Banana （HDU-1069）

题意与分析给定立方体（个数不限），求最多能堆叠（堆叠要求上方的方块严格小于下方方块）的高度。表面上个数不限，问题是堆叠的要求决定了每个方块最多可以使用三次。然后就是对3n3n3n的方格序列用LIS。注意：排序和求LIS的标准不同，否则答案会错误。代码#include <iostream>#include <cstring>#include &lt...

2018-08-13 08:16:22 140

原创「暑期训练」「基础DP」 Piggy-Bank （HDU-1114）

题意与分析完全背包问题。算法背包九讲里面都有提到过，我自己再说下对完全背包的理解。为什么01背包中遍历状态从VVV到000？考虑一下基本方程dp[i][j]=max(dp[i−1][j−w[i]]+v[i],dp[i−1][j])dp[i][j]=max(dp[i−1][j−w[i]]+v[i],dp[i−1][j])dp[i][j]=max(dp[i-1][j-w[i]]+v[i],...

2018-08-13 00:20:13 111

原创「暑期训练」「基础DP」 Common Subsequence （POJ-1458）

题意与分析很简单：求最长公共子序列。注意子序列与子串的差别：一个不连续一个连续。一份比较好的参考资料见：https://segmentfault.com/a/1190000002641054状态转移方程是这样的：设dp[i][j]dp[i][j]dp[i][j]为a串1~i、b串1~j中的最长的公共子序列，则 dp[i][j]={dp[i−1][j−1]+1, &nbs...

2018-08-12 16:52:21 124

原创「暑期训练」「Brute Force」 Bitonix' Patrol （CFR134D1D）

题意有nnn个站点，排成圆形，每站间距mmm，现从0点出发，提供ttt个油箱，问：拿走若干个油箱可以让出发者无法到达任意一个站点，这样的方案有多少？（出发者可以顺时针走，也可以逆时针走）数据规模分别为：2 ≤ n ≤ 1000,1 ≤ m ≤ 120,1 ≤ t ≤ 100002 ≤ n ≤ 1000,1 ≤ m ≤ 120,1 ≤ t ≤ 100002 ≤ n ≤ 1000, 1 ≤ m ≤...

2018-08-10 15:52:09 221

原创「暑期训练」「Brute Force」 Multiplication Table （CFR256D2D）

题意给定一矩阵MMM,Mij=ijMij=ijM_{ij}=ij，求第k大值。分析这个题不看题解我是想不到二分的，但是二分当然属于暴力，不爽不要玩;) 实际上，现在做题解的时候，意识到一个有意思的结论：第k大xxx往往都与二分思想有关。我们还会与分治思想再见的。具体做法：二分第k大值p。求数组中p元素是第几大即可。代码#include <bits/stdc++....

2018-08-10 15:05:18 87

原创「暑期训练」「Brute Force」 Optimal Point on a Line （Educational Codeforces Round 16, B）

题意You are given n points on a line with their coordinates xixix_i. Find the point x so the sum of distances to the given points is minimal.分析答案是直觉上显然的：输出数组的中位数即可（对于偶数个数的，则是中间靠左）。这样的结果正确的原因也很显然...

2018-08-10 14:57:18 106

原创「日常训练」「小专题·图论」Domino Effect（1-5）

题意分析这题几乎就是一条dijkstra的问题。但是，如何考虑倒在中间？要意识到这题求什么：单源最短路的最大值。那么有没有更大的？倒在中间有可能会使它更大。但是要注意一个问题：不要把不存在的边（边长为inf）算进去；另外，n=1的情况需要注意。代码// Origin:// Theme: Graph Theory (Basic)// Date: 080618//...

2018-08-06 21:21:10 111

原创「日常训练」「小专题·图论」昂贵的聘礼（1-4）

题意分析dijkstra的变形，问题在于把题目的逻辑转化成图。这个图(V,E)(V,E)(V,E)是这样的：V是各个人（礼物+承诺+探险家），E是花费的金额。如果能够换到，就连一条边。这样一来，对[lv1−m,lv1][lv1−m,lv1][lv_1-m,lv_1]到[lv1,lv1+m][lv1,lv1+m][lv_1,lv_1+m]的各个区间分别求最短路（m次），即可求出答...

2018-08-06 19:50:16 122

原创「日常训练」「小专题·图论」 Cow Contest （1-3）

题意分析问题是要看出来这是个floyd闭包问题。我没看出来- - 分析之后补充。代码// Origin:// Theme: Graph Theory (Basic)// Date: 080618// Author: Sam X//#include <bits/stdc++.h>#include <iostream>#include &lt...

2018-08-06 11:30:39 127

原创「日常训练」「小专题·图论」 Frogger （1-1）

题意分析变形的dijkstra。分析题意之后补充。代码// Origin:// Theme: Graph Theory (Basic)// Date: 080518// Author: Sam X//#include &lt;bits/stdc++.h&gt;#include &lt;iostream&gt;#include &lt;utility&gt;#...

2018-08-06 10:53:29 113

原创「日常训练」「小专题·USACO」 Ski Course Design （1-4）

题目以后补分析mmp这题把我写蠢哭了我原来的思路是什么呢？每轮找min/max，然后两个决策：升min/降max 像这样子dfs找最优，然后花式剪枝但是一想不对啊，这才1-4，哪有那么复杂网上一看，沃日丢人现眼了由于数据范围（没错面向数据范围编程），只要穷举min/max，然后对小于大于min/max进行调整，最后找最优方案即可。贪心+枚举=人生赢家真实蠢...

2018-07-28 02:53:51 121

原创「暑期训练」「Brute Force」 Money Transfers （CFR353D2C）

题目分析这个Rnd353真是神仙题层出不穷啊，大力脑筋急转弯- - 不过问题也在我思维江化上。思考任何一种算法都得有一个“锚点”，就是说最笨的方法怎么办。为什么要这么思考，因为这样思考最符合我们的思维规律。然后从这种最笨的方法中找问题、找漏洞、找关键的变量不变量，就能转化出更好的更快的算法。这题就是这样。最笨的方法是什么？随便从哪个点出发，按照一个方向一个一个抹平差距。可以保证，...

2018-07-28 02:47:56 116

原创「日常训练」「小专题·USACO」 Wormholes（1-4）

题意之后补充。分析这是一条很好的考察递归（或者说搜索）的题目。它的两个过程（建立初步解，验证）都用到了递归（或者说运用递归可以相当程度的减少代码量）。具体实现见代码。注意，为了使用std::pair的比较操作符，代码交换了x、y的位置。代码/*ID: samhx1LANG: C++14TASK: wormhole*/#include <bits/stdc...

2018-07-28 01:43:26 116

原创「暑期训练」「Brute Force」 Restoring Painting （CFR353D2B）

题意给定一定条件，问符合的矩阵有几种。分析见了鬼了，这破题谁加的brute force的标签，素质极差。因为范围是1e5，那你平方（枚举算法）的复杂度必然爆。然后你就会思考其中奥妙无穷的数学规律（并没有），推出一系列相关的等式。然后坑爹无穷的来了：边界问题。不想说了，心累，自己看代码吧。代码#include <bits/stdc++.h>#defi...

2018-07-28 01:26:08 107

原创「日常训练」「小专题·USACO」 Barn Repair（1-4）

题意之后补。分析这题同样也很精巧。我们不妨思考一下，如果只允许用一块木板，那么要购买多少距离？是整个的距离吗？不是，是从第一个到最后一个（哈哈哈哈哈哈哈）。但是，不包括第一个的“左边”和最后一个的“右边”。只允许用两块的时候发生了什么变化？可以想见，最好的解是将最宽的那个间隔去掉。以此类推。以这样的思路就可以得到题目的解法。问题在于各种各样的细节（again）：样例数据里面给的牛棚...

2018-07-28 00:06:12 120

原创「暑期训练」「Brute Force」 Far Relative’s Problem （CFR343D2B）

题意之后补分析我哭了，强行增加自己的思考复杂度。。。明明一道尬写的题- -（往区间贪心方向想了其实完全没必要，注意到只有366天，直接穷举判断即可。代码#include <bits/stdc++.h>#define MP make_pair#define PB push_back#define fi first#define se second#d...

2018-07-27 23:23:50 113

原创「日常训练」「小专题·USACO」 Broken Necklace（1-2）

题意圆形链条，打断一处可以形成一条链。问在哪个地方开始打断，能够形成最大的连续颜色（白色视作同样的颜色）？分析说起来很高级，但是我们实际上并不需要穷举打断的地方，只需要把串重复三回啊三回。然后从第二个串的左边开始循环找连续颜色的“初始色”（如果是白色，那么左右看看），在初始色的左右找相同。可以看出共有n个初始色的位置，所以算法也就是O(n2)O(n2)O(n^2)的复杂度。然后还有一些...

2018-07-27 21:50:56 148

原创「日常训练」 Mike and Feet (CFR305D2D)

题意分析这是一道用了单调栈的题目，用的贼好。代码#include &lt;bits/stdc++.h&gt;#define MP make_pair#define PB push_back#define fi first#define se second#define ZERO(x) memset((x), 0, sizeof(x))#define ALL(x)...

2018-06-15 13:32:32 140

原创「日常训练」 Mike and Frog (CFR305D2C)

题意与分析（Codeforces 548C）我开始以为是一条数学题，死活不知道怎么做，无奈看题解，才知这是一条暴力，思维江化了- - 题意大概是这样的：两个东西的初始高度分别为h1,h2h1,h2h_1,h_2，每秒二者的高度分别变化为(x1h1+y1)%m1(x1h1+y1)%m1(x_1h_1+y_1)\%m_1与(x2h2+y2)%m2(x2h2+y2)%m2(x_2h_2+y_...

2018-06-14 15:41:17 139

原创「日常训练」 Mike and Fun (CFR305D2B)

题意（CodeForces 548B）每次对01矩阵中的一位取反，问每次操作后，单列中最长连续1的长度。分析非常非常简单，但是我当时训练的时候WA了四次。。。无力吐槽了，人间不值得.jpg代码#include <bits/stdc++.h>#define MP make_pair#define PB push_back#define fi first#...

2018-06-11 21:26:21 149

原创「日常训练」 Soldier and Traveling (CFR304D2E)

题意（CodeForces 546E）对一个无向图，给出图的情况与各个节点的人数/目标人数。每个节点的人只可以待在自己的城市或走到与他相邻的节点。问最后是否有解，输出一可行解（我以为是必须和答案一样，然后本机调了半天死活不一样，交上去结果A了- -）。分析典型的网络流。问题在于建模。如何解决两个节点的人数->目标人数？考虑到我们始终要和这两个状态打交道，不妨将每个结点拆...

2018-06-11 20:42:36 211

原创「日常训练」 Soldier and Number Game (CFR304D2D)

题意（Codeforces 546D）给定一个数x=a!b!x=a!b!x=\frac{a!}{b!}的形式，问其中有几个质因数。分析数据规模略大，故先作预处理。预处理的时候运用了前缀和和记忆化搜索的思想。之后就比较简单了。代码#include <bits/stdc++.h>#define MP make_pair#define PB push_back...

2018-06-11 20:23:33 196

原创「日常训练」 Soldier and Cards (CFR304D2C)

题意（Codeforces 546C）按照指定的规则打牌，问谁胜或无穷尽。分析又是一条模拟，用set处理即可。注意到两种局势“1 234”和“123 4”的差别，所以用set处理的时候需要在两方手牌中间加上相关的分割符号以示区分。代码#include &amp;amp;lt;bits/stdc++.h&amp;amp;gt;#define MP make_pair#define PB push_back...

2018-06-11 20:03:54 268

原创「日常训练」Soldier and Badges (CFR304D2B)

题意（Codeforces 548B）对一个n×mn×mn\times m的01方格作q次操作，每次操作分别对一个格子取反，问每次操作后单列的最长连续1格的长度。分析没什么难度，问题是，对题意的理解，以及每次只需要更新一列就可以了。代码#include &lt;bits/stdc++.h&gt;#define MP make_pair#define PB push_b...

2018-06-11 19:59:33 167

原创「题目代码」P1034～P1038（Java）

P1034 C基础-求同存异import java.util.*;import java.io.*;import java.math.BigInteger;public class Main{ public static void main(String args[]) { Scanner cin=new Scanner(System.in); ...

2018-05-27 01:34:57 146

原创「题目代码」P1029～P1033（Java）

1029 C基础-求解方程import java.util.*;import java.io.*;import java.math.BigInteger;public class Main{ public static void main(String args[]) { for(int i=100;i<=999;++i) {...

2018-05-24 13:53:12 402

原创「日常训练」 Finite or not? (CFR483D2C)

题意（Codeforces 984C）给定p,q,bp,q,bp,q,b，问pqpq\frac{p}{q}在进制b下是否是无限小数。分析这个我一开始做的很挫，激情纯模拟+摸……但是做着做着就能发现不对劲了。比如说，p与能否无限无关（因为只是倍数关系）；问题的实质在于q能否被bbb单纯的表示（这句词是个感性的认识，但是很关键）。因此，根据这两个认知，我们能够看出，判断无限与否的重点是...

2018-05-24 13:40:57 139

原创「赛后补题」HBCPC2018题目代码与思路简析

这次比赛（2018年第二届河北省大学生程序设计竞赛）虽然没有打，但是题目还是要写的。未完成的题目（还差比较硬核的四题）和思路分析会陆续更新完。Problem A 2011 Mex Query/* * Operation China Wall * Author: Zuiho * Date: 2018-05 * Problem: 2011-Mex Query */#includ...

2018-05-24 02:41:08 1331

原创「学习记录」《数值分析》第三章计算实习题（Python语言）

第三题暂缺，之后补充。import matplotlib.pyplot as pltimport numpy as npimport scipy.optimize as soimport sympy as spx = sp.symbols('x')def calculate(expr_i, expr_j, expr_value,expr_omega): ans=0 ...

2018-05-22 09:24:25 1265

原创「功能笔记」Linux常用Shell命令（终端命令）备忘录

长期更新，空置、缺漏的部分会逐渐补上。未指明时，均为GNU版本。文件操作列表（ls）、复制（cp）、删除（rm）与移动（mv）ls默认显示非隐藏文件、以文件名进行排序、文件名有颜色（蓝色文件夹、白色一般文件、绿色可执行文件）。 Cheatsheet：ls -al ~ # 显示主文件夹下的所有文件（夹）；并显示它们的属性与权限。ls -alF --color=never ...

2018-05-15 23:10:50 186

原创「日常训练」神、上帝以及老天爷（HDU 2048）

题意错排问题。记错排为DnDnD_n，求Dnn!Dnn!\frac{D_n}{n!}。分析显然D1=0,D2=1D1=0,D2=1D_1=0,D_2=1。当n≥3n≥3n≥3时，不妨设n排在了第k位，其中k≠nk≠nk≠n，也就是1≤k≤n−11≤k≤n−11≤k≤n-1。那么我们现在考虑k的情况。当k排在第n位时：n放k、k放n确定，因而除了n和k以外还有n-2个数，其错排...

2018-05-15 20:58:50 310

原创「日常训练」不容易系列之(3)—— LELE的RPG难题（HDU 2045）

题目简述有排成一行的nnn个方格，用红(Red)、粉(Pink)、绿(Green)三色涂每个格子，每格涂一色，要求任何相邻的方格不能同色，且首尾两格也不同色，求全部的满足要求的涂法。分析首先感谢题解，我个人想半天是出不来的。考虑第n个与第n-1个的关系。因为第n个不能和第1个同色，那么第n个颜色就是我们判断的突破口，而它是由第n-1个决定的。如果第n-1个保持原来的状况不变，那么第...

2018-05-15 11:36:33 143

原创「题目代码」P1013～P1017（Java）

1013 C基础-求偶数和import java.util.*;import java.io.*;import java.math.BigInteger;public class Main{ public static void main(String args[]) { Scanner sc=new Scanner(System.in); ...

2018-05-15 02:29:09 181

原创「题目代码」P1007～P1012（Java）

C基础-计负均正import java.util.*;import java.io.*;public class Main{ public static void main(String args[]) { Scanner sc=new Scanner(System.in); int x; int negativeCn...

2018-05-11 11:35:15 119

原创「日常训练」 Single-use Stones (CFR476D2D)

题意（Codeforces 965D）分析我是激情看题解的，很惭愧。因为自己的算法喜提TLE了w 我参考的题解在这儿。官方题解用了二分的思想。这个算法是怎么贪心的呢？就在while(p<i && frog[p]+frog[i]<=a[i])这一句。当第i 处已经满了的时候，我们就不考虑[p+1,i−1][p+1,i−1][p+1,i-1]到i的跳跃了。后...

2018-05-11 03:24:36 156

原创「日常训练」Greedy Arkady (CFR476D2C)

题意（Codeforces 965C）k人分n个糖果，每个糖果至多属于1个人。A某人是第一个拿糖果的。（这点很重要！！）他x个x个的发糖果，从第一个（他自己）到最后一个，然后再到第一个；多余的糖果丢掉。x不能大于M，单个人最多分糖果轮到他D次。问A某人最多能拿多少糖果。分析先说一句话：这条题目极度坑爹。先考虑题意，可以发现，A某人不论如何，一定会吃到xdmaxxdmaxxd_{m...

2018-05-11 02:37:35 125

空空如也

空空如也