xyc1719
临别之谈 好好看待，好好珍惜一路走过的自己。遥不可及的未来旋即成为了永恒不变的过去。我有我的骄傲，在noip赛场上稳住了自己，也稳住了比赛。我有我的幸福，戒不掉的机房成了我的瘾，下雨的夜与算法和机友在一起。我有我的过去，zjoi看到了世界的广阔，自己的渺小和临别前人内心的脆弱。船上的摆渡人是坚强的，他不必念及无法割舍的过去，面对难以想象的未来。桨在手上，彼岸未及，所以，请继续。Jus... 原创 发布博客 2019.05.01 · 293 阅读 · 2 点赞 · 0 评论 · 0 收藏 codeforces 554div.2 A.Neko Finds Grapes【题面】给你两个数列，求两个数列中相加，最多的奇数个数。【分析】一道sb题，整两个桶记录两个数列的奇偶数各有几个，取个min相加即可。然而。。。。我交了另一场比赛的代码，改了半天死活过不了。... 原创 发布博客 2019.04.25 · 244 阅读 · 1 点赞 · 0 评论 · 0 收藏 ZJOI2019游记 又是一阵咕咕声，实在是不想写什么东西。昨天颓到两点，就打了一把cf，zjoi rp++。若有以后，再谈以后。 原创 发布博客 2019.04.25 · 316 阅读 · 1 点赞 · 0 评论 · 0 收藏 字符串(p)review学习笔记 目前会持续填充一些字符串的模板，后续会对有关题目进行进一步展开。【Hash】一个比较万能的算法，在Θ(n)Theta(n)Θ(n)的预处理之后，就可以对两个字符串进行Θ(常数)Theta(常数)Θ(常数)的比较了。其基本思想是将一串字符串映射成一个数字，通过比较数字来比较字符串。具体上是将每位字母映射成一个值，每加进来一个值，就把前面的值乘上一个位数。这些数用前缀和存起来，需要比较时移... 原创 发布博客 2019.04.06 · 380 阅读 · 0 点赞 · 0 评论 · 0 收藏 【算法进阶】 CIty Games 【题面】有一天，小猫rainbow和freda来到了湘西张家界的天门山玉蟾宫，玉蟾宫宫主蓝兔盛情地款待了它们，并赐予它们一片土地。这片土地被分成N∗MN*MN∗M个格子，每个格子里写着’R’或者’F’，R代表这块土地被赐予了rainbow，F代表这块土地被赐予了freda。现在freda要在这里卖萌。。。它要找一块矩形土地，要求这片土地都标着’F’并且面积最大。但是rainbow和freda... 原创 发布博客 2019.04.03 · 208 阅读 · 1 点赞 · 0 评论 · 0 收藏 【算法进阶0x00】七夕祭 【题面】           ;;;;;,TYVJ七夕祭和11区的夏祭的形式很像。矩形的祭典会场由N排M列共计N×M个摊点组成。虽然摊点种类繁多，不过cl只对其中的一部分摊点感兴趣，比如章鱼烧、苹果糖、棉花糖、射的屋…... 原创 发布博客 2019.03.31 · 439 阅读 · 0 点赞 · 0 评论 · 0 收藏 最近的叶子 题目来源：CF1110F【简要题意】给一棵有边权的树，已知各点编号的等于该点的dfs序。求对于每个vi,li,ri，求li到ri中到vi距离最小的叶子结点到vi的距离。【分析】暴力树形dp有70分就果断写完去搞T2，结果T2愣是没有结果。。。。又是一道方便离线维护的题。和2月24日卡常数那道题颇为相似。考虑从u到v边权为c，显然有所有v的子树点距离-c，其余点距离+c，回溯也也是一个Θ(l... 原创 发布博客 2019.03.10 · 132 阅读 · 0 点赞 · 1 评论 · 0 收藏 魔法石 题目来源：CF1110E【简要题意】对于给定数列{a}能否通过对第2…n-1项进行ci=ci−1+ci+1−cic_i=c_{i-1}+c_{i+1}-c_ici=ci−1+ci+1−ci的变换得到数列{b}。数列长度小于等于1e5【分析】考场上就打了暴力判断头和尾是否相同，然后数据出锅，暴力就过了。。。。。正确解法是差分。暴力判断头尾之后，经过神奇的观察发现每次进行操作相当于... 原创 发布博客 2019.03.10 · 440 阅读 · 0 点赞 · 0 评论 · 0 收藏 麻将 hongmah 题目来源：CF1110D【简要题意】有n个数集合（多重集），每个数不超过m。可以分成{i,i,i}或{i-1,i,i+1}的三元组，求最多分成几份三元组。n、m<=1e6【分析】考虑动态规划，写出一个Θ(n3)Theta(n^3)Θ(n3)的动归方程，放下转贪心。试了好几种贪心策略都被hack，并且对于贪心证明毫无头绪。回到dp，结果是一种对于状态定义的优化：定义f[i][j][k... 原创 发布博客 2019.03.10 · 156 阅读 · 0 点赞 · 0 评论 · 1 收藏 无意义运算符 题目来源：CF1110C【简要题意】给定a，求f(a)的最大值。f(a)=max0&lt;b&lt;a(gcd(a⊕b,a &amp; b))f(a)= maxlimits_{0&lt;b&lt;a}(gcd(aoplus b,a &amp; b))f(a)=0<b<amax(gcd(a⊕b,a&nb... 原创 发布博客 2019.03.10 · 399 阅读 · 0 点赞 · 0 评论 · 0 收藏 JYM的公司 【简要题意】求序列中任意两个数的差之和。n<=5e5【分析】排序扫一遍，over【code】#include<cstdio>#include<iostream>#include<algorithm>using namespace std;typedef long long LL;const int maxn=5e5+1000;int n;... 原创 发布博客 2019.02.24 · 1457 阅读 · 0 点赞 · 0 评论 · 0 收藏 图像分析 【简要题意】有n个点，求一条直线穿过至少n3frac{n}{3}3n个点。n<=1e6，保证一定存在一条这样的直线。输出穿过任意两点的坐标。【分析】思前想后没有办法，结果随机化就a了。。。考虑最坏的情况：只存在一个n3frac{n}{3}3n的点集当中任意两点满足。则每次两点均选中的概率为19frac{1}{9}91。可以循环一百次，一百次后失败的概率为约为71e6fra... 原创 发布博客 2019.02.24 · 162 阅读 · 0 点赞 · 0 评论 · 0 收藏 卡内存 【简要题意】给一个长度为n序列。进行m次如下操作：1.add x k:给a[x]加上k。2.ask x y:查询区间[x,y]内所有数的和。3.goto t:回到第t次操作之后的状态。n,m<=1e5。特别注意：空间限制为8MB【分析】由于题目背景中出现了可持久化线段树，又有回退到历史版本的操作，所以很多人试图如题目所说的那样卡可持久化的内存。事实证明是卡不过的。这里有一种神奇... 原创 发布博客 2019.02.24 · 10485 阅读 · 0 点赞 · 0 评论 · 0 收藏 密码 【简要题意】求Σi=1ni22iSigma^n_{i=1}i^22^iΣi=1ni22i mod 1e9+7mod 1e9+7mod 1e9+7的值，n&lt;=1e9n&lt;=1e9n<=1e9【分析】线性复杂度的算法显然是好想的。低于线性的算法有两种：1.数论2.推式子这道题是后者，证明过程如下：设Sn=1∗2+4∗22+9∗23... 原创 发布博客 2019.02.24 · 130 阅读 · 0 点赞 · 0 评论 · 0 收藏 聪明幽默的JYM 【简要题意】给定n个二元组。从中任选一些，使得两个元素之和均不小于0。求满足上述情况下的总和的最大值。【分析】直接暴力dp水过，注意一下边界。【code】#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;c... 原创 发布博客 2019.02.18 · 217 阅读 · 0 点赞 · 0 评论 · 0 收藏 区间最小 【简要题意】给一个长度为n序列，对每个位置i问[max(1,i-m),i]中最小的值。n<=1e6,m<=1e6。【分析】一道单调队列模板题。当然鉴于n没有非常大，所以也可以用st表水过。【code】#include<cstdio>#include<cstring>#include<iostream>#include<algorit... 原创 发布博客 2019.02.18 · 335 阅读 · 0 点赞 · 0 评论 · 0 收藏 皮卡丘逃亡 【简要题意】跨越空地代价为1，跨越障碍代价为5，求从(x1,y1)到(x2,y2)的最小代价。网格图的长宽均小于500.【分析】spfa水过。。。。数据范围非常小所以用Θ(n∗m)Theta(n*m)Θ(n∗m)卡掉也无所谓。【code】#include<queue>#include<cstdio>#include<cstring>#includ... 原创 发布博客 2019.02.18 · 163 阅读 · 0 点赞 · 0 评论 · 0 收藏 调换纸牌 【简要题意】将n个纸牌移动到任意位置后可以形成升序的序列。求最小的n。Len<=5e5。【分析】求最长不降子序列（LIS）。用f[i]记目前为止，长度为i的序列最小为多少再用二分查找。总复杂度为Θ(nlog2n)Theta(nlog_2n)Θ(nlog2n)【code】#include<cstdio>#include<cstring>#include&... 原创 发布博客 2019.02.18 · 179 阅读 · 0 点赞 · 0 评论 · 1 收藏 家园重建 【简要题意】有n个点和m条边。选出其中的某些边构成一个新的图（不一定联通），要求新图中每个连通块中至多有一个环。求新图的边权最大和。【分析】贪心，依旧是一道kruskal类似的题，不同只是要记录当前集合中是否有环。【code】#include<cstdio>#include<cstring>#include<iostream>#include<... 原创 发布博客 2019.02.17 · 469 阅读 · 0 点赞 · 0 评论 · 0 收藏 弹药分配 【简要题意】原先有一个序列各有一定的值。有5e4个操作，分两种：1.在选取一个区间【a，b】，并给出一个值k，区间上如果编号i 满足（i- a) % k = 0 就加上c。(k<=10)2.询问序列中某个数的当前值。【分析】对于k较小，且序列长度<=5e4的情况，我们可以分模数和余数建K2个树状数组。询问时将这些修改相加。【code】#include<cstdio&g... 原创 发布博客 2019.02.17 · 241 阅读 · 0 点赞 · 0 评论 · 0 收藏网址: xyc1719 https://m.huajiangbk.com/newsview104810.html
