• avatar just_sort 2017-06-19 20:19:08

    UESTC 1639 云中谁寄锦书来?雁字回时,月满西楼

    题目链接:http://acm.uestc.edu.cn/#/problem/show/1639 题意: 在n个点m条边的无向图上,有k个出口 从起点出发,每到一个点(包括起点),该点连出的边中有d条会被封锁 求最坏情况下到达出口的最短路 数据范围: 1<=n<=100000

    来自 just_sort
    00
  • avatar just_sort 2017-06-19 20:15:29

    UESTC 1638 红藕香残玉簟秋,轻解罗裳,独上兰舟。

    题目链接:http://acm.uestc.edu.cn/#/problem/show/1638 题意: 给定n个点(点权未知)和m条信息:u的权值>=v的权值+w 求点权的极小解和极大解(无解则输出-1) 极小解即每个点的点权可能的最小值 极大解即每个点的点权可能的最大值 数据范

    来自 just_sort
    00
  • avatar just_sort 2017-06-14 16:05:36

    UESTC 图论专题 A-D

    A:梦后楼台高锁,酒醒帘幕低垂 题目链接:http://acm.uestc.edu.cn/#/problem/show/1636 解法:首先,考虑到,我们需要找到一条路径,使它的最小边尽量大,最大边尽量小。然后,考虑到m比较小,我们可以去寻找一个m^2或者m^2logm的算法。考虑枚举最小边,那

    来自 just_sort
    00
  • avatar just_sort 2017-06-10 21:01:57

    SWUSTACM 2017周赛一

    A:多推几组样例可以发现合法的情况下,答案就是a/k+b/k,由于打的比赛场数 是完整的,所以不存在的条件就是a%k=0并且b不等于0或者b%k=0并且a不等于0 B:以图片上的字母对称,注意题上的i是对称的。 C: 方法一:前缀和加上二分,因为是整数,前缀和满足递增。由于查询的值 <

    来自 just_sort
    00
  • avatar just_sort 2017-06-09 21:46:36

    UESTC 数据结构专题训练 K,L,M

    K:http://acm.uestc.edu.cn/#/problem/show/1593 解法:直接并查集加SET维护即可。 #include <bits/stdc++.h> using namespace std; typedef long long LL; cons

    来自 just_sort
    00
  • avatar just_sort 2017-06-08 15:29:35

    UESTC 数据结构专题训练 D,E,F

    D,http://acm.uestc.edu.cn/#/problem/show/1584 题意:平面上n个点,询问每个点左下方的点有多少个? 解法:排序(以Y坐标为第一关键字,X坐标为第二关键字)+树状数组 #include <bits/stdc++.h> using

    来自 just_sort
    00
  • avatar just_sort 2017-06-07 14:16:30

    UESTC 数据结构专题训练 A,B,C

    A:题目链接 http://acm.uestc.edu.cn/#/problem/show/1591 解法:RMQ或者线段树 【num of wa】 0 #include <bits/stdc++.h> using namespace std; int n, q, mx[50

    来自 just_sort
    00
  • avatar just_sort 2017-06-02 20:58:03

    BZOJ 3295: [Cqoi2011]动态逆序对 分块大法好

    题目链接:这里 解法:树套树 和 CDQ不会写,分块暴力大法好。 我们可以把原序列a[]分成个块,每个块有个数。然后维护一个b[],b[]中的每一个块都是一个单调递增的序列。 当前要删除的数为x,所在的块是k,那我们分两种情况做: 1.对于k号块,直接在a[]的k号块中枚举求逆序对,复杂度

    来自 just_sort
    00
  • avatar just_sort 2017-06-20 16:43:23

    UESTC 1606 难喝的饮料

    题目链接:http://acm.uestc.edu.cn/#/problem/show/1606 解法: 算法复杂度:O(N*K) memset(dp,-1,sizeof(dp)); dp[0]=0; 饮用水:完全背包 for(j=b;j<=k;j++) if (dp[j-b]!

    来自 just_sort
    00
  • avatar just_sort 2017-06-20 14:27:22

    UESTC 1646 穷且益坚, 不坠青云之志。

    题目链接:http://acm.uestc.edu.cn/#/problem/show/1646 题意:求一个有n个元素的数列,满足任意连续p个数的和不小于s, 任意连续q个数的和不大于t。 解法:令sum[i]表示前i项的和(0<=i<=n,sum[0]=0) 那么题目的条件可

    来自 just_sort
    00
  • avatar just_sort 2017-06-08 16:20:54

    UESTC数据结构专题训练 G,H,I,J

    G,http://acm.uestc.edu.cn/#/problem/show/1598 题意:给你一个n个元素的序列,支持以下操作:单点修改,查询区间内连续的最大子段和。 解法:线段树每个结点维护四个域:maxv,maxl,maxr,sumv,其中sumv为该区间的和,maxv为该区间上的最

    来自 just_sort
    00
  • avatar just_sort 2017-06-01 16:03:37

    CSU 1812 两个凸多边形面积交

    题目链接:http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1812 解法:套凸多边交模板。 #include <bits/stdc++.h> using namespace std; const int maxn = 555; c

    来自 just_sort
    00
  • avatar wyxAIbq 2019-07-26 18:18:45

    优秀网站

    1、HttpClient中文网http://www.httpclient.cn/ 2、掘金,Mysql必知必会读书笔记https://juejin.im/post/5d2335846fb9a07f021a2509 3、Mysql索引https://juejin.im/post/5d2

    来自 wyxAIbq
    00
  • avatar just_sort 2017-06-01 15:46:50

    CSU 1809 Parenthesis 思维,前缀RMQ

    题目链接:http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1809 题意:给了一个平衡的括号序列s(平衡是指括号匹配正常) 现在q次询问,每次输入两个数a、b 问将s[a] s[b]交换后是 否任然平衡(即是否正常匹配),平衡则输出“Yes”

    来自 just_sort
    00
  • avatar just_sort 2017-06-01 15:43:29

    CSU 1808 地铁 最短路变形

    题目链接:http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1808 题意:ICPCCamp 有 n 个地铁站,用 1,2,…,n 编号。 m 段双向的地铁线路连接 n 个地铁站,其中第 i 段地铁属于 ci 号 线,位于站 ai,bi 之间,

    来自 just_sort
    00
  • avatar just_sort 2017-06-01 15:36:32

    CSU 1806: Toll Simpon积分,最短路

    题目链接:http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1806 解法:被积函数,就是用spfa跑出来的结果,然后掏出辛普森就可以 了。注意加的边是单向边。 #include <bits/stdc++.h> using name

    来自 just_sort
    00
  • avatar just_sort 2017-06-01 15:31:02

    CSU 1804 有向无环图 拓扑序DP

    题目链接:http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1804 解法:先将每个点i对应的count(i,j)*bj算出来然后乘ai,累加就是答案,注意这里要类似拓扑排序那样,不过 要倒着做,避免后效性 #include <bits

    来自 just_sort
    00
  • avatar just_sort 2017-05-18 18:48:39

    BZOJ 2819: Nim 树剖,尼姆游戏

    Description 著名游戏设计师vfleaking,最近迷上了Nim。普通的Nim游戏为:两个人进行游戏,N堆石子,每回合可以取其中某一堆的任意多个,可以取完,但不可以不取。谁不能取谁输。这个游戏是有必胜策略的。于是vfleaking决定写一个玩Nim游戏的平台来坑玩家。 为了设计漂亮一点

    来自 just_sort
    00
  • avatar just_sort 2017-05-18 18:14:50

    BZOJ 3083: 遥远的国度 树链剖分,处理树的换根

    Description 描述 zcwwzdjn在追杀十分sb的zhx,而zhx逃入了一个遥远的国度。当zcwwzdjn准备进入遥远的国度继续追杀时,守护神RapiD阻拦了zcwwzdjn的去路,他需要zcwwzdjn完成任务后才能进入遥远的国度继续追杀。 问题是这样的:遥远的国度有n个城市,这

    来自 just_sort
    00
  • avatar just_sort 2017-05-18 16:53:14

    BZOJ 3589: 动态树 树链剖分线段树

    Description 别忘了这是一棵动态树, 每时每刻都是动态的. 小明要求你在这棵树上维护两种事件 事件0: 这棵树长出了一些果子, 即某个子树中的每个节点都会长出K个果子. 事件1: 小明希望你求出几条树枝上的果子数. 一条树枝其实就是一个从某个节点到根的路径的一段. 每次小明会选定

    来自 just_sort
    00
  • avatar just_sort 2017-05-17 18:36:11

    BZOJ 2836: 魔法树 树链剖分+DFS序

    题意:区间+,子树求和 解法:树剖维护一颗线段树,子树求和用DFS序即可。 ///BZOJ 2836 #include <bits/stdc++.h> using namespace std; const int maxn = 200010; int n, m, edgecnt,

    来自 just_sort
    00
  • avatar just_sort 2017-05-17 17:09:59

    BZOJ 2243: [SDOI2011]染色 树链剖分

    Description 给定一棵有n个节点的无根树和m个操作,操作有2类: 1、将节点a到节点b路径上所有点都染成颜色c; 2、询问节点a到节点b路径上的颜色段数量(连续相同颜色被认为是同一段),如“112221”由3段组成:“11”、“222”和“1”。 请你写一个程序依次完成这m个操作。

    来自 just_sort
    00
  • avatar just_sort 2017-05-17 09:26:00

    BZOJ 2157: 旅游 树链剖分

    Description Ray 乐忠于旅游,这次他来到了T 城。T 城是一个水上城市,一共有 N 个景点,有些景点之间会用一座桥连接。为了方便游客到达每个景点但又为了节约成本,T 城的任意两个景点之间有且只有一条路径。换句话说, T 城中只有N − 1 座桥。Ray 发现,有些桥上可以看到美丽的景

    来自 just_sort
    00
  • avatar just_sort 2017-05-15 20:57:17

    2017 西南交通大学ACM校赛简易题解

    2017/5/15敝队打了一发西南交通大学的校赛,仍然3人一台电脑的方式,最终A掉9题,现场竟然最多才A8题。。。 由于线下打的比赛记录好像全部GG了。所以我花了一下午的时间脑补掉了做出来的9道题,就分享一下我们 做出来的题,写个简易题解。。 A:SB题,直接模拟即可。 #include &

    来自 just_sort
    00
  • avatar just_sort 2017-05-15 12:50:23

    第二届CCPC女生赛 简易题解

    前言:2015/5/13用虚拟OJ的方式3人一台电脑打了CCPC女生赛,一共做出9题(共10题),因为自己太坑D 题错了9发,罚时爆炸,在现场就只能排第2,上交小姐姐太强啦,很稳。 接下来就把做出来的题,写个简易题解,题目在HDU上可以找到,题号对应为6023-6032。 A:模拟水题,不说了

    来自 just_sort
    00
  • avatar just_sort 2017-05-15 10:45:27

    BZOJ 2813: 奇妙的Fibonacci 线性筛

    Description Fibonacci数列是这样一个数列: F1 = 1, F2 = 1, F3 = 2 … Fi = Fi-1 + Fi-2 (当 i >= 3) pty忽然对这个古老的数列产生了浓厚的兴趣,他想知道:对于某一个Fibonacci数Fi, 有多少个Fj能够整除F

    来自 just_sort
    00
  • avatar just_sort 2017-05-12 20:30:57

    BZOJ 3288: Mato矩阵 行列式,线性筛

    Description Mato同学最近正在研究一种矩阵,这种矩阵有n行n列第i行第j列的数为gcd(i,j)。 例如n=5时,矩阵如下: 1 1 1 1 1 1 2 1 2 1 1 1 3 1 1 1 2 1 4 1 1 1 1 1 5 Mato想知道这个矩阵的行列式的值,你能求出

    来自 just_sort
    00
  • avatar just_sort 2017-05-12 19:52:37

    BZOJ 2818: Gcd 线形筛

    Description 给定整数N,求1<=x,y<=N且Gcd(x,y)为素数的 数对(x,y)有多少对. Input 一个整数N Output 如题 Sample Input 4 ample Output 4 解法:才发现直接莫比乌斯反弹T到哭。。。我们注意到,

    来自 just_sort
    00
  • avatar just_sort 2017-05-12 19:06:18

    BZOJ 1968: [Ahoi2005]COMMON 约数研究 思维

    题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1968 题意:求1-n每个数的约数之和的和。 解法:枚举下每一个因子,看有多少个数包含这个因子,累加到答案即可。。。。 ///BZOJ 1968 #include <bits/s

    来自 just_sort
    00
  • avatar just_sort 2017-05-12 15:27:53

    BZOJ 1409: Password 线性筛+矩阵乘法

    Description Rivest是密码学专家。近日他正在研究一种数列E = {E[1],E[2],……,E[n]}, 且E[1] = E[2] = p(p为一个质数),E[i] = E[i-2]*E[i-1] (若小i<=n)。 例如{2,2,4,8,32,256,8192,……}就

    来自 just_sort
    00
  • avatar just_sort 2017-06-01 16:01:59

    CSU 1811 Tree Intersection 平衡树启发式合并

    题目链接:http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1811 题意:每个点有一个颜色,删除一条边后,求这条边两边的点集的颜色交的个数。 解法:平衡树启发式合并。那么可以直接用map对每个子树的信息进行记录,然后回溯上去的时候父节点加上子

    来自 just_sort
    00
  • avatar just_sort 2017-06-01 15:28:01

    CSU 1803 2016

    Description 给出正整数 n 和 m,统计满足以下条件的正整数对 (a,b) 的数量: 1≤a≤n,1≤b≤m; a×b 是 2016 的倍数。 Input 输入包含不超过 30 组数据。 每组数据包含两个整数 n,m (1≤n,m≤109). Output 对

    来自 just_sort
    00
  • avatar 法拉利201903231900848 2019-07-26 18:24:44

    输入两棵二叉树A,B,判断B是不是A的子结构

    /* struct TreeNode {     int val;     struct TreeNode *left;     struct TreeNode *right;     TreeNode(int x) :             val(x), left(NULL), right(N

  • avatar TWerQi 2019-07-26 18:25:03

    字符串分割中有两个分隔符的不同处理

    任务:32核处理器编号,解析。 输入:1,2,3,4-9,11,23-26 字符串形式 输出:1,2,3,4,5,6,7,8,9,11,23,24,25,26 到指定整型数组 规则:数字从小到大顺序输入,返回处理器核心编号。 cpp Code //未使用库函数,遍历字符串每个字符,做处理

    来自 TWerQi
    00
  • avatar just_sort 2017-05-12 14:07:56

    BZOJ 2820 YY的GCD 莫比乌斯反演

    题意:求有多少个数对(x,y),使得x<=m,y<=n且GCD(x,y)为质数 解法:具体去见ACdream的博客里面讲的还是很详细的 这里 ///BZOJ 2820 #include <bits/stdc++.h> using namespace std; con

    来自 just_sort
    00
  • avatar just_sort 2017-05-11 20:13:35

    BZOJ 2440. -- [中山市选2011]完全平方数 莫比乌斯函数,二分答案

    [Submit][Status][Discuss] Description 小 X 自幼就很喜欢数。但奇怪的是,他十分讨厌完全平方数。他觉得这些 数看起来很令人难受。由此,他也讨厌所有是完全平方数的正整数倍的数。然而 这丝毫不影响他对其他数的热爱。 这天是小X的生日,小 W 想送一个数给他

    来自 just_sort
    00
  • avatar just_sort 2017-05-11 15:02:40

    BZOJ 1997: [Hnoi2010]Planar 平面图判定,TWOSAT

    题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1997 题意:给定一个图和一个哈密顿回路,判定是否是平台图。 解法: 用平面图m<=3n-6的性质剪枝条 若两条边在圆内相交,则他们在圆外也是相交的,即若a,b不能同时取,a’

    来自 just_sort
    00
  • avatar just_sort 2017-05-11 14:04:26

    BZOJ 3798: 特殊的质数 分块打表

    Description 求[A,B]之间的质数个数,并且满足X=Q^2+P^2,P,Q是正整数。 Input 第一行输入A,B Output 输出有多少组P,Q满足条件 Sample Input 6 66

    来自 just_sort
    00
  • avatar just_sort 2017-05-11 10:16:37

    BZOJ 3329: Xorequ 数位DP+矩阵快速幂

    题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3329 解法:x xor 2x=3x(与x xor 3x=2x等价)求满足等式且小于n的x的个数,与满足等式小于2n的数的个数。因为异或是不 进位的二进制加法,那么因为结果正好和加法相同

    来自 just_sort
    00
  • avatar just_sort 2017-05-10 20:20:07

    BZOJ 3679 数位DP,离散化

    题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3679 解法: 比较裸的数位DP,dp[i][j][k]表示前i位,当前位数字为j,乘积为k(k保存的是离散化之后的值),然后按照数位DP的做法去写就可以了。 ///BZOJ

    来自 just_sort
    00
  • avatar just_sort 2017-05-10 16:34:57

    BZOJ 3209 二进制数位DP

    Description 背景 众所周知,花神多年来凭借无边的神力狂虐各大 OJ、OI、CF、TC …… 当然也包括 CH 啦。 描述 话说花神这天又来讲课了。课后照例有超级难的神题啦…… 我等蒟蒻又遭殃了。 花神的题目是这样的 设 sum(i) 表示 i 的二进制表示中 1 的个数。给出

    来自 just_sort
    00
  • avatar just_sort 2017-05-10 16:09:28

    BZOJ 1833: [ZJOI2010]count 数字计数 数位DP,处理前导0

    Description 给定两个正整数a和b,求在[a,b]中的所有整数中,每个数码(digit)各出现了多少次。 Input 输入文件中仅包含一行两个整数a、b,含义如上所述。 Output 输出文件中包含一行10个整数,分别表示0-9在[a,b]中出现了多少次。 Sample Inp

    来自 just_sort
    00
  • avatar just_sort 2017-05-10 11:08:18

    BZOJ 1503: [NOI2004]郁闷的出纳员 Treap

    Description OIER公司是一家大型专业化软件公司,有着数以万计的员工。作为一名出纳员,我的任务之一便是统计每位员工的工资。这本来是一份不错的工作,但是令人郁闷的是,我们的老板反复无常,经常调整员工的工资。如果他心情好,就可能把每位员工的工资加上一个相同的量。反之,如果心情不好,就可能把

    来自 just_sort
    00
  • avatar just_sort 2017-05-10 09:59:07

    UVALive3713-Astronauts 2-SAT

    题目链接:https://vjudge.net/problem/UVALive-3713 题意:有A、B、C 3个任务分配给n个宇航员,其中每个宇航员恰好分配一个任务。假设n个宇航员的平均年龄 为x,只有年龄大于x的才能领取A任务;只有年龄严格小于x的才能领取B任务,而任务C没有限制。有m对宇

    来自 just_sort
    00
  • avatar just_sort 2017-05-09 17:38:50

    UVALive 3211 Now or later 二分+Twosat

    题目链接:https://vjudge.net/problem/UVALive-3211 题意:每架飞机有早晚起降两种方式,给定n架飞机两种方式的起落时间,为每架飞机安排起落时间(早或 晚),使得所有飞机起降时间按照早到晚的顺序之间的间隔时间最小值尽量大。 解法:最小时间尽量大应该采用二分的方

    来自 just_sort
    00
  • avatar just_sort 2017-05-09 16:58:30

    UVALIVE 4287 Proving Equivalences Tarjan求强连通分量

    题目链接:https://vjudge.net/problem/UVALive-4287 题意:有n个命题,已知其中的m个推导,要证明n个命题全部等价(等价具有传递性),最少还需要做出几次 推导 解法:由已知的推导可以建一张无向图,则问题变成了最少需要增加几条边能使图变成强连通图。找出所有的

    来自 just_sort
    00
  • avatar just_sort 2017-05-09 16:14:24

    UVALive - 5135 Mining Your Own Business 双连通分量

    题目链接:https://vjudge.net/problem/19845 题意:有N个矿井 ,由一些隧道连接起来,现在要修建尽量少的安全通道,使得无论哪里发生事故,所有人均 能逃出,求建的最少的安全通道数量和方案数 解法: 建安全通道的话,肯定不能建在割顶,因为割顶如果崩塌了,割顶所连接的

    来自 just_sort
    00
  • avatar just_sort 2017-05-09 15:34:32

    UVALIVE 3523 双连通分量+二分图染色

    题目链接:https://vjudge.net/problem/18122 题意: 有n个骑士经常举行圆桌会议,每次圆桌会议至少要有3个骑士参加(且每次参加的骑士数量是奇数个),且所有 互相憎恨的骑士不能坐在圆桌旁的相邻位置,问有多少个骑士不可能参加任何一个会议 解法: 这题最终转化为求解

    来自 just_sort
    00
  • avatar 笛安 2019-07-26 18:29:23

    开发岗基础面试题

    1.堆和栈的区别 答:首先需要询问指的是操作系统层面的还是数据结构层面的。 操作系统层面:操作系统层面的堆和栈其实说的是操作系统给进程分配的内存空间里面的概念,它包括代码段、数据段、堆、栈、BSS。 BSS段:BSS段(bss segment)通常是指用来存放程序中

    来自 笛安
    01
  • avatar just_sort 2017-05-09 09:28:41

    BZOJ 1500: [NOI2005]维修数列 Splay

    题目:http://www.lydsy.com/JudgeOnline/problem.php?id=1500 解法:Crash大神的论文上有详细解题方法,实现加调试花了很久很久。然后总算A掉啦。这个题都没过,说 啥学过Splay啊。 ///BZOJ 1500 #include <bi

    来自 just_sort
    00
  • avatar just_sort 2017-05-07 20:56:47

    BZOJ 1497: [NOI2006]最大获利 最大闭合权

    Description 新的技术正冲击着手机通讯市场,对于各大运营商来说,这既是机遇,更是挑战。THU集团旗下的CS&T通讯公司在新一代通讯技术血战的前夜,需要做太多的准备工作,仅就站址选择一项,就需要完成前期市场研究、站址勘测、最优化等项目。在前期市场调查和站址勘测之后,公司得到了一共N

    来自 just_sort
    00
  • avatar just_sort 2017-05-07 15:27:31

    BZOJ 1491: [NOI2007]社交网络 Floyd

    题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1491 解法:按照题目的公式跑Floyd统计方案 ///BZOJ 1491 #include <bits/stdc++.h> using namespace std;

    来自 just_sort
    00
  • avatar just_sort 2017-05-11 15:57:09

    BZOJ 2301: [HAOI2011]Problem b 容斥+莫比乌斯反演

    Description 对于给出的n个询问,每次求有多少个数对(x,y),满足a≤x≤b,c≤y≤d,且gcd(x,y) = k,gcd(x,y)函数为x和y的最大公约数。 Input 第一行一个整数n,接下来n行每行五个整数,分别表示a、b、c、d、k   Ou

    来自 just_sort
    00
  • avatar just_sort 2017-05-10 18:53:06

    SPOJ 10606 Balanced Numbers 数位DP

    题目链接:https://vjudge.net/problem/SPOJ-BALNUM 题意:个数被称为是平衡的数当且仅当对于所有出现过的数位,偶数出现奇数次,奇数出现偶数次。 给定A,B,请统计出[A,B]内所有平衡的数的个数。 解法: 注意,这里的偶数是指出现过的数,并且不能计算前导零。

    来自 just_sort
    00
  • avatar just_sort 2017-05-07 14:31:54

    BZOJ 1486: [HNOI2009]最小圈 01分数规划+SPFA判环

    Sample Input 4 5 1 2 5 2 3 5 3 1 5 2 4 3 4 1 3 Sample Output 3.66666667 解法:01分数规划+SPFA判环 ///BZOJ 1486 #include <bits/stdc++.h> using

    来自 just_sort
    00
  • avatar just_sort 2017-05-06 12:07:39

    BZOJ 1485: [HNOI2009]有趣的数列 卡特兰数

    Description 我们称一个长度为2n的数列是有趣的,当且仅当该数列满足以下三个条件: (1)它是从1到2n共2n个整数的一个排列{ai}; (2)所有的奇数项满足a1<a3<…<a2n-1,所有的偶数项满足a2<a4<…<a2n; (3)任意相邻的

    来自 just_sort
    00
  • avatar just_sort 2017-05-05 15:21:55

    BZOJ 1483: [HNOI2009]梦幻布丁 链表或者平衡树启发式合并

    Description N个布丁摆成一行,进行M次操作.每次将某个颜色的布丁全部变成另一种颜色的,然后再询问当前一共有多少段颜色.例如颜色分别为1,2,2,1的四个布丁一共有3段颜***r> Input 第一行给出N,M表示布丁的个数和好友的操作次数. 第二行N个数A1,A2…An表示第i

    来自 just_sort
    00
  • avatar just_sort 2017-05-04 16:14:50

    BZOJ 1460: Pku2114 Boatherds 点分治

    Description 给你一棵n个点的带权有根树,有p个询问,每次询问树中是否存在一条长度为Len的路径,如果是,输出Yes否输出No. Input 第一行两个整数n, p分别表示点的个数和询问的个数. 接下来n-1行每行三个数x, y, c,表示有一条树边x→y,长度为c. 接下来p行每行

    来自 just_sort
    00
  • avatar just_sort 2017-05-03 19:30:30

    BZOJ 1458: 士兵占领 网络最大流

    Description 有一个M * N的棋盘,有的格子是障碍。现在你要选择一些格子来放置一些士兵,一个格子里最多可以放置一个士兵,障碍格里不能放置士兵。我们称这些士兵占领了整个棋盘当满足第i行至少放置了Li个士兵, 第j列至少放置了Cj个士兵。现在你的任务是要求使用最少个数的士兵来占领整个棋盘。

    来自 just_sort
    00
  • avatar just_sort 2017-05-03 13:18:40

    BZOJ 1457: 棋盘游戏 SG函数

    Description 有一个100 * 100的棋盘,其中左下角的编号为(0, 0), 右上角编号为(99, 99)。棋盘上有N个Queen,最开始第i个Queen的位置为(Xi, Yi)。现在有两个玩家依次来操作,每一次一个玩家可以选择其中一个Queen,将它跳到(Xi – k, Yi)或(X

    来自 just_sort
    00
  • avatar just_sort 2017-05-02 21:03:50

    BZOJ 1452: [JSOI2009]Count 二维树状数组

    Sample Output 1 2 解法:二维树状数组。数组开到快1000w竟然没炸。 ///BZOJ 1452 #include <bits/stdc++.h> using namespace std; int n, m, q; int mp[305][305]; int

    来自 just_sort
    00
  • avatar just_sort 2017-05-02 20:34:35

    BZOJ 1449: [JSOI2009]球队收益 拆边费用流

    Output 一个整数表示联盟里所有球队收益之和的最小值。 Sample Input 3 3 1 0 2 1 1 1 10 1 0 1 3 3 1 2 2 3 3 1 Sample Output 43 解法:不会,膜拜神牛 题解来自:http://blog.csdn.n

    来自 just_sort
    00
  • avatar just_sort 2017-05-01 14:47:52

    BZOJ 1444: [Jsoi2009]有趣的游戏 AC自动机加矩阵快速幂

    题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1444 非权限题,就没粘贴题面了。 解法: AC自动机+矩阵乘法 首先把模式串建成AC自动机,构建出转移矩阵。 构造方法:a[i][j]表示从第i个结点转移到第j个结点的概率,则如果

    来自 just_sort
    00
  • avatar just_sort 2017-05-01 09:36:48

    BZOJ 1426: 收集邮票 期望DP,数学推导

    Description 有n种不同的邮票,皮皮想收集所有种类的邮票。唯一的收集方法是到同学凡凡那里购买,每次只能买一张,并且买到的邮票究竟是n种邮票中的哪一种是等概率的,概率均为1/n。但是由于凡凡也很喜欢邮票,所以皮皮购买第k张邮票需要支付k元钱。 现在皮皮手中没有邮票,皮皮想知道自己得到所有种

    来自 just_sort
    00
  • avatar just_sort 2017-04-30 17:32:46

    BZOJ 1419: Red is good 期望DP

    Description 桌面上有R张红牌和B张黑牌,随机打乱顺序后放在桌面上,开始一张一张地翻牌,翻到红牌得到1美元,黑牌则付出1美元。可以随时停止翻牌,在最优策略下平均能得到多少钱。 Input 一行输入两个数R,B,其值在0到5000之间 Output 在最优策略下平均能得到多少钱。

    来自 just_sort
    00
  • avatar just_sort 2017-04-30 16:38:44

    BZOJ 1417: Pku3156 Interconnect 期望DP

    Description 给出无向图G(V, E). 每次操作任意加一条非自环的边(u, v), 每条边的选择是等概率的. 问使得G连通的期望操作次数. (|V| <= 30, |E| <= 1000) Input 第一行两个整数N,M 1<=N<=30 0<=M&

    来自 just_sort
    00
  • avatar just_sort 2017-04-30 15:16:23

    BZOJ 1430: 小猴打架 树的prufer编码

    [Submit][Status][Discuss] Description 一开始森林里面有N只互不相识的小猴子,它们经常打架,但打架的双方都必须不是好朋友。每次打完架后,打架的双方以及它们的好朋友就会互相认识,成为好朋友。经过N-1次打架之后,整个森林的小猴都会成为好朋友。 现在的问题是,总共

    来自 just_sort
    00
  • avatar just_sort 2017-04-30 14:35:46

    BZOJ 1429: 方程的解 数论,雅克比4平方和定理

    Description 令F(x)=Sigma(i),1<=i<=x. 有一个不定方程f(x)+f(y)+f(z)+f(w)=N(0<=N<=10^12,x,y,z,w为自然数) 请统计方程的个数 Input 一个正数N Output 一个数表示解的个数 Samp

    来自 just_sort
    00
  • avatar just_sort 2017-04-30 11:33:02

    BZOJ 1441: Min 裴蜀定理

    Description 给出n个数(A1…An)现求一组整数序列(X1…Xn)使得S=A1*X1+…An*Xn>0,且S的值最小 Input 第一行给出数字N,代表有N个数 下面一行给出N个数 Output S的最小值 Sample Input 2 4059 -1782 Sa

    来自 just_sort
    00
  • avatar just_sort 2017-05-05 14:03:16

    BZOJ 1475: 方格取数 最大点权独立集

    Description 在一个n*n的方格里,每个格子里都有一个正整数。从中取出若干数,使得任意两个取出的数所在格子没有公共边,且取出的数的总和尽量大。 Input 第一行一个数n;(n<=30) 接下来n行每行n个数描述一个方阵 Output 仅一个数,即最大和 Sample I

    来自 just_sort
    00
  • avatar just_sort 2017-05-04 20:42:09

    BZOJ 1461: 字符串的匹配 kmp套树状数组

    解法:这题就是kmp匹配过程中用树状数组维护每个数字出现的次数,快速查询在前面比自己小的和等于自己的来判断是否能向后匹配 ///BZOJ 1461 ///KMP + BIT #include <bits/stdc++.h> using namespace std; const int

    来自 just_sort
    00
  • avatar just_sort 2017-05-02 18:51:09

    UVALive - 3490 Generator AC自动机+高斯消元

    题目链接:https://vjudge.net/problem/UVALive-3490 题意:随机字母组成一个串,有一个目标串,当这个由随机字母组成的串出现目标串就停止,求这个随机字母 组成串的期望长度。 解法:容易看出,dp[i] = 所有他下一步可能的节点dp[j]之和/m+1。可以想一

    来自 just_sort
    00
  • avatar just_sort 2017-04-30 19:41:13

    POJ 2417 baby_step giant_step 小步大步算法 a^x == b(mod n) 求解0

    题目照片:http://poj.org/problem?id=2417 题意:求解a^x==b(mod n),==表示同余的意思。 解法:大步小步算法裸题,我也不懂这个算法,先存个模板,应该有用。 复杂度是O(sqrt(n)*log(n))的 ///POJ 2417 #include <

    来自 just_sort
    00
  • avatar just_sort 2017-04-30 10:09:44

    UVA 10498 食物分配 单纯形算法

    题目链接:https://vjudge.net/problem/UVA-10498 题意:n种食物m个人,已知每种食物的单价,每个人吃每种食物的愉快值,每个人的愉快值上限,求花钱买食物所花钱 的最大值 解法: 线性规划;可得标准形式,带入模版; 标准形式即由不等式构成的方程组,松弛形式即由

    来自 just_sort
    00
  • avatar just_sort 2017-04-29 21:18:43

    BZOJ 1434: [ZJOI2009]染色游戏 博弈

    [Submit][Status][Discuss] Description 一共n × m 个硬币,摆成n × m 的长方形。dongdong 和xixi 玩一个游戏, 每次可以选择一个连通块,并把其中的硬币全部翻转,但是需要满足存在一个 硬币属于这个连通块并且所有其他硬币都在它的左上方(可以正

    来自 just_sort
    00
  • avatar just_sort 2017-04-29 20:14:53

    BZOJ 1433: [ZJOI2009]假期的宿舍 二分匹配

    Sample Input 1 3 1 1 0 0 1 0 0 1 1 1 0 0 1 0 0 Sample Output ˆ ˆ HINT 对于30% 的数据满足1 ≤ n ≤ 12。 对于100% 的数据满足1 ≤ n ≤ 50,1 ≤ T ≤ 20。 解法: 二分图。

    来自 just_sort
    00
  • avatar just_sort 2017-04-29 18:10:49

    1432: [ZJOI2009]Function 找规律

    Input 一行两个整数n; k。 Output 一行一个整数,表示n 个函数第k 层最少能由多少段组成。 Sample Input 1 1 Sample Output 1 HINT 对于100% 的数据满足1 ≤ k ≤ n ≤ 100。 解法: 脑洞题,找规律。蒟蒻画了好久

    来自 just_sort
    00
  • avatar just_sort 2017-04-29 16:19:14

    BZOJ 1416: [NOI2006]神奇的口袋 分数重载,模拟

    题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1416 解法:话说这个题目鬼畜了吧,神坑啊。我很快写完交上去wa了,实在改不出来,自己写了数据生成器想和网上的ac代 码拍一下,拍了大概10组随机数据发现答案完全一样啊,这能WA??? 想

    来自 just_sort
    00
  • avatar just_sort 2017-04-29 14:58:14

    BZOJ 1415: [Noi2005]聪聪和可可 概率DP,记忆化搜索,BFS

    Input 数据的第1行为两个整数N和E,以空格分隔,分别表示森林中的景点数和连接相邻景点的路的条数。 第2行包含两个整数C和M,以空格分隔,分别表示初始时聪聪和可可所在的景点的编号。 接下来E行,每行两个整数,第i+2行的两个整数Ai和Bi表示景点Ai和景点Bi之间有一条路。 所有的路都是无向的

    来自 just_sort
    00
  • avatar just_sort 2017-04-29 09:41:44

    BZOJ 1412: [ZJOI2009]狼和羊的故事 最小割

    Description “狼爱上羊啊爱的疯狂,谁让他们真爱了一场;狼爱上羊啊并不荒唐,他们说有爱就有方向......” Orez听到这首歌,心想:狼和羊如此和谐,为什么不尝试羊狼合养呢?说干就干! Orez的羊狼圈可以看作一个n*m个矩阵格子,这个矩阵的边缘已经装上了篱笆。可是Drake很快发现狼

    来自 just_sort
    00
  • avatar just_sort 2017-04-27 20:44:51

    BZOJ 1407: [Noi2002]Savage 扩展欧几里得

    Input 第1行为一个整数N(1<=N<=15),即野人的数目。 第2行到第N+1每行为三个整数Ci, Pi, Li表示每个野人所住的初始洞穴编号,每年走过的洞穴数及寿命值。 (1<=Ci,Pi<=100, 0<=Li<=10^6 ) Output 仅

    来自 just_sort
    00
  • avatar just_sort 2017-04-27 12:24:00

    BZOJ 1398: Vijos1382寻找主人 Necklace 字符串最小表示法

    给定两个项链的表示,判断他们是否可能是一条项链。 Input 输入文件只有两行,每行一个由0至9组成的字符串,描述一个项链的表示(保证项链的长度是相等的)。 Output 如果两条项链不可能同构,那么输出’No’,否则的话,第一行输出一个’Yes’ 第二行输出该项链的字典序最小的表示。 设

    来自 just_sort
    00
  • avatar just_sort 2017-04-26 21:03:15

    BZOJ 1367: [Baltic2004]sequence 左偏树

    Output 一个整数R Sample Input 7 9 4 8 20 14 15 18 Sample Output 13 HINT 所求的Z序列为6,7,8,13,14,15,18. R=13 论文题:https://wenku.baidu.com/view/20

    来自 just_sort
    00
  • avatar just_sort 2017-04-26 16:43:39

    HDU 5988 Coding Contest 2016青岛G题浮点费用流

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5988 题意:n个点有人有面包,有一些边,除了第一个走这个边的人其他人都有pi的概率破坏网络,让你安排吃饭 方案,使得每个人吃上饭,并且破坏网络的概率最小。 解法:这是2016青岛赛区的银牌题,当时

    来自 just_sort
    00
  • avatar just_sort 2017-04-25 21:14:50

    BZOJ 1355: [Baltic2009]Radio Transmission KMP

    Description 给你一个字符串,它是由某个字符串不断自我连接形成的。 但是这个字符串是不确定的,现在只想知道它的最短长度是多少. Input 第一行给出字符串的长度,1 < L ≤ 1,000,000. 第二行给出一个字符串,全由小写字母组成. Output 输出最短的长度

    来自 just_sort
    00
  • avatar just_sort 2017-04-25 20:46:34

    BZOJ 1336: [Balkan2002]Alien最小圆覆盖 随机增量法

    Description 给出N个点,让你画一个最小的包含所有点的圆。 Input 先给出点的个数N,2<=N<=100000,再给出坐标Xi,Yi.(-10000.0<=xi,yi<=10000.0) Output 输出圆的半径,及圆心的坐标 Sample Inp

    来自 just_sort
    00
  • avatar just_sort 2017-04-24 18:09:47

    BZOJ 1305: [CQOI2009]dance跳舞 多重匹配,网络最大流

    Description 一次舞会有n个男孩和n个女孩。每首曲子开始时,所有男孩和女孩恰好配成n对跳交谊舞。每个男孩都不会和同一个女孩跳两首(或更多)舞曲。有一些男孩女孩相互喜欢,而其他相互不喜欢(不会“单向喜欢”)。每个男孩最多只愿意和k个不喜欢的女孩跳舞,而每个女孩也最多只愿意和k个不喜欢的男孩

    来自 just_sort
    00
  • avatar just_sort 2017-04-24 17:19:58

    BZOJ 1304: [CQOI2009]叶子的染色 树形DP

    Description 给一棵m个结点的无根树,你可以选择一个度数大于1的结点作为根,然后给一些结点(根、内部结点和叶子均可)着以黑色或白色。你的着色方案应该保证根结点到每个叶子的简单路径上都至少包含一个有色结点(哪怕是这个叶子本身)。 对于每个叶结点u,定义c[u]为从根结点从U的简单路径上最后

    来自 just_sort
    00
  • avatar just_sort 2017-04-29 11:49:42

    1414: [ZJOI2009]对称的正方形 Hash+二分

    Description Orez很喜欢搜集一些神秘的数据,并经常把它们排成一个矩阵进行研究。最近,Orez又得到了一些数据,并已经把它们排成了一个n行m列的矩阵。通过观察,Orez发现这些数据蕴涵了一个奇特的数,就是矩阵中上下对称且左右对称的正方形子矩阵的个数。 Orez自然很想知道这个数是多少,

    来自 just_sort
    00
  • avatar just_sort 2017-04-27 14:15:34

    BZOJ 1406: [AHOI2007]密码箱 数论

    Description 在一次偶然的情况下,小可可得到了一个密码箱,听说里面藏着一份古代流传下来的藏宝图,只要能破解密码就能打开箱子,而箱子背面刻着的古代图标,就是对密码的提示。经过艰苦的破译,小可可发现,这些图标表示一个数以及这个数与密码的关系。假设这个数是n,密码为x,那么可以得到如下表述:

    来自 just_sort
    00
  • avatar just_sort 2017-04-26 10:51:05

    SGU 4554 Boring Game 来自队友的神奇随机Hash

    题目链接:http://acm.scu.edu.cn/soj/problem.action?id=4554 Description One day, Yutta and Rikka were playing a game. There were a N*M matrix. Every time

    来自 just_sort
    00
  • avatar just_sort 2017-04-26 10:39:37

    Educational Codeforces Round 3 E. Minimum spanning tree for each edge MST+树上路径倍增

    题目链接:http://codeforces.com/contest/609/problem/E 题意:给一个无向图,n个点,m条边,对任意边edge[i],求出包含有边edge[i]的最小生成树。 解法:考虑MST的性质,对任意两点u,v一定有且只有一条路径,当边[u,v]不是MST边的时候,

    来自 just_sort
    00
  • avatar just_sort 2017-04-22 09:36:20

    BZOJ 1297 1297: [SCOI2009]迷路 拆点,矩阵快速幂

    Description windy在有向图中迷路了。 该有向图有 N 个节点,windy从节点 0 出发,他必须恰好在 T 时刻到达节点 N-1。 现在给出该有向图,你能告诉windy总共有多少种不同的路径吗? 注意:windy不能在某个节点逗留,且通过某有向边的时间严格为给定的时间。 Inpu

    来自 just_sort
    00
  • avatar just_sort 2017-04-21 21:35:03

    BZOJ 1296: [SCOI2009]粉刷匠 动态规划

    Description windy有 N 条木板需要被粉刷。 每条木板被分为 M 个格子。 每个格子要被刷成红色或蓝色。 windy每次粉刷,只能选择一条木板上一段连续的格子,然后涂上一种颜色。 每个格子最多只能被粉刷一次。 如果windy只能粉刷 T 次,他最多能正确粉刷多少格子? 一个格子如果

    来自 just_sort
    00
  • avatar just_sort 2017-04-21 18:18:13

    BZOJ 1295: [SCOI2009]最长距离 枚举+SPFA水题

    Description windy有一块矩形土地,被分为 N*M 块 1*1 的小格子。 有的格子含有障碍物。 如果从格子A可以走到格子B,那么两个格子的距离就为两个格子中心的欧几里德距离。 如果从格子A不可以走到格子B,就没有距离。 如果格子X和格子Y有公共边,并且X和Y均不含有障碍物,就可以从

    来自 just_sort
    00
  • avatar just_sort 2017-04-21 16:41:57

    BZOJ 1294: [SCOI2009]围豆豆Bean 状压DP,SPFA,计算集合射线法

    Input 第一行两个整数N和M,为矩阵的边长。 第二行一个整数D,为豆子的总个数。 第三行包含D个整数V1到VD,分别为每颗豆子的分值。 接着N行有一个N×M的字符矩阵来描述游戏矩阵状态,0表示空格,#表示障碍物。而数字1到9分别表示对应编号的豆子。 Output 仅包含一个整数,为最高可能

    来自 just_sort
    00
  • avatar just_sort 2017-04-21 14:40:36

    BZOJ 1293: [SCOI2009]生日礼物 链表模拟

    Description 小西有一条很长的彩带,彩带上挂着各式各样的彩珠。已知彩珠有N个,分为K种。简单的说,可以将彩带考虑为x轴,每一个彩珠有一个对应的坐标(即位置)。某些坐标上可以没有彩珠,但多个彩珠也可以出现在同一个位置上。 小布生日快到了,于是小西打算剪一段彩带送给小布。为了让礼物彩带足够漂

    来自 just_sort
    00
  • avatar just_sort 2017-04-20 10:20:55

    BZOJ 1280: Emmy卖猪pigs 网络最大流,神奇建图

    Description Emmy在一个养猪场工作。这个养猪场有M个锁着的猪圈,但Emmy并没有钥匙。顾客会到养猪场来买猪,一个接着一个。每一位顾客都会有一些猪圈的钥匙,他们会将这些猪圈打开并买走固定数目的猪。 所有顾客有的钥匙和他们需要买猪的数量在事先都告诉了Emmy,于是Emmy要订一个计划,使

    来自 just_sort
    00
  • avatar just_sort 2017-04-19 19:42:58

    BZOJ 1272: [BeiJingWc2008]Gate Of Babylon 容斥+Lucas+隔板法+逆元

    解法: 1.首先,看到有限制的只有15个,因此可以用容斥原理: ans=全部没有限制的方案-有一个超过限制的方案数+有两个超过限制的方案数-有三个超过限制的方案数…. 2.把m组无限制的数中选n个的方案数:C(n+m-1,n)。就是隔板法公式,简单证明: xi为选xi个第i组数,这个问题相当

    来自 just_sort
    00
  • avatar just_sort 2017-04-19 17:04:28

    BZOJ 1271: [BeiJingWc2008]秦腾与教学评估 二分查找

    解法: 因为题中说了,最多只有一个位置有奇数个人。 所以我们可以先check一下,如果总人数是偶数那么显然就是 Poor Qin Teng 接下来的话我们只需要二分出那个奇数的位置,检验l到这个位置有多少个人即可。 得到位置之后直接O(n)求一下该位置的人数即可。 //BZOJ 1271

    来自 just_sort
    00